src/avl.c

   1 #ifdef HAVE_CONFIG_H
   2 #include <config.h>
   3 #endif
   4 // #include <assert.h>
   5
   6 #include "avl.h"
   7 #include "log.h"
   8
   9 /* ------------------------------------------------------------------------- */
  10 /*
  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).
  15  *
  16  * libavl - library for manipulation of binary trees.
  17  * Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004 Free Software
  18  * Foundation, Inc.
  19  * GNU Lesser General Public License
  20 */
  21
  22
  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) {
  26     avl *p;
  27
  28     // assert (tree != NULL && item != NULL);
  29
  30     for (p = tree->root; p != NULL; ) {
  31         int cmp = tree->compar(item, p);
  32
  33         if (cmp < 0)
  34             p = p->avl_link[0];
  35         else if (cmp > 0)
  36             p = p->avl_link[1];
  37         else /* |cmp == 0| */
  38             return p;
  39     }
  40
  41     return NULL;
  42 }
  43
  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|.
  47  */
  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. */
  54
  55     unsigned char da[AVL_MAX_HEIGHT]; /* Cached comparison results. */
  56     int k = 0;              /* Number of cached results. */
  57
  58     // assert(tree != NULL && item != NULL);
  59
  60     z = (avl *) &tree->root;
  61     y = tree->root;
  62     dir = 0;
  63     for (q = z, p = y; p != NULL; q = p, p = p->avl_link[dir]) {
  64         int cmp = tree->compar(item, p);
  65         if (cmp == 0)
  66             return p;
  67
  68         if (p->avl_balance != 0)
  69             z = q, y = p, k = 0;
  70         da[k++] = dir = (cmp > 0);
  71     }
  72
  73     n = q->avl_link[dir] = item;
  74
  75     // tree->avl_count++;
  76     n->avl_link[0] = n->avl_link[1] = NULL;
  77     n->avl_balance = 0;
  78     if (y == NULL) return n;
  79
  80     for (p = y, k = 0; p != n; p = p->avl_link[da[k]], k++)
  81         if (da[k] == 0)
  82             p->avl_balance--;
  83         else
  84             p->avl_balance++;
  85
  86     if (y->avl_balance == -2) {
  87         avl *x = y->avl_link[0];
  88         if (x->avl_balance == -1) {
  89             w = x;
  90             y->avl_link[0] = x->avl_link[1];
  91             x->avl_link[1] = y;
  92             x->avl_balance = y->avl_balance = 0;
  93         }
  94         else {
  95             // assert (x->avl_balance == +1);
  96             w = x->avl_link[1];
  97             x->avl_link[1] = w->avl_link[0];
  98             w->avl_link[0] = x;
  99             y->avl_link[0] = w->avl_link[1];
 100             w->avl_link[1] = y;
 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;
 107             w->avl_balance = 0;
 108         }
 109     }
 110     else if (y->avl_balance == +2) {
 111         avl *x = y->avl_link[1];
 112         if (x->avl_balance == +1) {
 113             w = x;
 114             y->avl_link[1] = x->avl_link[0];
 115             x->avl_link[0] = y;
 116             x->avl_balance = y->avl_balance = 0;
 117         }
 118         else {
 119             // assert (x->avl_balance == -1);
 120             w = x->avl_link[0];
 121             x->avl_link[0] = w->avl_link[1];
 122             w->avl_link[1] = x;
 123             y->avl_link[1] = w->avl_link[0];
 124             w->avl_link[0] = y;
 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;
 131             w->avl_balance = 0;
 132         }
 133     }
 134     else return n;
 135
 136     z->avl_link[y != z->avl_link[0]] = w;
 137
 138     // tree->avl_generation++;
 139     return n;
 140 }
 141
 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. */
 149
 150     avl *p;   /* Traverses tree to find node to delete. */
 151     int cmp;              /* Result of comparison between |item| and |p|. */
 152
 153     // assert (tree != NULL && item != NULL);
 154
 155     k = 0;
 156     p = (avl *) &tree->root;
 157     for(cmp = -1; cmp != 0; cmp = tree->compar(item, p)) {
 158         int dir = (cmp > 0);
 159
 160         pa[k] = p;
 161         da[k++] = dir;
 162
 163         p = p->avl_link[dir];
 164         if(p == NULL) return NULL;
 165     }
 166
 167     item = p;
 168
 169     if (p->avl_link[1] == NULL)
 170         pa[k - 1]->avl_link[da[k - 1]] = p->avl_link[0];
 171     else {
 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;
 177             da[k] = 1;
 178             pa[k++] = r;
 179         }
 180         else {
 181             avl *s;
 182             int j = k++;
 183
 184             for (;;) {
 185                 da[k] = 0;
 186                 pa[k++] = r;
 187                 s = r->avl_link[0];
 188                 if (s->avl_link[0] == NULL) break;
 189
 190                 r = s;
 191             }
 192
 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;
 197
 198             pa[j - 1]->avl_link[da[j - 1]] = s;
 199             da[j] = 1;
 200             pa[j] = s;
 201         }
 202     }
 203
 204     // assert (k > 0);
 205     while (--k > 0) {
 206         avl *y = pa[k];
 207
 208         if (da[k] == 0) {
 209             y->avl_balance++;
 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) {
 214                     avl *w;
 215                     // assert (x->avl_balance == -1);
 216                     w = x->avl_link[0];
 217                     x->avl_link[0] = w->avl_link[1];
 218                     w->avl_link[1] = x;
 219                     y->avl_link[1] = w->avl_link[0];
 220                     w->avl_link[0] = y;
 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;
 227                     w->avl_balance = 0;
 228                     pa[k - 1]->avl_link[da[k - 1]] = w;
 229                 }
 230                 else {
 231                     y->avl_link[1] = x->avl_link[0];
 232                     x->avl_link[0] = y;
 233                     pa[k - 1]->avl_link[da[k - 1]] = x;
 234                     if (x->avl_balance == 0) {
 235                         x->avl_balance = -1;
 236                         y->avl_balance = +1;
 237                         break;
 238                     }
 239                     else x->avl_balance = y->avl_balance = 0;
 240                 }
 241             }
 242         }
 243         else
 244         {
 245             y->avl_balance--;
 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) {
 250                     avl *w;
 251                     // assert (x->avl_balance == +1);
 252                     w = x->avl_link[1];
 253                     x->avl_link[1] = w->avl_link[0];
 254                     w->avl_link[0] = x;
 255                     y->avl_link[0] = w->avl_link[1];
 256                     w->avl_link[1] = y;
 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;
 263                     w->avl_balance = 0;
 264                     pa[k - 1]->avl_link[da[k - 1]] = w;
 265                 }
 266                 else {
 267                     y->avl_link[0] = x->avl_link[1];
 268                     x->avl_link[1] = y;
 269                     pa[k - 1]->avl_link[da[k - 1]] = x;
 270                     if (x->avl_balance == 0) {
 271                         x->avl_balance = +1;
 272                         y->avl_balance = -1;
 273                         break;
 274                     }
 275                     else x->avl_balance = y->avl_balance = 0;
 276                 }
 277             }
 278         }
 279     }
 280
 281     // tree->avl_count--;
 282     // tree->avl_generation++;
 283     return item;
 284 }
 285
 286 /* ------------------------------------------------------------------------- */
 287 // these functions are (C) Costa Tsaousis
 288
 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);
 293 #else
 294         pthread_rwlock_rdlock(&t->rwlock);
 295 #endif
 296 #endif /* AVL_WITHOUT_PTHREADS */
 297 }
 298
 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);
 303 #else
 304         pthread_rwlock_wrlock(&t->rwlock);
 305 #endif
 306 #endif /* AVL_WITHOUT_PTHREADS */
 307 }
 308
 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);
 313 #else
 314         pthread_rwlock_unlock(&t->rwlock);
 315 #endif
 316 #endif /* AVL_WITHOUT_PTHREADS */
 317 }
 318
 319 /* ------------------------------------------------------------------------- */
 320
 321 void avl_init_lock(avl_tree_lock *t, int (*compar)(void *a, void *b)) {
 322         avl_init(&t->avl_tree, compar);
 323
 324 #ifndef AVL_WITHOUT_PTHREADS
 325         int lock;
 326
 327 #ifdef AVL_LOCK_WITH_MUTEX
 328         lock = pthread_mutex_init(&t->mutex, NULL);
 329 #else
 330         lock = pthread_rwlock_init(&t->rwlock, NULL);
 331 #endif
 332
 333         if(lock != 0)
 334                 fatal("Failed to initialize AVL mutex/rwlock, error: %d", lock);
 335
 336 #endif /* AVL_WITHOUT_PTHREADS */
 337 }
 338
 339 avl *avl_search_lock(avl_tree_lock *t, avl *a) {
 340         avl_read_lock(t);
 341         avl *ret = avl_search(&t->avl_tree, a);
 342         avl_unlock(t);
 343         return ret;
 344 }
 345
 346 avl * avl_remove_lock(avl_tree_lock *t, avl *a) {
 347         avl_write_lock(t);
 348         avl *ret = avl_remove(&t->avl_tree, a);
 349         avl_unlock(t);
 350         return ret;
 351 }
 352
 353 avl *avl_insert_lock(avl_tree_lock *t, avl *a) {
 354         avl_write_lock(t);
 355     avl * ret = avl_insert(&t->avl_tree, a);
 356         avl_unlock(t);
 357         return ret;
 358 }
 359
 360 void avl_init(avl_tree *t, int (*compar)(void *a, void *b)) {
 361     t->root = NULL;
 362     t->compar = compar;
 363 }
 364