1 files changed, 29 insertions, 5 deletions

diff --git a/lib/rbtree.c b/lib/rbtree.c
index 4ba2828a67c0..d102d9d2ffaa 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -95,10 +95,14 @@ __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
@@ -434,19 +438,38 @@ static const struct rb_augment_callbacks dummy_callbacks = {
 
 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.
  *
@@ -455,9 +478,10 @@ EXPORT_SYMBOL(rb_erase);
  */
 
 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);
 
@@ -502,7 +526,7 @@ struct rb_node *rb_next(const struct rb_node *node)
          * as we can.
          */
         if (node->rb_right) {
-                node = node->rb_right; 
+                node = node->rb_right;
                 while (node->rb_left)
                         node=node->rb_left;
                 return (struct rb_node *)node;
@@ -534,7 +558,7 @@ struct rb_node *rb_prev(const struct rb_node *node)
          * as we can.
          */
         if (node->rb_left) {
-                node = node->rb_left; 
+                node = node->rb_left;
                 while (node->rb_right)
                         node=node->rb_right;
                 return (struct rb_node *)node;