4 #include "utils_avltree.h"
6 #define BALANCE(n) ((((n)->right == NULL) ? 0 : (n)->right->height) \
7 - (((n)->left == NULL) ? 0 : (n)->left->height))
18 struct avl_node_s *left;
19 struct avl_node_s *right;
20 struct avl_node_s *parent;
22 typedef struct avl_node_s avl_node_t;
27 int (*compare) (const void *, const void *);
39 static void free_node (avl_node_t *n)
52 static avl_node_t *search (avl_tree_t *t, void *key)
60 cmp = t->compare (key, n->key);
72 static void rebalance (avl_tree_t *t, avl_node_t *n)
81 height_left = (n->left == NULL) ? 0 : n->left->height;
82 height_right = (n->right == NULL) ? 0 : n->right->height;
84 height_new = 1 + ((height_left > height_right) ? height_left : height_right);
86 if (height_new == n->height)
89 n->height = height_new;
91 cmp = height_right - height_left;
101 l->parent = n->parent;
108 if (l->parent == NULL)
110 assert (t->root == n);
115 assert ((l->parent->left == n) || (l->parent->right == n));
116 if (l->parent->left == n)
119 l->parent->right = l;
131 r->parent = n->parent;
138 if (r->parent == NULL)
140 assert (t->root == n);
145 assert ((r->parent->left == n) || (r->parent->right == n));
146 if (r->parent->left == n)
149 r->parent->right = r;
157 assert ((n == NULL) || (n->parent == NULL)
158 || (n->parent->left == n)
159 || (n->parent->right == n));
160 } /* while (n != NULL) */
161 } /* void rebalance */
163 static avl_iterator_t *avl_create_iterator (avl_tree_t *t, avl_node_t *n)
165 avl_iterator_t *iter;
167 iter = (avl_iterator_t *) malloc (sizeof (avl_iterator_t));
177 void *avl_node_next (avl_tree_t *t, avl_node_t *n)
179 avl_node_t *r; /* return node */
185 else if (n->right == NULL)
191 /* stop if a bigger node is found */
192 if (t->compare (n, r) < 0) /* n < r */
200 while (r->left != NULL)
207 void *avl_node_prev (avl_tree_t *t, avl_node_t *n)
209 avl_node_t *r; /* return node */
215 else if (n->left == NULL)
221 /* stop if a smaller node is found */
222 if (t->compare (n, r) > 0) /* n > r */
230 while (r->right != NULL)
237 static void *_remove (avl_tree_t *t, avl_node_t *n)
241 assert ((t != NULL) && (n != NULL));
245 if ((n->left == NULL) && (n->right == NULL))
247 /* Deleting a leave is easy */
248 if (n->parent == NULL)
250 assert (t->root == n);
255 assert ((n->parent->left == n)
256 || (n->parent->right == n));
257 if (n->parent->left == n)
258 n->parent->left = NULL;
260 n->parent->right = NULL;
262 rebalance (t, n->parent);
269 avl_node_t *r; /* replacement node */
272 assert (n->left != NULL);
273 r = avl_node_prev (t, n);
277 assert (n->right != NULL);
278 r = avl_node_next (t, n);
287 } /* void *_remove */
292 avl_tree_t *avl_create (int (*compare) (const void *, const void *))
296 if ((t = (avl_tree_t *) malloc (sizeof (avl_tree_t))) == NULL)
300 t->compare = compare;
305 void avl_destroy (avl_tree_t *t)
311 int avl_insert (avl_tree_t *t, void *key, void *value)
317 if ((new = (avl_node_t *) malloc (sizeof (avl_node_t))) == NULL)
336 cmp = t->compare (nptr->key, new->key);
345 if (nptr->right == NULL)
357 else /* if (cmp > 0) */
360 if (nptr->left == NULL)
374 assert ((new->parent != NULL)
375 && ((new->parent->left == new)
376 || (new->parent->right == new)));
379 } /* int avl_insert */
381 void *avl_remove (avl_tree_t *t, void *key)
391 return (_remove (t, n));
392 } /* void *avl_remove */
394 void *avl_get (avl_tree_t *t, void *key)
405 avl_iterator_t *avl_get_iterator (avl_tree_t *t)
412 for (n = t->root; n != NULL; n = n->left)
416 return (avl_create_iterator (t, n));
417 } /* avl_iterator_t *avl_get_iterator */
419 void *avl_iterator_next (avl_iterator_t *iter)
423 if ((iter == NULL) || (iter->node == NULL))
426 n = avl_node_next (iter->tree, iter->node);
436 void *avl_iterator_prev (avl_iterator_t *iter)
440 if ((iter == NULL) || (iter->node == NULL))
443 n = avl_node_prev (iter->tree, iter->node);
453 void avl_iterator_destroy (avl_iterator_t *iter)