hi Arnaldo: On 9/29/17 2:26 PM, David Ahern wrote: > Update rbtree files to 4.14.
Haven't seen this one in your perf/core branch. You added the existing version, so assuming an update goes through you as well. > > Changes made after copy: > - update guards in header files > - remove rcu references > > Signed-off-by: David Ahern <dsah...@gmail.com> > --- > tools/include/linux/rbtree.h | 59 ++++++++--- > tools/include/linux/rbtree_augmented.h | 58 +++++++++-- > tools/lib/rbtree.c | 184 > +++++++++++++++++++++++++-------- > 3 files changed, 233 insertions(+), 68 deletions(-) > > diff --git a/tools/include/linux/rbtree.h b/tools/include/linux/rbtree.h > index 112582253dd0..fe5d79881749 100644 > --- a/tools/include/linux/rbtree.h > +++ b/tools/include/linux/rbtree.h > @@ -1,7 +1,7 @@ > /* > Red Black Trees > (C) 1999 Andrea Arcangeli <and...@suse.de> > - > + > This program is free software; you can redistribute it and/or modify > it under the terms of the GNU General Public License as published by > the Free Software Foundation; either version 2 of the License, or > @@ -43,13 +43,28 @@ 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) ((root)->rb_node == NULL) > +#define RB_EMPTY_ROOT(root) (READ_ONCE((root)->rb_node) == NULL) > > /* 'empty' nodes are nodes that are known not to be inserted in an rbtree */ > #define RB_EMPTY_NODE(node) \ > @@ -68,6 +83,12 @@ 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 *); > @@ -90,15 +111,27 @@ static inline void rb_link_node(struct rb_node *node, > struct rb_node *parent, > ____ptr ? rb_entry(____ptr, type, member) : NULL; \ > }) > > - > -/* > - * Handy for checking that we are not deleting an entry that is > - * already in a list, found in block/{blk-throttle,cfq-iosched}.c, > - * probably should be moved to lib/rbtree.c... > +/** > + * 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 > + * > + * @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_postorder_for_each_entry_safe() provides a similar guarantee as > + * list_for_each_entry_safe() and allows the 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. > */ > -static inline void rb_erase_init(struct rb_node *n, struct rb_root *root) > -{ > - rb_erase(n, root); > - RB_CLEAR_NODE(n); > -} > -#endif /* __TOOLS_LINUX_PERF_RBTREE_H */ > +#define rbtree_postorder_for_each_entry_safe(pos, n, root, field) \ > + for (pos = rb_entry_safe(rb_first_postorder(root), typeof(*pos), > field); \ > + pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \ > + typeof(*pos), field); 1; }); \ > + pos = n) > + > +#endif /* __TOOLS_LINUX_PERF_RBTREE_H */ > diff --git a/tools/include/linux/rbtree_augmented.h > b/tools/include/linux/rbtree_augmented.h > index 43be941db695..405716528516 100644 > --- a/tools/include/linux/rbtree_augmented.h > +++ b/tools/include/linux/rbtree_augmented.h > @@ -44,7 +44,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, > +extern 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)); > /* > * Fixup the rbtree and update the augmented information when rebalancing. > @@ -60,7 +62,16 @@ 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, augment->rotate); > + __rb_insert_augmented(node, root, false, NULL, augment->rotate); > +} > + > +static inline void > +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); > } > > #define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield, \ > @@ -93,7 +104,9 @@ rbname ## _rotate(struct rb_node *rb_old, struct rb_node > *rb_new) \ > old->rbaugmented = rbcompute(old); \ > } \ > rbstatic const struct rb_augment_callbacks rbname = { > \ > - rbname ## _propagate, rbname ## _copy, rbname ## _rotate \ > + .propagate = rbname ## _propagate, \ > + .copy = rbname ## _copy, \ > + .rotate = rbname ## _rotate \ > }; > > > @@ -126,11 +139,11 @@ __rb_change_child(struct rb_node *old, struct rb_node > *new, > { > if (parent) { > if (parent->rb_left == old) > - parent->rb_left = new; > + WRITE_ONCE(parent->rb_left, new); > else > - parent->rb_right = new; > + WRITE_ONCE(parent->rb_right, new); > } else > - root->rb_node = new; > + WRITE_ONCE(root->rb_node, new); > } > > extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root, > @@ -138,12 +151,17 @@ 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, *tmp = node->rb_left; > + struct rb_node *child = node->rb_right; > + struct rb_node *tmp = node->rb_left; > 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!) > @@ -170,6 +188,7 @@ __rb_erase_augmented(struct rb_node *node, struct rb_root > *root, > tmp = parent; > } else { > struct rb_node *successor = child, *child2; > + > tmp = child->rb_left; > if (!tmp) { > /* > @@ -183,6 +202,7 @@ __rb_erase_augmented(struct rb_node *node, struct rb_root > *root, > */ > parent = successor; > child2 = successor->rb_right; > + > augment->copy(node, successor); > } else { > /* > @@ -204,19 +224,23 @@ __rb_erase_augmented(struct rb_node *node, struct > rb_root *root, > successor = tmp; > tmp = tmp->rb_left; > } while (tmp); > - parent->rb_left = child2 = successor->rb_right; > - successor->rb_right = child; > + child2 = successor->rb_right; > + WRITE_ONCE(parent->rb_left, child2); > + WRITE_ONCE(successor->rb_right, child); > rb_set_parent(child, successor); > + > augment->copy(node, successor); > augment->propagate(parent, successor); > } > > - successor->rb_left = tmp = node->rb_left; > + tmp = node->rb_left; > + WRITE_ONCE(successor->rb_left, tmp); > rb_set_parent(tmp, successor); > > pc = node->__rb_parent_color; > tmp = __rb_parent(pc); > __rb_change_child(node, successor, tmp, root); > + > if (child2) { > successor->__rb_parent_color = pc; > rb_set_parent_color(child2, parent, RB_BLACK); > @@ -237,9 +261,21 @@ 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, augment); > + struct rb_node *rebalance = __rb_erase_augmented(node, root, > + NULL, augment); > if (rebalance) > __rb_erase_color(rebalance, root, augment->rotate); > } > > +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); > +} > + > #endif /* _TOOLS_LINUX_RBTREE_AUGMENTED_H */ > diff --git a/tools/lib/rbtree.c b/tools/lib/rbtree.c > index 17c2b596f043..a3bf68a3f1d4 100644 > --- a/tools/lib/rbtree.c > +++ b/tools/lib/rbtree.c > @@ -22,6 +22,7 @@ > */ > > #include <linux/rbtree_augmented.h> > +#include <linux/export.h> > > /* > * red-black trees properties: http://en.wikipedia.org/wiki/Rbtree > @@ -43,6 +44,30 @@ > * parentheses and have some accompanying text comment. > */ > > +/* > + * Notes on lockless lookups: > + * > + * All stores to the tree structure (rb_left and rb_right) must be done using > + * WRITE_ONCE(). And we must not inadvertently cause (temporary) loops in the > + * tree structure as seen in program order. > + * > + * These two requirements will allow lockless iteration of the tree -- not > + * correct iteration mind you, tree rotations are not atomic so a lookup > might > + * miss entire subtrees. > + * > + * But they do guarantee that any such traversal will only see valid elements > + * and that it will indeed complete -- does not get stuck in a loop. > + * > + * It also guarantees that if the lookup returns an element it is the > 'correct' > + * one. But not returning an element does _NOT_ mean it's not present. > + * > + * NOTE: > + * > + * Stores to __rb_parent_color are not important for simple lookups so those > + * are left undone as of now. Nor did I check for loops involving parent > + * pointers. > + */ > + > static inline void rb_set_black(struct rb_node *rb) > { > rb->__rb_parent_color |= RB_BLACK; > @@ -70,22 +95,35 @@ __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 > - * > - * If there is a black parent, we are done. > - * Otherwise, take some corrective action as we don't > - * want a red root or two consecutive red nodes. > + * Loop invariant: node is red. > */ > - if (!parent) { > + if (unlikely(!parent)) { > + /* > + * The inserted node is root. Either this is the > + * first node, or we recursed at Case 1 below and > + * are no longer violating 4). > + */ > rb_set_parent_color(node, NULL, RB_BLACK); > break; > - } else if (rb_is_black(parent)) > + } > + > + /* > + * If there is a black parent, we are done. > + * Otherwise, take some corrective action as, > + * per 4), we don't want a red root or two > + * consecutive red nodes. > + */ > + if(rb_is_black(parent)) > break; > > gparent = rb_red_parent(parent); > @@ -94,7 +132,7 @@ __rb_insert(struct rb_node *node, struct rb_root *root, > if (parent != tmp) { /* parent == gparent->rb_left */ > if (tmp && rb_is_red(tmp)) { > /* > - * Case 1 - color flips > + * Case 1 - node's uncle is red (color flips). > * > * G g > * / \ / \ > @@ -117,7 +155,8 @@ __rb_insert(struct rb_node *node, struct rb_root *root, > tmp = parent->rb_right; > if (node == tmp) { > /* > - * Case 2 - left rotate at parent > + * Case 2 - node's uncle is black and node is > + * the parent's right child (left rotate at > parent). > * > * G G > * / \ / \ > @@ -128,8 +167,9 @@ __rb_insert(struct rb_node *node, struct rb_root *root, > * This still leaves us in violation of 4), the > * continuation into Case 3 will fix that. > */ > - parent->rb_right = tmp = node->rb_left; > - node->rb_left = parent; > + tmp = node->rb_left; > + WRITE_ONCE(parent->rb_right, tmp); > + WRITE_ONCE(node->rb_left, parent); > if (tmp) > rb_set_parent_color(tmp, parent, > RB_BLACK); > @@ -140,7 +180,8 @@ __rb_insert(struct rb_node *node, struct rb_root *root, > } > > /* > - * Case 3 - right rotate at gparent > + * Case 3 - node's uncle is black and node is > + * the parent's left child (right rotate at gparent). > * > * G P > * / \ / \ > @@ -148,8 +189,8 @@ __rb_insert(struct rb_node *node, struct rb_root *root, > * / \ > * n U > */ > - gparent->rb_left = tmp; /* == parent->rb_right */ > - parent->rb_right = gparent; > + WRITE_ONCE(gparent->rb_left, tmp); /* == > parent->rb_right */ > + WRITE_ONCE(parent->rb_right, gparent); > if (tmp) > rb_set_parent_color(tmp, gparent, RB_BLACK); > __rb_rotate_set_parents(gparent, parent, root, RB_RED); > @@ -170,8 +211,9 @@ __rb_insert(struct rb_node *node, struct rb_root *root, > tmp = parent->rb_left; > if (node == tmp) { > /* Case 2 - right rotate at parent */ > - parent->rb_left = tmp = node->rb_right; > - node->rb_right = parent; > + tmp = node->rb_right; > + WRITE_ONCE(parent->rb_left, tmp); > + WRITE_ONCE(node->rb_right, parent); > if (tmp) > rb_set_parent_color(tmp, parent, > RB_BLACK); > @@ -182,8 +224,8 @@ __rb_insert(struct rb_node *node, struct rb_root *root, > } > > /* Case 3 - left rotate at gparent */ > - gparent->rb_right = tmp; /* == parent->rb_left */ > - parent->rb_left = gparent; > + WRITE_ONCE(gparent->rb_right, tmp); /* == > parent->rb_left */ > + WRITE_ONCE(parent->rb_left, gparent); > if (tmp) > rb_set_parent_color(tmp, gparent, RB_BLACK); > __rb_rotate_set_parents(gparent, parent, root, RB_RED); > @@ -223,8 +265,9 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root > *root, > * / \ / \ > * Sl Sr N Sl > */ > - parent->rb_right = tmp1 = sibling->rb_left; > - sibling->rb_left = parent; > + tmp1 = sibling->rb_left; > + WRITE_ONCE(parent->rb_right, tmp1); > + WRITE_ONCE(sibling->rb_left, parent); > rb_set_parent_color(tmp1, parent, RB_BLACK); > __rb_rotate_set_parents(parent, sibling, root, > RB_RED); > @@ -268,15 +311,31 @@ ____rb_erase_color(struct rb_node *parent, struct > rb_root *root, > * > * (p) (p) > * / \ / \ > - * N S --> N Sl > + * N S --> N sl > * / \ \ > - * sl Sr s > + * sl Sr S > * \ > * Sr > + * > + * Note: p might be red, and then both > + * p and sl are red after rotation(which > + * breaks property 4). This is fixed in > + * Case 4 (in __rb_rotate_set_parents() > + * which set sl the color of p > + * and set p RB_BLACK) > + * > + * (p) (sl) > + * / \ / \ > + * N sl --> P S > + * \ / \ > + * S N Sr > + * \ > + * Sr > */ > - sibling->rb_left = tmp1 = tmp2->rb_right; > - tmp2->rb_right = sibling; > - parent->rb_right = tmp2; > + tmp1 = tmp2->rb_right; > + WRITE_ONCE(sibling->rb_left, tmp1); > + WRITE_ONCE(tmp2->rb_right, sibling); > + WRITE_ONCE(parent->rb_right, tmp2); > if (tmp1) > rb_set_parent_color(tmp1, sibling, > RB_BLACK); > @@ -296,8 +355,9 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root > *root, > * / \ / \ > * (sl) sr N (sl) > */ > - parent->rb_right = tmp2 = sibling->rb_left; > - sibling->rb_left = parent; > + tmp2 = sibling->rb_left; > + WRITE_ONCE(parent->rb_right, tmp2); > + WRITE_ONCE(sibling->rb_left, parent); > rb_set_parent_color(tmp1, sibling, RB_BLACK); > if (tmp2) > rb_set_parent(tmp2, parent); > @@ -309,8 +369,9 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root > *root, > sibling = parent->rb_left; > if (rb_is_red(sibling)) { > /* Case 1 - right rotate at parent */ > - parent->rb_left = tmp1 = sibling->rb_right; > - sibling->rb_right = parent; > + tmp1 = sibling->rb_right; > + WRITE_ONCE(parent->rb_left, tmp1); > + WRITE_ONCE(sibling->rb_right, parent); > rb_set_parent_color(tmp1, parent, RB_BLACK); > __rb_rotate_set_parents(parent, sibling, root, > RB_RED); > @@ -334,10 +395,11 @@ ____rb_erase_color(struct rb_node *parent, struct > rb_root *root, > } > break; > } > - /* Case 3 - right rotate at sibling */ > - sibling->rb_right = tmp1 = tmp2->rb_left; > - tmp2->rb_left = sibling; > - parent->rb_left = tmp2; > + /* Case 3 - left rotate at sibling */ > + tmp1 = tmp2->rb_left; > + WRITE_ONCE(sibling->rb_right, tmp1); > + WRITE_ONCE(tmp2->rb_left, sibling); > + WRITE_ONCE(parent->rb_left, tmp2); > if (tmp1) > rb_set_parent_color(tmp1, sibling, > RB_BLACK); > @@ -345,9 +407,10 @@ ____rb_erase_color(struct rb_node *parent, struct > rb_root *root, > tmp1 = sibling; > sibling = tmp2; > } > - /* Case 4 - left rotate at parent + color flips */ > - parent->rb_left = tmp2 = sibling->rb_right; > - sibling->rb_right = parent; > + /* Case 4 - right rotate at parent + color flips */ > + tmp2 = sibling->rb_right; > + WRITE_ONCE(parent->rb_left, tmp2); > + WRITE_ONCE(sibling->rb_right, parent); > rb_set_parent_color(tmp1, sibling, RB_BLACK); > if (tmp2) > rb_set_parent(tmp2, parent); > @@ -365,6 +428,7 @@ void __rb_erase_color(struct rb_node *parent, struct > rb_root *root, > { > ____rb_erase_color(parent, root, augment_rotate); > } > +EXPORT_SYMBOL(__rb_erase_color); > > /* > * Non-augmented rbtree manipulation functions. > @@ -378,21 +442,44 @@ static inline void dummy_copy(struct rb_node *old, > struct rb_node *new) {} > static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {} > > static const struct rb_augment_callbacks dummy_callbacks = { > - dummy_propagate, dummy_copy, dummy_rotate > + .propagate = dummy_propagate, > + .copy = dummy_copy, > + .rotate = dummy_rotate > }; > > void rb_insert_color(struct rb_node *node, struct rb_root *root) > { > - __rb_insert(node, root, dummy_rotate); > + __rb_insert(node, root, false, NULL, 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, &dummy_callbacks); > + rebalance = __rb_erase_augmented(node, root, > + NULL, &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. > @@ -402,10 +489,12 @@ void rb_erase(struct rb_node *node, struct rb_root > *root) > */ > > 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, augment_rotate); > + __rb_insert(node, root, newleft, leftmost, augment_rotate); > } > +EXPORT_SYMBOL(__rb_insert_augmented); > > /* > * This function returns the first node (in sort order) of the tree. > @@ -421,6 +510,7 @@ struct rb_node *rb_first(const struct rb_root *root) > n = n->rb_left; > return n; > } > +EXPORT_SYMBOL(rb_first); > > struct rb_node *rb_last(const struct rb_root *root) > { > @@ -433,6 +523,7 @@ struct rb_node *rb_last(const struct rb_root *root) > n = n->rb_right; > return n; > } > +EXPORT_SYMBOL(rb_last); > > struct rb_node *rb_next(const struct rb_node *node) > { > @@ -464,6 +555,7 @@ struct rb_node *rb_next(const struct rb_node *node) > > return parent; > } > +EXPORT_SYMBOL(rb_next); > > struct rb_node *rb_prev(const struct rb_node *node) > { > @@ -492,22 +584,24 @@ struct rb_node *rb_prev(const struct rb_node *node) > > return parent; > } > +EXPORT_SYMBOL(rb_prev); > > void rb_replace_node(struct rb_node *victim, struct rb_node *new, > struct rb_root *root) > { > struct rb_node *parent = rb_parent(victim); > > + /* Copy the pointers/colour from the victim to the replacement */ > + *new = *victim; > + > /* Set the surrounding nodes to point to the replacement */ > - __rb_change_child(victim, new, parent, root); > if (victim->rb_left) > rb_set_parent(victim->rb_left, new); > if (victim->rb_right) > rb_set_parent(victim->rb_right, new); > - > - /* Copy the pointers/colour from the victim to the replacement */ > - *new = *victim; > + __rb_change_child(victim, new, parent, root); > } > +EXPORT_SYMBOL(rb_replace_node); > > static struct rb_node *rb_left_deepest_node(const struct rb_node *node) > { > @@ -538,6 +632,7 @@ struct rb_node *rb_next_postorder(const struct rb_node > *node) > * should be next */ > return (struct rb_node *)parent; > } > +EXPORT_SYMBOL(rb_next_postorder); > > struct rb_node *rb_first_postorder(const struct rb_root *root) > { > @@ -546,3 +641,4 @@ struct rb_node *rb_first_postorder(const struct rb_root > *root) > > return rb_left_deepest_node(root->rb_node); > } > +EXPORT_SYMBOL(rb_first_postorder); >