Add rtree unit tests.

2 files changed, 33 insertions, 4 deletions

diff --git a/src/chunk.c b/src/chunk.c
index a93d28a..71bad5a 100644
--- a/src/chunk.c
+++ b/src/chunk.c
@@ -356,7 +356,7 @@ chunk_boot(void)
 	extent_tree_ad_new(&chunks_ad_dss);
 	if (config_ivsalloc) {
 		chunks_rtree = rtree_new((ZU(1) << (LG_SIZEOF_PTR+3)) -
-		    opt_lg_chunk);
+		    opt_lg_chunk, base_alloc, NULL);
 		if (chunks_rtree == NULL)
 			return (true);
 	}
diff --git a/src/rtree.c b/src/rtree.c
index 90c6935..4e26766 100644
--- a/src/rtree.c
+++ b/src/rtree.c
@@ -2,24 +2,28 @@
 #include "jemalloc/internal/jemalloc_internal.h"
 
 rtree_t *
-rtree_new(unsigned bits)
+rtree_new(unsigned bits, rtree_alloc_t *alloc, rtree_dalloc_t *dalloc)
 {
 	rtree_t *ret;
 	unsigned bits_per_level, height, i;
 
+	assert(bits > 0 && bits <= (sizeof(uintptr_t) << 3));
+
 	bits_per_level = ffs(pow2_ceil((RTREE_NODESIZE / sizeof(void *)))) - 1;
 	height = bits / bits_per_level;
 	if (height * bits_per_level != bits)
 		height++;
 	assert(height * bits_per_level >= bits);
 
-	ret = (rtree_t*)base_alloc(offsetof(rtree_t, level2bits) +
+	ret = (rtree_t*)alloc(offsetof(rtree_t, level2bits) +
 	    (sizeof(unsigned) * height));
 	if (ret == NULL)
 		return (NULL);
 	memset(ret, 0, offsetof(rtree_t, level2bits) + (sizeof(unsigned) *
 	    height));
 
+	ret->alloc = alloc;
+	ret->dalloc = dalloc;
 	if (malloc_mutex_init(&ret->mutex)) {
 		/* Leak the rtree. */
 		return (NULL);
@@ -32,7 +36,7 @@ rtree_new(unsigned bits)
 	for (i = 1; i < height; i++)
 		ret->level2bits[i] = bits_per_level;
 
-	ret->root = (void**)base_alloc(sizeof(void *) << ret->level2bits[0]);
+	ret->root = (void**)alloc(sizeof(void *) << ret->level2bits[0]);
 	if (ret->root == NULL) {
 		/*
 		 * We leak the rtree here, since there's no generic base
@@ -45,6 +49,31 @@ rtree_new(unsigned bits)
 	return (ret);
 }
 
+static void
+rtree_delete_subtree(rtree_t *rtree, void **node, unsigned level)
+{
+
+	if (level < rtree->height - 1) {
+		size_t nchildren, i;
+
+		nchildren = ZU(1) << rtree->level2bits[level];
+		for (i = 0; i < nchildren; i++) {
+			void **child = (void **)node[i];
+			if (child != NULL)
+				rtree_delete_subtree(rtree, child, level + 1);
+		}
+	}
+	rtree->dalloc(node);
+}
+
+void
+rtree_delete(rtree_t *rtree)
+{
+
+	rtree_delete_subtree(rtree, rtree->root, 0);
+	rtree->dalloc(rtree);
+}
+
 void
 rtree_prefork(rtree_t *rtree)
 {