summaryrefslogtreecommitdiffstats
path: root/tools
diff options
context:
space:
mode:
authorMatthew Wilcox <willy@linux.intel.com>2016-05-20 17:03:36 -0700
committerLinus Torvalds <torvalds@linux-foundation.org>2016-05-20 17:58:30 -0700
commit8c1244de00ef98f73e21eecc42d84b2742fbb4f9 (patch)
tree387657f853337b8fffe77215c9254c2ccb2a2ca4 /tools
parentaf49a63e101eb62376cc1d6bd25b97eb8c691d54 (diff)
downloadlinux-8c1244de00ef98f73e21eecc42d84b2742fbb4f9.tar.bz2
radix-tree: tidy up next_chunk
Convert radix_tree_next_chunk to use 'child' instead of 'slot' as the name of the child node. Also use node_maxindex() where it makes sense. The 'rnode' variable was unnecessary; it doesn't overlap in usage with 'node', so we can just use 'node' the whole way through the function. Improve the testcase to start the walk from every index in the carefully constructed tree, and to accept any index within the range covered by the entry. Signed-off-by: Matthew Wilcox <willy@linux.intel.com> Cc: Konstantin Khlebnikov <koct9i@gmail.com> Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com> Cc: Jan Kara <jack@suse.com> Cc: Neil Brown <neilb@suse.de> Cc: Ross Zwisler <ross.zwisler@linux.intel.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'tools')
-rw-r--r--tools/testing/radix-tree/multiorder.c99
1 files changed, 55 insertions, 44 deletions
diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c
index c061f4bd6c05..39d9b9568fe2 100644
--- a/tools/testing/radix-tree/multiorder.c
+++ b/tools/testing/radix-tree/multiorder.c
@@ -202,7 +202,7 @@ void multiorder_iteration(void)
RADIX_TREE(tree, GFP_KERNEL);
struct radix_tree_iter iter;
void **slot;
- int i, err;
+ int i, j, err;
printf("Multiorder iteration test\n");
@@ -215,29 +215,21 @@ void multiorder_iteration(void)
assert(!err);
}
- i = 0;
- /* start from index 1 to verify we find the multi-order entry at 0 */
- radix_tree_for_each_slot(slot, &tree, &iter, 1) {
- int height = order[i] / RADIX_TREE_MAP_SHIFT;
- int shift = height * RADIX_TREE_MAP_SHIFT;
-
- assert(iter.index == index[i]);
- assert(iter.shift == shift);
- i++;
- }
-
- /*
- * Now iterate through the tree starting at an elevated multi-order
- * entry, beginning at an index in the middle of the range.
- */
- i = 8;
- radix_tree_for_each_slot(slot, &tree, &iter, 70) {
- int height = order[i] / RADIX_TREE_MAP_SHIFT;
- int shift = height * RADIX_TREE_MAP_SHIFT;
-
- assert(iter.index == index[i]);
- assert(iter.shift == shift);
- i++;
+ for (j = 0; j < 256; j++) {
+ for (i = 0; i < NUM_ENTRIES; i++)
+ if (j <= (index[i] | ((1 << order[i]) - 1)))
+ break;
+
+ radix_tree_for_each_slot(slot, &tree, &iter, j) {
+ int height = order[i] / RADIX_TREE_MAP_SHIFT;
+ int shift = height * RADIX_TREE_MAP_SHIFT;
+ int mask = (1 << order[i]) - 1;
+
+ assert(iter.index >= (index[i] &~ mask));
+ assert(iter.index <= (index[i] | mask));
+ assert(iter.shift == shift);
+ i++;
+ }
}
item_kill_tree(&tree);
@@ -249,7 +241,7 @@ void multiorder_tagged_iteration(void)
struct radix_tree_iter iter;
void **slot;
unsigned long first = 0;
- int i;
+ int i, j;
printf("Multiorder tagged iteration test\n");
@@ -268,30 +260,49 @@ void multiorder_tagged_iteration(void)
for (i = 0; i < TAG_ENTRIES; i++)
assert(radix_tree_tag_set(&tree, tag_index[i], 1));
- i = 0;
- /* start from index 1 to verify we find the multi-order entry at 0 */
- radix_tree_for_each_tagged(slot, &tree, &iter, 1, 1) {
- assert(iter.index == tag_index[i]);
- i++;
- }
-
- /*
- * Now iterate through the tree starting at an elevated multi-order
- * entry, beginning at an index in the middle of the range.
- */
- i = 4;
- radix_tree_for_each_slot(slot, &tree, &iter, 70) {
- assert(iter.index == tag_index[i]);
- i++;
+ for (j = 0; j < 256; j++) {
+ int mask, k;
+
+ for (i = 0; i < TAG_ENTRIES; i++) {
+ for (k = i; index[k] < tag_index[i]; k++)
+ ;
+ if (j <= (index[k] | ((1 << order[k]) - 1)))
+ break;
+ }
+
+ radix_tree_for_each_tagged(slot, &tree, &iter, j, 1) {
+ for (k = i; index[k] < tag_index[i]; k++)
+ ;
+ mask = (1 << order[k]) - 1;
+
+ assert(iter.index >= (tag_index[i] &~ mask));
+ assert(iter.index <= (tag_index[i] | mask));
+ i++;
+ }
}
radix_tree_range_tag_if_tagged(&tree, &first, ~0UL,
MT_NUM_ENTRIES, 1, 2);
- i = 0;
- radix_tree_for_each_tagged(slot, &tree, &iter, 1, 2) {
- assert(iter.index == tag_index[i]);
- i++;
+ for (j = 0; j < 256; j++) {
+ int mask, k;
+
+ for (i = 0; i < TAG_ENTRIES; i++) {
+ for (k = i; index[k] < tag_index[i]; k++)
+ ;
+ if (j <= (index[k] | ((1 << order[k]) - 1)))
+ break;
+ }
+
+ radix_tree_for_each_tagged(slot, &tree, &iter, j, 2) {
+ for (k = i; index[k] < tag_index[i]; k++)
+ ;
+ mask = (1 << order[k]) - 1;
+
+ assert(iter.index >= (tag_index[i] &~ mask));
+ assert(iter.index <= (tag_index[i] | mask));
+ i++;
+ }
}
first = 1;