testing/radix-tree/main.c

10 #include <linux/radix-tree.h>
18 	RADIX_TREE(tree, GFP_KERNEL);
23 		item_insert(&tree, middle + idx);
25 	item_check_absent(&tree, middle - down - 1);
27 		item_check_present(&tree, middle + idx);
28 	item_check_absent(&tree, middle + up);
31 		item_gang_check_present(&tree, middle - down, up + down,
33 		item_full_scan(&tree, middle - down, down + up, chunk);
35 	item_kill_tree(&tree);
81 	RADIX_TREE(tree, GFP_KERNEL);
83 	item_insert(&tree, 44);
84 	item_check_present(&tree, 44);
85 	item_check_absent(&tree, 43);
86 	item_kill_tree(&tree);
92 	RADIX_TREE(tree, GFP_KERNEL);
93 	tree_verify_min_height(&tree, 0);
95 	item_insert(&tree, 42);
96 	tree_verify_min_height(&tree, 42);
98 	item_insert(&tree, 1000000);
99 	tree_verify_min_height(&tree, 1000000);
101 	assert(item_delete(&tree, 1000000));
102 	tree_verify_min_height(&tree, 42);
104 	assert(item_delete(&tree, 42));
105 	tree_verify_min_height(&tree, 0);
108 		item_insert(&tree, i);
109 		tree_verify_min_height(&tree, i);
114 		assert(item_delete(&tree, i));
116 			tree_verify_min_height(&tree, 0);
120 		tree_verify_min_height(&tree, i);
123 	item_kill_tree(&tree);
126 void check_copied_tags(struct radix_tree_root *tree, unsigned long start, unsigned long end, unsigned long *idx, int count, int fromtag, int totag)
134 			if (item_tag_get(tree, idx[i], totag)) {
136 				       end, idx[i], item_tag_get(tree, idx[i],
138 				       item_tag_get(tree, idx[i], totag));
140 			assert(!item_tag_get(tree, idx[i], totag));
143 		if (item_tag_get(tree, idx[i], fromtag) ^
144 			item_tag_get(tree, idx[i], totag)) {
146 			       idx[i], item_tag_get(tree, idx[i], fromtag),
147 			       item_tag_get(tree, idx[i], totag));
149 		assert(!(item_tag_get(tree, idx[i], fromtag) ^
150 			 item_tag_get(tree, idx[i], totag)));
158 	RADIX_TREE(tree, GFP_KERNEL);
163 //	printf("generating radix tree indices...\n");
175 		item_insert(&tree, start);
179 			item_tag_set(&tree, start, 0);
183 		item_insert(&tree, start-1);
185 			item_tag_set(&tree, start-1, 0);
188 		item_insert(&tree, end);
192 			item_tag_set(&tree, end, 0);
196 		item_insert(&tree, end+1);
198 			item_tag_set(&tree, end+1, 0);
204 		} while (item_lookup(&tree, idx[i]));
206 		item_insert(&tree, idx[i]);
208 			item_tag_set(&tree, idx[i], 0);
217 	tagged = tag_tagged_items(&tree, start, end, ITEMS, XA_MARK_0, XA_MARK_1);
221 	check_copied_tags(&tree, start, end, idx, ITEMS, 0, 1);
226 	tagged = tag_tagged_items(&tree, start, end, tmp, XA_MARK_0, XA_MARK_2);
231 	check_copied_tags(&tree, start, end, idx, ITEMS, 0, 2);
232 	verify_tag_consistency(&tree, 0);
233 	verify_tag_consistency(&tree, 1);
234 	verify_tag_consistency(&tree, 2);
236 	item_kill_tree(&tree);