c-rbtree.h revision a0e4cae82065edae47885614d73c534171aa8f7b
#pragma once
/***
This file is part of systemd. See COPYING for details.
under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation; either version 2.1 of the License, or
(at your option) any later version.
systemd is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public License
along with systemd; If not, see <http://www.gnu.org/licenses/>.
***/
/*
* Standalone Red-Black-Tree Implementation in Standard ISO-C11
*
* This header provides an RB-Tree API, that is fully implemented in ISO-C11
* and has no external dependencies. Furthermore, tree traversal, memory
* allocations, and key comparisons a fully in control of the API user. The
* implementation only provides the RB-Tree specific rebalancing and coloring.
*
* A tree is represented by the "CRBTree" structure. It contains a *singly*
* field, which is a pointer to the root node. If NULL, the tree is empty. If
* non-NULL, there is at least a single element in the tree.
*
* Each node of the tree is represented by the "CRBNode" structure. It has
* three fields. The @left and @right members can be accessed by the API user
* directly to traverse the tree. The third member is an implementation detail
* and encodes the parent pointer and color of the node.
* API users are required to embed the CRBNode object into their own objects
* and then use offsetof() (i.e., container_of() and friends) to turn CRBNode
* pointers into pointers to their own structure.
*/
#ifdef __cplusplus
extern "C" {
#endif
/**
* struct CRBNode - Node of a Red-Black Tree
* @__parent_and_color: internal state
* @left: left child, or NULL
* @right: right child, or NULL
*
* Each node in an RB-Tree must embed an CRBNode object. This object contains
* pointers to its left and right child, which can be freely accessed by the
* child.
*
* The @__parent_and_color field must never be accessed directly. It encodes
* the pointer to the parent node, and the color of the node. Use the accessor
* functions instead.
*
* There is no reason to initialize a CRBNode object before linking it.
* However, if you need a boolean state that tells you whether the node is
* linked or not, you should initialize the node via c_rbnode_init() or
* C_RBNODE_INIT.
*/
struct CRBNode {
};
/**
* struct CRBTree - Red-Black Tree
* @root: pointer to the root node, or NULL
*
* Each Red-Black Tree is rooted in an CRBTree object. This object contains a
* pointer to the root node of the tree. The API user is free to access the
* @root member at any time, and use it to traverse the tree.
*
* To initialize an RB-Tree, set it to NULL / all zero.
*/
struct CRBTree {
};
/**
* c_rbnode_init() - mark a node as unlinked
* @n: node to operate on
*
* This marks the node @n as unlinked. The node will be set to a valid state
* that can never happen if the node is linked in a tree. Furthermore, this
* state is fully known to the implementation, and as such handled gracefully
* in all cases.
*
* You are *NOT* required to call this on your node. c_rbtree_add() can handle
* uninitialized nodes just fine. However, calling this allows to use
* c_rbnode_is_linked() to check for the state of a node. Furthermore,
* iterators and accessors can be called on initialized (yet unlinked) nodes.
*
* Use the C_RBNODE_INIT macro if you want to initialize static variables.
*/
static inline void c_rbnode_init(CRBNode *n) {
*n = (CRBNode)C_RBNODE_INIT(*n);
}
/**
* c_rbnode_is_linked() - check whether a node is linked
* @n: node to check, or NULL
*
* This checks whether the passed node is linked. If you pass NULL, or if the
* node is not linked into a tree, this will return false. Otherwise, this
* returns true.
*
* Note that you must have either linked the node or initialized it, before
* calling this function. Never call this function on uninitialized nodes.
* Furthermore, removing a node via c_rbtree_remove() does *NOT* mark the node
* as unlinked. You have to call c_rbnode_init() yourself after removal, or use
* the c_rbtree_remove_init() helper.
*
* Return: true if the node is linked, false if not.
*/
static inline _Bool c_rbnode_is_linked(CRBNode *n) {
return n && n->__parent_and_color != n;
}
/**
* c_rbnode_parent() - return parent pointer
* @n node to access
*
* This returns a pointer to the parent of the given node @n. If @n does not
* have a parent, NULL is returned. If @n is not linked, @n itself is returned.
*
* You should not call this on unlinked or uninitialized nodes! If you do, you
* better know how its semantics.
*
* Return: Pointer to parent.
*/
}
/**
* c_rbtree_remove_init() - safely remove node from tree and reinitialize it
* @t: tree to operate on
* @n: node to remove, or NULL
*
* This is almost the same as c_rbtree_remove(), but extends it slightly, to be
* more convenient to use in many cases:
* - if @n is unlinked or NULL, this is a no-op
* - @n is reinitialized after being removed
*/
if (c_rbnode_is_linked(n)) {
c_rbtree_remove(t, n);
c_rbnode_init(n);
}
}
/**
* CRBCompareFunc - compare a node to a key
* @t: tree where the node is linked to
* @k: key to compare
* @n: node to compare
*
* If you use the tree-traversal helpers (which are optional), you need to
* provide this callback so they can compare nodes in a tree to the key you
* look for.
*
* The tree @t is provided as optional context to this callback. The key you
* look for is provided as @k, the current node that should be compared to is
* provided as @n. This function should work like strcmp(), that is, return -1
* if @key orders before @n, 0 if both compare equal, and 1 if it orders after
* @n.
*/
/**
* c_rbtree_find_node() - find node
* @t: tree to search through
* @f: comparison function
* @k: key to search for
*
* This searches through @t for a node that compares equal to @k. The function
* @f must be provided by the caller, which is used to compare nodes to @k. See
* the documentation of CRBCompareFunc for details.
*
* If there are multiple entries that compare equal to @k, this will return a
* pseudo-randomly picked node. If you need stable lookup functions for trees
* where duplicate entries are allowed, you better code your own lookup.
*
* Return: Pointer to matching node, or NULL.
*/
CRBNode *i;
assert(t);
assert(f);
i = t->root;
while (i) {
int v = f(t, (void *)k, i);
if (v < 0)
i = i->left;
else if (v > 0)
i = i->right;
else
return i;
}
return NULL;
}
/**
* c_rbtree_find_entry() - find entry
* @_t: tree to search through
* @_f: comparison function
* @_k: key to search for
* @_t: type of the structure that embeds the nodes
* @_o: name of the node-member in type @_t
*
* This is very similar to c_rbtree_find_node(), but instead of returning a
* pointer to the CRBNode, it returns a pointer to the surrounding object. This
* object must embed the CRBNode object. The type of the surrounding object
* must be given as @_t, and the name of the embedded CRBNode member as @_o.
*
* See c_rbtree_find_node() for more details.
*
* Return: Pointer to found entry, NULL if not found.
*/
/**
* c_rbtree_find_slot() - find slot to insert new node
* @t: tree to search through
* @f: comparison function
* @k: key to search for
* @p: output storage for parent pointer
*
* This searches through @t just like c_rbtree_find_node() does. However,
* instead of returning a pointer to a node that compares equal to @k, this
* searches for a slot to insert a node with key @k. A pointer to the slot is
* returned, and a pointer to the parent of the slot is stored in @p. Both
* can be passed directly to c_rbtree_add(), together with your node to insert.
*
* If there already is a node in the tree, that compares equal to @k, this will
* return NULL and store the conflicting node in @p. In all other cases,
* this will return a pointer (non-NULL) to the empty slot to insert the node
* at. @p will point to the parent node of that slot.
*
* If you want trees that allow duplicate nodes, you better code your own
* insertion function.
*
* Return: Pointer to slot to insert node, or NULL on conflicts.
*/
static inline CRBNode **c_rbtree_find_slot(CRBTree *t, CRBCompareFunc f, const void *k, CRBNode **p) {
CRBNode **i;
assert(t);
assert(f);
assert(p);
i = &t->root;
*p = NULL;
while (*i) {
int v = f(t, (void *)k, *i);
*p = *i;
if (v < 0)
i = &(*i)->left;
else if (v > 0)
i = &(*i)->right;
else
return NULL;
}
return i;
}
#ifdef __cplusplus
}
#endif