3 /* ------------------------------------------------------------------------- */
5 * avl_insert(), avl_remove() and avl_search()
6 * are adaptations (by Costa Tsaousis) of the AVL algorithm found in libavl
7 * v2.0.3, so that they do not use any memory allocations and their memory
8 * footprint is optimized (by eliminating non-necessary data members).
10 * libavl - library for manipulation of binary trees.
11 * Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004 Free Software
13 * GNU Lesser General Public License
17 /* Search |tree| for an item matching |item|, and return it if found.
18 Otherwise return |NULL|. */
19 avl *avl_search(avl_tree *tree, avl *item) {
22 // assert (tree != NULL && item != NULL);
24 for (p = tree->root; p != NULL; ) {
25 int cmp = tree->compar(item, p);
38 /* Inserts |item| into |tree| and returns a pointer to |item|'s address.
39 If a duplicate item is found in the tree,
40 returns a pointer to the duplicate without inserting |item|.
42 avl *avl_insert(avl_tree *tree, avl *item) {
43 avl *y, *z; /* Top node to update balance factor, and parent. */
44 avl *p, *q; /* Iterator, and parent. */
45 avl *n; /* Newly inserted node. */
46 avl *w; /* New root of rebalanced subtree. */
47 int dir; /* Direction to descend. */
49 unsigned char da[AVL_MAX_HEIGHT]; /* Cached comparison results. */
50 int k = 0; /* Number of cached results. */
52 // assert(tree != NULL && item != NULL);
54 z = (avl *) &tree->root;
57 for (q = z, p = y; p != NULL; q = p, p = p->avl_link[dir]) {
58 int cmp = tree->compar(item, p);
62 if (p->avl_balance != 0)
64 da[k++] = dir = (cmp > 0);
67 n = q->avl_link[dir] = item;
70 n->avl_link[0] = n->avl_link[1] = NULL;
72 if (y == NULL) return n;
74 for (p = y, k = 0; p != n; p = p->avl_link[da[k]], k++)
80 if (y->avl_balance == -2) {
81 avl *x = y->avl_link[0];
82 if (x->avl_balance == -1) {
84 y->avl_link[0] = x->avl_link[1];
86 x->avl_balance = y->avl_balance = 0;
89 // assert (x->avl_balance == +1);
91 x->avl_link[1] = w->avl_link[0];
93 y->avl_link[0] = w->avl_link[1];
95 if (w->avl_balance == -1)
96 x->avl_balance = 0, y->avl_balance = +1;
97 else if (w->avl_balance == 0)
98 x->avl_balance = y->avl_balance = 0;
99 else /* |w->avl_balance == +1| */
100 x->avl_balance = -1, y->avl_balance = 0;
104 else if (y->avl_balance == +2) {
105 avl *x = y->avl_link[1];
106 if (x->avl_balance == +1) {
108 y->avl_link[1] = x->avl_link[0];
110 x->avl_balance = y->avl_balance = 0;
113 // assert (x->avl_balance == -1);
115 x->avl_link[0] = w->avl_link[1];
117 y->avl_link[1] = w->avl_link[0];
119 if (w->avl_balance == +1)
120 x->avl_balance = 0, y->avl_balance = -1;
121 else if (w->avl_balance == 0)
122 x->avl_balance = y->avl_balance = 0;
123 else /* |w->avl_balance == -1| */
124 x->avl_balance = +1, y->avl_balance = 0;
130 z->avl_link[y != z->avl_link[0]] = w;
132 // tree->avl_generation++;
136 /* Deletes from |tree| and returns an item matching |item|.
137 Returns a null pointer if no matching item found. */
138 avl *avl_remove(avl_tree *tree, avl *item) {
139 /* Stack of nodes. */
140 avl *pa[AVL_MAX_HEIGHT]; /* Nodes. */
141 unsigned char da[AVL_MAX_HEIGHT]; /* |avl_link[]| indexes. */
142 int k; /* Stack pointer. */
144 avl *p; /* Traverses tree to find node to delete. */
145 int cmp; /* Result of comparison between |item| and |p|. */
147 // assert (tree != NULL && item != NULL);
150 p = (avl *) &tree->root;
151 for(cmp = -1; cmp != 0; cmp = tree->compar(item, p)) {
157 p = p->avl_link[dir];
158 if(p == NULL) return NULL;
163 if (p->avl_link[1] == NULL)
164 pa[k - 1]->avl_link[da[k - 1]] = p->avl_link[0];
166 avl *r = p->avl_link[1];
167 if (r->avl_link[0] == NULL) {
168 r->avl_link[0] = p->avl_link[0];
169 r->avl_balance = p->avl_balance;
170 pa[k - 1]->avl_link[da[k - 1]] = r;
182 if (s->avl_link[0] == NULL) break;
187 s->avl_link[0] = p->avl_link[0];
188 r->avl_link[0] = s->avl_link[1];
189 s->avl_link[1] = p->avl_link[1];
190 s->avl_balance = p->avl_balance;
192 pa[j - 1]->avl_link[da[j - 1]] = s;
204 if (y->avl_balance == +1) break;
205 else if (y->avl_balance == +2) {
206 avl *x = y->avl_link[1];
207 if (x->avl_balance == -1) {
209 // assert (x->avl_balance == -1);
211 x->avl_link[0] = w->avl_link[1];
213 y->avl_link[1] = w->avl_link[0];
215 if (w->avl_balance == +1)
216 x->avl_balance = 0, y->avl_balance = -1;
217 else if (w->avl_balance == 0)
218 x->avl_balance = y->avl_balance = 0;
219 else /* |w->avl_balance == -1| */
220 x->avl_balance = +1, y->avl_balance = 0;
222 pa[k - 1]->avl_link[da[k - 1]] = w;
225 y->avl_link[1] = x->avl_link[0];
227 pa[k - 1]->avl_link[da[k - 1]] = x;
228 if (x->avl_balance == 0) {
233 else x->avl_balance = y->avl_balance = 0;
240 if (y->avl_balance == -1) break;
241 else if (y->avl_balance == -2) {
242 avl *x = y->avl_link[0];
243 if (x->avl_balance == +1) {
245 // assert (x->avl_balance == +1);
247 x->avl_link[1] = w->avl_link[0];
249 y->avl_link[0] = w->avl_link[1];
251 if (w->avl_balance == -1)
252 x->avl_balance = 0, y->avl_balance = +1;
253 else if (w->avl_balance == 0)
254 x->avl_balance = y->avl_balance = 0;
255 else /* |w->avl_balance == +1| */
256 x->avl_balance = -1, y->avl_balance = 0;
258 pa[k - 1]->avl_link[da[k - 1]] = w;
261 y->avl_link[0] = x->avl_link[1];
263 pa[k - 1]->avl_link[da[k - 1]] = x;
264 if (x->avl_balance == 0) {
269 else x->avl_balance = y->avl_balance = 0;
275 // tree->avl_count--;
276 // tree->avl_generation++;
280 /* ------------------------------------------------------------------------- */
281 // below are functions by (C) Costa Tsaousis
283 // ---------------------------
286 int avl_walker(avl *node, int (*callback)(void *entry, void *data), void *data) {
287 int total = 0, ret = 0;
289 if(node->avl_link[0]) {
290 ret = avl_walker(node->avl_link[0], callback, data);
291 if(ret < 0) return ret;
295 ret = callback(node, data);
296 if(ret < 0) return ret;
299 if(node->avl_link[1]) {
300 ret = avl_walker(node->avl_link[1], callback, data);
301 if (ret < 0) return ret;
308 int avl_traverse(avl_tree *t, int (*callback)(void *entry, void *data), void *data) {
309 return avl_walker(t->root, callback, data);
312 // ---------------------------
315 void avl_read_lock(avl_tree_lock *t) {
316 #ifndef AVL_WITHOUT_PTHREADS
317 #ifdef AVL_LOCK_WITH_MUTEX
318 pthread_mutex_lock(&t->mutex);
320 pthread_rwlock_rdlock(&t->rwlock);
322 #endif /* AVL_WITHOUT_PTHREADS */
325 void avl_write_lock(avl_tree_lock *t) {
326 #ifndef AVL_WITHOUT_PTHREADS
327 #ifdef AVL_LOCK_WITH_MUTEX
328 pthread_mutex_lock(&t->mutex);
330 pthread_rwlock_wrlock(&t->rwlock);
332 #endif /* AVL_WITHOUT_PTHREADS */
335 void avl_unlock(avl_tree_lock *t) {
336 #ifndef AVL_WITHOUT_PTHREADS
337 #ifdef AVL_LOCK_WITH_MUTEX
338 pthread_mutex_unlock(&t->mutex);
340 pthread_rwlock_unlock(&t->rwlock);
342 #endif /* AVL_WITHOUT_PTHREADS */
345 // ---------------------------
346 // operations with locking
348 void avl_init_lock(avl_tree_lock *t, int (*compar)(void *a, void *b)) {
349 avl_init(&t->avl_tree, compar);
351 #ifndef AVL_WITHOUT_PTHREADS
354 #ifdef AVL_LOCK_WITH_MUTEX
355 lock = pthread_mutex_init(&t->mutex, NULL);
357 lock = pthread_rwlock_init(&t->rwlock, NULL);
361 fatal("Failed to initialize AVL mutex/rwlock, error: %d", lock);
363 #endif /* AVL_WITHOUT_PTHREADS */
366 avl *avl_search_lock(avl_tree_lock *t, avl *a) {
368 avl *ret = avl_search(&t->avl_tree, a);
373 avl * avl_remove_lock(avl_tree_lock *t, avl *a) {
375 avl *ret = avl_remove(&t->avl_tree, a);
380 avl *avl_insert_lock(avl_tree_lock *t, avl *a) {
382 avl * ret = avl_insert(&t->avl_tree, a);
387 int avl_traverse_lock(avl_tree_lock *t, int (*callback)(void *entry, void *data), void *data) {
390 ret = avl_traverse(&t->avl_tree, callback, data);
395 void avl_init(avl_tree *t, int (*compar)(void *a, void *b)) {
400 // ------------------