src/basic/c-rbtree.h

   1 #pragma once
   2
   3 /***
   4   This file is part of systemd. See COPYING for details.
   5
   6   systemd is free software; you can redistribute it and/or modify it
   7   under the terms of the GNU Lesser General Public License as published by
   8   the Free Software Foundation; either version 2.1 of the License, or
   9   (at your option) any later version.
  10
  11   systemd is distributed in the hope that it will be useful, but
  12   WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  14   Lesser General Public License for more details.
  15
  16   You should have received a copy of the GNU Lesser General Public License
  17   along with systemd; If not, see <http://www.gnu.org/licenses/>.
  18 ***/
  19
  20 /*
  21  * Standalone Red-Black-Tree Implementation in Standard ISO-C11
  22  *
  23  * This header provides an RB-Tree API, that is fully implemented in ISO-C11
  24  * and has no external dependencies. Furthermore, tree traversal, memory
  25  * allocations, and key comparisons a fully in control of the API user. The
  26  * implementation only provides the RB-Tree specific rebalancing and coloring.
  27  *
  28  * A tree is represented by the "CRBTree" structure. It contains a *singly*
  29  * field, which is a pointer to the root node. If NULL, the tree is empty. If
  30  * non-NULL, there is at least a single element in the tree.
  31  *
  32  * Each node of the tree is represented by the "CRBNode" structure. It has
  33  * three fields. The @left and @right members can be accessed by the API user
  34  * directly to traverse the tree. The third member is an implementation detail
  35  * and encodes the parent pointer and color of the node.
  36  * API users are required to embed the CRBNode object into their own objects
  37  * and then use offsetof() (i.e., container_of() and friends) to turn CRBNode
  38  * pointers into pointers to their own structure.
  39  */
  40
  41 #ifdef __cplusplus
  42 extern "C" {
  43 #endif
  44
  45 typedef struct CRBNode CRBNode;
  46 typedef struct CRBTree CRBTree;
  47
  48 /**
  49  * struct CRBNode - Node of a Red-Black Tree
  50  * @__parent_and_color:         internal state
  51  * @left:                       left child, or NULL
  52  * @right:                      right child, or NULL
  53  *
  54  * Each node in an RB-Tree must embed an CRBNode object. This object contains
  55  * pointers to its left and right child, which can be freely accessed by the
  56  * API user at any time. They are NULL, if the node does not have a left/right
  57  * child.
  58  *
  59  * The @__parent_and_color field must never be accessed directly. It encodes
  60  * the pointer to the parent node, and the color of the node. Use the accessor
  61  * functions instead.
  62  *
  63  * There is no reason to initialize a CRBNode object before linking it.
  64  * However, if you need a boolean state that tells you whether the node is
  65  * linked or not, you should initialize the node via c_rbnode_init() or
  66  * C_RBNODE_INIT.
  67  */
  68 struct CRBNode {
  69         CRBNode *__parent_and_color;
  70         CRBNode *left;
  71         CRBNode *right;
  72 };
  73
  74 #define C_RBNODE_INIT(_var) { .__parent_and_color = &(_var) }
  75
  76 CRBNode *c_rbnode_leftmost(CRBNode *n);
  77 CRBNode *c_rbnode_rightmost(CRBNode *n);
  78 CRBNode *c_rbnode_next(CRBNode *n);
  79 CRBNode *c_rbnode_prev(CRBNode *n);
  80
  81 /**
  82  * struct CRBTree - Red-Black Tree
  83  * @root:       pointer to the root node, or NULL
  84  *
  85  * Each Red-Black Tree is rooted in an CRBTree object. This object contains a
  86  * pointer to the root node of the tree. The API user is free to access the
  87  * @root member at any time, and use it to traverse the tree.
  88  *
  89  * To initialize an RB-Tree, set it to NULL / all zero.
  90  */
  91 struct CRBTree {
  92         CRBNode *root;
  93 };
  94
  95 CRBNode *c_rbtree_first(CRBTree *t);
  96 CRBNode *c_rbtree_last(CRBTree *t);
  97
  98 void c_rbtree_add(CRBTree *t, CRBNode *p, CRBNode **l, CRBNode *n);
  99 void c_rbtree_remove(CRBTree *t, CRBNode *n);
 100
 101 /**
 102  * c_rbnode_init() - mark a node as unlinked
 103  * @n:          node to operate on
 104  *
 105  * This marks the node @n as unlinked. The node will be set to a valid state
 106  * that can never happen if the node is linked in a tree. Furthermore, this
 107  * state is fully known to the implementation, and as such handled gracefully
 108  * in all cases.
 109  *
 110  * You are *NOT* required to call this on your node. c_rbtree_add() can handle
 111  * uninitialized nodes just fine. However, calling this allows to use
 112  * c_rbnode_is_linked() to check for the state of a node. Furthermore,
 113  * iterators and accessors can be called on initialized (yet unlinked) nodes.
 114  *
 115  * Use the C_RBNODE_INIT macro if you want to initialize static variables.
 116  */
 117 static inline void c_rbnode_init(CRBNode *n) {
 118         *n = (CRBNode)C_RBNODE_INIT(*n);
 119 }
 120
 121 /**
 122  * c_rbnode_is_linked() - check whether a node is linked
 123  * @n:          node to check, or NULL
 124  *
 125  * This checks whether the passed node is linked. If you pass NULL, or if the
 126  * node is not linked into a tree, this will return false. Otherwise, this
 127  * returns true.
 128  *
 129  * Note that you must have either linked the node or initialized it, before
 130  * calling this function. Never call this function on uninitialized nodes.
 131  * Furthermore, removing a node via c_rbtree_remove() does *NOT* mark the node
 132  * as unlinked. You have to call c_rbnode_init() yourself after removal, or use
 133  * the c_rbtree_remove_init() helper.
 134  *
 135  * Return: true if the node is linked, false if not.
 136  */
 137 static inline _Bool c_rbnode_is_linked(CRBNode *n) {
 138         return n && n->__parent_and_color != n;
 139 }
 140
 141 /**
 142  * c_rbnode_parent() - return parent pointer
 143  * @n           node to access
 144  *
 145  * This returns a pointer to the parent of the given node @n. If @n does not
 146  * have a parent, NULL is returned. If @n is not linked, @n itself is returned.
 147  *
 148  * You should not call this on unlinked or uninitialized nodes! If you do, you
 149  * better know how its semantics.
 150  *
 151  * Return: Pointer to parent.
 152  */
 153 static inline CRBNode *c_rbnode_parent(CRBNode *n) {
 154         return (CRBNode*)((unsigned long)n->__parent_and_color & ~1UL);
 155 }
 156
 157 /**
 158  * c_rbtree_remove_init() - safely remove node from tree and reinitialize it
 159  * @t:          tree to operate on
 160  * @n:          node to remove, or NULL
 161  *
 162  * This is almost the same as c_rbtree_remove(), but extends it slightly, to be
 163  * more convenient to use in many cases:
 164  *  - if @n is unlinked or NULL, this is a no-op
 165  *  - @n is reinitialized after being removed
 166  */
 167 static inline void c_rbtree_remove_init(CRBTree *t, CRBNode *n) {
 168         if (c_rbnode_is_linked(n)) {
 169                 c_rbtree_remove(t, n);
 170                 c_rbnode_init(n);
 171         }
 172 }
 173
 174 /**
 175  * CRBCompareFunc - compare a node to a key
 176  * @t:          tree where the node is linked to
 177  * @k:          key to compare
 178  * @n:          node to compare
 179  *
 180  * If you use the tree-traversal helpers (which are optional), you need to
 181  * provide this callback so they can compare nodes in a tree to the key you
 182  * look for.
 183  *
 184  * The tree @t is provided as optional context to this callback. The key you
 185  * look for is provided as @k, the current node that should be compared to is
 186  * provided as @n. This function should work like strcmp(), that is, return -1
 187  * if @key orders before @n, 0 if both compare equal, and 1 if it orders after
 188  * @n.
 189  */
 190 typedef int (*CRBCompareFunc) (CRBTree *t, void *k, CRBNode *n);
 191
 192 /**
 193  * c_rbtree_find_node() - find node
 194  * @t:          tree to search through
 195  * @f:          comparison function
 196  * @k:          key to search for
 197  *
 198  * This searches through @t for a node that compares equal to @k. The function
 199  * @f must be provided by the caller, which is used to compare nodes to @k. See
 200  * the documentation of CRBCompareFunc for details.
 201  *
 202  * If there are multiple entries that compare equal to @k, this will return a
 203  * pseudo-randomly picked node. If you need stable lookup functions for trees
 204  * where duplicate entries are allowed, you better code your own lookup.
 205  *
 206  * Return: Pointer to matching node, or NULL.
 207  */
 208 static inline CRBNode *c_rbtree_find_node(CRBTree *t, CRBCompareFunc f, const void *k) {
 209         CRBNode *i;
 210
 211         assert(t);
 212         assert(f);
 213
 214         i = t->root;
 215         while (i) {
 216                 int v = f(t, (void *)k, i);
 217                 if (v < 0)
 218                         i = i->left;
 219                 else if (v > 0)
 220                         i = i->right;
 221                 else
 222                         return i;
 223         }
 224
 225         return NULL;
 226 }
 227
 228 /**
 229  * c_rbtree_find_entry() - find entry
 230  * @_t:         tree to search through
 231  * @_f:         comparison function
 232  * @_k:         key to search for
 233  * @_t:         type of the structure that embeds the nodes
 234  * @_o:         name of the node-member in type @_t
 235  *
 236  * This is very similar to c_rbtree_find_node(), but instead of returning a
 237  * pointer to the CRBNode, it returns a pointer to the surrounding object. This
 238  * object must embed the CRBNode object. The type of the surrounding object
 239  * must be given as @_t, and the name of the embedded CRBNode member as @_o.
 240  *
 241  * See c_rbtree_find_node() for more details.
 242  *
 243  * Return: Pointer to found entry, NULL if not found.
 244  */
 245 #define c_rbtree_find_entry(_m, _f, _k, _t, _o) \
 246         ((_t *)(((char *)c_rbtree_find_node((_m), (_f), (_k)) ?: \
 247                 (char *)NULL + offsetof(_t, _o)) - offsetof(_t, _o)))
 248
 249 /**
 250  * c_rbtree_find_slot() - find slot to insert new node
 251  * @t:          tree to search through
 252  * @f:          comparison function
 253  * @k:          key to search for
 254  * @p:          output storage for parent pointer
 255  *
 256  * This searches through @t just like c_rbtree_find_node() does. However,
 257  * instead of returning a pointer to a node that compares equal to @k, this
 258  * searches for a slot to insert a node with key @k. A pointer to the slot is
 259  * returned, and a pointer to the parent of the slot is stored in @p. Both
 260  * can be passed directly to c_rbtree_add(), together with your node to insert.
 261  *
 262  * If there already is a node in the tree, that compares equal to @k, this will
 263  * return NULL and store the conflicting node in @p. In all other cases,
 264  * this will return a pointer (non-NULL) to the empty slot to insert the node
 265  * at. @p will point to the parent node of that slot.
 266  *
 267  * If you want trees that allow duplicate nodes, you better code your own
 268  * insertion function.
 269  *
 270  * Return: Pointer to slot to insert node, or NULL on conflicts.
 271  */
 272 static inline CRBNode **c_rbtree_find_slot(CRBTree *t, CRBCompareFunc f, const void *k, CRBNode **p) {
 273         CRBNode **i;
 274
 275         assert(t);
 276         assert(f);
 277         assert(p);
 278
 279         i = &t->root;
 280         *p = NULL;
 281         while (*i) {
 282                 int v = f(t, (void *)k, *i);
 283                 *p = *i;
 284                 if (v < 0)
 285                         i = &(*i)->left;
 286                 else if (v > 0)
 287                         i = &(*i)->right;
 288                 else
 289                         return NULL;
 290         }
 291
 292         return i;
 293 }
 294
 295 #ifdef __cplusplus
 296 }
 297 #endif