From: Rik van Riel <riel@surriel.com> To: linux-mm@kvack.org Cc: akpm@linux-foundation.org, aarcange@redhat.com, peterz@infradead.org, minchan@gmail.com, kosaki.motohiro@gmail.com, andi@firstfloor.org, hannes@cmpxchg.org, mel@csn.ul.ie, linux-kernel@vger.kernel.org, Rik van Riel <riel@surriel.com>, Rik van Riel <riel@redhat.com> Subject: [PATCH -mm v2 04/11] rbtree: add helpers to find nearest uncle node Date: Thu, 21 Jun 2012 17:57:08 -0400 [thread overview] Message-ID: <1340315835-28571-5-git-send-email-riel@surriel.com> (raw) In-Reply-To: <1340315835-28571-1-git-send-email-riel@surriel.com> It is useful to search an augmented rbtree based on the augmented data, ie. not using the sort key as the primary search criterium. However, we may still need to limit our search to a sub-part of the whole tree, using the sort key as limiters where we can search. In that case, we may need to stop searching in one part of the tree, and continue the search at the nearest (great-?)uncle node in a particular direction. Add helper functions to find the nearest uncle node. Signed-off-by: Rik van Riel <riel@redhat.com> --- include/linux/rbtree.h | 4 ++++ lib/rbtree.c | 46 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 50 insertions(+), 0 deletions(-) diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h index 661288d..a74b74b 100644 --- a/include/linux/rbtree.h +++ b/include/linux/rbtree.h @@ -169,6 +169,10 @@ extern struct rb_node *rb_prev(const struct rb_node *); extern struct rb_node *rb_first(const struct rb_root *); extern struct rb_node *rb_last(const struct rb_root *); +/* Find the prev or next uncle of a node in the desired direction. */ +extern struct rb_node *rb_find_prev_uncle(struct rb_node *); +extern struct rb_node *rb_find_next_uncle(struct rb_node *); + /* Fast replacement of a single node without remove/rebalance/add/rebalance */ extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root); diff --git a/lib/rbtree.c b/lib/rbtree.c index d417556..08c16d8 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -437,6 +437,52 @@ struct rb_node *rb_prev(const struct rb_node *node) } EXPORT_SYMBOL(rb_prev); +/* + * rb_find_{prev,next}_uncle - Find the nearest "uncle" node in a direction + * + * An "uncle" node is a sibling node of a parent or grandparent. These + * functions walk up the tree to the nearest uncle of this node in the + * desired direction. + * + * G + * / \ + * P U + * \ + * N + * This is necessary when searching for something in a bounded subset + * of an augmented rbtree, when the primary search criterium is the + * augmented data, and not the sort key. + */ +struct rb_node *rb_find_prev_uncle(struct rb_node *node) +{ + struct rb_node *prev; + + while ((prev = node) && (node = rb_parent(node))) { + if (prev == node->rb_left) + continue; + + if (node->rb_left) + return node->rb_left; + } + + return NULL; +} + +struct rb_node *rb_find_next_uncle(struct rb_node *node) +{ + struct rb_node *prev; + + while ((prev = node) && (node = rb_parent(node))) { + if (prev == node->rb_right) + continue; + + if (node->rb_right) + return node->rb_right; + } + + return NULL; +} + void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root) { -- 1.7.7.6
WARNING: multiple messages have this Message-ID (diff)
From: Rik van Riel <riel@surriel.com> To: linux-mm@kvack.org Cc: akpm@linux-foundation.org, aarcange@redhat.com, peterz@infradead.org, minchan@gmail.com, kosaki.motohiro@gmail.com, andi@firstfloor.org, hannes@cmpxchg.org, mel@csn.ul.ie, linux-kernel@vger.kernel.org, Rik van Riel <riel@surriel.com>, Rik van Riel <riel@redhat.com> Subject: [PATCH -mm v2 04/11] rbtree: add helpers to find nearest uncle node Date: Thu, 21 Jun 2012 17:57:08 -0400 [thread overview] Message-ID: <1340315835-28571-5-git-send-email-riel@surriel.com> (raw) In-Reply-To: <1340315835-28571-1-git-send-email-riel@surriel.com> It is useful to search an augmented rbtree based on the augmented data, ie. not using the sort key as the primary search criterium. However, we may still need to limit our search to a sub-part of the whole tree, using the sort key as limiters where we can search. In that case, we may need to stop searching in one part of the tree, and continue the search at the nearest (great-?)uncle node in a particular direction. Add helper functions to find the nearest uncle node. Signed-off-by: Rik van Riel <riel@redhat.com> --- include/linux/rbtree.h | 4 ++++ lib/rbtree.c | 46 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 50 insertions(+), 0 deletions(-) diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h index 661288d..a74b74b 100644 --- a/include/linux/rbtree.h +++ b/include/linux/rbtree.h @@ -169,6 +169,10 @@ extern struct rb_node *rb_prev(const struct rb_node *); extern struct rb_node *rb_first(const struct rb_root *); extern struct rb_node *rb_last(const struct rb_root *); +/* Find the prev or next uncle of a node in the desired direction. */ +extern struct rb_node *rb_find_prev_uncle(struct rb_node *); +extern struct rb_node *rb_find_next_uncle(struct rb_node *); + /* Fast replacement of a single node without remove/rebalance/add/rebalance */ extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root); diff --git a/lib/rbtree.c b/lib/rbtree.c index d417556..08c16d8 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -437,6 +437,52 @@ struct rb_node *rb_prev(const struct rb_node *node) } EXPORT_SYMBOL(rb_prev); +/* + * rb_find_{prev,next}_uncle - Find the nearest "uncle" node in a direction + * + * An "uncle" node is a sibling node of a parent or grandparent. These + * functions walk up the tree to the nearest uncle of this node in the + * desired direction. + * + * G + * / \ + * P U + * \ + * N + * This is necessary when searching for something in a bounded subset + * of an augmented rbtree, when the primary search criterium is the + * augmented data, and not the sort key. + */ +struct rb_node *rb_find_prev_uncle(struct rb_node *node) +{ + struct rb_node *prev; + + while ((prev = node) && (node = rb_parent(node))) { + if (prev == node->rb_left) + continue; + + if (node->rb_left) + return node->rb_left; + } + + return NULL; +} + +struct rb_node *rb_find_next_uncle(struct rb_node *node) +{ + struct rb_node *prev; + + while ((prev = node) && (node = rb_parent(node))) { + if (prev == node->rb_right) + continue; + + if (node->rb_right) + return node->rb_right; + } + + return NULL; +} + void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root) { -- 1.7.7.6 -- 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:[~2012-06-21 21:57 UTC|newest] Thread overview: 90+ messages / expand[flat|nested] mbox.gz Atom feed top 2012-06-21 21:57 [PATCH -mm v2 00/11] mm: scalable and unified arch_get_unmapped_area Rik van Riel 2012-06-21 21:57 ` Rik van Riel 2012-06-21 21:57 ` [PATCH -mm v2 01/11] mm: track free size between VMAs in VMA rbtree Rik van Riel 2012-06-21 21:57 ` Rik van Riel 2012-06-22 9:57 ` Peter Zijlstra 2012-06-22 9:57 ` Peter Zijlstra 2012-06-22 9:58 ` Peter Zijlstra 2012-06-22 9:58 ` Peter Zijlstra 2012-06-22 14:11 ` Rik van Riel 2012-06-22 14:11 ` Rik van Riel 2012-06-22 14:13 ` Peter Zijlstra 2012-06-22 14:13 ` Peter Zijlstra 2012-06-22 14:25 ` Rik van Riel 2012-06-22 14:25 ` Rik van Riel 2012-06-22 14:37 ` Peter Zijlstra 2012-06-22 14:37 ` Peter Zijlstra 2012-06-22 15:41 ` Rik van Riel 2012-06-22 15:41 ` Rik van Riel 2012-06-25 19:29 ` Peter Zijlstra 2012-06-25 19:29 ` Peter Zijlstra 2012-06-25 21:52 ` Rik van Riel 2012-06-25 21:52 ` Rik van Riel 2012-06-26 8:31 ` Peter Zijlstra 2012-06-26 8:31 ` Peter Zijlstra 2012-06-26 13:05 ` Rik van Riel 2012-06-26 13:05 ` Rik van Riel 2012-06-26 13:45 ` Peter Zijlstra 2012-06-26 13:45 ` Peter Zijlstra 2012-06-26 15:49 ` Rik van Riel 2012-06-26 15:49 ` Rik van Riel 2012-06-27 12:27 ` Peter Zijlstra 2012-06-27 12:27 ` Peter Zijlstra 2012-06-26 8:37 ` Peter Zijlstra 2012-06-26 8:37 ` Peter Zijlstra 2012-06-22 10:02 ` Peter Zijlstra 2012-06-22 10:02 ` Peter Zijlstra 2012-06-29 23:46 ` Michel Lespinasse 2012-06-29 23:46 ` Michel Lespinasse 2012-07-03 21:37 ` Rik van Riel 2012-07-03 21:37 ` Rik van Riel 2012-07-03 23:16 ` Michel Lespinasse 2012-07-03 23:16 ` Michel Lespinasse 2012-07-04 10:12 ` Peter Zijlstra 2012-07-04 10:12 ` Peter Zijlstra 2012-06-21 21:57 ` [PATCH -mm v2 02/11] mm: rearrange vm_area_struct for fewer cache misses Rik van Riel 2012-06-21 21:57 ` Rik van Riel 2012-06-21 21:57 ` [PATCH -mm v2 03/11] mm: vma_adjust: only call adjust_free_gap when needed Rik van Riel 2012-06-21 21:57 ` Rik van Riel 2012-06-21 21:57 ` Rik van Riel [this message] 2012-06-21 21:57 ` [PATCH -mm v2 04/11] rbtree: add helpers to find nearest uncle node Rik van Riel 2012-06-22 9:49 ` Peter Zijlstra 2012-06-22 9:49 ` Peter Zijlstra 2012-06-21 21:57 ` [PATCH -mm v2 05/11] mm: get unmapped area from VMA tree Rik van Riel 2012-06-21 21:57 ` Rik van Riel 2012-06-30 1:33 ` Michel Lespinasse 2012-06-30 1:33 ` Michel Lespinasse 2012-07-03 0:23 ` Michel Lespinasse 2012-07-03 0:23 ` Michel Lespinasse 2012-06-30 2:42 ` Michel Lespinasse 2012-06-30 2:42 ` Michel Lespinasse 2012-06-21 21:57 ` [PATCH -mm v2 06/11] mm: arbitrary address ranges for arch_get_unmapped_area Rik van Riel 2012-06-21 21:57 ` Rik van Riel 2012-06-21 21:57 ` [PATCH -mm v2 07/11] mm: make cache alignment code generic Rik van Riel 2012-06-21 21:57 ` Rik van Riel 2012-06-30 2:22 ` Michel Lespinasse 2012-06-30 2:22 ` Michel Lespinasse 2012-06-21 21:57 ` [PATCH -mm v2 08/11] mm: remove x86 arch_get_unmapped_area(_topdown) Rik van Riel 2012-06-21 21:57 ` Rik van Riel 2012-06-21 21:57 ` [PATCH -mm v2 09/11] mm: remove MIPS arch_get_unmapped_area code Rik van Riel 2012-06-21 21:57 ` Rik van Riel 2012-06-21 21:57 ` [PATCH -mm v2 10/11] mm: remove ARM arch_get_unmapped_area functions Rik van Riel 2012-06-21 21:57 ` Rik van Riel 2012-06-22 22:27 ` Russell King - ARM Linux 2012-06-22 22:27 ` Russell King - ARM Linux 2012-06-23 17:50 ` Johannes Weiner 2012-06-23 17:50 ` Johannes Weiner 2012-06-21 21:57 ` [PATCH -mm v2 11/11] mm: remove SH " Rik van Riel 2012-06-21 21:57 ` Rik van Riel 2012-06-21 21:57 ` Rik van Riel 2012-06-25 2:11 ` Paul Mundt 2012-06-25 2:11 ` Paul Mundt 2012-06-25 2:11 ` Paul Mundt 2012-06-22 14:24 ` [PATCH -mm v2 00/11] mm: scalable and unified arch_get_unmapped_area John Stoffel 2012-06-22 14:24 ` John Stoffel 2012-06-22 21:47 ` Andrew Morton 2012-06-22 21:47 ` Andrew Morton 2012-06-23 16:03 ` John Stoffel 2012-06-23 16:03 ` John Stoffel 2012-06-22 15:01 ` Johannes Weiner 2012-06-22 15:01 ` Johannes Weiner
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=1340315835-28571-5-git-send-email-riel@surriel.com \ --to=riel@surriel.com \ --cc=aarcange@redhat.com \ --cc=akpm@linux-foundation.org \ --cc=andi@firstfloor.org \ --cc=hannes@cmpxchg.org \ --cc=kosaki.motohiro@gmail.com \ --cc=linux-kernel@vger.kernel.org \ --cc=linux-mm@kvack.org \ --cc=mel@csn.ul.ie \ --cc=minchan@gmail.com \ --cc=peterz@infradead.org \ --cc=riel@redhat.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.