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"
35 #include <assert.h>
37 #include <stdlib.h>
38 #include <pthread.h>
40 /*
41 * private data types
42 */
44 struct node;
45 typedef struct node node_t;
47 struct node {
48 sdb_object_t *obj;
50 node_t *parent;
51 node_t *left;
52 node_t *right;
54 size_t height;
55 };
57 #define NODE_HEIGHT(n) ((n) ? (n)->height : (size_t)0)
58 #define CALC_HEIGHT(n) (SDB_MAX(NODE_HEIGHT((n)->right), \
59 NODE_HEIGHT((n)->left)) + 1)
61 #define BALANCE(n) \
62 ((n) ? (int)NODE_HEIGHT((n)->left) - (int)NODE_HEIGHT((n)->right) : 0)
64 struct sdb_avltree {
65 pthread_rwlock_t lock;
67 sdb_object_cmp_cb cmp;
69 node_t *root;
70 size_t size;
71 };
73 struct sdb_avltree_iter {
74 sdb_avltree_t *tree;
75 node_t *node;
76 };
78 /*
79 * private helper functions
80 */
82 static void
83 node_destroy(node_t *n)
84 {
85 sdb_object_deref(n->obj);
86 n->obj = NULL;
87 n->parent = n->left = n->right = NULL;
88 free(n);
89 } /* node_destroy */
91 static node_t *
92 node_create(sdb_object_t *obj)
93 {
94 node_t *n = malloc(sizeof(*n));
95 if (! n)
96 return NULL;
98 sdb_object_ref(obj);
99 n->obj = obj;
100 n->parent = n->left = n->right = NULL;
101 n->height = 1;
102 return n;
103 } /* node_create */
105 static node_t *
106 node_next(node_t *n)
107 {
108 node_t *next;
110 if (! n)
111 return NULL;
113 /* descend into the right tree */
114 if (n->right) {
115 next = n->right;
116 while (next->left)
117 next = next->left;
118 return next;
119 }
121 /* visit the parent if we're in its left tree */
122 if (n->parent && (n->parent->left == n))
123 return n->parent;
125 /* find the parent of the sibling sub-tree on the right */
126 next = n->parent;
127 next = NULL;
128 while (n->parent && (n->parent->right == n)) {
129 n = n->parent;
130 next = n;
131 }
132 if (next)
133 next = next->parent;
134 return next;
135 } /* node_next */
137 static node_t *
138 node_smallest(sdb_avltree_t *tree)
139 {
140 node_t *n;
142 if (! tree)
143 return NULL;
145 n = tree->root;
146 while (n && n->left)
147 n = n->left;
148 return n;
149 } /* node_smallest */
151 static void
152 tree_clear(sdb_avltree_t *tree)
153 {
154 node_t *n;
156 n = node_smallest(tree);
157 while (n) {
158 node_t *tmp = node_next(n);
160 node_destroy(n);
161 n = tmp;
162 }
164 tree->root = NULL;
165 tree->size = 0;
166 } /* tree_clear */
168 /* Switch node 'n' with its right child, making 'n'
169 * the new left child of that node. */
170 static void
171 rotate_left(sdb_avltree_t *tree, node_t *n)
172 {
173 node_t *n2 = n->right;
174 node_t *c = n2->left;
176 n2->parent = n->parent;
177 if (! n2->parent)
178 tree->root = n2;
179 else if (n2->parent->left == n)
180 n2->parent->left = n2;
181 else
182 n2->parent->right = n2;
184 n2->left = n;
185 n->parent = n2;
187 n->right = c;
188 if (c)
189 c->parent = n;
191 n->height = CALC_HEIGHT(n);
192 n2->height = CALC_HEIGHT(n2);
193 } /* rotate_left */
195 /* Switch node 'n' with its left child, making 'n'
196 * the new right child of that node. */
197 static void
198 rotate_right(sdb_avltree_t *tree, node_t *n)
199 {
200 node_t *n2 = n->left;
201 node_t *c = n2->right;
203 n2->parent = n->parent;
204 if (! n2->parent)
205 tree->root = n2;
206 else if (n2->parent->left == n)
207 n2->parent->left = n2;
208 else
209 n2->parent->right = n2;
211 n2->right = n;
212 n->parent = n2;
214 n->left = c;
215 if (c)
216 c->parent = n;
218 n->height = CALC_HEIGHT(n);
219 n2->height = CALC_HEIGHT(n2);
220 } /* rotate_right */
222 /* Rebalance a tree starting at node 'n' towards the root;
223 * also, update the node heights all the way up to the root. */
224 static void
225 rebalance(sdb_avltree_t *tree, node_t *n)
226 {
227 for ( ; n; n = n->parent) {
228 int bf = BALANCE(n);
230 if (bf == 0)
231 return;
233 if ((-1 <= bf) && (bf <= 1)) {
234 n->height = CALC_HEIGHT(n);
235 continue;
236 }
238 assert((-2 <= bf) && (bf <= 2));
240 if (bf == 2) {
241 if (BALANCE(n->left) == -1)
242 rotate_left(tree, n->left);
243 rotate_right(tree, n);
244 }
245 else {
246 if (BALANCE(n->right) == 1)
247 rotate_right(tree, n->right);
248 rotate_left(tree, n);
249 }
251 /* n was moved downwards; get back to the previous level */
252 n = n->parent;
253 }
254 } /* rebalance */
256 /*
257 * public API
258 */
260 sdb_avltree_t *
261 sdb_avltree_create(sdb_object_cmp_cb cmp)
262 {
263 sdb_avltree_t *tree;
265 tree = malloc(sizeof(*tree));
266 if (! tree)
267 return NULL;
269 if (! cmp)
270 cmp = sdb_object_cmp_by_name;
272 pthread_rwlock_init(&tree->lock, /* attr = */ NULL);
273 tree->cmp = cmp;
275 tree->root = NULL;
276 tree->size = 0;
277 return tree;
278 } /* sdb_avltree_create */
280 void
281 sdb_avltree_destroy(sdb_avltree_t *tree)
282 {
283 if (! tree)
284 return;
286 pthread_rwlock_wrlock(&tree->lock);
287 tree_clear(tree);
288 pthread_rwlock_unlock(&tree->lock);
289 pthread_rwlock_destroy(&tree->lock);
290 free(tree);
291 } /* sdb_avltree_destroy */
293 void
294 sdb_avltree_clear(sdb_avltree_t *tree)
295 {
296 if (! tree)
297 return;
299 pthread_rwlock_wrlock(&tree->lock);
300 tree_clear(tree);
301 pthread_rwlock_unlock(&tree->lock);
302 } /* sdb_avltree_clear */
304 int
305 sdb_avltree_insert(sdb_avltree_t *tree, sdb_object_t *obj)
306 {
307 node_t *parent;
308 node_t *n;
310 int diff = -1;
312 if (! tree)
313 return -1;
315 n = node_create(obj);
316 if (! n)
317 return -1;
319 pthread_rwlock_wrlock(&tree->lock);
321 if (! tree->root) {
322 tree->root = n;
323 tree->size = 1;
324 pthread_rwlock_unlock(&tree->lock);
325 return 0;
326 }
328 parent = tree->root;
329 while (42) {
330 assert(parent);
332 diff = tree->cmp(obj, parent->obj);
333 if (! diff) {
334 node_destroy(n);
335 pthread_rwlock_unlock(&tree->lock);
336 return -1;
337 }
339 if (diff < 0) {
340 if (! parent->left) {
341 parent->left = n;
342 break;
343 }
344 parent = parent->left;
345 }
346 else {
347 if (! parent->right) {
348 parent->right = n;
349 break;
350 }
351 parent = parent->right;
352 }
353 }
355 n->parent = parent;
356 ++tree->size;
358 rebalance(tree, parent);
359 pthread_rwlock_unlock(&tree->lock);
360 return 0;
361 } /* sdb_avltree_insert */
363 sdb_avltree_iter_t *
364 sdb_avltree_get_iter(sdb_avltree_t *tree)
365 {
366 sdb_avltree_iter_t *iter;
368 if (! tree)
369 return NULL;
371 iter = malloc(sizeof(*iter));
372 if (! iter)
373 return NULL;
375 pthread_rwlock_rdlock(&tree->lock);
377 iter->tree = tree;
378 iter->node = node_smallest(tree);
380 pthread_rwlock_unlock(&tree->lock);
381 return iter;
382 } /* sdb_avltree_get_iter */
384 void
385 sdb_avltree_iter_destroy(sdb_avltree_iter_t *iter)
386 {
387 if (! iter)
388 return;
390 iter->tree = NULL;
391 iter->node = NULL;
392 free(iter);
393 } /* sdb_avltree_iter_destroy */
395 _Bool
396 sdb_avltree_iter_has_next(sdb_avltree_iter_t *iter)
397 {
398 if (! iter)
399 return 0;
401 return iter->node != NULL;
402 } /* sdb_avltree_iter_has_next */
404 sdb_object_t *
405 sdb_avltree_iter_get_next(sdb_avltree_iter_t *iter)
406 {
407 node_t *n;
409 if (! iter)
410 return NULL;
412 n = iter->node;
413 iter->node = node_next(iter->node);
414 return n ? n->obj : NULL;
415 } /* sdb_avltree_iter_get_next */
417 size_t
418 sdb_avltree_size(sdb_avltree_t *tree)
419 {
420 return tree ? tree->size : 0;
421 } /* sdb_avltree_size */
423 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */