lib,rb-tree - introduce rb_for_each helper
RFC 1/1 lib,rb-tree - introduce rb_for_each helper
perftools already use a number of opencoded for() iterators over rbtree. The patch introduce rb_for_each helper for this purpose.
---
The real conversion for this macro usage should be done later.
Also I think having rb_for_each_entry for being used with container_of inbetween could be convinient as well.
Anyway if we don't need such a helper -- just drop the patch.
include/linux/rbtree.h | 3 +++ 1 file changed, 3 insertions(+)
include/linux/rbtree.h +3 -0
@@ -145,6 +145,9 @@ extern struct rb_node *rb_prev(const strextern struct rb_node *rb_first (const struct rb_root *);extern struct rb_node *rb_last (const struct rb_root *); +#define rb_for_each (nd, root) \ + for (nd = rb_first((root)); nd; nd = rb_next(nd)) +/* 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);
Quoted 25 lines · Cyrill Gorcunov
perftools already use a number of opencoded
for()iterators over rbtree. The patch introducerb_for_eachhelper for this purpose.Signed-off-by Cyrill Gorcunov <[email protected]>---
The real conversion for this macro usage should be done later.
Also I think having
rb_for_each_entryfor being used withcontainer_ofinbetween could be convinient as well.Anyway if we don't need such a helper -- just drop the patch.
include/linux/rbtree.h | 3 +++ 1 file changed, 3 insertions(+)Index:
linux-2.6.git/include/linux/rbtree.h
=====================================================================
include/linux/rbtree.h extern struct rb_node *rb_prev(const str · line 153
Quoted 9 lines
include/linux/rbtree.h +3
-0@@ -145,6 +145,9 @@ extern struct rb_node *rb_prev(const strextern struct rb_node *rb_first (const struct rb_root *);extern struct rb_node *rb_last (const struct rb_root *); +#define rb_for_each (nd, root) \ + for (nd = rb_first((root)); nd; nd = rb_next(nd)) +/* 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);
Nice idea!
This pattern is often taken in perfcounter tools. Also to complete this pattern, an abstract container retrieval would be also useful as an iterator:
#define rb_for_each_entry(tpos, pos, root, memb) \ for (pos = rb_first(root); pos && tpos = rb_entry(pos, typeof(*tpos), memb); \ pos = rb_next(pos->memb, typeof(*pos), memb))
Or something like that...
Quoted 1 line · Frederic Weisbecker
pos = rb_next(pos->memb, typeof(*pos), memb))
pos = rb_next(pos) would suffice :)
[Frederic Weisbecker - Sun, Jul 12, 2009 at 12:32:33AM +0200]
| On Sun, Jul 12, 2009 at 12:29:30AM +0200, Frederic Weisbecker wrote: | > pos = rb_next(pos->memb, typeof(*pos), memb)) | | pos = rb_next(pos) would suffice :) |
Hi Frederic,
mind to pick the patch up and complete it withrb_for_each_entry as well? ;)
-- Cyrill
Quoted 3 lines · Frederic Weisbecker
#define rb_for_each_entry(tpos, pos, root, memb) \
for (pos = rb_first(root); pos && tpos = rb_entry(pos, typeof(*tpos), memb); \
pos = rb_next(pos->memb, typeof(*pos), memb))if you really want to do this, then at least call it:for_each_rb_entry().