radix-tree: add radix_tree_join

[linux] / tools / testing / radix-tree / multiorder.c

diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c
index 86daf23..c9f656c 100644 (file)
--- a/tools/testing/radix-tree/multiorder.c
+++ b/tools/testing/radix-tree/multiorder.c
@@ -332,6 +332,63 @@ void multiorder_tagged_iteration(void)
        item_kill_tree(&tree);
 }
 
+static void __multiorder_join(unsigned long index,
+                               unsigned order1, unsigned order2)
+{
+       unsigned long loc;
+       void *item, *item2 = item_create(index + 1, order1);
+       RADIX_TREE(tree, GFP_KERNEL);
+
+       item_insert_order(&tree, index, order2);
+       item = radix_tree_lookup(&tree, index);
+       radix_tree_join(&tree, index + 1, order1, item2);
+       loc = find_item(&tree, item);
+       if (loc == -1)
+               free(item);
+       item = radix_tree_lookup(&tree, index + 1);
+       assert(item == item2);
+       item_kill_tree(&tree);
+}
+
+static void __multiorder_join2(unsigned order1, unsigned order2)
+{
+       RADIX_TREE(tree, GFP_KERNEL);
+       struct radix_tree_node *node;
+       void *item1 = item_create(0, order1);
+       void *item2;
+
+       item_insert_order(&tree, 0, order2);
+       radix_tree_insert(&tree, 1 << order2, (void *)0x12UL);
+       item2 = __radix_tree_lookup(&tree, 1 << order2, &node, NULL);
+       assert(item2 == (void *)0x12UL);
+       assert(node->exceptional == 1);
+
+       radix_tree_join(&tree, 0, order1, item1);
+       item2 = __radix_tree_lookup(&tree, 1 << order2, &node, NULL);
+       assert(item2 == item1);
+       assert(node->exceptional == 0);
+       item_kill_tree(&tree);
+}
+
+static void multiorder_join(void)
+{
+       int i, j, idx;
+
+       for (idx = 0; idx < 1024; idx = idx * 2 + 3) {
+               for (i = 1; i < 15; i++) {
+                       for (j = 0; j < i; j++) {
+                               __multiorder_join(idx, i, j);
+                       }
+               }
+       }
+
+       for (i = 1; i < 15; i++) {
+               for (j = 0; j < i; j++) {
+                       __multiorder_join2(i, j);
+               }
+       }
+}
+
 void multiorder_checks(void)
 {
        int i;
@@ -349,4 +406,5 @@ void multiorder_checks(void)
        multiorder_tag_tests();
        multiorder_iteration();
        multiorder_tagged_iteration();
+       multiorder_join();
 }