wimlib.net Git - wimlib/blob - include/wimlib/avl_tree.h

   1 /*
   2  * avl_tree.h
   3  *
   4  * Intrusive, nonrecursive AVL tree data structure (self-balancing binary search
   5  * tree), header file.
   6  *
   7  * Author:  Eric Biggers
   8  * Year:    2014
   9  *
  10  * This file is placed into the public domain.  You can do whatever you want
  11  * with it.
  12  */
  13
  14 #ifndef _AVL_TREE_H_
  15 #define _AVL_TREE_H_
  16
  17 #include <stdbool.h>
  18 #include <stddef.h>
  19 #include <inttypes.h>           /* for uintptr_t */
  20 #include <wimlib/compiler.h>    /* for _always_inline_attribute. You can
  21                                    instead define it below if you want.  */
  22
  23 #define AVL_INLINE _always_inline_attribute
  24
  25 /* Node in an AVL tree.  Embed this in some other data structure.  */
  26 struct avl_tree_node {
  27
  28         /* Pointer to left child or NULL  */
  29         struct avl_tree_node *left;
  30
  31         /* Pointer to right child or NULL  */
  32         struct avl_tree_node *right;
  33
  34         /* Pointer to parent combined with the balance factor.  This saves 4 or
  35          * 8 bytes of memory depending on the CPU architecture.
  36          *
  37          * Low 2 bits:  One greater than the balance factor of this subtree,
  38          * which is equal to height(right) - height(left).  The mapping is:
  39          *
  40          * 00 => -1
  41          * 01 =>  0
  42          * 10 => +1
  43          * 11 => undefined
  44          *
  45          * The rest of the bits are the pointer to the parent node.  It must be
  46          * 4-byte aligned, and it will be NULL if this is the root note and
  47          * therefore has no parent.  */
  48         uintptr_t parent_balance;
  49 };
  50
  51 /* Cast an AVL tree node to the containing data structure.  */
  52 #define avl_tree_entry(entry, type, member) \
  53         ((type*) ((char *)(entry) - offsetof(type, member)))
  54
  55 /* Extracts the parent pointer from the specified AVL tree node.
  56  * Returns the parent pointer, or NULL if @node is the root node.  */
  57 static AVL_INLINE struct avl_tree_node *
  58 avl_get_parent(const struct avl_tree_node *node)
  59 {
  60         return (struct avl_tree_node *)(node->parent_balance & ~3);
  61 }
  62
  63 /* Mark the node as unlinked from any tree.  */
  64 static AVL_INLINE void
  65 avl_tree_node_set_unlinked(struct avl_tree_node *node)
  66 {
  67         node->parent_balance = (uintptr_t)node;
  68 }
  69
  70 /* Returns true iff the specified node has been marked with
  71  * avl_tree_node_set_unlinked() and has not subsequently been inserted into a
  72  * tree.  */
  73 static AVL_INLINE bool
  74 avl_tree_node_is_unlinked(const struct avl_tree_node *node)
  75 {
  76         return node->parent_balance == (uintptr_t)node;
  77 }
  78
  79 /* Internal use only */
  80 extern void
  81 avl_tree_rebalance_after_insert(struct avl_tree_node **root_ptr,
  82                                 struct avl_tree_node *inserted);
  83
  84 /*
  85  * Look up an item in an AVL tree.
  86  *
  87  * @root
  88  *      Pointer to the root of the AVL tree.  (This can be NULL --- that just
  89  *      means the tree is empty.)
  90  *
  91  * @cmp_ctx
  92  *      First argument to pass to the comparison callback --- generally a
  93  *      pointer to an object equal to the one being searched for.
  94  *
  95  * @cmp
  96  *      Comparison callback.  Must return < 0, 0, or > 0 if the first argument
  97  *      is less than, equal to, or greater than the second argument,
  98  *      respectively.  The first argument will be @cmp_ctx and the second
  99  *      argument will be a pointer to the AVL tree node contained in the item
 100  *      inserted into the AVL tree.
 101  *
 102  * Returns a pointer to the AVL tree node embedded in the resulting item, or
 103  * NULL if the item was not found.
 104  */
 105 static AVL_INLINE struct avl_tree_node *
 106 avl_tree_lookup(const struct avl_tree_node *root,
 107                 const void *cmp_ctx,
 108                 int (*cmp)(const void *, const struct avl_tree_node *))
 109 {
 110         const struct avl_tree_node *cur = root;
 111
 112         while (cur) {
 113                 int res = (*cmp)(cmp_ctx, cur);
 114                 if (res < 0)
 115                         cur = cur->left;
 116                 else if (res > 0)
 117                         cur = cur->right;
 118                 else
 119                         break;
 120         }
 121         return (struct avl_tree_node*)cur;
 122 }
 123
 124 /* Same as avl_tree_lookup(), just uses a more specific type for the comparison
 125  * function.  Specifically, the item being searched for is expected to be in the
 126  * same format as those already in the tree, with an embedded 'struct
 127  * avl_tree_node'.  */
 128 static AVL_INLINE struct avl_tree_node *
 129 avl_tree_lookup_node(const struct avl_tree_node *root,
 130                      const struct avl_tree_node *node,
 131                      int (*cmp)(const struct avl_tree_node *,
 132                                 const struct avl_tree_node *))
 133 {
 134         return avl_tree_lookup(root,
 135                                (const void *)node,
 136                                (int (*) (const void *,
 137                                          const struct avl_tree_node *))cmp);
 138 }
 139
 140 /*
 141  * Insert an item into an AVL tree.
 142  *
 143  * @root_ptr
 144  *      Pointer to the pointer to the root of the AVL tree.  (Indirection is
 145  *      needed because the root node may change.)  Initialize *root_ptr to NULL
 146  *      for an empty tree.
 147  *
 148  * @item
 149  *      Pointer to the `struct avl_tree_node' embedded in the item to insert.
 150  *      No members in it need be pre-initialized, although members in the
 151  *      containing structure should be pre-initialized so that @cmp can use them
 152  *      in comparisons.
 153  *
 154  * @cmp
 155  *      Comparison callback.  Must return < 0, 0, or > 0 if the first argument
 156  *      is less than, equal to, or greater than the second argument,
 157  *      respectively.  The first argument will be @item and the second
 158  *      argument will be a pointer to an AVL tree node embedded in some
 159  *      previously-inserted item that @item is being compared with.
 160  *
 161  * Returns NULL if the item was successfully inserted, otherwise the node of a
 162  * previously-inserted item which compared equal to @item and prevented the new
 163  * insertion of @item.
 164  */
 165 static AVL_INLINE struct avl_tree_node *
 166 avl_tree_insert(struct avl_tree_node **root_ptr,
 167                 struct avl_tree_node *item,
 168                 int (*cmp)(const struct avl_tree_node *,
 169                            const struct avl_tree_node *))
 170 {
 171         struct avl_tree_node **cur_ptr = root_ptr, *cur = NULL;
 172         int res;
 173
 174         while (*cur_ptr) {
 175                 cur = *cur_ptr;
 176                 res = (*cmp)(item, cur);
 177                 if (res < 0)
 178                         cur_ptr = &cur->left;
 179                 else if (res > 0)
 180                         cur_ptr = &cur->right;
 181                 else
 182                         return cur;
 183         }
 184         *cur_ptr = item;
 185         item->parent_balance = (uintptr_t)cur | 1;
 186         avl_tree_rebalance_after_insert(root_ptr, item);
 187         return NULL;
 188 }
 189
 190 extern void
 191 avl_tree_remove(struct avl_tree_node **root_ptr, struct avl_tree_node *node);
 192
 193 /* Nonrecursive AVL tree traversal functions  */
 194
 195 extern struct avl_tree_node *
 196 avl_tree_first_in_order(const struct avl_tree_node *root);
 197
 198 extern struct avl_tree_node *
 199 avl_tree_next_in_order(const struct avl_tree_node *prev);
 200
 201 extern struct avl_tree_node *
 202 avl_tree_first_in_postorder(const struct avl_tree_node *root);
 203
 204 extern struct avl_tree_node *
 205 avl_tree_next_in_postorder(const struct avl_tree_node *prev,
 206                            const struct avl_tree_node *prev_parent);
 207
 208 #endif /* _AVL_TREE_H_ */