include/a/rbt.h

   1 /*!
   2  @file rbt.h
   3  @brief red–black self-balancing binary search tree
   4 */
   5
   6 #ifndef LIBA_RBT_H
   7 #define LIBA_RBT_H
   8
   9 #include "a.h"
  10
  11 /*!
  12  @ingroup liba
  13  @addtogroup a_rbt red–black binary search tree
  14  @{
  15 */
  16
  17 /* clang-format off */
  18 #define A_RBT_ROOT {A_NULL}
  19 /* clang-format on */
  20
  21 /*!
  22  @brief instance structure for red–black binary search tree node
  23 */
  24 typedef struct a_rbt_node
  25 {
  26     struct a_rbt_node *left; /*!< pointer to left child or null */
  27     struct a_rbt_node *right; /*!< pointer to right child or null */
  28     /*! pointer to parent combined with the color. The mapping is: 0 => red, 1 => black.
  29      The rest of the bits are the pointer to the parent node. It must be 2-byte aligned,
  30      and it will be null if this is the root node and therefore has no parent.
  31     */
  32 #if defined(A_SIZE_POINTER) && (A_SIZE_POINTER + 0 > 1)
  33     a_uptr parent_;
  34 #else /* !A_SIZE_POINTER */
  35     struct a_rbt_node *parent;
  36     unsigned int color;
  37 #endif /* A_SIZE_POINTER */
  38 } a_rbt_node;
  39
  40 /*!
  41  @brief access parent of red–black binary search tree node
  42  @param[in] node points to red–black binary search tree node
  43  @return a pointer to the parent of the specified red–black tree node,
  44  or null if it is already the root of the tree.
  45 */
  46 A_INTERN a_rbt_node *a_rbt_parent(a_rbt_node const *node)
  47 {
  48 #if defined(A_SIZE_POINTER) && (A_SIZE_POINTER + 0 > 1)
  49     return a_cast_r(a_rbt_node *, node->parent_ & ~a_uptr_c(1));
  50 #else /* !A_SIZE_POINTER */
  51     return node->parent;
  52 #endif /* A_SIZE_POINTER */
  53 }
  54
  55 /*!
  56  @brief initialize for red–black binary search tree node
  57  @param[in] node node to be initialized
  58  @param[in] parent node parent
  59  @return initialized node
  60 */
  61 A_INTERN a_rbt_node *a_rbt_init(a_rbt_node *node, a_rbt_node *parent)
  62 {
  63 #if defined(A_SIZE_POINTER) && (A_SIZE_POINTER + 0 > 1)
  64     node->parent_ = a_cast_r(a_uptr, parent);
  65 #else /* !A_SIZE_POINTER */
  66     node->parent = parent;
  67     node->color = 0;
  68 #endif /* A_SIZE_POINTER */
  69     node->right = A_NULL;
  70     node->left = A_NULL;
  71     return node;
  72 }
  73
  74 /*!
  75  @brief instance structure for red–black binary search tree root
  76 */
  77 typedef union a_rbt
  78 {
  79     struct a_rbt_node *node; /*!< root node */
  80 } a_rbt;
  81
  82 /*!
  83  @brief initialize for red–black binary search tree root
  84  @param[in,out] root red–black binary search tree root
  85 */
  86 A_INTERN void a_rbt_root(a_rbt *root) { root->node = A_NULL; }
  87
  88 #if defined(__cplusplus)
  89 extern "C" {
  90 #endif /* __cplusplus */
  91
  92 /*!
  93  @brief access head node of red–black binary search tree in-order
  94  @param[in] root red–black binary search tree root
  95  @return head node or null
  96 */
  97 A_EXTERN a_rbt_node *a_rbt_head(a_rbt const *root);
  98
  99 /*!
 100  @brief access tail node of red–black binary search tree in-order
 101  @param[in] root red–black binary search tree root
 102  @return tail node or null
 103 */
 104 A_EXTERN a_rbt_node *a_rbt_tail(a_rbt const *root);
 105
 106 /*!
 107  @brief access next node of red–black binary search tree node in-order
 108  @param[in] node red–black binary search tree node
 109  @return next node or null
 110 */
 111 A_EXTERN a_rbt_node *a_rbt_next(a_rbt_node *node);
 112
 113 /*!
 114  @brief access prev node of red–black binary search tree node in-order
 115  @param[in] node red–black binary search tree node
 116  @return prev node or null
 117 */
 118 A_EXTERN a_rbt_node *a_rbt_prev(a_rbt_node *node);
 119
 120 /*!
 121  @brief access next node of red–black binary search tree node preorder
 122  @param[in] node red–black binary search tree node
 123  @return next node or null
 124 */
 125 A_EXTERN a_rbt_node *a_rbt_pre_next(a_rbt_node *node);
 126
 127 /*!
 128  @brief access prev node of red–black binary search tree node preorder
 129  @param[in] node red–black binary search tree node
 130  @return prev node or null
 131 */
 132 A_EXTERN a_rbt_node *a_rbt_pre_prev(a_rbt_node *node);
 133
 134 /*!
 135  @brief access head node of red–black binary search tree postorder
 136  @param[in] root red–black binary search tree root
 137  @return head node or null
 138 */
 139 A_EXTERN a_rbt_node *a_rbt_post_head(a_rbt const *root);
 140
 141 /*!
 142  @brief access tail node of red–black binary search tree postorder
 143  @param[in] root red–black binary search tree root
 144  @return tail node or null
 145 */
 146 A_EXTERN a_rbt_node *a_rbt_post_tail(a_rbt const *root);
 147
 148 /*!
 149  @brief access next node of red–black binary search tree node postorder
 150  @param[in] node red–black binary search tree node
 151  @return next node or null
 152 */
 153 A_EXTERN a_rbt_node *a_rbt_post_next(a_rbt_node *node);
 154
 155 /*!
 156  @brief access prev node of red–black binary search tree node postorder
 157  @param[in] node red–black binary search tree node
 158  @return prev node or null
 159 */
 160 A_EXTERN a_rbt_node *a_rbt_post_prev(a_rbt_node *node);
 161
 162 /*!
 163  @brief tear a node from red–black binary search tree
 164  @param[in] root red–black binary search tree root
 165  @param[in,out] next input starting node or,
 166  if null, root node. output next node or null.
 167  @return teared node or null
 168 */
 169 A_EXTERN a_rbt_node *a_rbt_tear(a_rbt *root, a_rbt_node **next);
 170
 171 /*!
 172  @brief search specified content from red–black binary search tree
 173  @param[in] root red–black binary search tree root
 174  @param[in] ctx specified content
 175  @param[in] cmp a function that compares two nodes
 176   @arg cmp(lhs,rhs)==0 *lhs is equivalent to *rhs
 177   @arg cmp(lhs,rhs)<0 *lhs goes before *rhs
 178   @arg cmp(lhs,rhs)>0 *lhs goes after *rhs
 179  @return specified node or null
 180 */
 181 A_EXTERN a_rbt_node *a_rbt_search(a_rbt const *root, void const *ctx, int (*cmp)(void const *, void const *));
 182
 183 /*!
 184  @brief insert specified node into red–black binary search tree
 185  @param[in] root red–black binary search tree root
 186  @param[in] node specified tree node
 187  @param[in] cmp a function that compares two nodes
 188   @arg cmp(lhs,rhs)==0 *lhs is equivalent to *rhs
 189   @arg cmp(lhs,rhs)<0 *lhs goes before *rhs
 190   @arg cmp(lhs,rhs)>0 *lhs goes after *rhs
 191  @return null or duplicate node
 192 */
 193 A_EXTERN a_rbt_node *a_rbt_insert(a_rbt *root, a_rbt_node *node, int (*cmp)(void const *, void const *));
 194
 195 /*!
 196  @brief rebalance the tree after insertion of the specified node
 197  @param[in] root red–black binary search tree root
 198  @param[in] node insert tree node
 199 */
 200 A_EXTERN void a_rbt_insert_adjust(a_rbt *root, a_rbt_node *node);
 201
 202 /*!
 203  @brief remove specified node from red–black binary search tree
 204  @param[in] root red–black binary search tree root
 205  @param[in] node specified tree node
 206 */
 207 A_EXTERN void a_rbt_remove(a_rbt *root, a_rbt_node *node);
 208
 209 #if defined(__cplusplus)
 210 } /* extern "C" */
 211 #endif /* __cplusplus */
 212
 213 /*!
 214  @brief access the struct for this entry
 215  @param ptr the &a_rbt_node pointer
 216  @param type the type of the struct this is embedded in
 217  @param member the name of the a_rbt_node within the struct
 218 */
 219 #define a_rbt_entry(ptr, type, member) a_container_of(ptr, type, member)
 220
 221 /*!
 222  @brief iterate over a red–black binary search tree in-order
 223  @code{.c}
 224  typedef struct
 225  {
 226      a_rbt_node node;
 227  } T;
 228  a_rbt root = A_RBT_ROOT;
 229  a_rbt_foreach(cur, &root)
 230  {
 231      T *it = a_rbt_entry(cur, T, node);
 232  }
 233  @endcode
 234  @param cur the &a_rbt_node to use as a loop counter
 235  @param root red–black binary search tree root
 236 */
 237 #define a_rbt_foreach(cur, root) \
 238     for (a_rbt_node *cur = a_rbt_head(root); cur; cur = a_rbt_next(cur))
 239 #define A_RBT_FOREACH(cur, root) \
 240     for (cur = a_rbt_head(root); cur; cur = a_rbt_next(cur))
 241
 242 /*!
 243  @brief iterate over a red–black binary search tree in-order reverse
 244  @code{.c}
 245  typedef struct
 246  {
 247      a_rbt_node node;
 248  } T;
 249  a_rbt root = A_RBT_ROOT;
 250  a_rbt_foreach_reverse(cur, &root)
 251  {
 252      T *it = a_rbt_entry(cur, T, node);
 253  }
 254  @endcode
 255  @param cur the &a_rbt_node to use as a loop counter
 256  @param root red–black binary search tree root
 257 */
 258 #define a_rbt_foreach_reverse(cur, root) \
 259     for (a_rbt_node *cur = a_rbt_tail(root); cur; cur = a_rbt_prev(cur))
 260 #define A_RBT_FOREACH_REVERSE(cur, root) \
 261     for (cur = a_rbt_tail(root); cur; cur = a_rbt_prev(cur))
 262
 263 /*!
 264  @brief iterate over a red–black binary search tree preorder
 265  @code{.c}
 266  typedef struct
 267  {
 268      a_rbt_node node;
 269  } T;
 270  a_rbt root = A_RBT_ROOT;
 271  a_rbt_pre_foreach(cur, &root)
 272  {
 273      T *it = a_rbt_entry(cur, T, node);
 274  }
 275  @endcode
 276  @param cur the &a_rbt_node to use as a loop counter
 277  @param root red–black binary search tree root
 278 */
 279 #define a_rbt_pre_foreach(cur, root) \
 280     for (a_rbt_node *cur = (root)->node; cur; cur = a_rbt_pre_next(cur))
 281 #define A_RBT_PRE_FOREACH(cur, root) \
 282     for (cur = (root)->node; cur; cur = a_rbt_pre_next(cur))
 283
 284 /*!
 285  @brief iterate over a red–black binary search tree preorder reverse
 286  @code{.c}
 287  typedef struct
 288  {
 289      a_rbt_node node;
 290  } T;
 291  a_rbt root = A_RBT_ROOT;
 292  a_rbt_pre_foreach_reverse(cur, &root)
 293  {
 294      T *it = a_rbt_entry(cur, T, node);
 295  }
 296  @endcode
 297  @param cur the &a_rbt_node to use as a loop counter
 298  @param root red–black binary search tree root
 299 */
 300 #define a_rbt_pre_foreach_reverse(cur, root) \
 301     for (a_rbt_node *cur = (root)->node; cur; cur = a_rbt_pre_prev(cur))
 302 #define A_RBT_PRE_FOREACH_REVERSE(cur, root) \
 303     for (cur = (root)->node; cur; cur = a_rbt_pre_prev(cur))
 304
 305 /*!
 306  @brief iterate over a red–black binary search tree postorder
 307  @code{.c}
 308  typedef struct
 309  {
 310      a_rbt_node node;
 311  } T;
 312  a_rbt root = A_RBT_ROOT;
 313  a_rbt_post_foreach(cur, &root)
 314  {
 315      T *it = a_rbt_entry(cur, T, node);
 316  }
 317  @endcode
 318  @param cur the &a_rbt_node to use as a loop counter
 319  @param root red–black binary search tree root
 320 */
 321 #define a_rbt_post_foreach(cur, root) \
 322     for (a_rbt_node *cur = a_rbt_post_head(root); cur; cur = a_rbt_post_next(cur))
 323 #define A_RBT_POST_FOREACH(cur, root) \
 324     for (cur = a_rbt_post_head(root); cur; cur = a_rbt_post_next(cur))
 325
 326 /*!
 327  @brief iterate over a red–black binary search tree postorder reverse
 328  @code{.c}
 329  typedef struct
 330  {
 331      a_rbt_node node;
 332  } T;
 333  a_rbt root = A_RBT_ROOT;
 334  a_rbt_post_foreach_reverse(cur, &root)
 335  {
 336      T *it = a_rbt_entry(cur, T, node);
 337  }
 338  @endcode
 339  @param cur the &a_rbt_node to use as a loop counter
 340  @param root red–black binary search tree root
 341 */
 342 #define a_rbt_post_foreach_reverse(cur, root) \
 343     for (a_rbt_node *cur = a_rbt_post_tail(root); cur; cur = a_rbt_post_prev(cur))
 344 #define A_RBT_POST_FOREACH_REVERSE(cur, root) \
 345     for (cur = a_rbt_post_tail(root); cur; cur = a_rbt_post_prev(cur))
 346
 347 /*!
 348  @brief tear a red–black binary search tree using postorder traversal
 349  @code{.c}
 350  typedef struct
 351  {
 352      a_rbt_node node;
 353  } T;
 354  a_rbt root = A_AVL_ROOT;
 355  a_rbt_fortear(cur, next, &root)
 356  {
 357      T *it = a_rbt_entry(cur, T, node);
 358  }
 359  @endcode
 360  @param cur the &a_rbt_node to use as a loop counter
 361  @param next the &a_rbt_node to use as next node
 362  @param root red–black binary search tree root
 363 */
 364 #define a_rbt_fortear(cur, next, root) \
 365     for (a_rbt_node *next = A_NULL, *cur = a_rbt_tear(root, &next); cur; cur = a_rbt_tear(root, &next))
 366 #define A_RBT_FORTEAR(cur, next, root) \
 367     for ((void)(next = A_NULL), cur = a_rbt_tear(root, &next); cur; cur = a_rbt_tear(root, &next))
 368
 369 /*! @} a_rbt */
 370
 371 #endif /* a/rbt.h */