23 #define for_each_index(i, base, order) \  argument
24 	for (i = base; i < base + (1 << order); i++)
29 	int base, err, i;  in __multiorder_tag_test()  local
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()
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()
58 	for_each_index(i, base, order) {  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()
66 	for_each_index(i, base, order) {  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()
98 	int i, j;  in multiorder_tag_tests()  local
140 	for (i = 1; i < 10; i++)  in multiorder_tag_tests()
141 		for (j = 0; j < (10 << i); j++)  in multiorder_tag_tests()
142 			__multiorder_tag_test2(i, j);  in multiorder_tag_tests()
147 	unsigned long i;  in multiorder_check()  local
158 	for (i = min; i < max; i++) {  in multiorder_check()
159 		struct item *item = item_lookup(&tree, i);  in multiorder_check()
163 	for (i = 0; i < min; i++)  in multiorder_check()
164 		item_check_absent(&tree, i);  in multiorder_check()
165 	for (i = max; i < 2*max; i++)  in multiorder_check()
166 		item_check_absent(&tree, i);  in multiorder_check()
167 	for (i = min; i < max; i++)  in multiorder_check()
168 		assert(radix_tree_insert(&tree, i, item2) == -EEXIST);  in multiorder_check()
173 	for (i = min; i < max; i++) {  in multiorder_check()
174 		struct item *item = item_lookup(&tree, i);  in multiorder_check()
181 	for (i = 0; i < 2*max; i++)  in multiorder_check()
182 		item_check_absent(&tree, i);  in multiorder_check()
187 	unsigned long i;  in multiorder_shrink()  local
204 	for (i = 0; i < max; i++) {  in multiorder_shrink()
205 		struct item *item = item_lookup(&tree, i);  in multiorder_shrink()
209 	for (i = max; i < 2*max; i++)  in multiorder_shrink()
210 		item_check_absent(&tree, i);  in multiorder_shrink()
217 	for (i = 0; i < 2*max; i++)  in multiorder_shrink()
218 		item_check_absent(&tree, i);  in multiorder_shrink()
237 	int i, j, err;  in multiorder_iteration()  local
245 	for (i = 0; i < NUM_ENTRIES; i++) {  in multiorder_iteration()
246 		err = item_insert_order(&tree, index[i], order[i]);  in multiorder_iteration()
251 		for (i = 0; i < NUM_ENTRIES; 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()
261 			assert((iter.index | mask) == (index[i] | mask));  in multiorder_iteration()
264 			assert((item->index | mask) == (index[i] | mask));  in multiorder_iteration()
265 			assert(item->order == order[i]);  in multiorder_iteration()
266 			i++;  in multiorder_iteration()
278 	int i, j;  in multiorder_tagged_iteration()  local
289 	for (i = 0; i < MT_NUM_ENTRIES; i++)  in multiorder_tagged_iteration()
290 		assert(!item_insert_order(&tree, index[i], order[i]));  in multiorder_tagged_iteration()
294 	for (i = 0; i < TAG_ENTRIES; i++)  in multiorder_tagged_iteration()
295 		assert(radix_tree_tag_set(&tree, tag_index[i], 1));  in multiorder_tagged_iteration()
300 		for (i = 0; i < TAG_ENTRIES; i++) {  in multiorder_tagged_iteration()
301 			for (k = i; index[k] < tag_index[i]; k++)  in multiorder_tagged_iteration()
310 			for (k = i; index[k] < tag_index[i]; k++)  in multiorder_tagged_iteration()
314 			assert((iter.index | mask) == (tag_index[i] | mask));  in multiorder_tagged_iteration()
316 			assert((item->index | mask) == (tag_index[i] | mask));  in multiorder_tagged_iteration()
318 			i++;  in multiorder_tagged_iteration()
328 		for (i = 0; i < TAG_ENTRIES; i++) {  in multiorder_tagged_iteration()
329 			for (k = i; index[k] < tag_index[i]; k++)  in multiorder_tagged_iteration()
337 			for (k = i; index[k] < tag_index[i]; k++)  in multiorder_tagged_iteration()
341 			assert((iter.index | mask) == (tag_index[i] | mask));  in multiorder_tagged_iteration()
343 			assert((item->index | mask) == (tag_index[i] | mask));  in multiorder_tagged_iteration()
345 			i++;  in multiorder_tagged_iteration()
351 	i = 0;  in multiorder_tagged_iteration()
353 		assert(iter.index == tag_index[i]);  in multiorder_tagged_iteration()
354 		i++;  in multiorder_tagged_iteration()
421 	unsigned long i;  in multiorder_join3()  local
423 	for (i = 0; i < (1 << order); i++) {  in multiorder_join3()
424 		radix_tree_insert(&tree, i, (void *)0x12UL);  in multiorder_join3()
444 	int i, j, idx;  in multiorder_join()  local
447 		for (i = 1; i < 15; i++) {  in multiorder_join()
448 			for (j = 0; j < i; j++) {  in multiorder_join()
449 				multiorder_join1(idx, i, j);  in multiorder_join()
454 	for (i = 1; i < 15; i++) {  in multiorder_join()
455 		for (j = 0; j < i; j++) {  in multiorder_join()
456 			multiorder_join2(i, j);  in multiorder_join()
460 	for (i = 3; i < 10; i++) {  in multiorder_join()
461 		multiorder_join3(i);  in multiorder_join()
595 	int i, j;  in multiorder_split()  local
597 	for (i = 3; i < 11; i++)  in multiorder_split()
598 		for (j = 0; j < i; j++) {  in multiorder_split()
599 			__multiorder_split(i, j);  in multiorder_split()
600 			__multiorder_split2(i, j);  in multiorder_split()
601 			__multiorder_split3(i, j);  in multiorder_split()
635 	int i;  in creator_func()  local
637 	for (i = 0; i < 10000; i++) {  in creator_func()
677 	int i;  in multiorder_iteration_race()  local
680 	for (i = 1; i < num_threads; i++)  in multiorder_iteration_race()
681 		pthread_create(&worker_thread[i], NULL, &iterator_func, &tree);  in multiorder_iteration_race()
683 	for (i = 0; i < num_threads; i++)  in multiorder_iteration_race()
684 		pthread_join(worker_thread[i], NULL);  in multiorder_iteration_race()
691 	int i;  in multiorder_checks()  local
693 	for (i = 0; i < 20; i++) {  in multiorder_checks()
694 		multiorder_check(200, i);  in multiorder_checks()
695 		multiorder_check(0, i);  in multiorder_checks()
696 		multiorder_check((1UL << i) + 1, i);  in multiorder_checks()
699 	for (i = 0; i < 15; i++)  in multiorder_checks()
700 		multiorder_shrink((1UL << (i + RADIX_TREE_MAP_SHIFT)), i);  in multiorder_checks()