src/avl.c

   1 #include "common.h"
   2
   3 /* ------------------------------------------------------------------------- */
   4 /*
   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).
   9  *
  10  * libavl - library for manipulation of binary trees.
  11  * Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004 Free Software
  12  * Foundation, Inc.
  13  * GNU Lesser General Public License
  14 */
  15
  16
  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) {
  20     avl *p;
  21
  22     // assert (tree != NULL && item != NULL);
  23
  24     for (p = tree->root; p != NULL; ) {
  25         int cmp = tree->compar(item, p);
  26
  27         if (cmp < 0)
  28             p = p->avl_link[0];
  29         else if (cmp > 0)
  30             p = p->avl_link[1];
  31         else /* |cmp == 0| */
  32             return p;
  33     }
  34
  35     return NULL;
  36 }
  37
  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|.
  41  */
  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. */
  48
  49     unsigned char da[AVL_MAX_HEIGHT]; /* Cached comparison results. */
  50     int k = 0;              /* Number of cached results. */
  51
  52     // assert(tree != NULL && item != NULL);
  53
  54     z = (avl *) &tree->root;
  55     y = tree->root;
  56     dir = 0;
  57     for (q = z, p = y; p != NULL; q = p, p = p->avl_link[dir]) {
  58         int cmp = tree->compar(item, p);
  59         if (cmp == 0)
  60             return p;
  61
  62         if (p->avl_balance != 0)
  63             z = q, y = p, k = 0;
  64         da[k++] = dir = (cmp > 0);
  65     }
  66
  67     n = q->avl_link[dir] = item;
  68
  69     // tree->avl_count++;
  70     n->avl_link[0] = n->avl_link[1] = NULL;
  71     n->avl_balance = 0;
  72     if (y == NULL) return n;
  73
  74     for (p = y, k = 0; p != n; p = p->avl_link[da[k]], k++)
  75         if (da[k] == 0)
  76             p->avl_balance--;
  77         else
  78             p->avl_balance++;
  79
  80     if (y->avl_balance == -2) {
  81         avl *x = y->avl_link[0];
  82         if (x->avl_balance == -1) {
  83             w = x;
  84             y->avl_link[0] = x->avl_link[1];
  85             x->avl_link[1] = y;
  86             x->avl_balance = y->avl_balance = 0;
  87         }
  88         else {
  89             // assert (x->avl_balance == +1);
  90             w = x->avl_link[1];
  91             x->avl_link[1] = w->avl_link[0];
  92             w->avl_link[0] = x;
  93             y->avl_link[0] = w->avl_link[1];
  94             w->avl_link[1] = y;
  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;
 101             w->avl_balance = 0;
 102         }
 103     }
 104     else if (y->avl_balance == +2) {
 105         avl *x = y->avl_link[1];
 106         if (x->avl_balance == +1) {
 107             w = x;
 108             y->avl_link[1] = x->avl_link[0];
 109             x->avl_link[0] = y;
 110             x->avl_balance = y->avl_balance = 0;
 111         }
 112         else {
 113             // assert (x->avl_balance == -1);
 114             w = x->avl_link[0];
 115             x->avl_link[0] = w->avl_link[1];
 116             w->avl_link[1] = x;
 117             y->avl_link[1] = w->avl_link[0];
 118             w->avl_link[0] = y;
 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;
 125             w->avl_balance = 0;
 126         }
 127     }
 128     else return n;
 129
 130     z->avl_link[y != z->avl_link[0]] = w;
 131
 132     // tree->avl_generation++;
 133     return n;
 134 }
 135
 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. */
 143
 144     avl *p;   /* Traverses tree to find node to delete. */
 145     int cmp;              /* Result of comparison between |item| and |p|. */
 146
 147     // assert (tree != NULL && item != NULL);
 148
 149     k = 0;
 150     p = (avl *) &tree->root;
 151     for(cmp = -1; cmp != 0; cmp = tree->compar(item, p)) {
 152         int dir = (cmp > 0);
 153
 154         pa[k] = p;
 155         da[k++] = dir;
 156
 157         p = p->avl_link[dir];
 158         if(p == NULL) return NULL;
 159     }
 160
 161     item = p;
 162
 163     if (p->avl_link[1] == NULL)
 164         pa[k - 1]->avl_link[da[k - 1]] = p->avl_link[0];
 165     else {
 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;
 171             da[k] = 1;
 172             pa[k++] = r;
 173         }
 174         else {
 175             avl *s;
 176             int j = k++;
 177
 178             for (;;) {
 179                 da[k] = 0;
 180                 pa[k++] = r;
 181                 s = r->avl_link[0];
 182                 if (s->avl_link[0] == NULL) break;
 183
 184                 r = s;
 185             }
 186
 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;
 191
 192             pa[j - 1]->avl_link[da[j - 1]] = s;
 193             da[j] = 1;
 194             pa[j] = s;
 195         }
 196     }
 197
 198     // assert (k > 0);
 199     while (--k > 0) {
 200         avl *y = pa[k];
 201
 202         if (da[k] == 0) {
 203             y->avl_balance++;
 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) {
 208                     avl *w;
 209                     // assert (x->avl_balance == -1);
 210                     w = x->avl_link[0];
 211                     x->avl_link[0] = w->avl_link[1];
 212                     w->avl_link[1] = x;
 213                     y->avl_link[1] = w->avl_link[0];
 214                     w->avl_link[0] = y;
 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;
 221                     w->avl_balance = 0;
 222                     pa[k - 1]->avl_link[da[k - 1]] = w;
 223                 }
 224                 else {
 225                     y->avl_link[1] = x->avl_link[0];
 226                     x->avl_link[0] = y;
 227                     pa[k - 1]->avl_link[da[k - 1]] = x;
 228                     if (x->avl_balance == 0) {
 229                         x->avl_balance = -1;
 230                         y->avl_balance = +1;
 231                         break;
 232                     }
 233                     else x->avl_balance = y->avl_balance = 0;
 234                 }
 235             }
 236         }
 237         else
 238         {
 239             y->avl_balance--;
 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) {
 244                     avl *w;
 245                     // assert (x->avl_balance == +1);
 246                     w = x->avl_link[1];
 247                     x->avl_link[1] = w->avl_link[0];
 248                     w->avl_link[0] = x;
 249                     y->avl_link[0] = w->avl_link[1];
 250                     w->avl_link[1] = y;
 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;
 257                     w->avl_balance = 0;
 258                     pa[k - 1]->avl_link[da[k - 1]] = w;
 259                 }
 260                 else {
 261                     y->avl_link[0] = x->avl_link[1];
 262                     x->avl_link[1] = y;
 263                     pa[k - 1]->avl_link[da[k - 1]] = x;
 264                     if (x->avl_balance == 0) {
 265                         x->avl_balance = +1;
 266                         y->avl_balance = -1;
 267                         break;
 268                     }
 269                     else x->avl_balance = y->avl_balance = 0;
 270                 }
 271             }
 272         }
 273     }
 274
 275     // tree->avl_count--;
 276     // tree->avl_generation++;
 277     return item;
 278 }
 279
 280 /* ------------------------------------------------------------------------- */
 281 // below are functions by (C) Costa Tsaousis
 282
 283 // ---------------------------
 284 // traversing
 285
 286 int avl_walker(avl *node, int (*callback)(void *entry, void *data), void *data) {
 287     int total = 0, ret = 0;
 288
 289     if(node->avl_link[0]) {
 290         ret = avl_walker(node->avl_link[0], callback, data);
 291         if(ret < 0) return ret;
 292         total += ret;
 293     }
 294
 295     ret = callback(node, data);
 296     if(ret < 0) return ret;
 297     total += ret;
 298
 299     if(node->avl_link[1]) {
 300         ret = avl_walker(node->avl_link[1], callback, data);
 301         if (ret < 0) return ret;
 302         total += ret;
 303     }
 304
 305     return total;
 306 }
 307
 308 int avl_traverse(avl_tree *t, int (*callback)(void *entry, void *data), void *data) {
 309     return avl_walker(t->root, callback, data);
 310 }
 311
 312 // ---------------------------
 313 // locks
 314
 315 void avl_read_lock(avl_tree_lock *t) {
 316 #ifndef AVL_WITHOUT_PTHREADS
 317 #ifdef AVL_LOCK_WITH_MUTEX
 318     if(unlikely(pthread_mutex_lock(&t->mutex) != 0))
 319         error("Cannot get mutex of an AVL");
 320 #else
 321     if(unlikely(pthread_rwlock_rdlock(&t->rwlock) != 0))
 322         error("Cannot get read lock of an AVL");
 323 #endif
 324 #endif /* AVL_WITHOUT_PTHREADS */
 325 }
 326
 327 void avl_write_lock(avl_tree_lock *t) {
 328 #ifndef AVL_WITHOUT_PTHREADS
 329 #ifdef AVL_LOCK_WITH_MUTEX
 330     if(unlikely(pthread_mutex_lock(&t->mutex) != 0)
 331         error("Cannot get mutex of an AVL");
 332 #else
 333     if(unlikely(pthread_rwlock_wrlock(&t->rwlock) != 0))
 334         error("Cannot write lock an AVL.");
 335 #endif
 336 #endif /* AVL_WITHOUT_PTHREADS */
 337 }
 338
 339 void avl_unlock(avl_tree_lock *t) {
 340 #ifndef AVL_WITHOUT_PTHREADS
 341 #ifdef AVL_LOCK_WITH_MUTEX
 342     if(unlikely(pthread_mutex_unlock(&t->mutex) != 0))
 343         error("Cannot unlock mutex of an AVL");
 344 #else
 345     if(unlikely(pthread_rwlock_unlock(&t->rwlock) != 0))
 346         error("Cannot unlock an AVL");
 347 #endif
 348 #endif /* AVL_WITHOUT_PTHREADS */
 349 }
 350
 351 // ---------------------------
 352 // operations with locking
 353
 354 void avl_init_lock(avl_tree_lock *t, int (*compar)(void *a, void *b)) {
 355     avl_init(&t->avl_tree, compar);
 356
 357 #ifndef AVL_WITHOUT_PTHREADS
 358     int lock;
 359
 360 #ifdef AVL_LOCK_WITH_MUTEX
 361     lock = pthread_mutex_init(&t->mutex, NULL);
 362 #else
 363     lock = pthread_rwlock_init(&t->rwlock, NULL);
 364 #endif
 365
 366     if(lock != 0)
 367         fatal("Failed to initialize AVL mutex/rwlock, error: %d", lock);
 368
 369 #endif /* AVL_WITHOUT_PTHREADS */
 370 }
 371
 372 avl *avl_search_lock(avl_tree_lock *t, avl *a) {
 373     avl_read_lock(t);
 374     avl *ret = avl_search(&t->avl_tree, a);
 375     avl_unlock(t);
 376     return ret;
 377 }
 378
 379 avl * avl_remove_lock(avl_tree_lock *t, avl *a) {
 380     avl_write_lock(t);
 381     avl *ret = avl_remove(&t->avl_tree, a);
 382     avl_unlock(t);
 383     return ret;
 384 }
 385
 386 avl *avl_insert_lock(avl_tree_lock *t, avl *a) {
 387     avl_write_lock(t);
 388     avl * ret = avl_insert(&t->avl_tree, a);
 389     avl_unlock(t);
 390     return ret;
 391 }
 392
 393 int avl_traverse_lock(avl_tree_lock *t, int (*callback)(void *entry, void *data), void *data) {
 394     int ret;
 395     avl_read_lock(t);
 396     ret = avl_traverse(&t->avl_tree, callback, data);
 397     avl_unlock(t);
 398     return ret;
 399 }
 400
 401 void avl_init(avl_tree *t, int (*compar)(void *a, void *b)) {
 402     t->root = NULL;
 403     t->compar = compar;
 404 }
 405
 406 // ------------------