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 void
138 tree_clear(sdb_avltree_t *tree)
139 {
140 node_t *n;
142 n = tree->root;
143 while (n) {
144 node_t *tmp = node_next(n);
146 node_destroy(n);
147 n = tmp;
148 }
150 tree->root = NULL;
151 tree->size = 0;
152 } /* tree_clear */
154 /* Switch node 'n' with its right child, making 'n'
155 * the new left child of that node. */
156 static void
157 rotate_left(sdb_avltree_t *tree, node_t *n)
158 {
159 node_t *n2 = n->right;
160 node_t *c = n2->left;
162 n2->parent = n->parent;
163 if (! n2->parent)
164 tree->root = n2;
165 else if (n2->parent->left == n)
166 n2->parent->left = n2;
167 else
168 n2->parent->right = n2;
170 n2->left = n;
171 n->parent = n2;
173 n->right = c;
174 if (c)
175 c->parent = n;
177 n->height = CALC_HEIGHT(n);
178 n2->height = CALC_HEIGHT(n2);
179 } /* rotate_left */
181 /* Switch node 'n' with its left child, making 'n'
182 * the new right child of that node. */
183 static void
184 rotate_right(sdb_avltree_t *tree, node_t *n)
185 {
186 node_t *n2 = n->left;
187 node_t *c = n2->right;
189 n2->parent = n->parent;
190 if (! n2->parent)
191 tree->root = n2;
192 else if (n2->parent->left == n)
193 n2->parent->left = n2;
194 else
195 n2->parent->right = n2;
197 n2->right = n;
198 n->parent = n2;
200 n->left = c;
201 if (c)
202 c->parent = n;
204 n->height = CALC_HEIGHT(n);
205 n2->height = CALC_HEIGHT(n2);
206 } /* rotate_right */
208 /* Rebalance a tree starting at node 'n' towards the root;
209 * also, update the node heights all the way up to the root. */
210 static void
211 rebalance(sdb_avltree_t *tree, node_t *n)
212 {
213 for ( ; n; n = n->parent) {
214 int bf = BALANCE(n);
216 if (bf == 0)
217 return;
219 if ((-1 <= bf) && (bf <= 1)) {
220 n->height = CALC_HEIGHT(n);
221 continue;
222 }
224 assert((-2 <= bf) && (bf <= 2));
226 if (bf == 2) {
227 if (BALANCE(n->left) == -1)
228 rotate_left(tree, n->left);
229 rotate_right(tree, n);
230 }
231 else {
232 if (BALANCE(n->right) == 1)
233 rotate_right(tree, n->right);
234 rotate_left(tree, n);
235 }
237 /* n was moved downwards; get back to the previous level */
238 n = n->parent;
239 }
240 } /* rebalance */
242 /*
243 * public API
244 */
246 sdb_avltree_t *
247 sdb_avltree_create(sdb_object_cmp_cb cmp)
248 {
249 sdb_avltree_t *tree;
251 tree = malloc(sizeof(*tree));
252 if (! tree)
253 return NULL;
255 if (! cmp)
256 cmp = sdb_object_cmp_by_name;
258 pthread_rwlock_init(&tree->lock, /* attr = */ NULL);
259 tree->cmp = cmp;
261 tree->root = NULL;
262 tree->size = 0;
263 return tree;
264 } /* sdb_avltree_create */
266 void
267 sdb_avltree_destroy(sdb_avltree_t *tree)
268 {
269 if (! tree)
270 return;
272 pthread_rwlock_wrlock(&tree->lock);
273 tree_clear(tree);
274 pthread_rwlock_unlock(&tree->lock);
275 pthread_rwlock_destroy(&tree->lock);
276 free(tree);
277 } /* sdb_avltree_destroy */
279 void
280 sdb_avltree_clear(sdb_avltree_t *tree)
281 {
282 if (! tree)
283 return;
285 pthread_rwlock_wrlock(&tree->lock);
286 tree_clear(tree);
287 pthread_rwlock_unlock(&tree->lock);
288 } /* sdb_avltree_clear */
290 int
291 sdb_avltree_insert(sdb_avltree_t *tree, sdb_object_t *obj)
292 {
293 node_t *parent;
294 node_t *n;
296 int diff = -1;
298 if (! tree)
299 return -1;
301 n = node_create(obj);
302 if (! n)
303 return -1;
305 if (! tree->root) {
306 tree->root = n;
307 tree->size = 1;
308 return 0;
309 }
311 parent = tree->root;
312 while (42) {
313 assert(parent);
315 diff = tree->cmp(obj, parent->obj);
316 if (! diff) {
317 node_destroy(n);
318 return -1;
319 }
321 if (diff < 0) {
322 if (! parent->left) {
323 parent->left = n;
324 break;
325 }
326 parent = parent->left;
327 }
328 else {
329 if (! parent->right) {
330 parent->right = n;
331 break;
332 }
333 parent = parent->right;
334 }
335 }
337 n->parent = parent;
338 ++tree->size;
340 rebalance(tree, parent);
341 return 0;
342 } /* sdb_avltree_insert */
344 sdb_avltree_iter_t *
345 sdb_avltree_get_iter(sdb_avltree_t *tree)
346 {
347 sdb_avltree_iter_t *iter;
349 if (! tree)
350 return NULL;
352 iter = malloc(sizeof(*iter));
353 if (! iter)
354 return NULL;
356 pthread_rwlock_rdlock(&tree->lock);
358 iter->tree = tree;
359 iter->node = tree->root->left;
360 while (iter->node && iter->node->left)
361 iter->node = iter->node->left;
363 pthread_rwlock_unlock(&tree->lock);
364 return iter;
365 } /* sdb_avltree_get_iter */
367 void
368 sdb_avltree_iter_destroy(sdb_avltree_iter_t *iter)
369 {
370 if (! iter)
371 return;
373 iter->tree = NULL;
374 iter->node = NULL;
375 free(iter);
376 } /* sdb_avltree_iter_destroy */
378 _Bool
379 sdb_avltree_iter_has_next(sdb_avltree_iter_t *iter)
380 {
381 if (! iter)
382 return 0;
384 return iter->node != NULL;
385 } /* sdb_avltree_iter_has_next */
387 sdb_object_t *
388 sdb_avltree_iter_get_next(sdb_avltree_iter_t *iter)
389 {
390 node_t *n;
392 if (! iter)
393 return NULL;
395 n = iter->node;
396 iter->node = node_next(iter->node);
397 return n ? n->obj : NULL;
398 } /* sdb_avltree_iter_get_next */
400 size_t
401 sdb_avltree_size(sdb_avltree_t *tree)
402 {
403 return tree ? tree->size : 0;
404 } /* sdb_avltree_size */
406 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */