X-Git-Url: https://gerrit.fd.io/r/gitweb?a=blobdiff_plain;f=src%2Fvppinfra%2Frbtree.c;h=f7383cb1d1b6633137e1088455d688225de2e71c;hb=f22f4e562e1b922cff036ef628b77fd2d479d015;hp=d99367a2c6fb5b40f509b3010746075fee0788db;hpb=672d5fc6d36ebc3a3815c4658a8ef3bf256ef044;p=vpp.git

diff --git a/src/vppinfra/rbtree.c b/src/vppinfra/rbtree.c
index d99367a2c6f..f7383cb1d1b 100644
--- a/src/vppinfra/rbtree.c
+++ b/src/vppinfra/rbtree.c
@@ -20,24 +20,6 @@
 
 #include <vppinfra/rbtree.h>
 
-static inline rb_node_t *
-rb_node_right (rb_tree_t * rt, rb_node_t * n)
-{
-  return pool_elt_at_index (rt->nodes, n->right);
-}
-
-static inline rb_node_t *
-rb_node_left (rb_tree_t * rt, rb_node_t * n)
-{
-  return pool_elt_at_index (rt->nodes, n->left);
-}
-
-static inline rb_node_t *
-rb_node_parent (rb_tree_t * rt, rb_node_t * n)
-{
-  return pool_elt_at_index (rt->nodes, n->parent);
-}
-
 static inline void
 rb_tree_rotate_left (rb_tree_t * rt, rb_node_t * x)
 {
@@ -92,32 +74,12 @@ rb_tree_rotate_right (rb_tree_t * rt, rb_node_t * y)
   y->parent = xi;
 }
 
-static void
-rb_tree_insert (rb_tree_t * rt, rb_node_t * z)
+static inline void
+rb_tree_fixup_inline (rb_tree_t * rt, rb_node_t * y, rb_node_t * z)
 {
-  rb_node_index_t yi = 0, xi = rt->root, zi;
-  rb_node_t *y, *zpp, *x, *zp;
+  rb_node_t *zpp, *zp;
+  rb_node_index_t zi;
 
-  y = rb_node (rt, RBTREE_TNIL_INDEX);
-  while (xi != RBTREE_TNIL_INDEX)
-    {
-      x = rb_node (rt, xi);
-      y = x;
-      if (z->key < x->key)
-	xi = x->left;
-      else
-	xi = x->right;
-    }
-  yi = rb_node_index (rt, y);
-  z->parent = yi;
-  if (yi == RBTREE_TNIL_INDEX)
-    rt->root = rb_node_index (rt, z);
-  else if (z->key < y->key)
-    y->left = rb_node_index (rt, z);
-  else
-    y->right = rb_node_index (rt, z);
-
-  /* Tree fixup stage */
   while (y->color == RBTREE_RED)
     {
       zi = rb_node_index (rt, z);
@@ -175,6 +137,35 @@ rb_tree_insert (rb_tree_t * rt, rb_node_t * z)
   rb_node (rt, rt->root)->color = RBTREE_BLACK;
 }
 
+static void
+rb_tree_insert (rb_tree_t * rt, rb_node_t * z)
+{
+  rb_node_index_t yi = 0, xi = rt->root;
+  rb_node_t *y, *x;
+
+  y = rb_node (rt, RBTREE_TNIL_INDEX);
+  while (xi != RBTREE_TNIL_INDEX)
+    {
+      x = rb_node (rt, xi);
+      y = x;
+      if (z->key < x->key)
+	xi = x->left;
+      else
+	xi = x->right;
+    }
+  yi = rb_node_index (rt, y);
+  z->parent = yi;
+  if (yi == RBTREE_TNIL_INDEX)
+    rt->root = rb_node_index (rt, z);
+  else if (z->key < y->key)
+    y->left = rb_node_index (rt, z);
+  else
+    y->right = rb_node_index (rt, z);
+
+  /* Tree fixup stage */
+  rb_tree_fixup_inline (rt, y, z);
+}
+
 rb_node_index_t
 rb_tree_add (rb_tree_t * rt, u32 key)
 {
@@ -188,7 +179,7 @@ rb_tree_add (rb_tree_t * rt, u32 key)
 }
 
 rb_node_index_t
-rb_tree_add2 (rb_tree_t * rt, u32 key, u32 opaque)
+rb_tree_add2 (rb_tree_t * rt, u32 key, uword opaque)
 {
   rb_node_t *n;
 
@@ -200,6 +191,42 @@ rb_tree_add2 (rb_tree_t * rt, u32 key, u32 opaque)
   return rb_node_index (rt, n);
 }
 
+rb_node_index_t
+rb_tree_add_custom (rb_tree_t * rt, u32 key, uword opaque, rb_tree_lt_fn ltfn)
+{
+  rb_node_index_t yi = 0, xi = rt->root;
+  rb_node_t *z, *y, *x;
+
+  pool_get_zero (rt->nodes, z);
+  z->key = key;
+  z->color = RBTREE_RED;
+  z->opaque = opaque;
+
+  y = rb_node (rt, RBTREE_TNIL_INDEX);
+  while (xi != RBTREE_TNIL_INDEX)
+    {
+      x = rb_node (rt, xi);
+      y = x;
+      ASSERT (z->key != x->key);
+      if (ltfn (z->key, x->key))
+	xi = x->left;
+      else
+	xi = x->right;
+    }
+  yi = rb_node_index (rt, y);
+  z->parent = yi;
+  if (yi == RBTREE_TNIL_INDEX)
+    rt->root = rb_node_index (rt, z);
+  else if (ltfn (z->key, y->key))
+    y->left = rb_node_index (rt, z);
+  else
+    y->right = rb_node_index (rt, z);
+
+  rb_tree_fixup_inline (rt, y, z);
+
+  return rb_node_index (rt, z);
+}
+
 rb_node_t *
 rb_tree_search_subtree (rb_tree_t * rt, rb_node_t * x, u32 key)
 {
@@ -211,6 +238,18 @@ rb_tree_search_subtree (rb_tree_t * rt, rb_node_t * x, u32 key)
   return x;
 }
 
+rb_node_t *
+rb_tree_search_subtree_custom (rb_tree_t * rt, rb_node_t * x, u32 key,
+			       rb_tree_lt_fn ltfn)
+{
+  while (rb_node_index (rt, x) != RBTREE_TNIL_INDEX && key != x->key)
+    if (ltfn (key, x->key))
+      x = rb_node_left (rt, x);
+    else
+      x = rb_node_right (rt, x);
+  return x;
+}
+
 rb_node_t *
 rb_tree_min_subtree (rb_tree_t * rt, rb_node_t * x)
 {
@@ -227,6 +266,40 @@ rb_tree_max_subtree (rb_tree_t * rt, rb_node_t * x)
   return x;
 }
 
+rb_node_t *
+rb_tree_successor (rb_tree_t * rt, rb_node_t * x)
+{
+  rb_node_t *y;
+
+  if (x->right != RBTREE_TNIL_INDEX)
+    return rb_tree_min_subtree (rt, rb_node_right (rt, x));
+
+  y = rb_node_parent (rt, x);
+  while (!rb_node_is_tnil (rt, y) && y->right == rb_node_index (rt, x))
+    {
+      x = y;
+      y = rb_node_parent (rt, y);
+    }
+  return y;
+}
+
+rb_node_t *
+rb_tree_predecessor (rb_tree_t * rt, rb_node_t * x)
+{
+  rb_node_t *y;
+
+  if (x->left != RBTREE_TNIL_INDEX)
+    return rb_tree_max_subtree (rt, rb_node_left (rt, x));
+
+  y = rb_node_parent (rt, x);
+  while (!rb_node_is_tnil (rt, y) && y->left == rb_node_index (rt, x))
+    {
+      x = y;
+      y = rb_node_parent (rt, y);
+    }
+  return y;
+}
+
 static inline void
 rb_tree_transplant (rb_tree_t * rt, rb_node_t * u, rb_node_t * v)
 {
@@ -242,8 +315,8 @@ rb_tree_transplant (rb_tree_t * rt, rb_node_t * u, rb_node_t * v)
   v->parent = u->parent;
 }
 
-void
-rb_tree_del_node (rb_tree_t * rt, rb_node_t * z)
+static void
+rb_tree_del_node_internal (rb_tree_t * rt, rb_node_t * z)
 {
   rb_node_color_t y_original_color;
   rb_node_t *x, *y, *yr, *yl, *xp, *w, *wl, *wr;
@@ -272,7 +345,7 @@ rb_tree_del_node (rb_tree_t * rt, rb_node_t * z)
 	x->parent = yi;
       else
 	{
-	  rb_tree_transplant (rt, y, rb_node_right (rt, y));
+	  rb_tree_transplant (rt, y, x);
 	  y->right = z->right;
 	  yr = rb_node_right (rt, y);
 	  yr->parent = yi;
@@ -307,7 +380,8 @@ rb_tree_del_node (rb_tree_t * rt, rb_node_t * z)
 	  wr = rb_node_right (rt, w);
 	  if (wl->color == RBTREE_BLACK && wr->color == RBTREE_BLACK)
 	    {
-	      w->color = RBTREE_RED;
+	      if (!rb_node_is_tnil (rt, w))
+		w->color = RBTREE_RED;
 	      x = xp;
 	    }
 	  else
@@ -318,6 +392,7 @@ rb_tree_del_node (rb_tree_t * rt, rb_node_t * z)
 		  w->color = RBTREE_RED;
 		  rb_tree_rotate_right (rt, w);
 		  w = rb_node_right (rt, xp);
+		  wr = rb_node_right (rt, w);
 		}
 	      w->color = xp->color;
 	      xp->color = RBTREE_BLACK;
@@ -340,7 +415,8 @@ rb_tree_del_node (rb_tree_t * rt, rb_node_t * z)
 	  wr = rb_node_right (rt, w);
 	  if (wl->color == RBTREE_BLACK && wr->color == RBTREE_BLACK)
 	    {
-	      w->color = RBTREE_RED;
+	      if (!rb_node_is_tnil (rt, w))
+		w->color = RBTREE_RED;
 	      x = xp;
 	    }
 	  else
@@ -351,6 +427,7 @@ rb_tree_del_node (rb_tree_t * rt, rb_node_t * z)
 		  w->color = RBTREE_RED;
 		  rb_tree_rotate_left (rt, w);
 		  w = rb_node_left (rt, xp);
+		  wl = rb_node_left (rt, w);
 		}
 	      w->color = xp->color;
 	      xp->color = RBTREE_BLACK;
@@ -364,16 +441,29 @@ rb_tree_del_node (rb_tree_t * rt, rb_node_t * z)
   x->color = RBTREE_BLACK;
 }
 
+void
+rb_tree_del_node (rb_tree_t * rt, rb_node_t * z)
+{
+  rb_tree_del_node_internal (rt, z);
+  pool_put (rt->nodes, z);
+}
+
 void
 rb_tree_del (rb_tree_t * rt, u32 key)
 {
   rb_node_t *n;
   n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), key);
   if (rb_node_index (rt, n) != RBTREE_TNIL_INDEX)
-    {
-      rb_tree_del_node (rt, n);
-      pool_put (rt->nodes, n);
-    }
+    rb_tree_del_node (rt, n);
+}
+
+void
+rb_tree_del_custom (rb_tree_t * rt, u32 key, rb_tree_lt_fn ltfn)
+{
+  rb_node_t *n;
+  n = rb_tree_search_subtree_custom (rt, rb_node (rt, rt->root), key, ltfn);
+  if (rb_node_index (rt, n) != RBTREE_TNIL_INDEX)
+    rb_tree_del_node (rt, n);
 }
 
 u32
@@ -385,8 +475,8 @@ rb_tree_n_nodes (rb_tree_t * rt)
 void
 rb_tree_free_nodes (rb_tree_t * rt)
 {
-  rb_node_t *n;
-  pool_flush (n, rt->nodes,;);
+  pool_free (rt->nodes);
+  rt->root = RBTREE_TNIL_INDEX;
 }
 
 void
@@ -402,6 +492,14 @@ rb_tree_init (rb_tree_t * rt)
   tnil->color = RBTREE_BLACK;
 }
 
+int
+rb_tree_is_init (rb_tree_t * rt)
+{
+  if (pool_elts (rt->nodes) == 0)
+    return 0;
+  return 1;
+}
+
 /*
  * fd.io coding-style-patch-verification: ON
  *