From c341ad7300afa3f71db5cd9813bbeebf32f9195b Mon Sep 17 00:00:00 2001 From: "H. Peter Anvin (Intel)" Date: Wed, 8 Jul 2020 08:56:03 -0700 Subject: rbtree: implement rb_first(), rb_last() operations Add operations to get the first and last entry in the tree, respectively. Searching for 0 or ~UINT64_C(0) is not sufficient in the presence of duplicated keys, and is more inefficient anyway. rb_first() followed by rb_next() until NULL, or equivalently rb_last() followed by rb_prev() until NULL, can be used to walk the tree in key order (ascending or descending), including all duplicate key entries. Since this is a *threaded* tree now, this walk can safely free entires as it goes along, as long as the whole tree is destroyed; once any one entry has been freed, the tree is no longer valid for anything other than proceeding with the same tree walk. Signed-off-by: H. Peter Anvin (Intel) --- nasmlib/rbtree.c | 36 ++++++++++++++++++++++++++---------- 1 file changed, 26 insertions(+), 10 deletions(-) (limited to 'nasmlib') diff --git a/nasmlib/rbtree.c b/nasmlib/rbtree.c index 8b74c0c4..510f34b1 100644 --- a/nasmlib/rbtree.c +++ b/nasmlib/rbtree.c @@ -208,17 +208,36 @@ _rb_insert(struct rbtree *tree, struct rbtree *node) return tree; } +struct rbtree *rb_first(const struct rbtree *tree) +{ + if (unlikely(!tree)) + return NULL; + + while (!(tree->m.flags & RBTREE_NODE_PRED)) + tree = tree->m.left; + + return (struct rbtree *)tree; +} + +struct rbtree *rb_last(const struct rbtree *tree) +{ + if (unlikely(!tree)) + return NULL; + + while (!(tree->m.flags & RBTREE_NODE_SUCC)) + tree = tree->m.right; + + return (struct rbtree *)tree; +} + struct rbtree *rb_prev(const struct rbtree *node) { struct rbtree *np = node->m.left; if (node->m.flags & RBTREE_NODE_PRED) return np; - - while (!(np->m.flags & RBTREE_NODE_SUCC)) - np = np->m.right; - - return np; + else + return rb_last(np); } struct rbtree *rb_next(const struct rbtree *node) @@ -227,9 +246,6 @@ struct rbtree *rb_next(const struct rbtree *node) if (node->m.flags & RBTREE_NODE_SUCC) return np; - - while (!(np->m.flags & RBTREE_NODE_PRED)) - np = np->m.left; - - return np; + else + return rb_first(np); } -- cgit v1.2.1