rbtree: introduce three helpers about sort-order iteration
PATCH 1/1 rbtree: introduce three helpers about sort-order iteration
From: chenqiwu <[email protected]>
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.
--- include/linux/rbtree.h | 45 +++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 43 insertions(+), 2 deletions(-)
include/linux/rbtree.h +43 -2
@@ -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'. *
Signature · 1 line
1.9.1
Quoted 11 lines · On Tue, Mar 10, 2020 at 12:02:14AM +0800, [email protected] wrote:
include/linux/rbtree.h +11
-0+/** +* 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.
include/linux/rbtree.h static inline void rb_link_node_rcu(struct rb_node *node, struct rb_node *parent · line 131
Quoted 10 lines
include/linux/rbtree.h +10
-0+* +* 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?
Quoted 17 lines · Peter Zijlstra
Quoted 16 lines · On Tue, Mar 10, 2020 at 12:02:14AM +0800, [email protected] 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 therb_nodefield 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 callingrb_erase()on @pos, as
+ *rb_erase()may rebalance the tree, causing us to miss some nodes.
+ */
Quoted 8 lines
include/linux/rbtree.h static inline void rb_link_node_rcu(struct rb_node *node, struct rb_node *parent · line 131
Quoted 5 lines
include/linux/rbtree.h +5
-0+#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.