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 // these functions are (C) Costa Tsaousis
283 void avl_read_lock(avl_tree_lock *t) {
284 #ifndef AVL_WITHOUT_PTHREADS
285 #ifdef AVL_LOCK_WITH_MUTEX
286 pthread_mutex_lock(&t->mutex);
288 pthread_rwlock_rdlock(&t->rwlock);
290 #endif /* AVL_WITHOUT_PTHREADS */
293 void avl_write_lock(avl_tree_lock *t) {
294 #ifndef AVL_WITHOUT_PTHREADS
295 #ifdef AVL_LOCK_WITH_MUTEX
296 pthread_mutex_lock(&t->mutex);
298 pthread_rwlock_wrlock(&t->rwlock);
300 #endif /* AVL_WITHOUT_PTHREADS */
303 void avl_unlock(avl_tree_lock *t) {
304 #ifndef AVL_WITHOUT_PTHREADS
305 #ifdef AVL_LOCK_WITH_MUTEX
306 pthread_mutex_unlock(&t->mutex);
308 pthread_rwlock_unlock(&t->rwlock);
310 #endif /* AVL_WITHOUT_PTHREADS */
313 /* ------------------------------------------------------------------------- */
315 void avl_init_lock(avl_tree_lock *t, int (*compar)(void *a, void *b)) {
316 avl_init(&t->avl_tree, compar);
318 #ifndef AVL_WITHOUT_PTHREADS
321 #ifdef AVL_LOCK_WITH_MUTEX
322 lock = pthread_mutex_init(&t->mutex, NULL);
324 lock = pthread_rwlock_init(&t->rwlock, NULL);
328 fatal("Failed to initialize AVL mutex/rwlock, error: %d", lock);
330 #endif /* AVL_WITHOUT_PTHREADS */
333 avl *avl_search_lock(avl_tree_lock *t, avl *a) {
335 avl *ret = avl_search(&t->avl_tree, a);
340 avl * avl_remove_lock(avl_tree_lock *t, avl *a) {
342 avl *ret = avl_remove(&t->avl_tree, a);
347 avl *avl_insert_lock(avl_tree_lock *t, avl *a) {
349 avl * ret = avl_insert(&t->avl_tree, a);
354 void avl_init(avl_tree *t, int (*compar)(void *a, void *b)) {