9 /* ------------------------------------------------------------------------- */
11 * avl_insert(), avl_remove() and avl_search()
12 * are adaptations (by Costa Tsaousis) of the AVL algorithm found in libavl
13 * v2.0.3, so that they do not use any memory allocations and their memory
14 * footprint is optimized (by eliminating non-necessary data members).
16 * libavl - library for manipulation of binary trees.
17 * Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004 Free Software
19 * GNU Lesser General Public License
23 /* Search |tree| for an item matching |item|, and return it if found.
24 Otherwise return |NULL|. */
25 avl *avl_search(avl_tree *tree, avl *item) {
28 // assert (tree != NULL && item != NULL);
30 for (p = tree->root; p != NULL; ) {
31 int cmp = tree->compar(item, p);
44 /* Inserts |item| into |tree| and returns a pointer to |item|'s address.
45 If a duplicate item is found in the tree,
46 returns a pointer to the duplicate without inserting |item|.
48 avl *avl_insert(avl_tree *tree, avl *item) {
49 avl *y, *z; /* Top node to update balance factor, and parent. */
50 avl *p, *q; /* Iterator, and parent. */
51 avl *n; /* Newly inserted node. */
52 avl *w; /* New root of rebalanced subtree. */
53 int dir; /* Direction to descend. */
55 unsigned char da[AVL_MAX_HEIGHT]; /* Cached comparison results. */
56 int k = 0; /* Number of cached results. */
58 // assert(tree != NULL && item != NULL);
60 z = (avl *) &tree->root;
63 for (q = z, p = y; p != NULL; q = p, p = p->avl_link[dir]) {
64 int cmp = tree->compar(item, p);
68 if (p->avl_balance != 0)
70 da[k++] = dir = (cmp > 0);
73 n = q->avl_link[dir] = item;
76 n->avl_link[0] = n->avl_link[1] = NULL;
78 if (y == NULL) return n;
80 for (p = y, k = 0; p != n; p = p->avl_link[da[k]], k++)
86 if (y->avl_balance == -2) {
87 avl *x = y->avl_link[0];
88 if (x->avl_balance == -1) {
90 y->avl_link[0] = x->avl_link[1];
92 x->avl_balance = y->avl_balance = 0;
95 // assert (x->avl_balance == +1);
97 x->avl_link[1] = w->avl_link[0];
99 y->avl_link[0] = w->avl_link[1];
101 if (w->avl_balance == -1)
102 x->avl_balance = 0, y->avl_balance = +1;
103 else if (w->avl_balance == 0)
104 x->avl_balance = y->avl_balance = 0;
105 else /* |w->avl_balance == +1| */
106 x->avl_balance = -1, y->avl_balance = 0;
110 else if (y->avl_balance == +2) {
111 avl *x = y->avl_link[1];
112 if (x->avl_balance == +1) {
114 y->avl_link[1] = x->avl_link[0];
116 x->avl_balance = y->avl_balance = 0;
119 // assert (x->avl_balance == -1);
121 x->avl_link[0] = w->avl_link[1];
123 y->avl_link[1] = w->avl_link[0];
125 if (w->avl_balance == +1)
126 x->avl_balance = 0, y->avl_balance = -1;
127 else if (w->avl_balance == 0)
128 x->avl_balance = y->avl_balance = 0;
129 else /* |w->avl_balance == -1| */
130 x->avl_balance = +1, y->avl_balance = 0;
136 z->avl_link[y != z->avl_link[0]] = w;
138 // tree->avl_generation++;
142 /* Deletes from |tree| and returns an item matching |item|.
143 Returns a null pointer if no matching item found. */
144 avl *avl_remove(avl_tree *tree, avl *item) {
145 /* Stack of nodes. */
146 avl *pa[AVL_MAX_HEIGHT]; /* Nodes. */
147 unsigned char da[AVL_MAX_HEIGHT]; /* |avl_link[]| indexes. */
148 int k; /* Stack pointer. */
150 avl *p; /* Traverses tree to find node to delete. */
151 int cmp; /* Result of comparison between |item| and |p|. */
153 // assert (tree != NULL && item != NULL);
156 p = (avl *) &tree->root;
157 for(cmp = -1; cmp != 0; cmp = tree->compar(item, p)) {
163 p = p->avl_link[dir];
164 if(p == NULL) return NULL;
169 if (p->avl_link[1] == NULL)
170 pa[k - 1]->avl_link[da[k - 1]] = p->avl_link[0];
172 avl *r = p->avl_link[1];
173 if (r->avl_link[0] == NULL) {
174 r->avl_link[0] = p->avl_link[0];
175 r->avl_balance = p->avl_balance;
176 pa[k - 1]->avl_link[da[k - 1]] = r;
188 if (s->avl_link[0] == NULL) break;
193 s->avl_link[0] = p->avl_link[0];
194 r->avl_link[0] = s->avl_link[1];
195 s->avl_link[1] = p->avl_link[1];
196 s->avl_balance = p->avl_balance;
198 pa[j - 1]->avl_link[da[j - 1]] = s;
210 if (y->avl_balance == +1) break;
211 else if (y->avl_balance == +2) {
212 avl *x = y->avl_link[1];
213 if (x->avl_balance == -1) {
215 // assert (x->avl_balance == -1);
217 x->avl_link[0] = w->avl_link[1];
219 y->avl_link[1] = w->avl_link[0];
221 if (w->avl_balance == +1)
222 x->avl_balance = 0, y->avl_balance = -1;
223 else if (w->avl_balance == 0)
224 x->avl_balance = y->avl_balance = 0;
225 else /* |w->avl_balance == -1| */
226 x->avl_balance = +1, y->avl_balance = 0;
228 pa[k - 1]->avl_link[da[k - 1]] = w;
231 y->avl_link[1] = x->avl_link[0];
233 pa[k - 1]->avl_link[da[k - 1]] = x;
234 if (x->avl_balance == 0) {
239 else x->avl_balance = y->avl_balance = 0;
246 if (y->avl_balance == -1) break;
247 else if (y->avl_balance == -2) {
248 avl *x = y->avl_link[0];
249 if (x->avl_balance == +1) {
251 // assert (x->avl_balance == +1);
253 x->avl_link[1] = w->avl_link[0];
255 y->avl_link[0] = w->avl_link[1];
257 if (w->avl_balance == -1)
258 x->avl_balance = 0, y->avl_balance = +1;
259 else if (w->avl_balance == 0)
260 x->avl_balance = y->avl_balance = 0;
261 else /* |w->avl_balance == +1| */
262 x->avl_balance = -1, y->avl_balance = 0;
264 pa[k - 1]->avl_link[da[k - 1]] = w;
267 y->avl_link[0] = x->avl_link[1];
269 pa[k - 1]->avl_link[da[k - 1]] = x;
270 if (x->avl_balance == 0) {
275 else x->avl_balance = y->avl_balance = 0;
281 // tree->avl_count--;
282 // tree->avl_generation++;
286 /* ------------------------------------------------------------------------- */
287 // these functions are (C) Costa Tsaousis
289 void avl_read_lock(avl_tree_lock *t) {
290 #ifndef AVL_WITHOUT_PTHREADS
291 #ifdef AVL_LOCK_WITH_MUTEX
292 pthread_mutex_lock(&t->mutex);
294 pthread_rwlock_rdlock(&t->rwlock);
296 #endif /* AVL_WITHOUT_PTHREADS */
299 void avl_write_lock(avl_tree_lock *t) {
300 #ifndef AVL_WITHOUT_PTHREADS
301 #ifdef AVL_LOCK_WITH_MUTEX
302 pthread_mutex_lock(&t->mutex);
304 pthread_rwlock_wrlock(&t->rwlock);
306 #endif /* AVL_WITHOUT_PTHREADS */
309 void avl_unlock(avl_tree_lock *t) {
310 #ifndef AVL_WITHOUT_PTHREADS
311 #ifdef AVL_LOCK_WITH_MUTEX
312 pthread_mutex_unlock(&t->mutex);
314 pthread_rwlock_unlock(&t->rwlock);
316 #endif /* AVL_WITHOUT_PTHREADS */
319 /* ------------------------------------------------------------------------- */
321 void avl_init_lock(avl_tree_lock *t, int (*compar)(void *a, void *b)) {
322 avl_init(&t->avl_tree, compar);
324 #ifndef AVL_WITHOUT_PTHREADS
327 #ifdef AVL_LOCK_WITH_MUTEX
328 lock = pthread_mutex_init(&t->mutex, NULL);
330 lock = pthread_rwlock_init(&t->rwlock, NULL);
334 fatal("Failed to initialize AVL mutex/rwlock, error: %d", lock);
336 #endif /* AVL_WITHOUT_PTHREADS */
339 avl *avl_search_lock(avl_tree_lock *t, avl *a) {
341 avl *ret = avl_search(&t->avl_tree, a);
346 avl * avl_remove_lock(avl_tree_lock *t, avl *a) {
348 avl *ret = avl_remove(&t->avl_tree, a);
353 avl *avl_insert_lock(avl_tree_lock *t, avl *a) {
355 avl * ret = avl_insert(&t->avl_tree, a);
360 void avl_init(avl_tree *t, int (*compar)(void *a, void *b)) {