95c004d32ffbe10ae39a31b9a146a80adccd2b41
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 "utils/avltree.h"
34 #include <stdlib.h>
36 #include <pthread.h>
38 /*
39 * private data types
40 */
42 struct node;
43 typedef struct node node_t;
45 struct node {
46 sdb_object_t *obj;
48 node_t *parent;
49 node_t *left;
50 node_t *right;
51 };
53 struct sdb_avltree {
54 pthread_rwlock_t lock;
56 sdb_object_cmp_cb cmp;
58 node_t *root;
59 size_t size;
60 };
62 struct sdb_avltree_iter {
63 sdb_avltree_t *tree;
64 node_t *node;
65 };
67 /*
68 * private helper functions
69 */
71 static void
72 node_destroy(node_t *n)
73 {
74 sdb_object_deref(n->obj);
75 n->obj = NULL;
76 n->parent = n->left = n->right = NULL;
77 free(n);
78 } /* node_destroy */
80 static node_t *
81 node_create(sdb_object_t *obj)
82 {
83 node_t *n = malloc(sizeof(*n));
84 if (! n)
85 return NULL;
87 sdb_object_ref(obj);
88 n->obj = obj;
89 n->parent = n->left = n->right = NULL;
90 return n;
91 } /* node_create */
93 static node_t *
94 node_next(node_t *n)
95 {
96 node_t *next;
98 if (! n)
99 return NULL;
101 /* descend into the right tree */
102 if (n->right) {
103 next = n->right;
104 while (next->left)
105 next = next->left;
106 return next;
107 }
109 /* visit the parent if we're in its left tree */
110 if (n->parent && (n->parent->left == n))
111 return n->parent;
113 /* find the parent of the sibling sub-tree on the right */
114 next = n->parent;
115 next = NULL;
116 while (n->parent && (n->parent->right == n)) {
117 n = n->parent;
118 next = n;
119 }
120 if (next)
121 next = next->parent;
122 return next;
123 } /* node_next */
125 static void
126 tree_clear(sdb_avltree_t *tree)
127 {
128 node_t *n;
130 n = tree->root;
131 while (n) {
132 node_t *tmp = node_next(n);
134 node_destroy(n);
135 n = tmp;
136 }
138 tree->root = NULL;
139 tree->size = 0;
140 } /* tree_clear */
142 /*
143 * public API
144 */
146 sdb_avltree_t *
147 sdb_avltree_create(sdb_object_cmp_cb cmp)
148 {
149 sdb_avltree_t *tree;
151 tree = malloc(sizeof(*tree));
152 if (! tree)
153 return NULL;
155 if (! cmp)
156 cmp = sdb_object_cmp_by_name;
158 pthread_rwlock_init(&tree->lock, /* attr = */ NULL);
159 tree->cmp = cmp;
161 tree->root = NULL;
162 tree->size = 0;
163 return tree;
164 } /* sdb_avltree_create */
166 void
167 sdb_avltree_destroy(sdb_avltree_t *tree)
168 {
169 if (! tree)
170 return;
172 pthread_rwlock_wrlock(&tree->lock);
173 tree_clear(tree);
174 pthread_rwlock_unlock(&tree->lock);
175 pthread_rwlock_destroy(&tree->lock);
176 free(tree);
177 } /* sdb_avltree_destroy */
179 void
180 sdb_avltree_clear(sdb_avltree_t *tree)
181 {
182 if (! tree)
183 return;
185 pthread_rwlock_wrlock(&tree->lock);
186 tree_clear(tree);
187 pthread_rwlock_unlock(&tree->lock);
188 } /* sdb_avltree_clear */
190 int
191 sdb_avltree_insert(sdb_avltree_t *tree, sdb_object_t *obj)
192 {
193 node_t *parent;
194 node_t *n;
196 int diff = -1;
198 if (! tree)
199 return -1;
201 n = node_create(obj);
202 if (! n)
203 return -1;
205 parent = tree->root;
206 while (parent) {
207 diff = tree->cmp(obj, parent->obj);
208 if (! diff) {
209 node_destroy(n);
210 return -1;
211 }
213 if (diff < 0) {
214 if (! parent->left) {
215 parent->left = n;
216 break;
217 }
218 parent = parent->left;
219 }
220 else {
221 if (! parent->right) {
222 parent->right = n;
223 break;
224 }
225 parent = parent->right;
226 }
227 }
229 if (! parent) {
230 /* new root */
231 if (diff < 0)
232 n->right = tree->root;
233 else
234 n->left = tree->root;
235 tree->root = n;
236 }
238 n->parent = parent;
239 ++tree->size;
241 /* XXX: rebalance */
242 return 0;
243 } /* sdb_avltree_insert */
245 sdb_avltree_iter_t *
246 sdb_avltree_get_iter(sdb_avltree_t *tree)
247 {
248 sdb_avltree_iter_t *iter;
250 if (! tree)
251 return NULL;
253 iter = malloc(sizeof(*iter));
254 if (! iter)
255 return NULL;
257 pthread_rwlock_rdlock(&tree->lock);
259 iter->tree = tree;
260 iter->node = tree->root->left;
261 while (iter->node && iter->node->left)
262 iter->node = iter->node->left;
264 pthread_rwlock_unlock(&tree->lock);
265 return iter;
266 } /* sdb_avltree_get_iter */
268 void
269 sdb_avltree_iter_destroy(sdb_avltree_iter_t *iter)
270 {
271 if (! iter)
272 return;
274 iter->tree = NULL;
275 iter->node = NULL;
276 free(iter);
277 } /* sdb_avltree_iter_destroy */
279 _Bool
280 sdb_avltree_iter_has_next(sdb_avltree_iter_t *iter)
281 {
282 if (! iter)
283 return 0;
285 return iter->node != NULL;
286 } /* sdb_avltree_iter_has_next */
288 sdb_object_t *
289 sdb_avltree_iter_get_next(sdb_avltree_iter_t *iter)
290 {
291 node_t *n;
293 if (! iter)
294 return NULL;
296 n = iter->node;
297 iter->node = node_next(iter->node);
298 return n ? n->obj : NULL;
299 } /* sdb_avltree_iter_get_next */
301 size_t
302 sdb_avltree_size(sdb_avltree_t *tree)
303 {
304 return tree ? tree->size : 0;
305 } /* sdb_avltree_size */
307 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */