7397a34fdbb56dfd54d4db07c82f797cf3d93b76
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 n = node_smallest(tree);
158 while (n) {
159 node_t *tmp = node_next(n);
161 node_destroy(n);
162 n = tmp;
163 }
165 tree->root = NULL;
166 tree->size = 0;
167 } /* tree_clear */
169 /* Switch node 'n' with its right child, making 'n'
170 * the new left child of that node. */
171 static void
172 rotate_left(sdb_avltree_t *tree, node_t *n)
173 {
174 node_t *n2 = n->right;
175 node_t *c = n2->left;
177 n2->parent = n->parent;
178 if (! n2->parent)
179 tree->root = n2;
180 else if (n2->parent->left == n)
181 n2->parent->left = n2;
182 else
183 n2->parent->right = n2;
185 n2->left = n;
186 n->parent = n2;
188 n->right = c;
189 if (c)
190 c->parent = n;
192 n->height = CALC_HEIGHT(n);
193 n2->height = CALC_HEIGHT(n2);
194 } /* rotate_left */
196 /* Switch node 'n' with its left child, making 'n'
197 * the new right child of that node. */
198 static void
199 rotate_right(sdb_avltree_t *tree, node_t *n)
200 {
201 node_t *n2 = n->left;
202 node_t *c = n2->right;
204 n2->parent = n->parent;
205 if (! n2->parent)
206 tree->root = n2;
207 else if (n2->parent->left == n)
208 n2->parent->left = n2;
209 else
210 n2->parent->right = n2;
212 n2->right = n;
213 n->parent = n2;
215 n->left = c;
216 if (c)
217 c->parent = n;
219 n->height = CALC_HEIGHT(n);
220 n2->height = CALC_HEIGHT(n2);
221 } /* rotate_right */
223 /* Rebalance a tree starting at node 'n' towards the root;
224 * also, update the node heights all the way up to the root. */
225 static void
226 rebalance(sdb_avltree_t *tree, node_t *n)
227 {
228 for ( ; n; n = n->parent) {
229 int bf = BALANCE(n);
231 if (bf == 0)
232 return;
234 if ((-1 <= bf) && (bf <= 1)) {
235 n->height = CALC_HEIGHT(n);
236 continue;
237 }
239 assert((-2 <= bf) && (bf <= 2));
241 if (bf == 2) {
242 if (BALANCE(n->left) == -1)
243 rotate_left(tree, n->left);
244 rotate_right(tree, n);
245 }
246 else {
247 if (BALANCE(n->right) == 1)
248 rotate_right(tree, n->right);
249 rotate_left(tree, n);
250 }
252 /* n was moved downwards; get back to the previous level */
253 n = n->parent;
254 }
255 } /* rebalance */
257 /*
258 * public API
259 */
261 sdb_avltree_t *
262 sdb_avltree_create(void)
263 {
264 sdb_avltree_t *tree;
266 tree = malloc(sizeof(*tree));
267 if (! tree)
268 return NULL;
270 pthread_rwlock_init(&tree->lock, /* attr = */ NULL);
272 tree->root = NULL;
273 tree->size = 0;
274 return tree;
275 } /* sdb_avltree_create */
277 void
278 sdb_avltree_destroy(sdb_avltree_t *tree)
279 {
280 if (! tree)
281 return;
283 pthread_rwlock_wrlock(&tree->lock);
284 tree_clear(tree);
285 pthread_rwlock_unlock(&tree->lock);
286 pthread_rwlock_destroy(&tree->lock);
287 free(tree);
288 } /* sdb_avltree_destroy */
290 void
291 sdb_avltree_clear(sdb_avltree_t *tree)
292 {
293 if (! tree)
294 return;
296 pthread_rwlock_wrlock(&tree->lock);
297 tree_clear(tree);
298 pthread_rwlock_unlock(&tree->lock);
299 } /* sdb_avltree_clear */
301 int
302 sdb_avltree_insert(sdb_avltree_t *tree, sdb_object_t *obj)
303 {
304 node_t *parent;
305 node_t *n;
307 int diff = -1;
309 if (! tree)
310 return -1;
312 n = node_create(obj);
313 if (! n)
314 return -1;
316 pthread_rwlock_wrlock(&tree->lock);
318 if (! tree->root) {
319 tree->root = n;
320 tree->size = 1;
321 pthread_rwlock_unlock(&tree->lock);
322 return 0;
323 }
325 parent = tree->root;
326 while (42) {
327 assert(parent);
329 diff = strcasecmp(obj->name, parent->obj->name);
330 if (! diff) {
331 node_destroy(n);
332 pthread_rwlock_unlock(&tree->lock);
333 return -1;
334 }
336 if (diff < 0) {
337 if (! parent->left) {
338 parent->left = n;
339 break;
340 }
341 parent = parent->left;
342 }
343 else {
344 if (! parent->right) {
345 parent->right = n;
346 break;
347 }
348 parent = parent->right;
349 }
350 }
352 n->parent = parent;
353 ++tree->size;
355 rebalance(tree, parent);
356 pthread_rwlock_unlock(&tree->lock);
357 return 0;
358 } /* sdb_avltree_insert */
360 sdb_object_t *
361 sdb_avltree_lookup(sdb_avltree_t *tree, const char *name)
362 {
363 node_t *n;
365 if (! tree)
366 return NULL;
368 n = tree->root;
369 while (n) {
370 int diff = strcasecmp(n->obj->name, name);
372 if (! diff) {
373 sdb_object_ref(n->obj);
374 return n->obj;
375 }
377 if (diff < 0)
378 n = n->right;
379 else
380 n = n->left;
381 }
382 return NULL;
383 } /* sdb_avltree_lookup_by_name */
385 sdb_avltree_iter_t *
386 sdb_avltree_get_iter(sdb_avltree_t *tree)
387 {
388 sdb_avltree_iter_t *iter;
390 if (! tree)
391 return NULL;
393 iter = malloc(sizeof(*iter));
394 if (! iter)
395 return NULL;
397 pthread_rwlock_rdlock(&tree->lock);
399 iter->tree = tree;
400 iter->node = node_smallest(tree);
402 pthread_rwlock_unlock(&tree->lock);
403 return iter;
404 } /* sdb_avltree_get_iter */
406 void
407 sdb_avltree_iter_destroy(sdb_avltree_iter_t *iter)
408 {
409 if (! iter)
410 return;
412 iter->tree = NULL;
413 iter->node = NULL;
414 free(iter);
415 } /* sdb_avltree_iter_destroy */
417 _Bool
418 sdb_avltree_iter_has_next(sdb_avltree_iter_t *iter)
419 {
420 if (! iter)
421 return 0;
423 return iter->node != NULL;
424 } /* sdb_avltree_iter_has_next */
426 sdb_object_t *
427 sdb_avltree_iter_get_next(sdb_avltree_iter_t *iter)
428 {
429 node_t *n;
431 if (! iter)
432 return NULL;
434 n = iter->node;
435 iter->node = node_next(iter->node);
436 return n ? n->obj : NULL;
437 } /* sdb_avltree_iter_get_next */
439 size_t
440 sdb_avltree_size(sdb_avltree_t *tree)
441 {
442 return tree ? tree->size : 0;
443 } /* sdb_avltree_size */
445 _Bool
446 sdb_avltree_valid(sdb_avltree_t *tree)
447 {
448 node_t *n;
450 _Bool status = 1;
451 size_t size = 0;
453 if (! tree)
454 return 1;
456 for (n = node_smallest(tree); n; n = node_next(n)) {
457 int bf = BALANCE(n);
459 if ((bf < -1) || (1 < bf)) {
460 sdb_log(SDB_LOG_ERR, "avltree: Unbalanced node '%s' (bf=%i)",
461 NODE_NAME(n), bf);
462 status = 0;
463 }
465 if (NODE_HEIGHT(n) != n->height) {
466 sdb_log(SDB_LOG_ERR, "avltree: Unexpected height for node '%s': "
467 "%zu; expected: %zu", NODE_NAME(n), n->height,
468 NODE_HEIGHT(n));
469 status = 0;
470 }
472 if (n->parent && (n->parent->left != n) && (n->parent->right != n)) {
473 sdb_log(SDB_LOG_ERR, "avltree: Invalid child nodes for parent of "
474 "node '%s': {left: %s, right: %s}; expected: %s",
475 NODE_NAME(n), NODE_NAME(n->parent->left),
476 NODE_NAME(n->parent->right), NODE_NAME(n));
477 status = 0;
478 }
479 if ((! n->parent) && (n != tree->root)) {
480 sdb_log(SDB_LOG_ERR, "avltree: Non-root node '%s' does not "
481 "have a parent", NODE_NAME(n));
482 status = 0;
483 }
485 ++size;
486 }
488 if (size != tree->size) {
489 sdb_log(SDB_LOG_ERR, "avltree: Invalid size %zu; expected: %zu",
490 tree->size, size);
491 status = 0;
492 }
493 return status;
494 } /* sdb_avltree_valid */
496 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */