Messages in this thread Patch in this message | | | From | qiwuchen55@gmail ... | Subject | [PATCH] rbtree: introduce three helpers about sort-order iteration | Date | Tue, 10 Mar 2020 00:02:14 +0800 |
| |
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
| |