* [PATCH] rbtree: introduce three helpers about sort-order iteration
@ 2020-03-09 16:02 qiwuchen55
2020-03-09 16:55 ` Peter Zijlstra
0 siblings, 1 reply; 3+ messages in thread
From: qiwuchen55 @ 2020-03-09 16:02 UTC (permalink / raw)
To: akpm, peterz, walken, rfontana, dbueso; +Cc: tglx, linux-kernel, chenqiwu
From: chenqiwu <chenqiwu@xiaomi.com>
I noticed that there are many relatively common usages about the
sort-order iteration for rbtree, like this:
[drivers/android/binder.c]
for (n = rb_first(&proc->nodes); n != NULL; n = rb_next(n)) {
struct binder_node *node = rb_entry(n, struct binder_node,
rb_node);
......
}
This patch introduced three helpers to simplify sort-order iteration
for rbtree.
Signed-off-by: chenqiwu <chenqiwu@xiaomi.com>
---
include/linux/rbtree.h | 45 +++++++++++++++++++++++++++++++++++++++++++--
1 file changed, 43 insertions(+), 2 deletions(-)
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 1fd61a9..26b4359 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -90,11 +90,52 @@ static inline void rb_link_node_rcu(struct rb_node *node, struct rb_node *parent
})
/**
+ * rbtree_for_each - iterate in sort-order over a rbtree.
+ * @pos: the 'rb_node *' to use as a loop cursor.
+ * @root: 'rb_root *' of the rbtree.
+ */
+#define rbtree_for_each(pos, root) \
+ for (pos = rb_first(root); pos; pos = rb_next(pos))
+
+/**
+ * rbtree_for_each_entry - iterate in sort-order over rb_root of given type.
+ * @pos: the 'type *' to use as a loop cursor.
+ * @root: 'rb_root *' of the rbtree.
+ * @field: the name of the rb_node field within 'type'.
+ */
+#define rbtree_for_each_entry(pos, root, field) \
+ for (pos = rb_entry_safe(rb_first(root), typeof(*pos), field); \
+ pos; \
+ pos = rb_entry_safe(rb_next(&pos->field), typeof(*pos), field))
+
+/**
+ * rbtree_for_each_entry_safe - iterate in sort-order over of given type
+ * allowing the backing memory of @pos to be invalidated.
+ * @pos: the 'type *' to use as a loop cursor.
+ * @n: another 'type *' to use as temporary storage.
+ * @root: 'rb_root *' of the rbtree.
+ * @field: the name of the rb_node field within 'type'.
+ *
+ * rbtree_order_for_each_entry_safe() provides a similar guarantee as
+ * list_for_each_entry_safe() and allows the sort-order iteration to
+ * continue independent of changes to @pos by the body of the loop.
+ *
+ * Note, however, that it cannot handle other modifications that re-order the
+ * rbtree it is iterating over. This includes calling rb_erase() on @pos, as
+ * rb_erase() may rebalance the tree, causing us to miss some nodes.
+ */
+#define rbtree_for_each_entry_safe(pos, n, root, field) \
+ for (pos = rb_entry_safe(rb_first(root), typeof(*pos), field); \
+ pos && ({ n = rb_entry_safe(rb_next(&pos->field), \
+ typeof(*pos), field); 1; }); \
+ pos = n)
+
+/**
* rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of
- * given type allowing the backing memory of @pos to be invalidated
+ * given type allowing the backing memory of @pos to be invalidated.
*
* @pos: the 'type *' to use as a loop cursor.
- * @n: another 'type *' to use as temporary storage
+ * @n: another 'type *' to use as temporary storage.
* @root: 'rb_root *' of the rbtree.
* @field: the name of the rb_node field within 'type'.
*
--
1.9.1
^ permalink raw reply related [flat|nested] 3+ messages in thread
* Re: [PATCH] rbtree: introduce three helpers about sort-order iteration
2020-03-09 16:02 [PATCH] rbtree: introduce three helpers about sort-order iteration qiwuchen55
@ 2020-03-09 16:55 ` Peter Zijlstra
2020-03-10 2:02 ` chenqiwu
0 siblings, 1 reply; 3+ messages in thread
From: Peter Zijlstra @ 2020-03-09 16:55 UTC (permalink / raw)
To: qiwuchen55; +Cc: akpm, walken, rfontana, dbueso, tglx, linux-kernel, chenqiwu
On Tue, Mar 10, 2020 at 12:02:14AM +0800, qiwuchen55@gmail.com wrote:
> +/**
> + * rbtree_for_each_entry_safe - iterate in sort-order over of given type
> + * allowing the backing memory of @pos to be invalidated.
> + * @pos: the 'type *' to use as a loop cursor.
> + * @n: another 'type *' to use as temporary storage.
> + * @root: 'rb_root *' of the rbtree.
> + * @field: the name of the rb_node field within 'type'.
> + *
> + * rbtree_order_for_each_entry_safe() provides a similar guarantee as
> + * list_for_each_entry_safe() and allows the sort-order iteration to
> + * continue independent of changes to @pos by the body of the loop.
> + *
> + * Note, however, that it cannot handle other modifications that re-order the
> + * rbtree it is iterating over. This includes calling rb_erase() on @pos, as
> + * rb_erase() may rebalance the tree, causing us to miss some nodes.
> + */
> +#define rbtree_for_each_entry_safe(pos, n, root, field) \
> + for (pos = rb_entry_safe(rb_first(root), typeof(*pos), field); \
> + pos && ({ n = rb_entry_safe(rb_next(&pos->field), \
> + typeof(*pos), field); 1; }); \
> + pos = n)
Since this cannot deal with rb_erase(), what exactly is the purpose of
this thing?
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] rbtree: introduce three helpers about sort-order iteration
2020-03-09 16:55 ` Peter Zijlstra
@ 2020-03-10 2:02 ` chenqiwu
0 siblings, 0 replies; 3+ messages in thread
From: chenqiwu @ 2020-03-10 2:02 UTC (permalink / raw)
To: Peter Zijlstra
Cc: akpm, walken, rfontana, dbueso, tglx, linux-kernel, chenqiwu
On Mon, Mar 09, 2020 at 05:55:11PM +0100, Peter Zijlstra wrote:
> On Tue, Mar 10, 2020 at 12:02:14AM +0800, qiwuchen55@gmail.com wrote:
> > +/**
> > + * rbtree_for_each_entry_safe - iterate in sort-order over of given type
> > + * allowing the backing memory of @pos to be invalidated.
> > + * @pos: the 'type *' to use as a loop cursor.
> > + * @n: another 'type *' to use as temporary storage.
> > + * @root: 'rb_root *' of the rbtree.
> > + * @field: the name of the rb_node field within 'type'.
> > + *
> > + * rbtree_order_for_each_entry_safe() provides a similar guarantee as
> > + * list_for_each_entry_safe() and allows the sort-order iteration to
> > + * continue independent of changes to @pos by the body of the loop.
> > + *
> > + * Note, however, that it cannot handle other modifications that re-order the
> > + * rbtree it is iterating over. This includes calling rb_erase() on @pos, as
> > + * rb_erase() may rebalance the tree, causing us to miss some nodes.
> > + */
> > +#define rbtree_for_each_entry_safe(pos, n, root, field) \
> > + for (pos = rb_entry_safe(rb_first(root), typeof(*pos), field); \
> > + pos && ({ n = rb_entry_safe(rb_next(&pos->field), \
> > + typeof(*pos), field); 1; }); \
> > + pos = n)
>
> Since this cannot deal with rb_erase(), what exactly is the purpose of
> this thing?
It's just a copy of rbtree_postorder_for_each_entry_safe() for
the usage scenario of sort-order iteration. It can be used for
walking the tree and free all entries of the given type.
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2020-03-10 2:02 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-03-09 16:02 [PATCH] rbtree: introduce three helpers about sort-order iteration qiwuchen55
2020-03-09 16:55 ` Peter Zijlstra
2020-03-10 2:02 ` chenqiwu
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.