Add missing inequality searches to rbtree

PostgreSQL contains the implementation of the red-black tree.  The red-black
tree is the ordered data structure, and one of its advantages is the ability
to do inequality searches.  This commit adds rbt_find_less() and
rbt_find_great() functions implementing these searches.  While these searches
aren't yet used in the core code, they might be useful for extensions.

Discussion: https://postgr.es/m/CAGRrpzYE8-7GCoaPjOiL9T_HY605MRax-2jgTtLq236uksZ1Sw%40mail.gmail.com
Author: Steve Chavez, Alexander Korotkov
Reviewed-by: Alexander Korotkov

1 files changed, 62 insertions, 0 deletions

diff --git a/src/backend/lib/rbtree.c b/src/backend/lib/rbtree.c
index e1cc4110bd4..427cec1ada8 100644
--- a/src/backend/lib/rbtree.c
+++ b/src/backend/lib/rbtree.c
@@ -162,6 +162,68 @@ rbt_find(RBTree *rbt, const RBTNode *data)
 }
 
 /*
+ * rbt_find_great: search for a greater value in an RBTree
+ *
+ * If equal_match is true, this will be a great or equal search.
+ *
+ * Returns the matching tree entry, or NULL if no match is found.
+ */
+RBTNode *
+rbt_find_great(RBTree *rbt, const RBTNode *data, bool equal_match)
+{
+	RBTNode    *node = rbt->root;
+	RBTNode    *greater = NULL;
+
+	while (node != RBTNIL)
+	{
+		int			cmp = rbt->comparator(data, node, rbt->arg);
+
+		if (equal_match && cmp == 0)
+			return node;
+		else if (cmp < 0)
+		{
+			greater = node;
+			node = node->left;
+		}
+		else
+			node = node->right;
+	}
+
+	return greater;
+}
+
+/*
+ * rbt_find_less: search for a lesser value in an RBTree
+ *
+ * If equal_match is true, this will be a less or equal search.
+ *
+ * Returns the matching tree entry, or NULL if no match is found.
+ */
+RBTNode *
+rbt_find_less(RBTree *rbt, const RBTNode *data, bool equal_match)
+{
+	RBTNode    *node = rbt->root;
+	RBTNode    *lesser = NULL;
+
+	while (node != RBTNIL)
+	{
+		int			cmp = rbt->comparator(data, node, rbt->arg);
+
+		if (equal_match && cmp == 0)
+			return node;
+		else if (cmp > 0)
+		{
+			lesser = node;
+			node = node->right;
+		}
+		else
+			node = node->left;
+	}
+
+	return lesser;
+}
+
+/*
  * rbt_leftmost: fetch the leftmost (smallest-valued) tree node.
  * Returns NULL if tree is empty.
  *