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 <pthread.h>
42 /*
43 * private data types
44 */
46 struct node;
47 typedef struct node node_t;
49 struct node {
50 sdb_object_t *obj;
52 node_t *parent;
53 node_t *left;
54 node_t *right;
56 size_t height;
57 };
59 #define NODE_NAME(n) ((n) && (n)->obj ? (n)->obj->name : "<nil>")
60 #define NODE_HEIGHT(n) ((n) ? (n)->height : (size_t)0)
61 #define CALC_HEIGHT(n) (SDB_MAX(NODE_HEIGHT((n)->right), \
62 NODE_HEIGHT((n)->left)) + 1)
64 #define BALANCE(n) \
65 ((n) ? (int)NODE_HEIGHT((n)->left) - (int)NODE_HEIGHT((n)->right) : 0)
67 struct sdb_avltree {
68 pthread_rwlock_t lock;
70 node_t *root;
71 size_t size;
72 };
74 struct sdb_avltree_iter {
75 sdb_avltree_t *tree;
76 node_t *node;
77 };
79 /*
80 * private helper functions
81 */
83 static void
84 node_destroy(node_t *n)
85 {
86 sdb_object_deref(n->obj);
87 n->obj = NULL;
88 n->parent = n->left = n->right = NULL;
89 free(n);
90 } /* node_destroy */
92 static node_t *
93 node_create(sdb_object_t *obj)
94 {
95 node_t *n = malloc(sizeof(*n));
96 if (! n)
97 return NULL;
99 sdb_object_ref(obj);
100 n->obj = obj;
101 n->parent = n->left = n->right = NULL;
102 n->height = 1;
103 return n;
104 } /* node_create */
106 static node_t *
107 node_next(node_t *n)
108 {
109 node_t *next;
111 if (! n)
112 return NULL;
114 /* descend into the right tree */
115 if (n->right) {
116 next = n->right;
117 while (next->left)
118 next = next->left;
119 return next;
120 }
122 /* visit the parent if we're in its left tree */
123 if (n->parent && (n->parent->left == n))
124 return n->parent;
126 /* find the parent of the sibling sub-tree on the right */
127 next = n->parent;
128 next = NULL;
129 while (n->parent && (n->parent->right == n)) {
130 n = n->parent;
131 next = n;
132 }
133 if (next)
134 next = next->parent;
135 return next;
136 } /* node_next */
138 static node_t *
139 node_smallest(sdb_avltree_t *tree)
140 {
141 node_t *n;
143 if (! tree)
144 return NULL;
146 n = tree->root;
147 while (n && n->left)
148 n = n->left;
149 return n;
150 } /* node_smallest */
152 static void
153 tree_clear(sdb_avltree_t *tree)
154 {
155 node_t *n;
157 if ((! tree) || (! tree->root))
158 return;
160 /* do a depth-first iteration and delete the leafs */
161 n = tree->root;
162 while (n) {
163 node_t *tmp;
165 if (n->left) {
166 n = n->left;
167 continue;
168 }
169 else if (n->right) {
170 n = n->right;
171 continue;
172 }
174 tmp = n->parent;
175 if (tmp) {
176 if (tmp->left == n)
177 tmp->left = NULL;
178 else
179 tmp->right = NULL;
180 }
182 node_destroy(n);
183 n = tmp;
184 }
186 tree->root = NULL;
187 tree->size = 0;
188 } /* tree_clear */
190 /* Switch node 'n' with its right child, making 'n'
191 * the new left child of that node. */
192 static void
193 rotate_left(sdb_avltree_t *tree, node_t *n)
194 {
195 node_t *n2 = n->right;
196 node_t *c = n2->left;
198 n2->parent = n->parent;
199 if (! n2->parent)
200 tree->root = n2;
201 else if (n2->parent->left == n)
202 n2->parent->left = n2;
203 else
204 n2->parent->right = n2;
206 n2->left = n;
207 n->parent = n2;
209 n->right = c;
210 if (c)
211 c->parent = n;
213 n->height = CALC_HEIGHT(n);
214 n2->height = CALC_HEIGHT(n2);
215 } /* rotate_left */
217 /* Switch node 'n' with its left child, making 'n'
218 * the new right child of that node. */
219 static void
220 rotate_right(sdb_avltree_t *tree, node_t *n)
221 {
222 node_t *n2 = n->left;
223 node_t *c = n2->right;
225 n2->parent = n->parent;
226 if (! n2->parent)
227 tree->root = n2;
228 else if (n2->parent->left == n)
229 n2->parent->left = n2;
230 else
231 n2->parent->right = n2;
233 n2->right = n;
234 n->parent = n2;
236 n->left = c;
237 if (c)
238 c->parent = n;
240 n->height = CALC_HEIGHT(n);
241 n2->height = CALC_HEIGHT(n2);
242 } /* rotate_right */
244 /* Rebalance a tree starting at node 'n' towards the root;
245 * also, update the node heights all the way up to the root. */
246 static void
247 rebalance(sdb_avltree_t *tree, node_t *n)
248 {
249 for ( ; n; n = n->parent) {
250 int bf = BALANCE(n);
252 if (bf == 0)
253 return;
255 if ((-1 <= bf) && (bf <= 1)) {
256 n->height = CALC_HEIGHT(n);
257 continue;
258 }
260 assert((-2 <= bf) && (bf <= 2));
262 if (bf == 2) {
263 if (BALANCE(n->left) == -1)
264 rotate_left(tree, n->left);
265 rotate_right(tree, n);
266 }
267 else {
268 if (BALANCE(n->right) == 1)
269 rotate_right(tree, n->right);
270 rotate_left(tree, n);
271 }
273 /* n was moved downwards; get back to the previous level */
274 n = n->parent;
275 }
276 } /* rebalance */
278 /*
279 * public API
280 */
282 sdb_avltree_t *
283 sdb_avltree_create(void)
284 {
285 sdb_avltree_t *tree;
287 tree = malloc(sizeof(*tree));
288 if (! tree)
289 return NULL;
291 pthread_rwlock_init(&tree->lock, /* attr = */ NULL);
293 tree->root = NULL;
294 tree->size = 0;
295 return tree;
296 } /* sdb_avltree_create */
298 void
299 sdb_avltree_destroy(sdb_avltree_t *tree)
300 {
301 if (! tree)
302 return;
304 pthread_rwlock_wrlock(&tree->lock);
305 tree_clear(tree);
306 pthread_rwlock_unlock(&tree->lock);
307 pthread_rwlock_destroy(&tree->lock);
308 free(tree);
309 } /* sdb_avltree_destroy */
311 void
312 sdb_avltree_clear(sdb_avltree_t *tree)
313 {
314 if (! tree)
315 return;
317 pthread_rwlock_wrlock(&tree->lock);
318 tree_clear(tree);
319 pthread_rwlock_unlock(&tree->lock);
320 } /* sdb_avltree_clear */
322 int
323 sdb_avltree_insert(sdb_avltree_t *tree, sdb_object_t *obj)
324 {
325 node_t *parent;
326 node_t *n;
328 int diff = -1;
330 if (! tree)
331 return -1;
333 n = node_create(obj);
334 if (! n)
335 return -1;
337 pthread_rwlock_wrlock(&tree->lock);
339 if (! tree->root) {
340 tree->root = n;
341 tree->size = 1;
342 pthread_rwlock_unlock(&tree->lock);
343 return 0;
344 }
346 parent = tree->root;
347 while (42) {
348 assert(parent);
350 diff = strcasecmp(obj->name, parent->obj->name);
351 if (! diff) {
352 node_destroy(n);
353 pthread_rwlock_unlock(&tree->lock);
354 return -1;
355 }
357 if (diff < 0) {
358 if (! parent->left) {
359 parent->left = n;
360 break;
361 }
362 parent = parent->left;
363 }
364 else {
365 if (! parent->right) {
366 parent->right = n;
367 break;
368 }
369 parent = parent->right;
370 }
371 }
373 n->parent = parent;
374 ++tree->size;
376 rebalance(tree, parent);
377 pthread_rwlock_unlock(&tree->lock);
378 return 0;
379 } /* sdb_avltree_insert */
381 sdb_object_t *
382 sdb_avltree_lookup(sdb_avltree_t *tree, const char *name)
383 {
384 node_t *n;
386 if (! tree)
387 return NULL;
389 n = tree->root;
390 while (n) {
391 int diff = strcasecmp(n->obj->name, name);
393 if (! diff) {
394 sdb_object_ref(n->obj);
395 return n->obj;
396 }
398 if (diff < 0)
399 n = n->right;
400 else
401 n = n->left;
402 }
403 return NULL;
404 } /* sdb_avltree_lookup_by_name */
406 sdb_avltree_iter_t *
407 sdb_avltree_get_iter(sdb_avltree_t *tree)
408 {
409 sdb_avltree_iter_t *iter;
411 if (! tree)
412 return NULL;
414 iter = malloc(sizeof(*iter));
415 if (! iter)
416 return NULL;
418 pthread_rwlock_rdlock(&tree->lock);
420 iter->tree = tree;
421 iter->node = node_smallest(tree);
423 pthread_rwlock_unlock(&tree->lock);
424 return iter;
425 } /* sdb_avltree_get_iter */
427 void
428 sdb_avltree_iter_destroy(sdb_avltree_iter_t *iter)
429 {
430 if (! iter)
431 return;
433 iter->tree = NULL;
434 iter->node = NULL;
435 free(iter);
436 } /* sdb_avltree_iter_destroy */
438 bool
439 sdb_avltree_iter_has_next(sdb_avltree_iter_t *iter)
440 {
441 if (! iter)
442 return 0;
444 return iter->node != NULL;
445 } /* sdb_avltree_iter_has_next */
447 sdb_object_t *
448 sdb_avltree_iter_get_next(sdb_avltree_iter_t *iter)
449 {
450 node_t *n;
452 if (! iter)
453 return NULL;
455 n = iter->node;
456 iter->node = node_next(iter->node);
457 return n ? n->obj : NULL;
458 } /* sdb_avltree_iter_get_next */
460 sdb_object_t *
461 sdb_avltree_iter_peek_next(sdb_avltree_iter_t *iter)
462 {
463 if ((! iter) || (! iter->node))
464 return NULL;
465 return iter->node->obj;
466 } /* sdb_avltree_iter_peek_next */
468 size_t
469 sdb_avltree_size(sdb_avltree_t *tree)
470 {
471 return tree ? tree->size : 0;
472 } /* sdb_avltree_size */
474 bool
475 sdb_avltree_valid(sdb_avltree_t *tree)
476 {
477 node_t *n;
479 bool status = 1;
480 size_t size = 0;
482 if (! tree)
483 return 1;
485 for (n = node_smallest(tree); n; n = node_next(n)) {
486 int bf = BALANCE(n);
488 if ((bf < -1) || (1 < bf)) {
489 sdb_log(SDB_LOG_ERR, "avltree: Unbalanced node '%s' (bf=%i)",
490 NODE_NAME(n), bf);
491 status = 0;
492 }
494 if (NODE_HEIGHT(n) != n->height) {
495 sdb_log(SDB_LOG_ERR, "avltree: Unexpected height for node '%s': "
496 "%zu; expected: %zu", NODE_NAME(n), n->height,
497 NODE_HEIGHT(n));
498 status = 0;
499 }
501 if (n->parent && (n->parent->left != n) && (n->parent->right != n)) {
502 sdb_log(SDB_LOG_ERR, "avltree: Invalid child nodes for parent of "
503 "node '%s': {left: %s, right: %s}; expected: %s",
504 NODE_NAME(n), NODE_NAME(n->parent->left),
505 NODE_NAME(n->parent->right), NODE_NAME(n));
506 status = 0;
507 }
508 if ((! n->parent) && (n != tree->root)) {
509 sdb_log(SDB_LOG_ERR, "avltree: Non-root node '%s' does not "
510 "have a parent", NODE_NAME(n));
511 status = 0;
512 }
514 ++size;
515 }
517 if (size != tree->size) {
518 sdb_log(SDB_LOG_ERR, "avltree: Invalid size %zu; expected: %zu",
519 tree->size, size);
520 status = 0;
521 }
522 return status;
523 } /* sdb_avltree_valid */
525 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */