include/a/avl.h

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