Lines Matching full:tree
2 * multiorder.c: Multi-order radix tree entry testing
16 #include <linux/radix-tree.h>
28 RADIX_TREE(tree, GFP_KERNEL); in __multiorder_tag_test()
37 err = item_insert_order(&tree, index, order); in __multiorder_tag_test()
46 err = __radix_tree_insert(&tree, i, order, in __multiorder_tag_test()
52 assert(!radix_tree_tag_get(&tree, i, 0)); in __multiorder_tag_test()
53 assert(!radix_tree_tag_get(&tree, i, 1)); in __multiorder_tag_test()
56 assert(radix_tree_tag_set(&tree, index, 0)); in __multiorder_tag_test()
59 assert(radix_tree_tag_get(&tree, i, 0)); in __multiorder_tag_test()
60 assert(!radix_tree_tag_get(&tree, i, 1)); in __multiorder_tag_test()
63 assert(tag_tagged_items(&tree, NULL, 0, ~0UL, 10, 0, 1) == 1); in __multiorder_tag_test()
64 assert(radix_tree_tag_clear(&tree, index, 0)); in __multiorder_tag_test()
67 assert(!radix_tree_tag_get(&tree, i, 0)); in __multiorder_tag_test()
68 assert(radix_tree_tag_get(&tree, i, 1)); in __multiorder_tag_test()
71 assert(radix_tree_tag_clear(&tree, index, 1)); in __multiorder_tag_test()
73 assert(!radix_tree_tagged(&tree, 0)); in __multiorder_tag_test()
74 assert(!radix_tree_tagged(&tree, 1)); in __multiorder_tag_test()
76 item_kill_tree(&tree); in __multiorder_tag_test()
81 RADIX_TREE(tree, GFP_KERNEL); in __multiorder_tag_test2()
85 assert(item_insert_order(&tree, 0, order) == 0); in __multiorder_tag_test2()
86 assert(item_insert(&tree, index2) == 0); in __multiorder_tag_test2()
88 assert(radix_tree_tag_set(&tree, 0, 0)); in __multiorder_tag_test2()
89 assert(radix_tree_tag_set(&tree, index2, 0)); in __multiorder_tag_test2()
91 assert(tag_tagged_items(&tree, NULL, 0, ~0UL, 10, 0, 1) == 2); in __multiorder_tag_test2()
93 item_kill_tree(&tree); in __multiorder_tag_test2()
109 * Our order 5 entry covers indices 0-31 in a tree with height=2. in multiorder_tag_tests()
124 * Our order 8 entry covers indices 0-255 in a tree with height=3. in multiorder_tag_tests()
152 RADIX_TREE(tree, GFP_KERNEL); in multiorder_check()
156 assert(item_insert_order(&tree, index, order) == 0); in multiorder_check()
159 struct item *item = item_lookup(&tree, i); in multiorder_check()
164 item_check_absent(&tree, i); in multiorder_check()
166 item_check_absent(&tree, i); in multiorder_check()
168 assert(radix_tree_insert(&tree, i, item2) == -EEXIST); in multiorder_check()
170 slot = radix_tree_lookup_slot(&tree, index); in multiorder_check()
172 radix_tree_replace_slot(&tree, slot, item2); in multiorder_check()
174 struct item *item = item_lookup(&tree, i); in multiorder_check()
179 assert(item_delete(&tree, min) != 0); in multiorder_check()
182 item_check_absent(&tree, i); in multiorder_check()
189 RADIX_TREE(tree, GFP_KERNEL); in multiorder_shrink()
194 assert(item_insert_order(&tree, 0, order) == 0); in multiorder_shrink()
196 node = tree.rnode; in multiorder_shrink()
198 assert(item_insert(&tree, index) == 0); in multiorder_shrink()
199 assert(node != tree.rnode); in multiorder_shrink()
201 assert(item_delete(&tree, index) != 0); in multiorder_shrink()
202 assert(node == tree.rnode); in multiorder_shrink()
205 struct item *item = item_lookup(&tree, i); in multiorder_shrink()
210 item_check_absent(&tree, i); in multiorder_shrink()
212 if (!item_delete(&tree, 0)) { in multiorder_shrink()
218 item_check_absent(&tree, i); in multiorder_shrink()
223 RADIX_TREE(tree, GFP_KERNEL); in multiorder_insert_bug()
225 item_insert(&tree, 0); in multiorder_insert_bug()
226 radix_tree_tag_set(&tree, 0, 0); in multiorder_insert_bug()
227 item_insert_order(&tree, 3 << 6, 6); in multiorder_insert_bug()
229 item_kill_tree(&tree); in multiorder_insert_bug()
234 RADIX_TREE(tree, GFP_KERNEL); in multiorder_iteration()
246 err = item_insert_order(&tree, index[i], order[i]); in multiorder_iteration()
255 radix_tree_for_each_slot(slot, &tree, &iter, j) { in multiorder_iteration()
270 item_kill_tree(&tree); in multiorder_iteration()
275 RADIX_TREE(tree, GFP_KERNEL); in multiorder_tagged_iteration()
290 assert(!item_insert_order(&tree, index[i], order[i])); in multiorder_tagged_iteration()
292 assert(!radix_tree_tagged(&tree, 1)); in multiorder_tagged_iteration()
295 assert(radix_tree_tag_set(&tree, tag_index[i], 1)); in multiorder_tagged_iteration()
307 radix_tree_for_each_tagged(slot, &tree, &iter, j, 1) { in multiorder_tagged_iteration()
322 assert(tag_tagged_items(&tree, NULL, 0, ~0UL, TAG_ENTRIES, 1, 2) == in multiorder_tagged_iteration()
335 radix_tree_for_each_tagged(slot, &tree, &iter, j, 2) { in multiorder_tagged_iteration()
349 assert(tag_tagged_items(&tree, NULL, 1, ~0UL, MT_NUM_ENTRIES * 2, 1, 0) in multiorder_tagged_iteration()
352 radix_tree_for_each_tagged(slot, &tree, &iter, 0, 0) { in multiorder_tagged_iteration()
357 item_kill_tree(&tree); in multiorder_tagged_iteration()
361 * Basic join checks: make sure we can't find an entry in the tree after
369 RADIX_TREE(tree, GFP_KERNEL); in multiorder_join1()
371 item_insert_order(&tree, index, order2); in multiorder_join1()
372 item = radix_tree_lookup(&tree, index); in multiorder_join1()
373 radix_tree_join(&tree, index + 1, order1, item2); in multiorder_join1()
374 loc = find_item(&tree, item); in multiorder_join1()
377 item = radix_tree_lookup(&tree, index + 1); in multiorder_join1()
379 item_kill_tree(&tree); in multiorder_join1()
388 RADIX_TREE(tree, GFP_KERNEL); in multiorder_join2()
393 item_insert_order(&tree, 0, order2); in multiorder_join2()
394 radix_tree_insert(&tree, 1 << order2, (void *)0x12UL); in multiorder_join2()
395 item2 = __radix_tree_lookup(&tree, 1 << order2, &node, NULL); in multiorder_join2()
399 item2 = radix_tree_lookup(&tree, 0); in multiorder_join2()
402 radix_tree_join(&tree, 0, order1, item1); in multiorder_join2()
403 item2 = __radix_tree_lookup(&tree, 1 << order2, &node, NULL); in multiorder_join2()
406 item_kill_tree(&tree); in multiorder_join2()
417 RADIX_TREE(tree, GFP_KERNEL); in multiorder_join3()
424 radix_tree_insert(&tree, i, (void *)0x12UL); in multiorder_join3()
427 radix_tree_join(&tree, 0, order, (void *)0x16UL); in multiorder_join3()
430 radix_tree_split(&tree, 0, 0); in multiorder_join3()
432 radix_tree_for_each_slot(slot, &tree, &iter, 0) { in multiorder_join3()
433 radix_tree_iter_replace(&tree, &iter, slot, (void *)0x12UL); in multiorder_join3()
436 __radix_tree_lookup(&tree, 0, &node, NULL); in multiorder_join3()
439 item_kill_tree(&tree); in multiorder_join3()
483 RADIX_TREE(tree, GFP_ATOMIC); in __multiorder_split()
490 assert(item_insert_order(&tree, 0, old_order) == 0); in __multiorder_split()
496 item = radix_tree_tag_set(&tree, 0, 2); in __multiorder_split()
500 radix_tree_split(&tree, 0, new_order); in __multiorder_split()
502 radix_tree_for_each_slot(slot, &tree, &iter, 0) { in __multiorder_split()
503 radix_tree_iter_replace(&tree, &iter, slot, in __multiorder_split()
508 item_kill_tree(&tree); in __multiorder_split()
514 RADIX_TREE(tree, GFP_KERNEL); in __multiorder_split2()
520 __radix_tree_insert(&tree, 0, old_order, (void *)0x12); in __multiorder_split2()
522 item = __radix_tree_lookup(&tree, 0, &node, NULL); in __multiorder_split2()
526 radix_tree_split(&tree, 0, new_order); in __multiorder_split2()
527 radix_tree_for_each_slot(slot, &tree, &iter, 0) { in __multiorder_split2()
528 radix_tree_iter_replace(&tree, &iter, slot, in __multiorder_split2()
532 item = __radix_tree_lookup(&tree, 0, &node, NULL); in __multiorder_split2()
536 item_kill_tree(&tree); in __multiorder_split2()
541 RADIX_TREE(tree, GFP_KERNEL); in __multiorder_split3()
547 __radix_tree_insert(&tree, 0, old_order, (void *)0x12); in __multiorder_split3()
549 item = __radix_tree_lookup(&tree, 0, &node, NULL); in __multiorder_split3()
553 radix_tree_split(&tree, 0, new_order); in __multiorder_split3()
554 radix_tree_for_each_slot(slot, &tree, &iter, 0) { in __multiorder_split3()
555 radix_tree_iter_replace(&tree, &iter, slot, (void *)0x16); in __multiorder_split3()
558 item = __radix_tree_lookup(&tree, 0, &node, NULL); in __multiorder_split3()
562 item_kill_tree(&tree); in __multiorder_split3()
564 __radix_tree_insert(&tree, 0, old_order, (void *)0x12); in __multiorder_split3()
566 item = __radix_tree_lookup(&tree, 0, &node, NULL); in __multiorder_split3()
570 radix_tree_split(&tree, 0, new_order); in __multiorder_split3()
571 radix_tree_for_each_slot(slot, &tree, &iter, 0) { in __multiorder_split3()
573 radix_tree_iter_replace(&tree, &iter, slot, in __multiorder_split3()
576 radix_tree_iter_replace(&tree, &iter, slot, NULL); in __multiorder_split3()
579 item = __radix_tree_lookup(&tree, 1 << new_order, &node, NULL); in __multiorder_split3()
590 item_kill_tree(&tree); in __multiorder_split3()
607 RADIX_TREE(tree, GFP_KERNEL); in multiorder_account()
611 item_insert_order(&tree, 0, 5); in multiorder_account()
613 __radix_tree_insert(&tree, 1 << 5, 5, (void *)0x12); in multiorder_account()
614 __radix_tree_lookup(&tree, 0, &node, NULL); in multiorder_account()
616 radix_tree_delete(&tree, 1 << 5); in multiorder_account()
619 __radix_tree_insert(&tree, 1 << 5, 5, (void *)0x12); in multiorder_account()
620 __radix_tree_lookup(&tree, 1 << 5, &node, &slot); in multiorder_account()
622 __radix_tree_replace(&tree, node, slot, NULL, NULL); in multiorder_account()
625 item_kill_tree(&tree); in multiorder_account()
634 struct radix_tree_root *tree = ptr; in creator_func() local
638 item_insert_order(tree, 0, order); in creator_func()
639 item_delete_rcu(tree, 0); in creator_func()
648 struct radix_tree_root *tree = ptr; in iterator_func() local
655 radix_tree_for_each_slot(slot, tree, &iter, 0) { in iterator_func()
676 RADIX_TREE(tree, GFP_KERNEL); in multiorder_iteration_race()
679 pthread_create(&worker_thread[0], NULL, &creator_func, &tree); in multiorder_iteration_race()
681 pthread_create(&worker_thread[i], NULL, &iterator_func, &tree); in multiorder_iteration_race()
686 item_kill_tree(&tree); in multiorder_iteration_race()