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