avl/avl.c

   1 /*
   2  * Copyright (C) 1995-1997 by Sam Rushing <rushing@nightmare.com>
   3  *
   4  *                         All Rights Reserved
   5  *
   6  * Permission to use, copy, modify, and distribute this software and
   7  * its documentation for any purpose and without fee is hereby
   8  * granted, provided that the above copyright notice appear in all
   9  * copies and that both that copyright notice and this permission
  10  * notice appear in supporting documentation, and that the name of Sam
  11  * Rushing not be used in advertising or publicity pertaining to
  12  * distribution of the software without specific, written prior
  13  * permission.
  14  *
  15  * SAM RUSHING DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  16  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN
  17  * NO EVENT SHALL SAM RUSHING BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  18  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
  19  * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
  20  * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
  21  * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  22  *
  23  */
  24
  25 /* $Id: avl.c,v 1.11 2004/01/27 02:16:25 karl Exp $ */
  26
  27 /*
  28  * This is a fairly straightfoward translation of a prototype
  29  * written in python, 'avl_tree.py'. Read that file first.
  30  */
  31
  32 #ifdef HAVE_CONFIG_H
  33  #include <config.h>
  34 #endif
  35
  36 #include <stdio.h>
  37 #include <stdlib.h>
  38
  39 #include "avl.h"
  40
  41 avl_node *
  42 avl_node_new (void *        key,
  43           avl_node *    parent)
  44 {
  45   avl_node * node = (avl_node *) malloc (sizeof (avl_node));
  46
  47   if (!node) {
  48     return NULL;
  49   } else {
  50     node->parent = parent;
  51     node->key = key;
  52     node->left = NULL;
  53     node->right = NULL;
  54     node->rank_and_balance = 0;
  55     AVL_SET_BALANCE (node, 0);
  56     AVL_SET_RANK (node, 1);
  57     thread_rwlock_create(&node->rwlock);
  58     return node;
  59   }
  60 }
  61
  62 avl_tree *
  63 avl_tree_new (avl_key_compare_fun_type compare_fun,
  64           void * compare_arg)
  65 {
  66   avl_tree * t = (avl_tree *) malloc (sizeof (avl_tree));
  67
  68   if (!t) {
  69     return NULL;
  70   } else {
  71     avl_node * root = avl_node_new((void *)NULL, (avl_node *) NULL);
  72     if (!root) {
  73       return NULL;
  74     } else {
  75       t->root = root;
  76       t->height = 0;
  77       t->length = 0;
  78       t->compare_fun = compare_fun;
  79       t->compare_arg = compare_arg;
  80       thread_rwlock_create(&t->rwlock);
  81       return t;
  82     }
  83   }
  84 }
  85
  86 static void
  87 avl_tree_free_helper (avl_node * node, avl_free_key_fun_type free_key_fun)
  88 {
  89   if (node->left) {
  90     avl_tree_free_helper (node->left, free_key_fun);
  91   }
  92   if (free_key_fun)
  93       free_key_fun (node->key);
  94   if (node->right) {
  95     avl_tree_free_helper (node->right, free_key_fun);
  96   }
  97   thread_rwlock_destroy (&node->rwlock);
  98   free (node);
  99 }
 100
 101 void
 102 avl_tree_free (avl_tree * tree, avl_free_key_fun_type free_key_fun)
 103 {
 104   if (tree->length) {
 105     avl_tree_free_helper (tree->root->right, free_key_fun);
 106   }
 107   if (tree->root) {
 108     thread_rwlock_destroy(&tree->root->rwlock);
 109     free (tree->root);
 110   }
 111   thread_rwlock_destroy(&tree->rwlock);
 112   free (tree);
 113 }
 114
 115 int
 116 avl_insert (avl_tree * ob,
 117            void * key)
 118 {
 119   if (!(ob->root->right)) {
 120     avl_node * node = avl_node_new (key, ob->root);
 121     if (!node) {
 122       return -1;
 123     } else {
 124       ob->root->right = node;
 125       ob->length = ob->length + 1;
 126       return 0;
 127     }
 128   } else { /* not self.right == None */
 129     avl_node *t, *p, *s, *q, *r;
 130     int a;
 131
 132     t = ob->root;
 133     s = p = t->right;
 134
 135     while (1) {
 136       if (ob->compare_fun (ob->compare_arg, key, p->key) < 1) {
 137     /* move left */
 138     AVL_SET_RANK (p, (AVL_GET_RANK (p) + 1));
 139     q = p->left;
 140     if (!q) {
 141       /* insert */
 142       avl_node * q_node = avl_node_new (key, p);
 143       if (!q_node) {
 144         return (-1);
 145       } else {
 146         q = q_node;
 147         p->left = q;
 148         break;
 149       }
 150     } else if (AVL_GET_BALANCE(q)) {
 151       t = p;
 152       s = q;
 153     }
 154     p = q;
 155       } else {
 156     /* move right */
 157     q = p->right;
 158     if (!q) {
 159       /* insert */
 160       avl_node * q_node = avl_node_new (key, p);
 161       if (!q_node) {
 162         return -1;
 163       } else {
 164         q = q_node;
 165         p->right = q;
 166         break;
 167       }
 168     } else if (AVL_GET_BALANCE(q)) {
 169       t = p;
 170       s = q;
 171     }
 172     p = q;
 173       }
 174     }
 175
 176     ob->length = ob->length + 1;
 177
 178     /* adjust balance factors */
 179     if (ob->compare_fun (ob->compare_arg, key, s->key) < 1) {
 180       r = p = s->left;
 181     } else {
 182       r = p = s->right;
 183     }
 184     while (p != q) {
 185       if (ob->compare_fun (ob->compare_arg, key, p->key) < 1) {
 186     AVL_SET_BALANCE (p, -1);
 187     p = p->left;
 188       } else {
 189     AVL_SET_BALANCE (p, +1);
 190     p = p->right;
 191       }
 192     }
 193
 194     /* balancing act */
 195
 196     if (ob->compare_fun (ob->compare_arg, key, s->key) < 1) {
 197       a = -1;
 198     } else {
 199       a = +1;
 200     }
 201
 202     if (AVL_GET_BALANCE (s) == 0) {
 203       AVL_SET_BALANCE (s, a);
 204       ob->height = ob->height + 1;
 205       return 0;
 206     } else if (AVL_GET_BALANCE (s) == -a) {
 207       AVL_SET_BALANCE (s, 0);
 208       return 0;
 209     } else if (AVL_GET_BALANCE(s) == a) {
 210       if (AVL_GET_BALANCE (r) == a) {
 211     /* single rotation */
 212     p = r;
 213     if (a == -1) {
 214       s->left = r->right;
 215       if (r->right) {
 216         r->right->parent = s;
 217       }
 218       r->right = s;
 219       s->parent = r;
 220       AVL_SET_RANK (s, (AVL_GET_RANK (s) - AVL_GET_RANK (r)));
 221     } else {
 222       s->right = r->left;
 223       if (r->left) {
 224         r->left->parent = s;
 225       }
 226       r->left = s;
 227       s->parent = r;
 228       AVL_SET_RANK (r, (AVL_GET_RANK (r) + AVL_GET_RANK (s)));
 229     }
 230     AVL_SET_BALANCE (s, 0);
 231     AVL_SET_BALANCE (r, 0);
 232       } else if (AVL_GET_BALANCE (r) == -a) {
 233     /* double rotation */
 234     if (a == -1) {
 235       p = r->right;
 236       r->right = p->left;
 237       if (p->left) {
 238         p->left->parent = r;
 239       }
 240       p->left = r;
 241       r->parent = p;
 242       s->left = p->right;
 243       if (p->right) {
 244         p->right->parent = s;
 245       }
 246       p->right = s;
 247       s->parent = p;
 248       AVL_SET_RANK (p, (AVL_GET_RANK (p) + AVL_GET_RANK (r)));
 249       AVL_SET_RANK (s, (AVL_GET_RANK (s) - AVL_GET_RANK (p)));
 250     } else {
 251       p = r->left;
 252       r->left = p->right;
 253       if (p->right) {
 254         p->right->parent = r;
 255       }
 256       p->right = r;
 257       r->parent = p;
 258       s->right = p->left;
 259       if (p->left) {
 260         p->left->parent = s;
 261       }
 262       p->left = s;
 263       s->parent = p;
 264       AVL_SET_RANK (r, (AVL_GET_RANK (r) - AVL_GET_RANK (p)));
 265       AVL_SET_RANK (p, (AVL_GET_RANK (p) + AVL_GET_RANK (s)));
 266     }
 267     if (AVL_GET_BALANCE (p) == a) {
 268       AVL_SET_BALANCE (s, -a);
 269       AVL_SET_BALANCE (r, 0);
 270     } else if (AVL_GET_BALANCE (p) == -a) {
 271       AVL_SET_BALANCE (s, 0);
 272       AVL_SET_BALANCE (r, a);
 273     } else {
 274       AVL_SET_BALANCE (s, 0);
 275       AVL_SET_BALANCE (r, 0);
 276     }
 277     AVL_SET_BALANCE (p, 0);
 278       }
 279       /* finishing touch */
 280       if (s == t->right) {
 281     t->right = p;
 282       } else {
 283     t->left = p;
 284       }
 285       p->parent = t;
 286     }
 287   }
 288   return 0;
 289 }
 290
 291 int
 292 avl_get_by_index (avl_tree * tree,
 293            unsigned long index,
 294            void ** value_address)
 295 {
 296   avl_node * p = tree->root->right;
 297   unsigned long m = index + 1;
 298   while (1) {
 299     if (!p) {
 300       return -1;
 301     }
 302     if (m < AVL_GET_RANK(p)) {
 303       p = p->left;
 304     } else if (m > AVL_GET_RANK(p)) {
 305       m = m - AVL_GET_RANK(p);
 306       p = p->right;
 307     } else {
 308       *value_address = p->key;
 309       return 0;
 310     }
 311   }
 312 }
 313
 314 int
 315 avl_get_by_key (avl_tree * tree,
 316          void * key,
 317          void **value_address)
 318 {
 319   avl_node * x = tree->root->right;
 320   if (!x) {
 321     return -1;
 322   }
 323   while (1) {
 324     int compare_result = tree->compare_fun (tree->compare_arg, key, x->key);
 325     if (compare_result < 0) {
 326       if (x->left) {
 327     x = x->left;
 328       } else {
 329     return -1;
 330       }
 331     } else if (compare_result > 0) {
 332       if (x->right) {
 333     x = x->right;
 334       } else {
 335     return -1;
 336       }
 337     } else {
 338       *value_address = x->key;
 339       return 0;
 340     }
 341   }
 342 }
 343
 344 int avl_delete(avl_tree *tree, void *key, avl_free_key_fun_type free_key_fun)
 345 {
 346   avl_node *x, *y, *p, *q, *r, *top, *x_child;
 347   int shortened_side, shorter;
 348
 349   x = tree->root->right;
 350   if (!x) {
 351     return -1;
 352   }
 353   while (1) {
 354     int compare_result = tree->compare_fun (tree->compare_arg, key, x->key);
 355     if (compare_result < 0) {
 356       /* move left
 357        * We will be deleting from the left, adjust this node's
 358        * rank accordingly
 359        */
 360       AVL_SET_RANK (x, (AVL_GET_RANK(x) - 1));
 361       if (x->left) {
 362     x = x->left;
 363       } else {
 364     /* Oops! now we have to undo the rank changes
 365      * all the way up the tree
 366      */
 367     AVL_SET_RANK(x, (AVL_GET_RANK (x) + 1));
 368     while (x != tree->root->right) {
 369       if (x->parent->left == x) {
 370         AVL_SET_RANK(x->parent, (AVL_GET_RANK (x->parent) + 1));
 371       }
 372       x = x->parent;
 373     }
 374     return -1;        /* key not in tree */
 375       }
 376     } else if (compare_result > 0) {
 377       /* move right */
 378       if (x->right) {
 379     x = x->right;
 380       } else {
 381     AVL_SET_RANK(x, (AVL_GET_RANK (x) + 1));
 382     while (x != tree->root->right) {
 383       if (x->parent->left == x) {
 384         AVL_SET_RANK(x->parent, (AVL_GET_RANK (x->parent) + 1));
 385       }
 386       x = x->parent;
 387     }
 388     return -1;        /* key not in tree */
 389       }
 390     } else {
 391       break;
 392     }
 393   }
 394
 395   if (x->left && x->right) {
 396     void * temp_key;
 397
 398     /* The complicated case.
 399      * reduce this to the simple case where we are deleting
 400      * a node with at most one child.
 401      */
 402
 403     /* find the immediate predecessor <y> */
 404     y = x->left;
 405     while (y->right) {
 406       y = y->right;
 407     }
 408     /* swap <x> with <y> */
 409     temp_key = x->key;
 410     x->key = y->key;
 411     y->key = temp_key;
 412     /* we know <x>'s left subtree lost a node because that's
 413      * where we took it from
 414      */
 415     AVL_SET_RANK (x, (AVL_GET_RANK (x) - 1));
 416     x = y;
 417   }
 418   /* now <x> has at most one child
 419    * scoot this child into the place of <x>
 420    */
 421   if (x->left) {
 422     x_child = x->left;
 423     x_child->parent = x->parent;
 424   } else if (x->right) {
 425     x_child = x->right;
 426     x_child->parent = x->parent;
 427   } else {
 428     x_child = NULL;
 429   }
 430
 431   /* now tell <x>'s parent that a grandchild became a child */
 432   if (x == x->parent->left) {
 433     x->parent->left = x_child;
 434     shortened_side = -1;
 435   } else {
 436     x->parent->right = x_child;
 437     shortened_side = +1;
 438   }
 439
 440   /*
 441    * the height of the subtree <x>
 442    * has now been shortened.  climb back up
 443    * the tree, rotating when necessary to adjust
 444    * for the change.
 445    */
 446   shorter = 1;
 447   p = x->parent;
 448
 449   /* return the key and node to storage */
 450   if (free_key_fun)
 451       free_key_fun (x->key);
 452   thread_rwlock_destroy (&x->rwlock);
 453   free (x);
 454
 455   while (shorter && p->parent) {
 456
 457     /* case 1: height unchanged */
 458     if (AVL_GET_BALANCE(p) == 0) {
 459       if (shortened_side == -1) {
 460     /* we removed a left child, the tree is now heavier
 461      * on the right
 462      */
 463     AVL_SET_BALANCE (p, +1);
 464       } else {
 465     /* we removed a right child, the tree is now heavier
 466      * on the left
 467      */
 468     AVL_SET_BALANCE (p, -1);
 469       }
 470       shorter = 0;
 471
 472     } else if (AVL_GET_BALANCE (p) == shortened_side) {
 473       /* case 2: taller subtree shortened, height reduced */
 474       AVL_SET_BALANCE (p, 0);
 475     } else {
 476       /* case 3: shorter subtree shortened */
 477       top = p->parent;
 478       /* set <q> to the taller of the two subtrees of <p> */
 479       if (shortened_side == 1) {
 480     q = p->left;
 481       } else {
 482     q = p->right;
 483       }
 484       if (AVL_GET_BALANCE (q) == 0) {
 485     /* case 3a: height unchanged */
 486     if (shortened_side == -1) {
 487       /* single rotate left */
 488       q->parent = p->parent;
 489       p->right = q->left;
 490       if (q->left) {
 491         q->left->parent = p;
 492       }
 493       q->left = p;
 494       p->parent = q;
 495       AVL_SET_RANK (q, (AVL_GET_RANK (q) + AVL_GET_RANK (p)));
 496     } else {
 497       /* single rotate right */
 498       q->parent = p->parent;
 499       p->left = q->right;
 500       if (q->right) {
 501         q->right->parent = p;
 502       }
 503       q->right = p;
 504       p->parent = q;
 505       AVL_SET_RANK (p, (AVL_GET_RANK (p) - AVL_GET_RANK (q)));
 506     }
 507     shorter = 0;
 508     AVL_SET_BALANCE (q, shortened_side);
 509     AVL_SET_BALANCE (p, (- shortened_side));
 510       } else if (AVL_GET_BALANCE (q) == AVL_GET_BALANCE (p)) {
 511     /* case 3b: height reduced */
 512     if (shortened_side == -1) {
 513       /* single rotate left */
 514       q->parent = p->parent;
 515       p->right = q->left;
 516       if (q->left) {
 517         q->left->parent = p;
 518       }
 519       q->left = p;
 520       p->parent = q;
 521       AVL_SET_RANK (q, (AVL_GET_RANK (q) + AVL_GET_RANK (p)));
 522     } else {
 523       /* single rotate right */
 524       q->parent = p->parent;
 525       p->left = q->right;
 526       if (q->right) {
 527         q->right->parent = p;
 528       }
 529       q->right = p;
 530       p->parent = q;
 531       AVL_SET_RANK (p, (AVL_GET_RANK (p) - AVL_GET_RANK (q)));
 532     }
 533     shorter = 1;
 534     AVL_SET_BALANCE (q, 0);
 535     AVL_SET_BALANCE (p, 0);
 536       } else {
 537     /* case 3c: height reduced, balance factors opposite */
 538     if (shortened_side == 1) {
 539       /* double rotate right */
 540       /* first, a left rotation around q */
 541       r = q->right;
 542       r->parent = p->parent;
 543       q->right = r->left;
 544       if (r->left) {
 545         r->left->parent = q;
 546       }
 547       r->left = q;
 548       q->parent = r;
 549       /* now, a right rotation around p */
 550       p->left = r->right;
 551       if (r->right) {
 552         r->right->parent = p;
 553       }
 554       r->right = p;
 555       p->parent = r;
 556       AVL_SET_RANK (r, (AVL_GET_RANK (r) + AVL_GET_RANK (q)));
 557       AVL_SET_RANK (p, (AVL_GET_RANK (p) - AVL_GET_RANK (r)));
 558     } else {
 559       /* double rotate left */
 560       /* first, a right rotation around q */
 561       r = q->left;
 562       r->parent = p->parent;
 563       q->left = r->right;
 564       if (r->right) {
 565         r->right->parent = q;
 566       }
 567       r->right = q;
 568       q->parent = r;
 569       /* now a left rotation around p */
 570       p->right = r->left;
 571       if (r->left) {
 572         r->left->parent = p;
 573       }
 574       r->left = p;
 575       p->parent = r;
 576       AVL_SET_RANK (q, (AVL_GET_RANK (q) - AVL_GET_RANK (r)));
 577       AVL_SET_RANK (r, (AVL_GET_RANK (r) + AVL_GET_RANK (p)));
 578     }
 579     if (AVL_GET_BALANCE (r) == shortened_side) {
 580       AVL_SET_BALANCE (q, (- shortened_side));
 581       AVL_SET_BALANCE (p, 0);
 582     } else if (AVL_GET_BALANCE (r) == (- shortened_side)) {
 583       AVL_SET_BALANCE (q, 0);
 584       AVL_SET_BALANCE (p, shortened_side);
 585     } else {
 586       AVL_SET_BALANCE (q, 0);
 587       AVL_SET_BALANCE (p, 0);
 588     }
 589     AVL_SET_BALANCE (r, 0);
 590     q = r;
 591       }
 592       /* a rotation has caused <q> (or <r> in case 3c) to become
 593        * the root.  let <p>'s former parent know this.
 594        */
 595       if (top->left == p) {
 596     top->left = q;
 597       } else {
 598     top->right = q;
 599       }
 600       /* end case 3 */
 601       p = q;
 602     }
 603     x = p;
 604     p = x->parent;
 605     /* shortened_side tells us which side we came up from */
 606     if (x == p->left) {
 607       shortened_side = -1;
 608     } else {
 609       shortened_side = +1;
 610     }
 611   } /* end while(shorter) */
 612   /* when we're all done, we're one shorter */
 613   tree->length = tree->length - 1;
 614   return (0);
 615 }
 616
 617 static int
 618 avl_iterate_inorder_helper (avl_node * node,
 619             avl_iter_fun_type iter_fun,
 620             void * iter_arg)
 621 {
 622   int result;
 623   if (node->left) {
 624     result = avl_iterate_inorder_helper (node->left, iter_fun, iter_arg);
 625     if (result != 0) {
 626       return result;
 627     }
 628   }
 629   result = (iter_fun (node->key, iter_arg));
 630   if (result != 0) {
 631     return result;
 632   }
 633   if (node->right) {
 634     result = avl_iterate_inorder_helper (node->right, iter_fun, iter_arg);
 635     if (result != 0) {
 636       return result;
 637     }
 638   }
 639   return 0;
 640 }
 641
 642 int
 643 avl_iterate_inorder (avl_tree * tree,
 644          avl_iter_fun_type iter_fun,
 645          void * iter_arg)
 646 {
 647   int result;
 648
 649   if (tree->length) {
 650     result = avl_iterate_inorder_helper (tree->root->right, iter_fun, iter_arg);
 651     return (result);
 652   } else {
 653     return 0;
 654   }
 655 }
 656
 657 avl_node *avl_get_first(avl_tree *tree)
 658 {
 659     avl_node *node;
 660
 661     node = tree->root->right;
 662     if (node == NULL || node->key == NULL) return NULL;
 663
 664     while (node->left)
 665         node = node->left;
 666
 667     return node;
 668 }
 669
 670 avl_node *avl_get_prev(avl_node *node)
 671 {
 672     if (node->left) {
 673         node = node->left;
 674         while (node->right) {
 675             node = node->right;
 676         }
 677
 678         return node;
 679     } else {
 680         avl_node *child = node;
 681         while (node->parent && node->parent->key) {
 682             node = node->parent;
 683             if (child == node->right) {
 684                 return node;
 685             }
 686             child = node;
 687         }
 688
 689         return NULL;
 690     }
 691 }
 692
 693 avl_node *avl_get_next(avl_node *node)
 694 {
 695     if (node->right) {
 696         node = node->right;
 697         while (node->left) {
 698             node = node->left;
 699         }
 700
 701         return node;
 702     } else {
 703         avl_node *child = node;
 704         while (node->parent && node->parent->key) {
 705             node = node->parent;
 706             if (child == node->left) {
 707                 return node;
 708             }
 709             child = node;
 710         }
 711
 712         return NULL;
 713     }
 714 }
 715
 716 /* iterate a function over a range of indices, using get_predecessor */
 717
 718 int
 719 avl_iterate_index_range (avl_tree * tree,
 720              avl_iter_index_fun_type iter_fun,
 721              unsigned long low,
 722              unsigned long high,
 723              void * iter_arg)
 724 {
 725   unsigned long m;
 726   unsigned long num_left;
 727   avl_node * node;
 728
 729   if (high > tree->length) {
 730     return -1;
 731   }
 732   num_left = (high - low);
 733   /* find the <high-1>th node */
 734   m = high;
 735   node = tree->root->right;
 736   while (1) {
 737     if (m < AVL_GET_RANK (node)) {
 738       node = node->left;
 739     } else if (m > AVL_GET_RANK (node)) {
 740       m = m - AVL_GET_RANK (node);
 741       node = node->right;
 742     } else {
 743       break;
 744     }
 745   }
 746   /* call <iter_fun> on <node>, <get_pred(node)>, ... */
 747   while (num_left) {
 748     num_left = num_left - 1;
 749     if (iter_fun (num_left, node->key, iter_arg) != 0) {
 750       return -1;
 751     }
 752     node = avl_get_prev (node);
 753   }
 754   return 0;
 755 }
 756
 757 /* If <key> is present in the tree, return that key's node, and set <*index>
 758  * appropriately.  If not, return NULL, and set <*index> to the position
 759  * representing the closest preceding value.
 760  */
 761
 762 static avl_node *
 763 avl_get_index_by_key (avl_tree * tree,
 764           void * key,
 765           unsigned long * index)
 766 {
 767   avl_node * x = tree->root->right;
 768   unsigned long m;
 769
 770   if (!x) {
 771     return NULL;
 772   }
 773   m = AVL_GET_RANK (x);
 774
 775   while (1) {
 776     int compare_result = tree->compare_fun (tree->compare_arg, key, x->key);
 777     if (compare_result < 0) {
 778       if (x->left) {
 779     m = m - AVL_GET_RANK(x);
 780     x = x->left;
 781     m = m + AVL_GET_RANK(x);
 782       } else {
 783     *index = m - 2;
 784     return NULL;
 785       }
 786     } else if (compare_result > 0) {
 787       if (x->right) {
 788     x = x->right;
 789     m = m + AVL_GET_RANK(x);
 790       } else {
 791     *index = m - 1;
 792     return NULL;
 793       }
 794     } else {
 795       *index = m - 1;
 796       return x;
 797     }
 798   }
 799 }
 800
 801 /* return the (low index, high index) pair that spans the given key */
 802
 803 int
 804 avl_get_span_by_key (avl_tree * tree,
 805          void * key,
 806          unsigned long * low,
 807          unsigned long * high)
 808 {
 809   unsigned long m, i, j;
 810   avl_node * node;
 811
 812   node = avl_get_index_by_key (tree, key, &m);
 813
 814   /* did we find an exact match?
 815    * if so, we have to search left and right
 816    * to find the span, since we know nothing about
 817    * the arrangement of like keys.
 818    */
 819   if (node) {
 820     avl_node * left, * right;
 821     /* search left */
 822     left = avl_get_prev (node);
 823     i = m;
 824     while ((i > 0) && (tree->compare_fun (tree->compare_arg, key, left->key) == 0)) {
 825       left = avl_get_prev (left);
 826       i = i - 1;
 827     }
 828     /* search right */
 829     right = avl_get_next (node);
 830     j = m;
 831     while ((j <= tree->length) && (tree->compare_fun (tree->compare_arg, key, right->key) == 0)) {
 832       right = avl_get_next (right);
 833       j = j + 1;
 834     }
 835     *low = i;
 836     *high = j + 1;
 837     return 0;
 838   } else {
 839     *low = *high = m;
 840   }
 841   return 0;
 842 }
 843
 844 /* return the (low index, high index) pair that spans the given key */
 845
 846 int
 847 avl_get_span_by_two_keys (avl_tree * tree,
 848               void * low_key,
 849               void * high_key,
 850               unsigned long * low,
 851               unsigned long * high)
 852 {
 853   unsigned long i, j;
 854   avl_node * low_node, * high_node;
 855   int order;
 856
 857   /* we may need to swap them */
 858   order = tree->compare_fun (tree->compare_arg, low_key, high_key);
 859   if (order > 0) {
 860     void * temp = low_key;
 861     low_key = high_key;
 862     high_key = temp;
 863   }
 864
 865   low_node = avl_get_index_by_key (tree, low_key, &i);
 866   high_node = avl_get_index_by_key (tree, high_key, &j);
 867
 868   if (low_node) {
 869     avl_node * left;
 870     /* search left */
 871     left = avl_get_prev (low_node);
 872     while ((i > 0) && (tree->compare_fun (tree->compare_arg, low_key, left->key) == 0)) {
 873       left = avl_get_prev (left);
 874       i = i - 1;
 875     }
 876   } else {
 877     i = i + 1;
 878   }
 879   if (high_node) {
 880     avl_node * right;
 881     /* search right */
 882     right = avl_get_next (high_node);
 883     while ((j <= tree->length) && (tree->compare_fun (tree->compare_arg, high_key, right->key) == 0)) {
 884       right = avl_get_next (right);
 885       j = j + 1;
 886     }
 887   } else {
 888     j = j + 1;
 889   }
 890
 891   *low = i;
 892   *high = j;
 893   return 0;
 894 }
 895
 896
 897 int
 898 avl_get_item_by_key_most (avl_tree * tree,
 899               void * key,
 900               void **value_address)
 901 {
 902   avl_node * x = tree->root->right;
 903   *value_address = NULL;
 904
 905   if (!x) {
 906     return -1;
 907   }
 908   while (1) {
 909     int compare_result = tree->compare_fun (tree->compare_arg, key, x->key);
 910
 911     if (compare_result == 0) {
 912       *value_address = x->key;
 913       return 0;
 914     } else if (compare_result < 0) {
 915       /* the given key is less than the current key */
 916       if (x->left) {
 917     x = x->left;
 918       } else {
 919     if (*value_address)
 920       return 0;
 921     else
 922       return -1;
 923       }
 924     } else {
 925       /* the given key is more than the current key */
 926       /* save this value, it might end up being the right one! */
 927       *value_address = x->key;
 928       if (x->right) {
 929     /* there is a bigger entry */
 930     x = x->right;
 931       } else {
 932     if (*value_address)
 933       return 0;
 934     else
 935       return -1;
 936       }
 937     }
 938   }
 939 }
 940
 941 int
 942 avl_get_item_by_key_least (avl_tree * tree,
 943                void * key,
 944                void **value_address)
 945 {
 946   avl_node * x = tree->root->right;
 947   *value_address = NULL;
 948
 949   if (!x) {
 950     return -1;
 951   }
 952   while (1) {
 953     int compare_result = tree->compare_fun (tree->compare_arg, key, x->key);
 954     if (compare_result == 0) {
 955       *value_address = x->key;
 956       return 0;  /* exact match */
 957     } else if (compare_result < 0) {
 958       /* the given key is less than the current key */
 959       /* save this value, it might end up being the right one! */
 960       *value_address = x->key;
 961       if (x->left) {
 962     x = x->left;
 963       } else {
 964     if (*value_address)  /* we have found a valid entry */
 965       return 0;
 966     else
 967       return -1;
 968       }
 969     } else {
 970       if (x->right) {
 971     /* there is a bigger entry */
 972     x = x->right;
 973       } else {
 974     if (*value_address)  /* we have found a valid entry */
 975       return 0;
 976     else
 977       return -1;
 978       }
 979     }
 980   }
 981 }
 982
 983 #define AVL_MAX(X, Y)  ((X) > (Y) ? (X) : (Y))
 984
 985 static long
 986 avl_verify_balance (avl_node * node)
 987 {
 988   if (!node) {
 989     return 0;
 990   } else {
 991     long lh = avl_verify_balance (node->left);
 992     long rh = avl_verify_balance (node->right);
 993     if ((rh - lh) != AVL_GET_BALANCE(node)) {
 994       return 0;
 995     }
 996     if (((lh - rh) > 1) || ((lh - rh) < -1)) {
 997       return 0;
 998     }
 999     return (1 + AVL_MAX (lh, rh));
1000   }
1001 }
1002
1003 static void
1004 avl_verify_parent (avl_node * node, avl_node * parent)
1005 {
1006   if (node->parent != parent) {
1007     return;
1008   }
1009   if (node->left) {
1010     avl_verify_parent (node->left, node);
1011   }
1012   if (node->right) {
1013     avl_verify_parent (node->right, node);
1014   }
1015 }
1016
1017 static long
1018 avl_verify_rank (avl_node * node)
1019 {
1020   if (!node) {
1021     return 0;
1022   } else {
1023     unsigned long num_left=0, num_right=0;
1024     if (node->left) {
1025       num_left = avl_verify_rank (node->left);
1026     }
1027     if (node->right) {
1028       num_right = avl_verify_rank (node->right);
1029     }
1030     if (AVL_GET_RANK (node) != num_left + 1) {
1031       fprintf (stderr, "invalid rank at node %ld\n", (long) node->key);
1032       exit (1);
1033     }
1034     return (num_left + num_right + 1);
1035   }
1036 }
1037
1038 /* sanity-check the tree */
1039
1040 int
1041 avl_verify (avl_tree * tree)
1042 {
1043   if (tree->length) {
1044     avl_verify_balance (tree->root->right);
1045     avl_verify_parent  (tree->root->right, tree->root);
1046     avl_verify_rank    (tree->root->right);
1047   }
1048   return (0);
1049 }
1050
1051 /*
1052  * These structures are accumulated on the stack during print_tree
1053  * and are used to keep track of the width and direction of each
1054  * branch in the history of a particular line <node>.
1055  */
1056
1057 typedef struct _link_node {
1058   struct _link_node    * parent;
1059   char            direction;
1060   int            width;
1061 } link_node;
1062
1063 static char balance_chars[3] = {'\\', '-', '/'};
1064
1065 static int
1066 default_key_printer (char * buffer, void * key)
1067 {
1068   return sprintf (buffer, "%p", key);
1069 }
1070
1071 /*
1072  * When traveling the family tree, a change in direction
1073  * indicates when to print a connector.  This is kinda crazy,
1074  * we use the stack to build a linked list, and then travel
1075  * it backwards using recursion.
1076  */
1077
1078 static void
1079 print_connectors (link_node * link)
1080 {
1081   if (link->parent) {
1082     print_connectors (link->parent);
1083   }
1084   if (link->parent && (link->parent->direction != link->direction) && (link->parent->parent)) {
1085     int i;
1086     fprintf (stdout, "|");
1087     for (i=0; i < (link->width - 1); i++) {
1088       fprintf (stdout, " ");
1089     }
1090   } else {
1091     int i;
1092     for (i=0; i < (link->width); i++) {
1093       fprintf (stdout, " ");
1094     }
1095   }
1096 }
1097
1098 /*
1099  * The <key_printer> function writes a representation of the
1100  * key into <buffer> (which is conveniently fixed in size to add
1101  * the spice of danger).  It should return the size of the
1102  * representation.
1103  */
1104
1105 static void
1106 print_node (avl_key_printer_fun_type key_printer,
1107         avl_node * node,
1108         link_node * link)
1109 {
1110   char buffer[256];
1111   unsigned int width;
1112   width = key_printer (buffer, node->key);
1113
1114   if (node->right) {
1115       link_node here;
1116       here.parent = link;
1117       here.direction = 1;
1118       here.width = width + 11;
1119     print_node (key_printer, node->right, &here);
1120   }
1121   print_connectors (link);
1122   fprintf (stdout, "+-[%c %s %03d]",
1123        balance_chars[AVL_GET_BALANCE(node)+1],
1124        buffer,
1125        (int)AVL_GET_RANK(node));
1126   if (node->left || node->right) {
1127     fprintf (stdout, "-|\n");
1128   } else {
1129     fprintf (stdout, "\n");
1130   }
1131   if (node->left) {
1132       link_node here;
1133       here.parent = link;
1134       here.direction = -1;
1135       here.width = width + 11;
1136       print_node (key_printer, node->left, &here);
1137   }
1138 }
1139
1140 void
1141 avl_print_tree (avl_tree * tree, avl_key_printer_fun_type key_printer)
1142 {
1143   link_node top = {NULL, 0, 0};
1144   if (!key_printer) {
1145     key_printer = default_key_printer;
1146   }
1147   if (tree->length) {
1148     print_node (key_printer, tree->root->right, &top);
1149   } else {
1150     fprintf (stdout, "<empty tree>\n");
1151   }
1152 }
1153
1154
1155 void avl_tree_rlock(avl_tree *tree)
1156 {
1157     thread_rwlock_rlock(&tree->rwlock);
1158 }
1159
1160 void avl_tree_wlock(avl_tree *tree)
1161 {
1162     thread_rwlock_wlock(&tree->rwlock);
1163 }
1164
1165 void avl_tree_unlock(avl_tree *tree)
1166 {
1167     thread_rwlock_unlock(&tree->rwlock);
1168 }
1169
1170 void avl_node_rlock(avl_node *node)
1171 {
1172     thread_rwlock_rlock(&node->rwlock);
1173 }
1174
1175 void avl_node_wlock(avl_node *node)
1176 {
1177     thread_rwlock_wlock(&node->rwlock);
1178 }
1179
1180 void avl_node_unlock(avl_node *node)
1181 {
1182     thread_rwlock_unlock(&node->rwlock);
1183 }