From: Matthew Wilcox <willy@linux.intel.com> To: linux-kernel@vger.kernel.org, Andrew Morton <akpm@linux-foundation.org> Cc: Matthew Wilcox <willy@linux.intel.com>, linux-mm@kvack.org, linux-fsdevel@vger.kernel.org, Konstantin Khlebnikov <koct9i@gmail.com>, Kirill Shutemov <kirill.shutemov@linux.intel.com>, Jan Kara <jack@suse.com>, Neil Brown <neilb@suse.de>, Ross Zwisler <ross.zwisler@linux.intel.com> Subject: [PATCH 14/19] radix-tree: Tidy up range_tag_if_tagged Date: Thu, 14 Apr 2016 10:37:17 -0400 [thread overview] Message-ID: <1460644642-30642-15-git-send-email-willy@linux.intel.com> (raw) In-Reply-To: <1460644642-30642-1-git-send-email-willy@linux.intel.com> Convert radix_tree_range_tag_if_tagged to name the nodes parent, node and child instead of node & slot. Use parent->offset instead of playing games with 'upindex'. Signed-off-by: Matthew Wilcox <willy@linux.intel.com> --- lib/radix-tree.c | 39 +++++++++++++++++---------------------- 1 file changed, 17 insertions(+), 22 deletions(-) diff --git a/lib/radix-tree.c b/lib/radix-tree.c index fab4485..412dc35 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -1009,9 +1009,9 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root, unsigned long nr_to_tag, unsigned int iftag, unsigned int settag) { - struct radix_tree_node *slot, *node = NULL; + struct radix_tree_node *parent, *node, *child; unsigned long maxindex; - unsigned int shift = radix_tree_load_root(root, &slot, &maxindex); + unsigned int shift = radix_tree_load_root(root, &child, &maxindex); unsigned long tagged = 0; unsigned long index = *first_indexp; @@ -1024,28 +1024,25 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root, *first_indexp = last_index + 1; return 0; } - if (!radix_tree_is_internal_node(slot)) { + if (!radix_tree_is_internal_node(child)) { *first_indexp = last_index + 1; root_tag_set(root, settag); return 1; } - node = entry_to_node(slot); + node = entry_to_node(child); shift -= RADIX_TREE_MAP_SHIFT; for (;;) { - unsigned long upindex; - unsigned offset; - - offset = (index >> shift) & RADIX_TREE_MAP_MASK; - offset = radix_tree_descend(node, &slot, offset); - if (!slot) + unsigned offset = (index >> shift) & RADIX_TREE_MAP_MASK; + offset = radix_tree_descend(node, &child, offset); + if (!child) goto next; if (!tag_get(node, iftag, offset)) goto next; /* Sibling slots never have tags set on them */ - if (radix_tree_is_internal_node(slot)) { - node = entry_to_node(slot); + if (radix_tree_is_internal_node(child)) { + node = entry_to_node(child); shift -= RADIX_TREE_MAP_SHIFT; continue; } @@ -1054,20 +1051,18 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root, tagged++; tag_set(node, settag, offset); - slot = node->parent; /* walk back up the path tagging interior nodes */ - upindex = index >> shift; - while (slot) { - upindex >>= RADIX_TREE_MAP_SHIFT; - offset = upindex & RADIX_TREE_MAP_MASK; - + parent = node; + for (;;) { + offset = parent->offset; + parent = parent->parent; + if (!parent) + break; /* stop if we find a node with the tag already set */ - if (tag_get(slot, settag, offset)) + if (tag_get(parent, settag, offset)) break; - tag_set(slot, settag, offset); - slot = slot->parent; + tag_set(parent, settag, offset); } - next: /* Go to next item at level determined by 'shift' */ index = ((index >> shift) + 1) << shift; -- 2.8.0.rc3
WARNING: multiple messages have this Message-ID (diff)
From: Matthew Wilcox <willy@linux.intel.com> To: linux-kernel@vger.kernel.org, Andrew Morton <akpm@linux-foundation.org> Cc: Matthew Wilcox <willy@linux.intel.com>, linux-mm@kvack.org, linux-fsdevel@vger.kernel.org, Konstantin Khlebnikov <koct9i@gmail.com>, Kirill Shutemov <kirill.shutemov@linux.intel.com>, Jan Kara <jack@suse.com>, Neil Brown <neilb@suse.de>, Ross Zwisler <ross.zwisler@linux.intel.com> Subject: [PATCH 14/19] radix-tree: Tidy up range_tag_if_tagged Date: Thu, 14 Apr 2016 10:37:17 -0400 [thread overview] Message-ID: <1460644642-30642-15-git-send-email-willy@linux.intel.com> (raw) In-Reply-To: <1460644642-30642-1-git-send-email-willy@linux.intel.com> Convert radix_tree_range_tag_if_tagged to name the nodes parent, node and child instead of node & slot. Use parent->offset instead of playing games with 'upindex'. Signed-off-by: Matthew Wilcox <willy@linux.intel.com> --- lib/radix-tree.c | 39 +++++++++++++++++---------------------- 1 file changed, 17 insertions(+), 22 deletions(-) diff --git a/lib/radix-tree.c b/lib/radix-tree.c index fab4485..412dc35 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -1009,9 +1009,9 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root, unsigned long nr_to_tag, unsigned int iftag, unsigned int settag) { - struct radix_tree_node *slot, *node = NULL; + struct radix_tree_node *parent, *node, *child; unsigned long maxindex; - unsigned int shift = radix_tree_load_root(root, &slot, &maxindex); + unsigned int shift = radix_tree_load_root(root, &child, &maxindex); unsigned long tagged = 0; unsigned long index = *first_indexp; @@ -1024,28 +1024,25 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root, *first_indexp = last_index + 1; return 0; } - if (!radix_tree_is_internal_node(slot)) { + if (!radix_tree_is_internal_node(child)) { *first_indexp = last_index + 1; root_tag_set(root, settag); return 1; } - node = entry_to_node(slot); + node = entry_to_node(child); shift -= RADIX_TREE_MAP_SHIFT; for (;;) { - unsigned long upindex; - unsigned offset; - - offset = (index >> shift) & RADIX_TREE_MAP_MASK; - offset = radix_tree_descend(node, &slot, offset); - if (!slot) + unsigned offset = (index >> shift) & RADIX_TREE_MAP_MASK; + offset = radix_tree_descend(node, &child, offset); + if (!child) goto next; if (!tag_get(node, iftag, offset)) goto next; /* Sibling slots never have tags set on them */ - if (radix_tree_is_internal_node(slot)) { - node = entry_to_node(slot); + if (radix_tree_is_internal_node(child)) { + node = entry_to_node(child); shift -= RADIX_TREE_MAP_SHIFT; continue; } @@ -1054,20 +1051,18 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root, tagged++; tag_set(node, settag, offset); - slot = node->parent; /* walk back up the path tagging interior nodes */ - upindex = index >> shift; - while (slot) { - upindex >>= RADIX_TREE_MAP_SHIFT; - offset = upindex & RADIX_TREE_MAP_MASK; - + parent = node; + for (;;) { + offset = parent->offset; + parent = parent->parent; + if (!parent) + break; /* stop if we find a node with the tag already set */ - if (tag_get(slot, settag, offset)) + if (tag_get(parent, settag, offset)) break; - tag_set(slot, settag, offset); - slot = slot->parent; + tag_set(parent, settag, offset); } - next: /* Go to next item at level determined by 'shift' */ index = ((index >> shift) + 1) << shift; -- 2.8.0.rc3 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
next prev parent reply other threads:[~2016-04-14 14:40 UTC|newest] Thread overview: 42+ messages / expand[flat|nested] mbox.gz Atom feed top 2016-04-14 14:37 [PATCH 00/19] Radix tree cleanups Matthew Wilcox 2016-04-14 14:37 ` Matthew Wilcox 2016-04-14 14:37 ` [PATCH 01/19] drivers/hwspinlock: Use correct radix tree API Matthew Wilcox 2016-04-14 14:37 ` Matthew Wilcox 2016-04-14 14:37 ` [PATCH 02/19] radix-tree: Miscellaneous fixes Matthew Wilcox 2016-04-14 14:37 ` Matthew Wilcox 2016-04-27 5:43 ` NeilBrown 2016-04-27 5:43 ` NeilBrown 2016-04-14 14:37 ` [PATCH 03/19] radix-tree: Split node->path into offset and height Matthew Wilcox 2016-04-14 14:37 ` Matthew Wilcox 2016-04-14 14:37 ` [PATCH 04/19] radix-tree: Replace node->height with node->shift Matthew Wilcox 2016-04-14 14:37 ` Matthew Wilcox 2016-04-14 14:37 ` [PATCH 05/19] radix-tree: Remove a use of root->height from delete_node Matthew Wilcox 2016-04-14 14:37 ` Matthew Wilcox 2016-04-14 14:37 ` [PATCH 06/19] radix tree test suite: Remove dependencies on height Matthew Wilcox 2016-04-14 14:37 ` Matthew Wilcox 2016-04-14 14:37 ` [PATCH 07/19] radix-tree: Remove root->height Matthew Wilcox 2016-04-14 14:37 ` Matthew Wilcox 2016-04-14 14:37 ` [PATCH 08/19] radix-tree: Rename INDIRECT_PTR to INTERNAL_NODE Matthew Wilcox 2016-04-14 14:37 ` Matthew Wilcox 2016-04-14 14:37 ` [PATCH 09/19] radix-tree: Rename ptr_to_indirect() to node_to_entry() Matthew Wilcox 2016-04-14 14:37 ` Matthew Wilcox 2016-04-14 14:37 ` [PATCH 10/19] radix-tree: Rename indirect_to_ptr() to entry_to_node() Matthew Wilcox 2016-04-14 14:37 ` Matthew Wilcox 2016-04-14 14:37 ` [PATCH 11/19] radix-tree: Rename radix_tree_is_indirect_ptr() Matthew Wilcox 2016-04-14 14:37 ` Matthew Wilcox 2016-04-14 14:37 ` [PATCH 12/19] radix-tree: Change naming conventions in radix_tree_shrink Matthew Wilcox 2016-04-14 14:37 ` Matthew Wilcox 2016-04-14 14:37 ` [PATCH 13/19] radix-tree: Tidy up next_chunk Matthew Wilcox 2016-04-14 14:37 ` Matthew Wilcox 2016-04-14 14:37 ` Matthew Wilcox [this message] 2016-04-14 14:37 ` [PATCH 14/19] radix-tree: Tidy up range_tag_if_tagged Matthew Wilcox 2016-04-14 14:37 ` [PATCH 15/19] radix-tree: Tidy up __radix_tree_create() Matthew Wilcox 2016-04-14 14:37 ` Matthew Wilcox 2016-04-14 14:37 ` [PATCH 16/19] radix-tree: Introduce radix_tree_replace_clear_tags() Matthew Wilcox 2016-04-14 14:37 ` Matthew Wilcox 2016-04-14 14:37 ` [PATCH 17/19] radix-tree: Make radix_tree_descend() more useful Matthew Wilcox 2016-04-14 14:37 ` Matthew Wilcox 2016-04-14 14:37 ` [PATCH 18/19] dax: move RADIX_DAX_ definitions to dax.c Matthew Wilcox 2016-04-14 14:37 ` Matthew Wilcox 2016-04-14 14:37 ` [PATCH 19/19] radix-tree: Free up the bottom bit of exceptional entries for reuse Matthew Wilcox 2016-04-14 14:37 ` Matthew Wilcox
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=1460644642-30642-15-git-send-email-willy@linux.intel.com \ --to=willy@linux.intel.com \ --cc=akpm@linux-foundation.org \ --cc=jack@suse.com \ --cc=kirill.shutemov@linux.intel.com \ --cc=koct9i@gmail.com \ --cc=linux-fsdevel@vger.kernel.org \ --cc=linux-kernel@vger.kernel.org \ --cc=linux-mm@kvack.org \ --cc=neilb@suse.de \ --cc=ross.zwisler@linux.intel.com \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.