2  * multiorder.c: Multi-order radix tree entry testing
23 #define for_each_index(i, base, order) \  argument
24 	for (i = base; i < base + (1 << order); i++)
26 static void __multiorder_tag_test(int index, int order)  in __multiorder_tag_test()  argument
32 	base = index & ~((1 << order) - 1);  in __multiorder_tag_test()
37 	err = item_insert_order(&tree, index, order);  in __multiorder_tag_test()
45 	for_each_index(i, base, order) {  in __multiorder_tag_test()
46 		err = __radix_tree_insert(&tree, i, order,  in __multiorder_tag_test()
51 	for_each_index(i, base, order) {  in __multiorder_tag_test()
58 	for_each_index(i, base, order) {  in __multiorder_tag_test()
66 	for_each_index(i, base, order) {  in __multiorder_tag_test()
79 static void __multiorder_tag_test2(unsigned order, unsigned long index2)  in __multiorder_tag_test2()  argument
82 	unsigned long index = (1 << order);  in __multiorder_tag_test2()
85 	assert(item_insert_order(&tree, 0, order) == 0);  in __multiorder_tag_test2()
100 	/* test multi-order entry for indices 0-7 with no sibling pointers */  in multiorder_tag_tests()
104 	/* test multi-order entry for indices 8-15 with no sibling pointers */  in multiorder_tag_tests()
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()
145 static void multiorder_check(unsigned long index, int order)  in multiorder_check()  argument
148 	unsigned long min = index & ~((1UL << order) - 1);  in multiorder_check()
149 	unsigned long max = min + (1UL << order);  in multiorder_check()
151 	struct item *item2 = item_create(min, order);  in multiorder_check()
154 	printv(2, "Multiorder index %ld, order %d\n", index, order);  in multiorder_check()
156 	assert(item_insert_order(&tree, index, order) == 0);  in multiorder_check()
185 static void multiorder_shrink(unsigned long index, int order)  in multiorder_shrink()  argument
188 	unsigned long max = 1 << order;  in multiorder_shrink()
192 	printv(2, "Multiorder shrink index %ld, order %d\n", index, order);  in multiorder_shrink()
194 	assert(item_insert_order(&tree, 0, order) == 0);  in multiorder_shrink()
213 		printv(2, "failed to delete index %ld (order %d)\n", index, order);  in multiorder_shrink()
243 	int order[NUM_ENTRIES] = {1, 1, 2, 3,  4,  1,  0,  1,  3,  0, 7};  in multiorder_iteration()  local
246 		err = item_insert_order(&tree, index[i], order[i]);  in multiorder_iteration()
252 			if (j <= (index[i] | ((1 << order[i]) - 1)))  in multiorder_iteration()
256 			int height = order[i] / RADIX_TREE_MAP_SHIFT;  in multiorder_iteration()
258 			unsigned long mask = (1UL << order[i]) - 1;  in multiorder_iteration()
265 			assert(item->order == order[i]);  in multiorder_iteration()
284 	int order[MT_NUM_ENTRIES] = {1, 0, 2, 4,  3,  1,  3,  0,   7};  in multiorder_tagged_iteration()  local
290 		assert(!item_insert_order(&tree, index[i], order[i]));  in multiorder_tagged_iteration()
303 			if (j <= (index[k] | ((1 << order[k]) - 1)))  in multiorder_tagged_iteration()
312 			mask = (1UL << order[k]) - 1;  in multiorder_tagged_iteration()
317 			assert(item->order == order[k]);  in multiorder_tagged_iteration()
331 			if (j <= (index[k] | ((1 << order[k]) - 1)))  in multiorder_tagged_iteration()
339 			mask = (1 << order[k]) - 1;  in multiorder_tagged_iteration()
344 			assert(item->order == order[k]);  in multiorder_tagged_iteration()
415 static void multiorder_join3(unsigned int order)  in multiorder_join3()  argument
423 	for (i = 0; i < (1 << order); i++) {  in multiorder_join3()
427 	radix_tree_join(&tree, 0, order, (void *)0x16UL);  in multiorder_join3()
632 	/* 'order' is set up to ensure we have sibling entries */  in creator_func()
633 	unsigned int order = RADIX_TREE_MAP_SHIFT - 1;  in creator_func()  local
638 		item_insert_order(tree, 0, order);  in creator_func()