rbtree: avoid generating code twice for the cached versions
PATCH 1/1 rbtree: avoid generating code twice for the cached versions
As was already noted in rbtree.h, the logic to cache rb_first (or rb_last) can easily be implemented externally to the core rbtree api.
Change the implementation to do just that. Previously the update of rb_leftmost was wired deeper into the implemntation, but there were some disadvantages to that - mostly, lib/rbtree.c had separate instantiations for rb_insert_color() vs rb_insert_color_cached(), as well as rb_erase() vs rb_erase_cached(), which were doing exactly the same thing save for the rb_leftmost update at the start of either function.
--- include/linux/rbtree.h | 70 +++++++++++++++++++++----------- include/linux/rbtree_augmented.h | 27 +++++------- lib/rbtree.c | 40 ++---------------- 3 files changed, 59 insertions(+), 78 deletions(-)
include/linux/rbtree.h +46 -24
@@ -44,25 +44,9 @@ struct rb_root {struct rb_node *rb_node; }; -/* -* Leftmost-cached rbtrees. -* -* We do not cache the rightmost node based on footprint -* size vs number of potential users that could benefit -* from O(1) rb_last(). Just not worth it, users that want -* this feature can always implement the logic explicitly. -* Furthermore, users that want to cache both pointers may -* find it a bit asymmetric, but that's ok. -*/ -struct rb_root_cached { -struct rb_root rb_root; -struct rb_node *rb_leftmost; -}; -#define rb_parent (r) ((struct rb_node *)((r)->__rb_parent_color & ~3))#define RB_ROOT (struct rb_root) { NULL, } -#define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL }#define rb_entry (ptr, type, member) container_of(ptr, type, member)#define RB_EMPTY_ROOT (root) (READ_ONCE((root)->rb_node) == NULL)
@@ -84,12 +68,6 @@ 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 *); -extern void rb_insert_color_cached (struct rb_node *, -struct rb_root_cached *,bool ); -extern void rb_erase_cached (struct rb_node *node,struct rb_root_cached *); -/* Same as rb_first(), but O(1) */ -#define rb_first_cached (root) (root)->rb_leftmost -/* Postorder iteration - always visit the parent after its children */ extern struct rb_node *rb_first_postorder (const struct rb_root *);extern struct rb_node *rb_next_postorder (const struct rb_node *);
@@ -99,8 +77,6 @@ extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root);extern void rb_replace_node_rcu (struct rb_node *victim,struct rb_node *new,struct rb_root *root); -extern void rb_replace_node_cached (struct rb_node *victim,struct rb_node *new, -struct rb_root_cached *root);static inline void rb_link_node (struct rb_node *node,struct rb_node *parent,struct rb_node **rb_link)
@@ -148,4 +124,50 @@ static inline void rb_link_node_rcu(struct rb_node *node, struct rb_node *parent typeof(*pos), field); 1; }); \ pos = n) +/* +* Leftmost-cached rbtrees. +* +* We do not cache the rightmost node based on footprint +* size vs number of potential users that could benefit +* from O(1) rb_last(). Just not worth it, users that want +* this feature can always implement the logic explicitly. +* Furthermore, users that want to cache both pointers may +* find it a bit asymmetric, but that's ok. +*/ +struct rb_root_cached { +struct rb_root rb_root; +struct rb_node *rb_leftmost; +}; + +#define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL } + +/* Same as rb_first(), but O(1) */ +#define rb_first_cached (root) (root)->rb_leftmost + +static inline void rb_insert_color_cached (struct rb_node *node, +struct rb_root_cached *root, +bool leftmost) +{ +if (leftmost) + root->rb_leftmost = node; +rb_insert_color (node, &root->rb_root); +} + +static inline void rb_erase_cached (struct rb_node *node, +struct rb_root_cached *root) +{ +if (root->rb_leftmost == node) + root->rb_leftmost =rb_next (node); +rb_erase (node, &root->rb_root); +} + +static inline void rb_replace_node_cached (struct rb_node *victim, +struct rb_node *new, +struct rb_root_cached *root) +{ +if (root->rb_leftmost == victim) + root->rb_leftmost = new; +rb_replace_node (victim, new, &root->rb_root); +} +#endif /* _LINUX_RBTREE_H */
include/linux/rbtree_augmented.h +10 -17
@@ -42,10 +42,9 @@ struct rb_augment_callbacks {void (*rotate)(struct rb_node *old,struct rb_node *new); }; -extern void __rb_insert_augmented (struct rb_node *node, -struct rb_root *root, -bool newleft,struct rb_node **leftmost, +extern void __rb_insert_augmented (struct rb_node *node,struct rb_root *root,void (*augment_rotate)(struct rb_node *old,struct rb_node *new)); +/* * Fixup the rbtree and update the augmented information when rebalancing. *
@@ -60,7 +59,7 @@ static inline void rb_insert_augmented(struct rb_node *node, struct rb_root *root, const struct rb_augment_callbacks *augment) { - __rb_insert_augmented(node, root, false, NULL, augment->rotate); + __rb_insert_augmented(node, root, augment->rotate); } static inline void
@@ -68,8 +67,9 @@ rb_insert_augmented_cached(struct rb_node *node, struct rb_root_cached *root, bool newleft, const struct rb_augment_callbacks *augment) { - __rb_insert_augmented(node, &root->rb_root, - newleft, &root->rb_leftmost, augment->rotate); + if (newleft) + root->rb_leftmost = node; +rb_insert_augmented (node, &root->rb_root, augment); } #define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield, \
@@ -162,7 +162,6 @@ extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root, static __always_inline struct rb_node *__rb_erase_augmented (struct rb_node *node,struct rb_root *root, -struct rb_node **leftmost,const struct rb_augment_callbacks *augment) {struct rb_node *child = node->rb_right;
@@ -170,9 +169,6 @@ __rb_erase_augmented(struct rb_node *node, struct rb_root *root,struct rb_node *parent, *rebalance;unsigned long pc; -if (leftmost && node == *leftmost) - *leftmost =rb_next (node); -if (!tmp) {/* * Case 1: node to erase has no more than 1 child (easy!)
@@ -272,8 +268,7 @@ static __always_inline void rb_erase_augmented(struct rb_node *node, struct rb_root *root, const struct rb_augment_callbacks *augment) { - struct rb_node *rebalance = __rb_erase_augmented(node, root, -NULL , augment); + struct rb_node *rebalance = __rb_erase_augmented(node, root, augment);if (rebalance)__rb_erase_color (rebalance, root, augment->rotate); }
@@ -282,11 +277,9 @@ static __always_inline void rb_erase_augmented_cached(struct rb_node *node, struct rb_root_cached *root, const struct rb_augment_callbacks *augment) { - struct rb_node *rebalance = __rb_erase_augmented(node, &root->rb_root, - &root->rb_leftmost, - augment); -if (rebalance) -__rb_erase_color (rebalance, &root->rb_root, augment->rotate); + if (root->rb_leftmost == node) + root->rb_leftmost = rb_next(node); +rb_erase_augmented (node, &root->rb_root, augment); }#endif /* _LINUX_RBTREE_AUGMENTED_H */
lib/rbtree.c +3 -37
@@ -95,14 +95,10 @@ __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, static __always_inline void__rb_insert (struct rb_node *node,struct rb_root *root, -bool newleft,struct rb_node **leftmost,void (*augment_rotate)(struct rb_node *old,struct rb_node *new)) {struct rb_node *parent =rb_red_parent (node), *gparent, *tmp; -if (newleft) - *leftmost = node; -while (true) {/* * Loop invariant: node is red.
@@ -449,38 +445,19 @@ static const struct rb_augment_callbacks dummy_callbacks = {void rb_insert_color (struct rb_node *node,struct rb_root *root) { -__rb_insert (node, root, false,NULL , dummy_rotate); +__rb_insert (node, root, dummy_rotate); }EXPORT_SYMBOL (rb_insert_color);void rb_erase (struct rb_node *node,struct rb_root *root) {struct rb_node *rebalance; - rebalance =__rb_erase_augmented (node, root, -NULL , &dummy_callbacks); + rebalance =__rb_erase_augmented (node, root, &dummy_callbacks);if (rebalance)____rb_erase_color (rebalance, root, dummy_rotate); }EXPORT_SYMBOL (rb_erase); -void rb_insert_color_cached (struct rb_node *node, -struct rb_root_cached *root,bool leftmost) -{ -__rb_insert (node, &root->rb_root, leftmost, - &root->rb_leftmost, dummy_rotate); -} -EXPORT_SYMBOL (rb_insert_color_cached); - -void rb_erase_cached (struct rb_node *node,struct rb_root_cached *root) -{ -struct rb_node *rebalance; - rebalance =__rb_erase_augmented (node, &root->rb_root, - &root->rb_leftmost, &dummy_callbacks); -if (rebalance) -____rb_erase_color (rebalance, &root->rb_root, dummy_rotate); -} -EXPORT_SYMBOL (rb_erase_cached); -/* * Augmented rbtree manipulation functions. *
@@ -489,10 +466,9 @@ EXPORT_SYMBOL(rb_erase_cached);*/ void __rb_insert_augmented (struct rb_node *node,struct rb_root *root, -bool newleft,struct rb_node **leftmost,void (*augment_rotate)(struct rb_node *old,struct rb_node *new)) { -__rb_insert (node, root, newleft, leftmost, augment_rotate); +__rb_insert (node, root, augment_rotate); }EXPORT_SYMBOL (__rb_insert_augmented);
@@ -603,16 +579,6 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new, }EXPORT_SYMBOL (rb_replace_node); -void rb_replace_node_cached (struct rb_node *victim,struct rb_node *new, -struct rb_root_cached *root) -{ -rb_replace_node (victim, new, &root->rb_root); - -if (root->rb_leftmost == victim) - root->rb_leftmost = new; -} -EXPORT_SYMBOL (rb_replace_node_cached); -void rb_replace_node_rcu (struct rb_node *victim,struct rb_node *new,struct rb_root *root) {
Signature · 1 line
2.22.0.410.gd8fdbe21b5-goog
Quoted 9 lines · Michel Lespinasse
As was already noted in
rbtree.h, the logic to cacherb_first(orrb_last) can easily be implemented externally to the core rbtree api.Change the implementation to do just that. Previously the update of
rb_leftmostwas wired deeper into the implemntation, but there were some disadvantages to that - mostly,lib/rbtree.chad separate instantiations forrb_insert_color()vsrb_insert_color_cached(), as well asrb_erase()vsrb_erase_cached(), which were doing exactly the same thing save for therb_leftmostupdate at the start of either function.
I think this makes sense, and is more along the lines of the augmented cached doing the static inline instead of separate instantiations of the calls.
Quoted 1 line
Change-Id: I0cb62be774fc0138b81188e6ae81d5f1da64578d
what is this?
Quoted 1 line
Signed-off-by Michel Lespinasse <[email protected]>
Thanks!
Hi Davidlohr,
Quoted 3 lines · Davidlohr Bueso
I think this makes sense, and is more along the lines of the augmented cached doing the static inline instead of separate instantiations of the calls.
Thanks for the review.
Quoted 2 lines
Quoted 1 line
Change-Id: I0cb62be774fc0138b81188e6ae81d5f1da64578d
what is this?
Gerrit code review insists on having this footer on every commit. I forgot to remove it before submitting. Please ignore it :)
Signature · 2 lines
Michel "Walken" Lespinasse A program is never fully debugged until the last user dies.
Quoted 9 lines · Michel Lespinasse
As was already noted in
rbtree.h, the logic to cacherb_first(orrb_last) can easily be implemented externally to the core rbtree api.Change the implementation to do just that. Previously the update of
rb_leftmostwas wired deeper into the implemntation, but there were some disadvantages to that - mostly,lib/rbtree.chad separate instantiations forrb_insert_color()vsrb_insert_color_cached(), as well asrb_erase()vsrb_erase_cached(), which were doing exactly the same thing save for therb_leftmostupdate at the start of either function.
Also:
text data bss dec hex filename
5405 120 0 5525 1595 lib/rbtree.o-vanilla 3827 96 0 3923 f53 lib/rbtree.o-patch
Quoted 11 lines · Michel Lespinasse
As was already noted in
rbtree.h, the logic to cacherb_first(orrb_last) can easily be implemented externally to the core rbtree api.Change the implementation to do just that. Previously the update of
rb_leftmostwas wired deeper into the implemntation, but there were some disadvantages to that - mostly,lib/rbtree.chad separate instantiations forrb_insert_color()vsrb_insert_color_cached(), as well asrb_erase()vsrb_erase_cached(), which were doing exactly the same thing save for therb_leftmostupdate at the start of either function.
Quoted 6 lines
Signed-off-by Michel Lespinasse <[email protected]>--- include/linux/rbtree.h | 70 +++++++++++++++++++++----------- include/linux/rbtree_augmented.h | 27 +++++------- lib/rbtree.c | 40 ++---------------- 3 files changed, 59 insertions(+), 78 deletions(-)