diff options
Diffstat (limited to 'include/rbtree.h')
| -rw-r--r-- | include/rbtree.h | 49 |
1 files changed, 40 insertions, 9 deletions
diff --git a/include/rbtree.h b/include/rbtree.h index f0ffb914..8ccd129c 100644 --- a/include/rbtree.h +++ b/include/rbtree.h @@ -1,6 +1,6 @@ /* ----------------------------------------------------------------------- * - * - * Copyright 1996-2009 The NASM Authors - All Rights Reserved + * + * Copyright 1996-2020 The NASM Authors - All Rights Reserved * See the file AUTHORS included with the NASM distribution for * the specific copyright holders. * @@ -14,7 +14,7 @@ * copyright notice, this list of conditions and the following * disclaimer in the documentation and/or other materials provided * with the distribution. - * + * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF @@ -36,16 +36,47 @@ #include "compiler.h" -/* This structure should be embedded in a larger data structure; - the final output from rb_search() can then be converted back - to the larger data structure via container_of(). */ +/* + * This structure should be embedded in a larger data structure; + * the final output from rb_search() can then be converted back + * to the larger data structure via container_of(). + * + * An empty tree is simply represented by a NULL pointer. + */ + +/* Note: the values of these flags is significant */ +enum rbtree_node_flags { + RBTREE_NODE_BLACK = 1, /* Node color is black */ + RBTREE_NODE_PRED = 2, /* Left pointer is an uplink */ + RBTREE_NODE_SUCC = 4 /* Right pointer is an uplink */ +}; + struct rbtree { uint64_t key; - struct rbtree *left, *right; - bool red; + struct rbtree_metadata { + struct rbtree *left, *right; + enum rbtree_node_flags flags; + } m; }; +/* + * Add a node to a tree. Returns the new root pointer. + * The key value in the structure needs to be preinitialized; + * the rest of the structure should be zero. + */ struct rbtree *rb_insert(struct rbtree *, struct rbtree *); -struct rbtree *rb_search(struct rbtree *, uint64_t); + +/* + * Find a node in the tree corresponding to the key immediately + * <= the passed-in key value. + */ +struct rbtree *rb_search(const struct rbtree *, uint64_t); + +/* + * Return the immediately previous or next node in key order. + * Returns NULL if this node is the end of the + */ +struct rbtree *rb_prev(const struct rbtree *); +struct rbtree *rb_next(const struct rbtree *); #endif /* NASM_RBTREE_H */ |