f2c5d06f988aac752ccaa7f0085c56aa04c46b74
1 #include <stdlib.h>
2 #include <assert.h>
4 #include "utils_avltree.h"
6 #define BALANCE(n) ((((n)->right == NULL) ? 0 : (n)->right->height) \
7 - (((n)->left == NULL) ? 0 : (n)->left->height))
9 /*
10 * private data types
11 */
12 struct avl_node_s
13 {
14 void *key;
15 void *value;
17 int height;
18 struct avl_node_s *left;
19 struct avl_node_s *right;
20 struct avl_node_s *parent;
21 };
22 typedef struct avl_node_s avl_node_t;
24 struct avl_tree_s
25 {
26 avl_node_t *root;
27 int (*compare) (const void *, const void *);
28 };
30 struct avl_iterator_s
31 {
32 avl_tree_t *tree;
33 avl_node_t *node;
34 };
36 /*
37 * private functions
38 */
39 static void free_node (avl_node_t *n)
40 {
41 if (n == NULL)
42 return;
44 if (n->left != NULL)
45 free_node (n->left);
46 if (n->right != NULL)
47 free_node (n->right);
49 free (n);
50 }
52 static avl_node_t *search (avl_tree_t *t, const void *key)
53 {
54 avl_node_t *n;
55 int cmp;
57 n = t->root;
58 while (n != NULL)
59 {
60 cmp = t->compare (key, n->key);
61 if (cmp == 0)
62 return (n);
63 else if (cmp < 0)
64 n = n->left;
65 else
66 n = n->right;
67 }
69 return (NULL);
70 }
72 static void rebalance (avl_tree_t *t, avl_node_t *n)
73 {
74 int height_left;
75 int height_right;
76 int height_new;
77 int cmp;
79 while (n != NULL)
80 {
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)
87 break;
89 /* FIXME */
90 if (n->left != NULL)
91 {
92 cmp = BALANCE(n->left);
93 assert ((cmp >= -1) && (cmp <= 1));
94 }
95 if (n->right != NULL)
96 {
97 cmp = BALANCE(n->right);
98 assert ((cmp >= -1) && (cmp <= 1));
99 }
101 n->height = height_new;
103 cmp = height_right - height_left;
104 if (cmp < -1)
105 {
106 avl_node_t *l;
107 avl_node_t *lr;
109 l = n->left;
110 lr = l->right;
112 l->right = n;
113 l->parent = n->parent;
114 n->parent = l;
115 n->left = lr;
117 if (lr != NULL)
118 lr->parent = n;
120 if (l->parent == NULL)
121 {
122 assert (t->root == n);
123 t->root = l;
124 }
125 else
126 {
127 assert ((l->parent->left == n) || (l->parent->right == n));
128 if (l->parent->left == n)
129 l->parent->left = l;
130 else
131 l->parent->right = l;
132 }
134 height_left = (n->left == NULL) ? 0 : n->left->height;
135 height_right = (n->right == NULL) ? 0 : n->right->height;
136 height_new = 1 + ((height_left > height_right) ? height_left : height_right);
137 cmp = BALANCE(n);
138 assert (height_new < n->height);
139 assert ((cmp >= -1) || (cmp <= 1));
140 n->height = height_new;
142 height_left = (l->left == NULL) ? 0 : l->left->height;
143 height_right = (l->right == NULL) ? 0 : l->right->height;
144 height_new = 1 + ((height_left > height_right) ? height_left : height_right);
145 cmp = BALANCE(l);
146 assert (height_new >= l->height);
147 assert ((cmp >= -1) || (cmp <= 1));
148 l->height = height_new;
150 n = l->parent;
151 }
152 else if (cmp > 1)
153 {
154 avl_node_t *r;
155 avl_node_t *rl;
157 r = n->right;
158 rl = r->left;
160 r->left = n;
161 r->parent = n->parent;
162 n->parent = r;
163 n->right = rl;
165 if (rl != NULL)
166 rl->parent = n;
168 if (r->parent == NULL)
169 {
170 assert (t->root == n);
171 t->root = r;
172 }
173 else
174 {
175 assert ((r->parent->left == n) || (r->parent->right == n));
176 if (r->parent->left == n)
177 r->parent->left = r;
178 else
179 r->parent->right = r;
180 }
182 height_left = (n->left == NULL) ? 0 : n->left->height;
183 height_right = (n->right == NULL) ? 0 : n->right->height;
184 height_new = 1 + ((height_left > height_right) ? height_left : height_right);
185 cmp = BALANCE(n);
186 assert (height_new < n->height);
187 assert ((cmp >= -1) || (cmp <= 1));
188 n->height = height_new;
190 height_left = (r->left == NULL) ? 0 : r->left->height;
191 height_right = (r->right == NULL) ? 0 : r->right->height;
192 height_new = 1 + ((height_left > height_right) ? height_left : height_right);
193 cmp = BALANCE(r);
194 assert (height_new >= r->height);
195 assert ((cmp >= -1) || (cmp <= 1));
196 r->height = height_new;
198 n = r->parent;
199 }
200 else
201 {
202 n = n->parent;
203 }
205 assert ((n == NULL) || (n->parent == NULL)
206 || (n->parent->left == n)
207 || (n->parent->right == n));
208 } /* while (n != NULL) */
209 } /* void rebalance */
211 static avl_iterator_t *avl_create_iterator (avl_tree_t *t, avl_node_t *n)
212 {
213 avl_iterator_t *iter;
215 iter = (avl_iterator_t *) malloc (sizeof (avl_iterator_t));
216 if (iter == NULL)
217 return (NULL);
219 iter->tree = t;
220 iter->node = n;
222 return (iter);
223 }
225 void *avl_node_next (avl_tree_t *t, avl_node_t *n)
226 {
227 avl_node_t *r; /* return node */
229 if (n == NULL)
230 {
231 return (NULL);
232 }
233 else if (n->right == NULL)
234 {
236 r = n->parent;
237 while (r != NULL)
238 {
239 /* stop if a bigger node is found */
240 if (t->compare (n, r) < 0) /* n < r */
241 break;
242 r = r->parent;
243 }
244 }
245 else
246 {
247 r = n->right;
248 while (r->left != NULL)
249 r = r->left;
250 }
252 return (r);
253 }
255 void *avl_node_prev (avl_tree_t *t, avl_node_t *n)
256 {
257 avl_node_t *r; /* return node */
259 if (n == NULL)
260 {
261 return (NULL);
262 }
263 else if (n->left == NULL)
264 {
266 r = n->parent;
267 while (r != NULL)
268 {
269 /* stop if a smaller node is found */
270 if (t->compare (n, r) > 0) /* n > r */
271 break;
272 r = r->parent;
273 }
274 }
275 else
276 {
277 r = n->left;
278 while (r->right != NULL)
279 r = r->right;
280 }
282 return (r);
283 }
285 static int _remove (avl_tree_t *t, avl_node_t *n)
286 {
287 assert ((t != NULL) && (n != NULL));
289 if ((n->left == NULL) && (n->right == NULL))
290 {
291 /* Deleting a leave is easy */
292 if (n->parent == NULL)
293 {
294 assert (t->root == n);
295 t->root = NULL;
296 }
297 else
298 {
299 assert ((n->parent->left == n)
300 || (n->parent->right == n));
301 if (n->parent->left == n)
302 n->parent->left = NULL;
303 else
304 n->parent->right = NULL;
306 rebalance (t, n->parent);
307 }
309 free_node (n);
310 }
311 else
312 {
313 avl_node_t *r; /* replacement node */
314 if (BALANCE (n) < 0)
315 {
316 assert (n->left != NULL);
317 r = avl_node_prev (t, n);
318 }
319 else
320 {
321 assert (n->right != NULL);
322 r = avl_node_next (t, n);
323 }
324 n->key = r->key;
325 n->value = r->value;
327 _remove (t, r);
328 }
330 return (0);
331 } /* void *_remove */
333 /*
334 * public functions
335 */
336 avl_tree_t *avl_create (int (*compare) (const void *, const void *))
337 {
338 avl_tree_t *t;
340 if ((t = (avl_tree_t *) malloc (sizeof (avl_tree_t))) == NULL)
341 return (NULL);
343 t->root = NULL;
344 t->compare = compare;
346 return (t);
347 }
349 void avl_destroy (avl_tree_t *t)
350 {
351 free_node (t->root);
352 free (t);
353 }
355 int avl_insert (avl_tree_t *t, void *key, void *value)
356 {
357 avl_node_t *new;
358 avl_node_t *nptr;
359 int cmp;
361 if ((new = (avl_node_t *) malloc (sizeof (avl_node_t))) == NULL)
362 return (-1);
364 new->key = key;
365 new->value = value;
366 new->height = 1;
367 new->left = NULL;
368 new->right = NULL;
370 if (t->root == NULL)
371 {
372 new->parent = NULL;
373 t->root = new;
374 return (0);
375 }
377 nptr = t->root;
378 while (42)
379 {
380 cmp = t->compare (nptr->key, new->key);
381 if (cmp == 0)
382 {
383 free_node (new);
384 return (-1);
385 }
386 else if (cmp < 0)
387 {
388 /* nptr < new */
389 if (nptr->right == NULL)
390 {
391 nptr->right = new;
392 new->parent = nptr;
393 nptr = NULL;
394 break;
395 }
396 else
397 {
398 nptr = nptr->right;
399 }
400 }
401 else /* if (cmp > 0) */
402 {
403 /* nptr > new */
404 if (nptr->left == NULL)
405 {
406 nptr->left = new;
407 new->parent = nptr;
408 nptr = NULL;
409 break;
410 }
411 else
412 {
413 nptr = nptr->left;
414 }
415 }
416 } /* while (42) */
418 assert ((new->parent != NULL)
419 && ((new->parent->left == new)
420 || (new->parent->right == new)));
422 return (0);
423 } /* int avl_insert */
425 int avl_remove (avl_tree_t *t, void *key, void **rkey, void **rvalue)
426 {
427 avl_node_t *n;
429 assert (t != NULL);
431 n = search (t, key);
432 if (n == NULL)
433 return (-1);
435 if (rkey != NULL)
436 *rkey = n->key;
437 if (rvalue != NULL)
438 *rvalue = n->value;
440 return (_remove (t, n));
441 } /* void *avl_remove */
443 int avl_get (avl_tree_t *t, const void *key, void **value)
444 {
445 avl_node_t *n;
447 assert (value != NULL);
449 n = search (t, key);
450 if (n == NULL)
451 return (-1);
453 *value = n->value;
455 return (0);
456 }
458 avl_iterator_t *avl_get_iterator (avl_tree_t *t)
459 {
460 avl_node_t *n;
462 if (t == NULL)
463 return (NULL);
465 for (n = t->root; n != NULL; n = n->left)
466 if (n->left == NULL)
467 break;
469 return (avl_create_iterator (t, n));
470 } /* avl_iterator_t *avl_get_iterator */
472 void *avl_iterator_next (avl_iterator_t *iter)
473 {
474 avl_node_t *n;
476 if ((iter == NULL) || (iter->node == NULL))
477 return (NULL);
479 n = avl_node_next (iter->tree, iter->node);
481 if (n == NULL)
482 return (NULL);
484 iter->node = n;
485 return (n);
487 }
489 void *avl_iterator_prev (avl_iterator_t *iter)
490 {
491 avl_node_t *n;
493 if ((iter == NULL) || (iter->node == NULL))
494 return (NULL);
496 n = avl_node_prev (iter->tree, iter->node);
498 if (n == NULL)
499 return (NULL);
501 iter->node = n;
502 return (n);
504 }
506 void avl_iterator_destroy (avl_iterator_t *iter)
507 {
508 free (iter);
509 }