Ensure that the tree goes back down to the same height when an item is
inserted & removed from the tree at a higher index.
Signed-off-by: Matthew Wilcox <wi...@linux.intel.com>
Reviewed-by: Ross Zwisler <ross.zwis...@linux.intel.com>
---
tools/testing/radix-tree/multiorder.c | 38 +++++++++++++++++++++++++++++++++++
1 file changed, 38 insertions(+)
diff --git a/tools/testing/radix-tree/multiorder.c
b/tools/testing/radix-tree/multiorder.c
index 583c5127fbcf..10b9708a71f9 100644
--- a/tools/testing/radix-tree/multiorder.c
+++ b/tools/testing/radix-tree/multiorder.c
@@ -46,6 +46,41 @@ static void multiorder_check(unsigned long index, int order)
item_check_absent(&tree, i);
}
+static void multiorder_shrink(unsigned long index, int order)
+{
+ unsigned long i;
+ unsigned long max = 1 << order;
+ RADIX_TREE(tree, GFP_KERNEL);
+ struct radix_tree_node *node;
+
+ printf("Multiorder shrink index %ld, order %d\n", index, order);
+
+ assert(item_insert_order(&tree, 0, order) == 0);
+
+ node = tree.rnode;
+
+ assert(item_insert(&tree, index) == 0);
+ assert(node != tree.rnode);
+
+ assert(item_delete(&tree, index) != 0);
+ assert(node == tree.rnode);
+
+ for (i = 0; i < max; i++) {
+ struct item *item = item_lookup(&tree, i);
+ assert(item != 0);
+ assert(item->index == 0);
+ }
+ for (i = max; i < 2*max; i++)
+ item_check_absent(&tree, i);
+
+ if (!item_delete(&tree, 0)) {
+ printf("failed to delete index %ld (order %d)\n", index,
order); abort();
+ }
+
+ for (i = 0; i < 2*max; i++)
+ item_check_absent(&tree, i);
+}
+
static void multiorder_insert_bug(void)
{
RADIX_TREE(tree, GFP_KERNEL);
@@ -157,6 +192,9 @@ void multiorder_checks(void)
multiorder_check((1UL << i) + 1, i);
}
+ for (i = 0; i < 15; i++)
+ multiorder_shrink((1UL << (i + RADIX_TREE_MAP_SHIFT)), i);
+
multiorder_iteration();
multiorder_tagged_iteration();
multiorder_insert_bug();
--
2.8.0.rc3
