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 <pthread.h>
41 /*
42 * private data types
43 */
45 struct node;
46 typedef struct node node_t;
48 struct node {
49 sdb_object_t *obj;
51 node_t *parent;
52 node_t *left;
53 node_t *right;
55 size_t height;
56 };
58 #define NODE_NAME(n) ((n) && (n)->obj ? (n)->obj->name : "<nil>")
59 #define NODE_HEIGHT(n) ((n) ? (n)->height : (size_t)0)
60 #define CALC_HEIGHT(n) (SDB_MAX(NODE_HEIGHT((n)->right), \
61 NODE_HEIGHT((n)->left)) + 1)
63 #define BALANCE(n) \
64 ((n) ? (int)NODE_HEIGHT((n)->left) - (int)NODE_HEIGHT((n)->right) : 0)
66 struct sdb_avltree {
67 pthread_rwlock_t lock;
69 sdb_object_cmp_cb cmp;
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 n = node_smallest(tree);
159 while (n) {
160 node_t *tmp = node_next(n);
162 node_destroy(n);
163 n = tmp;
164 }
166 tree->root = NULL;
167 tree->size = 0;
168 } /* tree_clear */
170 /* Switch node 'n' with its right child, making 'n'
171 * the new left child of that node. */
172 static void
173 rotate_left(sdb_avltree_t *tree, node_t *n)
174 {
175 node_t *n2 = n->right;
176 node_t *c = n2->left;
178 n2->parent = n->parent;
179 if (! n2->parent)
180 tree->root = n2;
181 else if (n2->parent->left == n)
182 n2->parent->left = n2;
183 else
184 n2->parent->right = n2;
186 n2->left = n;
187 n->parent = n2;
189 n->right = c;
190 if (c)
191 c->parent = n;
193 n->height = CALC_HEIGHT(n);
194 n2->height = CALC_HEIGHT(n2);
195 } /* rotate_left */
197 /* Switch node 'n' with its left child, making 'n'
198 * the new right child of that node. */
199 static void
200 rotate_right(sdb_avltree_t *tree, node_t *n)
201 {
202 node_t *n2 = n->left;
203 node_t *c = n2->right;
205 n2->parent = n->parent;
206 if (! n2->parent)
207 tree->root = n2;
208 else if (n2->parent->left == n)
209 n2->parent->left = n2;
210 else
211 n2->parent->right = n2;
213 n2->right = n;
214 n->parent = n2;
216 n->left = c;
217 if (c)
218 c->parent = n;
220 n->height = CALC_HEIGHT(n);
221 n2->height = CALC_HEIGHT(n2);
222 } /* rotate_right */
224 /* Rebalance a tree starting at node 'n' towards the root;
225 * also, update the node heights all the way up to the root. */
226 static void
227 rebalance(sdb_avltree_t *tree, node_t *n)
228 {
229 for ( ; n; n = n->parent) {
230 int bf = BALANCE(n);
232 if (bf == 0)
233 return;
235 if ((-1 <= bf) && (bf <= 1)) {
236 n->height = CALC_HEIGHT(n);
237 continue;
238 }
240 assert((-2 <= bf) && (bf <= 2));
242 if (bf == 2) {
243 if (BALANCE(n->left) == -1)
244 rotate_left(tree, n->left);
245 rotate_right(tree, n);
246 }
247 else {
248 if (BALANCE(n->right) == 1)
249 rotate_right(tree, n->right);
250 rotate_left(tree, n);
251 }
253 /* n was moved downwards; get back to the previous level */
254 n = n->parent;
255 }
256 } /* rebalance */
258 /*
259 * public API
260 */
262 sdb_avltree_t *
263 sdb_avltree_create(sdb_object_cmp_cb cmp)
264 {
265 sdb_avltree_t *tree;
267 tree = malloc(sizeof(*tree));
268 if (! tree)
269 return NULL;
271 if (! cmp)
272 cmp = sdb_object_cmp_by_name;
274 pthread_rwlock_init(&tree->lock, /* attr = */ NULL);
275 tree->cmp = cmp;
277 tree->root = NULL;
278 tree->size = 0;
279 return tree;
280 } /* sdb_avltree_create */
282 void
283 sdb_avltree_destroy(sdb_avltree_t *tree)
284 {
285 if (! tree)
286 return;
288 pthread_rwlock_wrlock(&tree->lock);
289 tree_clear(tree);
290 pthread_rwlock_unlock(&tree->lock);
291 pthread_rwlock_destroy(&tree->lock);
292 free(tree);
293 } /* sdb_avltree_destroy */
295 void
296 sdb_avltree_clear(sdb_avltree_t *tree)
297 {
298 if (! tree)
299 return;
301 pthread_rwlock_wrlock(&tree->lock);
302 tree_clear(tree);
303 pthread_rwlock_unlock(&tree->lock);
304 } /* sdb_avltree_clear */
306 int
307 sdb_avltree_insert(sdb_avltree_t *tree, sdb_object_t *obj)
308 {
309 node_t *parent;
310 node_t *n;
312 int diff = -1;
314 if (! tree)
315 return -1;
317 n = node_create(obj);
318 if (! n)
319 return -1;
321 pthread_rwlock_wrlock(&tree->lock);
323 if (! tree->root) {
324 tree->root = n;
325 tree->size = 1;
326 pthread_rwlock_unlock(&tree->lock);
327 return 0;
328 }
330 parent = tree->root;
331 while (42) {
332 assert(parent);
334 diff = tree->cmp(obj, parent->obj);
335 if (! diff) {
336 node_destroy(n);
337 pthread_rwlock_unlock(&tree->lock);
338 return -1;
339 }
341 if (diff < 0) {
342 if (! parent->left) {
343 parent->left = n;
344 break;
345 }
346 parent = parent->left;
347 }
348 else {
349 if (! parent->right) {
350 parent->right = n;
351 break;
352 }
353 parent = parent->right;
354 }
355 }
357 n->parent = parent;
358 ++tree->size;
360 rebalance(tree, parent);
361 pthread_rwlock_unlock(&tree->lock);
362 return 0;
363 } /* sdb_avltree_insert */
365 sdb_object_t *
366 sdb_avltree_lookup(sdb_avltree_t *tree, const sdb_object_t *ref)
367 {
368 node_t *n;
370 if (! tree)
371 return NULL;
373 n = tree->root;
374 while (n) {
375 int diff = tree->cmp(n->obj, ref);
377 if (! diff) {
378 sdb_object_ref(n->obj);
379 return n->obj;
380 }
382 if (diff < 0)
383 n = n->right;
384 else
385 n = n->left;
386 }
387 return NULL;
388 } /* sdb_avltree_lookup_by_name */
390 sdb_avltree_iter_t *
391 sdb_avltree_get_iter(sdb_avltree_t *tree)
392 {
393 sdb_avltree_iter_t *iter;
395 if (! tree)
396 return NULL;
398 iter = malloc(sizeof(*iter));
399 if (! iter)
400 return NULL;
402 pthread_rwlock_rdlock(&tree->lock);
404 iter->tree = tree;
405 iter->node = node_smallest(tree);
407 pthread_rwlock_unlock(&tree->lock);
408 return iter;
409 } /* sdb_avltree_get_iter */
411 void
412 sdb_avltree_iter_destroy(sdb_avltree_iter_t *iter)
413 {
414 if (! iter)
415 return;
417 iter->tree = NULL;
418 iter->node = NULL;
419 free(iter);
420 } /* sdb_avltree_iter_destroy */
422 _Bool
423 sdb_avltree_iter_has_next(sdb_avltree_iter_t *iter)
424 {
425 if (! iter)
426 return 0;
428 return iter->node != NULL;
429 } /* sdb_avltree_iter_has_next */
431 sdb_object_t *
432 sdb_avltree_iter_get_next(sdb_avltree_iter_t *iter)
433 {
434 node_t *n;
436 if (! iter)
437 return NULL;
439 n = iter->node;
440 iter->node = node_next(iter->node);
441 return n ? n->obj : NULL;
442 } /* sdb_avltree_iter_get_next */
444 size_t
445 sdb_avltree_size(sdb_avltree_t *tree)
446 {
447 return tree ? tree->size : 0;
448 } /* sdb_avltree_size */
450 _Bool
451 sdb_avltree_valid(sdb_avltree_t *tree)
452 {
453 node_t *n;
455 _Bool status = 1;
456 size_t size = 0;
458 if (! tree)
459 return 1;
461 for (n = node_smallest(tree); n; n = node_next(n)) {
462 int bf = BALANCE(n);
464 if ((bf < -1) || (1 < bf)) {
465 sdb_log(SDB_LOG_ERR, "avltree: Unbalanced node '%s' (bf=%i)",
466 NODE_NAME(n), bf);
467 status = 0;
468 }
470 if (NODE_HEIGHT(n) != n->height) {
471 sdb_log(SDB_LOG_ERR, "avltree: Unexpected height for node '%s': "
472 "%zu; expected: %zu", NODE_NAME(n), n->height,
473 NODE_HEIGHT(n));
474 status = 0;
475 }
477 if (n->parent && (n->parent->left != n) && (n->parent->right != n)) {
478 sdb_log(SDB_LOG_ERR, "avltree: Invalid child nodes for parent of "
479 "node '%s': {left: %s, right: %s}; expected: %s",
480 NODE_NAME(n), NODE_NAME(n->parent->left),
481 NODE_NAME(n->parent->right), NODE_NAME(n));
482 status = 0;
483 }
484 if ((! n->parent) && (n != tree->root)) {
485 sdb_log(SDB_LOG_ERR, "avltree: Non-root node '%s' does not "
486 "have a parent", NODE_NAME(n));
487 status = 0;
488 }
490 ++size;
491 }
493 if (size != tree->size) {
494 sdb_log(SDB_LOG_ERR, "avltree: Invalid size %zu; expected: %zu",
495 tree->size, size);
496 status = 0;
497 }
498 return status;
499 } /* sdb_avltree_valid */
501 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */