From 8159c340914c6616e470e1fd4a27ac85aec69db6 Mon Sep 17 00:00:00 2001 From: stevenj Date: Tue, 11 Sep 2007 18:43:07 -0400 Subject: [PATCH] added rb_tree_find_lt darcs-hash:20070911224307-c8de0-cbaa8a1784b3d5cf99c76a95ee8abb10463648cc.gz --- util/redblack.c | 22 ++++++++++++++++++++++ util/redblack.h | 1 + 2 files changed, 23 insertions(+) diff --git a/util/redblack.c b/util/redblack.c index 4fb4a4d..5ec2ffd 100644 --- a/util/redblack.c +++ b/util/redblack.c @@ -211,6 +211,28 @@ rb_node *rb_tree_find_le(rb_tree *t, rb_key k) return find_le(t->root, k, t); } +/* find greatest point in subtree p that is < k */ +static rb_node *find_lt(rb_node *p, rb_key k, rb_tree *t) +{ + rb_compare compare = t->compare; + while (p != NIL) { + if (compare(p->k, k) < 0) { /* p->k < k */ + rb_node *r = find_lt(p->r, k, t); + if (r) return r; + else return p; + } + else /* p->k >= k */ + p = p->l; + } + return NULL; /* k <= everything in subtree */ +} + +/* find greatest point in t < k */ +rb_node *rb_tree_find_lt(rb_tree *t, rb_key k) +{ + return find_lt(t->root, k, t); +} + /* find least point in subtree p that is > k */ static rb_node *find_gt(rb_node *p, rb_key k, rb_tree *t) { diff --git a/util/redblack.h b/util/redblack.h index d428d64..60fde3d 100644 --- a/util/redblack.h +++ b/util/redblack.h @@ -34,6 +34,7 @@ extern rb_node *rb_tree_insert(rb_tree *t, rb_key k); extern int rb_tree_check(rb_tree *t); extern rb_node *rb_tree_find(rb_tree *t, rb_key k); extern rb_node *rb_tree_find_le(rb_tree *t, rb_key k); +extern rb_node *rb_tree_find_lt(rb_tree *t, rb_key k); extern rb_node *rb_tree_find_gt(rb_tree *t, rb_key k); extern rb_node *rb_tree_resort(rb_tree *t, rb_node *n); extern rb_node *rb_tree_min(rb_tree *t); -- 2.30.2