testing/radix-tree/tag_check.c

8 #include <linux/radix-tree.h>
14 __simple_checks(struct radix_tree_root *tree, unsigned long index, int tag)
19 	item_check_absent(tree, index);
20 	assert(item_tag_get(tree, index, tag) == 0);
22 	item_insert(tree, index);
23 	assert(item_tag_get(tree, index, tag) == 0);
24 	item_tag_set(tree, index, tag);
25 	ret = item_tag_get(tree, index, tag);
27 	ret = tag_tagged_items(tree, first, ~0UL, 10, tag, !tag);
29 	ret = item_tag_get(tree, index, !tag);
31 	ret = item_delete(tree, index);
33 	item_insert(tree, index);
34 	ret = item_tag_get(tree, index, tag);
36 	ret = item_delete(tree, index);
38 	ret = item_delete(tree, index);
45 	RADIX_TREE(tree, GFP_KERNEL);
48 		__simple_checks(&tree, index, 0);
49 		__simple_checks(&tree, index, 1);
51 	verify_tag_consistency(&tree, 0);
52 	verify_tag_consistency(&tree, 1);
54 	item_kill_tree(&tree);
60  * Check that tags propagate correctly when extending a tree.
64 	RADIX_TREE(tree, GFP_KERNEL);
66 	item_insert(&tree, 43);
67 	assert(item_tag_get(&tree, 43, 0) == 0);
68 	item_tag_set(&tree, 43, 0);
69 	assert(item_tag_get(&tree, 43, 0) == 1);
70 	item_insert(&tree, 1000000);
71 	assert(item_tag_get(&tree, 43, 0) == 1);
73 	item_insert(&tree, 0);
74 	item_tag_set(&tree, 0, 0);
75 	item_delete(&tree, 1000000);
76 	assert(item_tag_get(&tree, 43, 0) != 0);
77 	item_delete(&tree, 43);
78 	assert(item_tag_get(&tree, 43, 0) == 0);	/* crash */
79 	assert(item_tag_get(&tree, 0, 0) == 1);
81 	verify_tag_consistency(&tree, 0);
83 	item_kill_tree(&tree);
87  * Check that tags propagate correctly when contracting a tree.
93 	RADIX_TREE(tree, GFP_KERNEL);
96 	item_insert(&tree, tmp);
97 	item_insert(&tree, tmp+1);
98 	item_tag_set(&tree, tmp, 0);
99 	item_tag_set(&tree, tmp, 1);
100 	item_tag_set(&tree, tmp+1, 0);
101 	item_delete(&tree, tmp+1);
102 	item_tag_clear(&tree, tmp, 1);
104 	assert(radix_tree_gang_lookup_tag(&tree, (void **)&item, 0, 1, 0) == 1);
105 	assert(radix_tree_gang_lookup_tag(&tree, (void **)&item, 0, 1, 1) == 0);
107 	assert(item_tag_get(&tree, tmp, 0) == 1);
108 	assert(item_tag_get(&tree, tmp, 1) == 0);
110 	verify_tag_consistency(&tree, 0);
111 	item_kill_tree(&tree);
117  * Create a large linear array corresponding to the tree.   Each element in
118  * the array is coherent with each node in the tree
131 static void gang_check(struct radix_tree_root *tree,
139 	while ((nr_found = radix_tree_gang_lookup_tag(tree, (void **)items,
157 static void do_thrash(struct radix_tree_root *tree, char *thrash_state, int tag)
183 			item_check_absent(tree, index);
184 			item_insert(tree, index);
195 			item_check_present(tree, index);
196 			if (item_tag_get(tree, index, tag)) {
202 			item_delete(tree, index);
212 				if (item_lookup(tree, index))
213 					assert(item_tag_get(tree, index, tag));
216 			item_tag_set(tree, index, tag);
217 			item_tag_set(tree, index, tag);
228 			item_check_present(tree, index);
229 			assert(item_tag_get(tree, index, tag));
230 			item_tag_clear(tree, index, tag);
231 			item_tag_clear(tree, index, tag);
243 				item_check_absent(tree, index);
246 				item_check_present(tree, index);
247 				assert(!item_tag_get(tree, index, tag));
251 				item_check_present(tree, index);
252 				assert(item_tag_get(tree, index, tag));
259 		gang_check(tree, thrash_state, tag);
274 	RADIX_TREE(tree, GFP_KERNEL);
280 	do_thrash(&tree, thrash_state, 0);
282 	verify_tag_consistency(&tree, 0);
283 	item_kill_tree(&tree);
289 	RADIX_TREE(tree, GFP_KERNEL);
291 	item_insert(&tree, 1000000);
292 	item_delete(&tree, 1000000);
293 	item_kill_tree(&tree);
298 	RADIX_TREE(tree, GFP_KERNEL);
301 	item_insert(&tree, 1000000);
303 	item_delete(&tree, 1000000);
305 	item_kill_tree(&tree);
312 	RADIX_TREE(tree, GFP_KERNEL);
316 	item_insert(&tree, 0);
317 	item_tag_set(&tree, 0, 0);
318 	ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 0);
320 	ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 1, BATCH, 0);
322 	verify_tag_consistency(&tree, 0);
323 	verify_tag_consistency(&tree, 1);
324 	ret = tag_tagged_items(&tree, first, 10, 10, XA_MARK_0, XA_MARK_1);
326 	ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 1);
328 	item_tag_clear(&tree, 0, 0);
329 	ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 0);
331 	item_kill_tree(&tree);