c3e83ae8a5ad7c66419996b5d87dba917401fad4
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, 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 cmp = height_right - height_left;
90 if (cmp < -1)
91 {
92 avl_node_t *l;
93 avl_node_t *lr;
95 l = n->left;
96 lr = l->right;
98 l->right = n;
99 l->parent = n->parent;
100 n->parent = l;
101 n->left = lr;
103 if (n == t->root)
104 t->root = l;
105 }
106 else if (cmp > 1)
107 {
108 avl_node_t *r;
109 avl_node_t *rl;
111 r = n->right;
112 rl = r->left;
114 r->left = n;
115 r->parent = n->parent;
116 n->parent = r;
117 n->right = rl;
119 if (n == t->root)
120 t->root = r;
121 }
122 else
123 {
124 n = n->parent;
125 }
126 } /* while (n != NULL) */
127 } /* void rebalance */
129 static avl_iterator_t *avl_create_iterator (avl_tree_t *t, avl_node_t *n)
130 {
131 avl_iterator_t *iter;
133 iter = (avl_iterator_t *) malloc (sizeof (avl_iterator_t));
134 if (iter == NULL)
135 return (NULL);
137 iter->tree = t;
138 iter->node = n;
140 return (iter);
141 }
143 void *avl_node_next (avl_tree_t *t, avl_node_t *n)
144 {
145 avl_node_t *r; /* return node */
147 if (n == NULL)
148 {
149 return (NULL);
150 }
151 else if (n->right == NULL)
152 {
154 r = n->parent;
155 while (r != NULL)
156 {
157 /* stop if a bigger node is found */
158 if (t->compare (n, r) < 0) /* n < r */
159 break;
160 r = r->parent;
161 }
162 }
163 else
164 {
165 r = n->right;
166 while (r->left != NULL)
167 r = r->left;
168 }
170 return (r);
171 }
173 void *avl_node_prev (avl_tree_t *t, avl_node_t *n)
174 {
175 avl_node_t *r; /* return node */
177 if (n == NULL)
178 {
179 return (NULL);
180 }
181 else if (n->left == NULL)
182 {
184 r = n->parent;
185 while (r != NULL)
186 {
187 /* stop if a smaller node is found */
188 if (t->compare (n, r) > 0) /* n > r */
189 break;
190 r = r->parent;
191 }
192 }
193 else
194 {
195 r = n->left;
196 while (r->right != NULL)
197 r = r->right;
198 }
200 return (r);
201 }
203 static void *remove (avl_tree_t *t, avl_node_t *n)
204 {
205 void *ret;
207 assert ((t != NULL) && (n != NULL));
209 ret = n->value;
211 if ((n->left == NULL) && (n->right == NULL))
212 {
213 /* Deleting a leave is easy */
214 if (n->parent == NULL)
215 {
216 assert (t->root == n);
217 t->root = NULL;
218 }
219 else
220 {
221 assert ((n->parent->left == n)
222 || (n->parent->right == n));
223 if (n->parent->left == n)
224 n->parent->left = NULL;
225 else
226 n->parent->right = NULL;
227 }
229 free_node (n);
230 }
231 else
232 {
233 avl_node_t *r; /* replacement node */
234 if (BALANCE (n) < 0)
235 {
236 assert (n->left != NULL);
237 r = avl_node_prev (t, n);
238 }
239 else
240 {
241 assert (n->right != NULL);
242 r = avl_node_next (t, n);
243 }
244 n->key = r->key;
245 n->value = r->value;
247 remove (t, r);
248 }
250 return (ret);
251 } /* void *remove */
253 /*
254 * public functions
255 */
256 avl_tree_t *avl_create (int (*compare) (const void *, const void *))
257 {
258 avl_tree_t *t;
260 if ((t = (avl_tree_t *) malloc (sizeof (avl_tree_t))) == NULL)
261 return (NULL);
263 t->root = NULL;
264 t->compare = compare;
266 return (t);
267 }
269 void avl_destroy (avl_tree_t *t)
270 {
271 free_node (t->root);
272 free (t);
273 }
275 int avl_insert (avl_tree_t *t, void *key, void *value)
276 {
277 avl_node_t *new;
278 avl_node_t *nptr;
279 int cmp;
281 if ((new = (avl_node_t *) malloc (sizeof (avl_node_t))) == NULL)
282 return (-1);
284 new->key = key;
285 new->value = value;
286 new->height = 0;
287 new->left = NULL;
288 new->right = NULL;
290 if (t->root == NULL)
291 {
292 new->parent = NULL;
293 t->root = new;
294 return (0);
295 }
297 nptr = t->root;
298 while (42)
299 {
300 cmp = t->compare (nptr->key, new->key);
301 if (cmp == 0)
302 {
303 free_node (new);
304 return (-1);
305 }
306 else if (cmp < 0)
307 {
308 /* nptr < new */
309 if (nptr->right == NULL)
310 {
311 nptr->right = new;
312 new->parent = nptr;
313 nptr = NULL;
314 break;
315 }
316 else
317 {
318 nptr = nptr->right;
319 }
320 }
321 else /* if (cmp > 0) */
322 {
323 /* nptr > new */
324 if (nptr->left == NULL)
325 {
326 nptr->left = new;
327 new->parent = nptr;
328 nptr = NULL;
329 break;
330 }
331 else
332 {
333 nptr = nptr->left;
334 }
335 }
336 } /* while (42) */
338 rebalance (t, new->parent);
340 return (0);
341 } /* int avl_insert */
343 void *avl_remove (avl_tree_t *t, void *key)
344 {
345 avl_node_t *n;
347 assert (t != NULL);
349 n = search (t, key);
350 if (n == NULL)
351 return (NULL);
353 return (remove (t, n));
354 } /* void *avl_remove */
356 void *avl_get (avl_tree_t *t, void *key)
357 {
358 avl_node_t *n;
360 n = search (t, key);
361 if (n == NULL)
362 return (NULL);
364 return (n->value);
365 }
367 avl_iterator_t *avl_get_iterator (avl_tree_t *t)
368 {
369 avl_node_t *n;
371 if (t == NULL)
372 return (NULL);
374 for (n = t->root; n != NULL; n = n->left)
375 if (n->left == NULL)
376 break;
378 return (avl_create_iterator (t, n));
379 } /* avl_iterator_t *avl_get_iterator */
381 void *avl_iterator_next (avl_iterator_t *iter)
382 {
383 avl_node_t *n;
385 if ((iter == NULL) || (iter->node == NULL))
386 return (NULL);
388 n = avl_node_next (iter->tree, iter->node);
390 if (n == NULL)
391 return (NULL);
393 iter->node = n;
394 return (n);
396 }
398 void *avl_iterator_prev (avl_iterator_t *iter)
399 {
400 avl_node_t *n;
402 if ((iter == NULL) || (iter->node == NULL))
403 return (NULL);
405 n = avl_node_prev (iter->tree, iter->node);
407 if (n == NULL)
408 return (NULL);
410 iter->node = n;
411 return (n);
413 }
415 void avl_iterator_destroy (avl_iterator_t *iter)
416 {
417 free (iter);
418 }