diff options
| author | David Lamparter <equinox@opensourcerouting.org> | 2022-03-09 14:26:05 +0100 |
|---|---|---|
| committer | David Lamparter <equinox@opensourcerouting.org> | 2022-03-12 13:23:36 +0100 |
| commit | 643ea83be2997d3c77ab53e2c2a8f5b87fbac64a (patch) | |
| tree | b2e37163a9daefa6309f2935df49e2715c3909ca /lib/typerb.c | |
| parent | 9d888674b2d2009e0f749c449a2a94a834d0160d (diff) | |
lib: add `_last` and `_prev` on typesafe RB/DLIST
RB-tree and double-linked-list easily support backwards iteration, and
an use case seems to have popped up. Let's make it accessible.
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
Diffstat (limited to 'lib/typerb.c')
| -rw-r--r-- | lib/typerb.c | 35 |
1 files changed, 35 insertions, 0 deletions
diff --git a/lib/typerb.c b/lib/typerb.c index e1346df191..fe142ff354 100644 --- a/lib/typerb.c +++ b/lib/typerb.c @@ -468,6 +468,28 @@ struct rb_entry *typed_rb_next(const struct rb_entry *rbe_const) return rbe; } +struct rb_entry *typed_rb_prev(const struct rb_entry *rbe_const) +{ + struct rb_entry *rbe = (struct rb_entry *)rbe_const; + + if (RBE_LEFT(rbe)) { + rbe = RBE_LEFT(rbe); + while (RBE_RIGHT(rbe)) + rbe = RBE_RIGHT(rbe); + } else { + if (RBE_PARENT(rbe) && (rbe == RBE_RIGHT(RBE_PARENT(rbe)))) + rbe = RBE_PARENT(rbe); + else { + while (RBE_PARENT(rbe) + && (rbe == RBE_LEFT(RBE_PARENT(rbe)))) + rbe = RBE_PARENT(rbe); + rbe = RBE_PARENT(rbe); + } + } + + return rbe; +} + struct rb_entry *typed_rb_min(const struct rbt_tree *rbt) { struct rb_entry *rbe = RBH_ROOT(rbt); @@ -481,6 +503,19 @@ struct rb_entry *typed_rb_min(const struct rbt_tree *rbt) return parent; } +struct rb_entry *typed_rb_max(const struct rbt_tree *rbt) +{ + struct rb_entry *rbe = RBH_ROOT(rbt); + struct rb_entry *parent = NULL; + + while (rbe != NULL) { + parent = rbe; + rbe = RBE_RIGHT(rbe); + } + + return parent; +} + bool typed_rb_member(const struct typed_rb_root *rbt, const struct typed_rb_entry *rbe) { |