4 * Intrusive, nonrecursive AVL tree data structure (self-balancing binary search
10 * This file is placed into the public domain. You can do whatever you want
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. */
23 #define AVL_INLINE _always_inline_attribute
25 /* Node in an AVL tree. Embed this in some other data structure. */
26 struct avl_tree_node {
28 /* Pointer to left child or NULL */
29 struct avl_tree_node *left;
31 /* Pointer to right child or NULL */
32 struct avl_tree_node *right;
34 /* Pointer to parent combined with the balance factor. This saves 4 or
35 * 8 bytes of memory depending on the CPU architecture.
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:
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;
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)))
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)
60 return (struct avl_tree_node *)(node->parent_balance & ~3);
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)
67 node->parent_balance = (uintptr_t)node;
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
73 static AVL_INLINE bool
74 avl_tree_node_is_unlinked(const struct avl_tree_node *node)
76 return node->parent_balance == (uintptr_t)node;
79 /* Internal use only */
81 avl_tree_rebalance_after_insert(struct avl_tree_node **root_ptr,
82 struct avl_tree_node *inserted);
85 * Look up an item in an AVL tree.
88 * Pointer to the root of the AVL tree. (This can be NULL --- that just
89 * means the tree is empty.)
92 * First argument to pass to the comparison callback --- generally a
93 * pointer to an object equal to the one being searched for.
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.
102 * Returns a pointer to the AVL tree node embedded in the resulting item, or
103 * NULL if the item was not found.
105 static AVL_INLINE struct avl_tree_node *
106 avl_tree_lookup(const struct avl_tree_node *root,
108 int (*cmp)(const void *, const struct avl_tree_node *))
110 const struct avl_tree_node *cur = root;
113 int res = (*cmp)(cmp_ctx, cur);
121 return (struct avl_tree_node*)cur;
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
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 *))
134 return avl_tree_lookup(root,
136 (int (*) (const void *,
137 const struct avl_tree_node *))cmp);
141 * Insert an item into an AVL tree.
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
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
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.
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.
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 *))
171 struct avl_tree_node **cur_ptr = root_ptr, *cur = NULL;
176 res = (*cmp)(item, cur);
178 cur_ptr = &cur->left;
180 cur_ptr = &cur->right;
185 item->parent_balance = (uintptr_t)cur | 1;
186 avl_tree_rebalance_after_insert(root_ptr, item);
191 avl_tree_remove(struct avl_tree_node **root_ptr, struct avl_tree_node *node);
193 /* Nonrecursive AVL tree traversal functions */
195 extern struct avl_tree_node *
196 avl_tree_first_in_order(const struct avl_tree_node *root);
198 extern struct avl_tree_node *
199 avl_tree_next_in_order(const struct avl_tree_node *prev);
201 extern struct avl_tree_node *
202 avl_tree_first_in_postorder(const struct avl_tree_node *root);
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);
208 #endif /* _AVL_TREE_H_ */