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 */
22 # define AVL_INLINE inline __attribute__((always_inline))
24 # define AVL_INLINE inline
25 # warning "AVL tree functions may not be inlined as intended"
28 /* Node in an AVL tree. Embed this in some other data structure. */
29 struct avl_tree_node {
31 /* Pointer to left child or NULL */
32 struct avl_tree_node *left;
34 /* Pointer to right child or NULL */
35 struct avl_tree_node *right;
37 /* Pointer to parent combined with the balance factor. This saves 4 or
38 * 8 bytes of memory depending on the CPU architecture.
40 * Low 2 bits: One greater than the balance factor of this subtree,
41 * which is equal to height(right) - height(left). The mapping is:
48 * The rest of the bits are the pointer to the parent node. It must be
49 * 4-byte aligned, and it will be NULL if this is the root node and
50 * therefore has no parent. */
51 uintptr_t parent_balance;
54 /* Cast an AVL tree node to the containing data structure. */
55 #define avl_tree_entry(entry, type, member) \
56 ((type*) ((char *)(entry) - offsetof(type, member)))
58 /* Returns a pointer to the parent of the specified AVL tree node, or NULL if it
59 * is already the root of the tree. */
60 static AVL_INLINE struct avl_tree_node *
61 avl_get_parent(const struct avl_tree_node *node)
63 return (struct avl_tree_node *)(node->parent_balance & ~3);
66 /* Marks the specified AVL tree node as unlinked from any tree. */
67 static AVL_INLINE void
68 avl_tree_node_set_unlinked(struct avl_tree_node *node)
70 node->parent_balance = (uintptr_t)node;
73 /* Returns true iff the specified AVL tree node has been marked with
74 * avl_tree_node_set_unlinked() and has not subsequently been inserted into a
76 static AVL_INLINE bool
77 avl_tree_node_is_unlinked(const struct avl_tree_node *node)
79 return node->parent_balance == (uintptr_t)node;
82 /* (Internal use only) */
84 avl_tree_rebalance_after_insert(struct avl_tree_node **root_ptr,
85 struct avl_tree_node *inserted);
88 * Looks up an item in the specified AVL tree.
91 * Pointer to the root of the AVL tree. (This can be NULL --- that just
92 * means the tree is empty.)
95 * First argument to pass to the comparison callback. This generally
96 * should be a pointer to an object equal to the one being searched for.
99 * Comparison callback. Must return < 0, 0, or > 0 if the first argument
100 * is less than, equal to, or greater than the second argument,
101 * respectively. The first argument will be @cmp_ctx and the second
102 * argument will be a pointer to the AVL tree node of an item in the tree.
104 * Returns a pointer to the AVL tree node of the resulting item, or NULL if the
105 * item was not found.
107 static AVL_INLINE struct avl_tree_node *
108 avl_tree_lookup(const struct avl_tree_node *root,
110 int (*cmp)(const void *, const struct avl_tree_node *))
112 const struct avl_tree_node *cur = root;
115 int res = (*cmp)(cmp_ctx, cur);
123 return (struct avl_tree_node*)cur;
126 /* Same as avl_tree_lookup(), but uses a more specific type for the comparison
127 * function. Specifically, with this function the item being searched for is
128 * expected to be in the same format as those already in the tree, with an
129 * embedded 'struct avl_tree_node'. */
130 static AVL_INLINE struct avl_tree_node *
131 avl_tree_lookup_node(const struct avl_tree_node *root,
132 const struct avl_tree_node *node,
133 int (*cmp)(const struct avl_tree_node *,
134 const struct avl_tree_node *))
136 return avl_tree_lookup(root,
138 (int (*) (const void *,
139 const struct avl_tree_node *))cmp);
143 * Inserts an item into the specified AVL tree.
146 * Location of the AVL tree's root pointer. Indirection is needed because
147 * the root node may change as a result of rotations caused by the
148 * insertion. Initialize *root_ptr to NULL for an empty tree.
151 * Pointer to the `struct avl_tree_node' embedded in the item to insert.
152 * No members in it need be pre-initialized, although members in the
153 * containing structure should be pre-initialized so that @cmp can use them
157 * Comparison callback. Must return < 0, 0, or > 0 if the first argument
158 * is less than, equal to, or greater than the second argument,
159 * respectively. The first argument will be @item and the second
160 * argument will be a pointer to an AVL tree node embedded in some
161 * previously-inserted item to which @item is being compared.
163 * If no item in the tree is comparatively equal (via @cmp) to @item, inserts
164 * @item and returns NULL. Otherwise does nothing and returns a pointer to the
165 * AVL tree node embedded in the previously-inserted item which compared equal
168 static AVL_INLINE struct avl_tree_node *
169 avl_tree_insert(struct avl_tree_node **root_ptr,
170 struct avl_tree_node *item,
171 int (*cmp)(const struct avl_tree_node *,
172 const struct avl_tree_node *))
174 struct avl_tree_node **cur_ptr = root_ptr, *cur = NULL;
179 res = (*cmp)(item, cur);
181 cur_ptr = &cur->left;
183 cur_ptr = &cur->right;
188 item->parent_balance = (uintptr_t)cur | 1;
189 avl_tree_rebalance_after_insert(root_ptr, item);
193 /* Removes an item from the specified AVL tree.
194 * See implementation for details. */
196 avl_tree_remove(struct avl_tree_node **root_ptr, struct avl_tree_node *node);
198 /* Nonrecursive AVL tree traversal functions */
200 extern struct avl_tree_node *
201 avl_tree_first_in_order(const struct avl_tree_node *root);
203 extern struct avl_tree_node *
204 avl_tree_next_in_order(const struct avl_tree_node *prev);
206 extern struct avl_tree_node *
207 avl_tree_first_in_postorder(const struct avl_tree_node *root);
209 extern struct avl_tree_node *
210 avl_tree_next_in_postorder(const struct avl_tree_node *prev,
211 const struct avl_tree_node *prev_parent);
213 #endif /* _AVL_TREE_H_ */