From f7cda7a9bc399258959084154263c42c5a91e030 Mon Sep 17 00:00:00 2001
From: Florin Coras <fcoras@cisco.com>
Date: Fri, 19 Apr 2019 18:50:34 -0700
Subject: rbtree: add successor and predecessor functions

Change-Id: I6934beaf5c08bae2d4f0bd3a6bb811810407c1f9
Signed-off-by: Florin Coras <fcoras@cisco.com>
---
 src/vppinfra/rbtree.c | 34 ++++++++++++++++++++++++++++++++++
 src/vppinfra/rbtree.h |  2 ++
 2 files changed, 36 insertions(+)

(limited to 'src/vppinfra')

diff --git a/src/vppinfra/rbtree.c b/src/vppinfra/rbtree.c
index d99367a2c6f..3770c2304ff 100644
--- a/src/vppinfra/rbtree.c
+++ b/src/vppinfra/rbtree.c
@@ -227,6 +227,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)
 {
diff --git a/src/vppinfra/rbtree.h b/src/vppinfra/rbtree.h
index ace07ac5622..73180d1d54c 100644
--- a/src/vppinfra/rbtree.h
+++ b/src/vppinfra/rbtree.h
@@ -54,6 +54,8 @@ u32 rb_tree_n_nodes (rb_tree_t * rt);
 rb_node_t *rb_tree_min_subtree (rb_tree_t * rt, rb_node_t * x);
 rb_node_t *rb_tree_max_subtree (rb_tree_t * rt, rb_node_t * x);
 rb_node_t *rb_tree_search_subtree (rb_tree_t * rt, rb_node_t * x, u32 key);
+rb_node_t *rb_tree_successor (rb_tree_t * rt, rb_node_t * x);
+rb_node_t *rb_tree_predecessor (rb_tree_t * rt, rb_node_t * x);
 
 static inline rb_node_index_t
 rb_node_index (rb_tree_t * rt, rb_node_t * n)
-- 
cgit 1.2.3-korg