1 /*
2 * SysDB - src/utils/avltree.c
3 * Copyright (C) 2014 Sebastian 'tokkee' Harl <sh@tokkee.org>
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
17 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
18 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR
19 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
20 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
21 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
22 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
23 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
24 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
25 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
28 #if HAVE_CONFIG_H
29 # include "config.h"
30 #endif /* HAVE_CONFIG_H */
32 #include "sysdb.h"
33 #include "utils/avltree.h"
34 #include "utils/error.h"
36 #include <assert.h>
38 #include <stdlib.h>
39 #include <string.h>
40 #include <strings.h>
41 #include <pthread.h>
43 /*
44 * private data types
45 */
47 struct node;
48 typedef struct node node_t;
50 struct node {
51 sdb_object_t *obj;
53 node_t *parent;
54 node_t *left;
55 node_t *right;
57 size_t height;
58 };
60 #define NODE_NAME(n) ((n) && (n)->obj ? (n)->obj->name : "<nil>")
61 #define NODE_HEIGHT(n) ((n) ? (n)->height : (size_t)0)
62 #define CALC_HEIGHT(n) (SDB_MAX(NODE_HEIGHT((n)->right), \
63 NODE_HEIGHT((n)->left)) + 1)
65 #define BALANCE(n) \
66 ((n) ? (int)NODE_HEIGHT((n)->left) - (int)NODE_HEIGHT((n)->right) : 0)
68 struct sdb_avltree {
69 pthread_rwlock_t lock;
71 node_t *root;
72 size_t size;
73 };
75 struct sdb_avltree_iter {
76 sdb_avltree_t *tree;
77 node_t *node;
78 };
80 /*
81 * private helper functions
82 */
84 static void
85 node_destroy(node_t *n)
86 {
87 sdb_object_deref(n->obj);
88 n->obj = NULL;
89 n->parent = n->left = n->right = NULL;
90 free(n);
91 } /* node_destroy */
93 static node_t *
94 node_create(sdb_object_t *obj)
95 {
96 node_t *n = malloc(sizeof(*n));
97 if (! n)
98 return NULL;
100 sdb_object_ref(obj);
101 n->obj = obj;
102 n->parent = n->left = n->right = NULL;
103 n->height = 1;
104 return n;
105 } /* node_create */
107 static node_t *
108 node_next(node_t *n)
109 {
110 node_t *next;
112 if (! n)
113 return NULL;
115 /* descend into the right tree */
116 if (n->right) {
117 next = n->right;
118 while (next->left)
119 next = next->left;
120 return next;
121 }
123 /* visit the parent if we're in its left tree */
124 if (n->parent && (n->parent->left == n))
125 return n->parent;
127 /* find the parent of the sibling sub-tree on the right */
128 next = n->parent;
129 next = NULL;
130 while (n->parent && (n->parent->right == n)) {
131 n = n->parent;
132 next = n;
133 }
134 if (next)
135 next = next->parent;
136 return next;
137 } /* node_next */
139 static node_t *
140 node_smallest(sdb_avltree_t *tree)
141 {
142 node_t *n;
144 if (! tree)
145 return NULL;
147 n = tree->root;
148 while (n && n->left)
149 n = n->left;
150 return n;
151 } /* node_smallest */
153 static void
154 tree_clear(sdb_avltree_t *tree)
155 {
156 node_t *n;
158 if ((! tree) || (! tree->root))
159 return;
161 /* do a depth-first iteration and delete the leafs */
162 n = tree->root;
163 while (n) {
164 node_t *tmp;
166 if (n->left) {
167 n = n->left;
168 continue;
169 }
170 else if (n->right) {
171 n = n->right;
172 continue;
173 }
175 tmp = n->parent;
176 if (tmp) {
177 if (tmp->left == n)
178 tmp->left = NULL;
179 else
180 tmp->right = NULL;
181 }
183 node_destroy(n);
184 n = tmp;
185 }
187 tree->root = NULL;
188 tree->size = 0;
189 } /* tree_clear */
191 /* Switch node 'n' with its right child, making 'n'
192 * the new left child of that node. */
193 static void
194 rotate_left(sdb_avltree_t *tree, node_t *n)
195 {
196 node_t *n2 = n->right;
197 node_t *c = n2->left;
199 n2->parent = n->parent;
200 if (! n2->parent)
201 tree->root = n2;
202 else if (n2->parent->left == n)
203 n2->parent->left = n2;
204 else
205 n2->parent->right = n2;
207 n2->left = n;
208 n->parent = n2;
210 n->right = c;
211 if (c)
212 c->parent = n;
214 n->height = CALC_HEIGHT(n);
215 n2->height = CALC_HEIGHT(n2);
216 } /* rotate_left */
218 /* Switch node 'n' with its left child, making 'n'
219 * the new right child of that node. */
220 static void
221 rotate_right(sdb_avltree_t *tree, node_t *n)
222 {
223 node_t *n2 = n->left;
224 node_t *c = n2->right;
226 n2->parent = n->parent;
227 if (! n2->parent)
228 tree->root = n2;
229 else if (n2->parent->left == n)
230 n2->parent->left = n2;
231 else
232 n2->parent->right = n2;
234 n2->right = n;
235 n->parent = n2;
237 n->left = c;
238 if (c)
239 c->parent = n;
241 n->height = CALC_HEIGHT(n);
242 n2->height = CALC_HEIGHT(n2);
243 } /* rotate_right */
245 /* Rebalance a tree starting at node 'n' towards the root;
246 * also, update the node heights all the way up to the root. */
247 static void
248 rebalance(sdb_avltree_t *tree, node_t *n)
249 {
250 for ( ; n; n = n->parent) {
251 int bf = BALANCE(n);
253 if (bf == 0)
254 return;
256 if ((-1 <= bf) && (bf <= 1)) {
257 n->height = CALC_HEIGHT(n);
258 continue;
259 }
261 assert((-2 <= bf) && (bf <= 2));
263 if (bf == 2) {
264 if (BALANCE(n->left) == -1)
265 rotate_left(tree, n->left);
266 rotate_right(tree, n);
267 }
268 else {
269 if (BALANCE(n->right) == 1)
270 rotate_right(tree, n->right);
271 rotate_left(tree, n);
272 }
274 /* n was moved downwards; get back to the previous level */
275 n = n->parent;
276 }
277 } /* rebalance */
279 /*
280 * public API
281 */
283 sdb_avltree_t *
284 sdb_avltree_create(void)
285 {
286 sdb_avltree_t *tree;
288 tree = malloc(sizeof(*tree));
289 if (! tree)
290 return NULL;
292 pthread_rwlock_init(&tree->lock, /* attr = */ NULL);
294 tree->root = NULL;
295 tree->size = 0;
296 return tree;
297 } /* sdb_avltree_create */
299 void
300 sdb_avltree_destroy(sdb_avltree_t *tree)
301 {
302 if (! tree)
303 return;
305 pthread_rwlock_wrlock(&tree->lock);
306 tree_clear(tree);
307 pthread_rwlock_unlock(&tree->lock);
308 pthread_rwlock_destroy(&tree->lock);
309 free(tree);
310 } /* sdb_avltree_destroy */
312 void
313 sdb_avltree_clear(sdb_avltree_t *tree)
314 {
315 if (! tree)
316 return;
318 pthread_rwlock_wrlock(&tree->lock);
319 tree_clear(tree);
320 pthread_rwlock_unlock(&tree->lock);
321 } /* sdb_avltree_clear */
323 int
324 sdb_avltree_insert(sdb_avltree_t *tree, sdb_object_t *obj)
325 {
326 node_t *parent;
327 node_t *n;
329 int diff = -1;
331 if (! tree)
332 return -1;
334 n = node_create(obj);
335 if (! n)
336 return -1;
338 pthread_rwlock_wrlock(&tree->lock);
340 if (! tree->root) {
341 tree->root = n;
342 tree->size = 1;
343 pthread_rwlock_unlock(&tree->lock);
344 return 0;
345 }
347 parent = tree->root;
348 while (42) {
349 assert(parent);
351 diff = strcasecmp(obj->name, parent->obj->name);
352 if (! diff) {
353 node_destroy(n);
354 pthread_rwlock_unlock(&tree->lock);
355 return -1;
356 }
358 if (diff < 0) {
359 if (! parent->left) {
360 parent->left = n;
361 break;
362 }
363 parent = parent->left;
364 }
365 else {
366 if (! parent->right) {
367 parent->right = n;
368 break;
369 }
370 parent = parent->right;
371 }
372 }
374 n->parent = parent;
375 ++tree->size;
377 rebalance(tree, parent);
378 pthread_rwlock_unlock(&tree->lock);
379 return 0;
380 } /* sdb_avltree_insert */
382 sdb_object_t *
383 sdb_avltree_lookup(sdb_avltree_t *tree, const char *name)
384 {
385 node_t *n;
387 if (! tree)
388 return NULL;
390 n = tree->root;
391 while (n) {
392 int diff = strcasecmp(n->obj->name, name);
394 if (! diff) {
395 sdb_object_ref(n->obj);
396 return n->obj;
397 }
399 if (diff < 0)
400 n = n->right;
401 else
402 n = n->left;
403 }
404 return NULL;
405 } /* sdb_avltree_lookup_by_name */
407 sdb_avltree_iter_t *
408 sdb_avltree_get_iter(sdb_avltree_t *tree)
409 {
410 sdb_avltree_iter_t *iter;
412 if (! tree)
413 return NULL;
415 iter = malloc(sizeof(*iter));
416 if (! iter)
417 return NULL;
419 pthread_rwlock_rdlock(&tree->lock);
421 iter->tree = tree;
422 iter->node = node_smallest(tree);
424 pthread_rwlock_unlock(&tree->lock);
425 return iter;
426 } /* sdb_avltree_get_iter */
428 void
429 sdb_avltree_iter_destroy(sdb_avltree_iter_t *iter)
430 {
431 if (! iter)
432 return;
434 iter->tree = NULL;
435 iter->node = NULL;
436 free(iter);
437 } /* sdb_avltree_iter_destroy */
439 bool
440 sdb_avltree_iter_has_next(sdb_avltree_iter_t *iter)
441 {
442 if (! iter)
443 return 0;
445 return iter->node != NULL;
446 } /* sdb_avltree_iter_has_next */
448 sdb_object_t *
449 sdb_avltree_iter_get_next(sdb_avltree_iter_t *iter)
450 {
451 node_t *n;
453 if (! iter)
454 return NULL;
456 n = iter->node;
457 iter->node = node_next(iter->node);
458 return n ? n->obj : NULL;
459 } /* sdb_avltree_iter_get_next */
461 sdb_object_t *
462 sdb_avltree_iter_peek_next(sdb_avltree_iter_t *iter)
463 {
464 if ((! iter) || (! iter->node))
465 return NULL;
466 return iter->node->obj;
467 } /* sdb_avltree_iter_peek_next */
469 size_t
470 sdb_avltree_size(sdb_avltree_t *tree)
471 {
472 return tree ? tree->size : 0;
473 } /* sdb_avltree_size */
475 bool
476 sdb_avltree_valid(sdb_avltree_t *tree)
477 {
478 node_t *n;
480 bool status = 1;
481 size_t size = 0;
483 if (! tree)
484 return 1;
486 for (n = node_smallest(tree); n; n = node_next(n)) {
487 int bf = BALANCE(n);
489 if ((bf < -1) || (1 < bf)) {
490 sdb_log(SDB_LOG_ERR, "avltree: Unbalanced node '%s' (bf=%i)",
491 NODE_NAME(n), bf);
492 status = 0;
493 }
495 if (NODE_HEIGHT(n) != n->height) {
496 sdb_log(SDB_LOG_ERR, "avltree: Unexpected height for node '%s': "
497 "%zu; expected: %zu", NODE_NAME(n), n->height,
498 NODE_HEIGHT(n));
499 status = 0;
500 }
502 if (n->parent && (n->parent->left != n) && (n->parent->right != n)) {
503 sdb_log(SDB_LOG_ERR, "avltree: Invalid child nodes for parent of "
504 "node '%s': {left: %s, right: %s}; expected: %s",
505 NODE_NAME(n), NODE_NAME(n->parent->left),
506 NODE_NAME(n->parent->right), NODE_NAME(n));
507 status = 0;
508 }
509 if ((! n->parent) && (n != tree->root)) {
510 sdb_log(SDB_LOG_ERR, "avltree: Non-root node '%s' does not "
511 "have a parent", NODE_NAME(n));
512 status = 0;
513 }
515 ++size;
516 }
518 if (size != tree->size) {
519 sdb_log(SDB_LOG_ERR, "avltree: Invalid size %zu; expected: %zu",
520 tree->size, size);
521 status = 0;
522 }
523 return status;
524 } /* sdb_avltree_valid */
526 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */