servers/vm/cavl_impl.h

   1 /* Abstract AVL Tree Generic C Package.
   2 ** Implementation generation header file.
   3 **
   4 ** This code is in the public domain.  See cavl_tree.html for interface
   5 ** documentation.
   6 **
   7 ** Version: 1.5  Author: Walt Karas
   8 */
   9
  10 #include <string.h>
  11
  12 #undef L__
  13 #undef L__EST_LONG_BIT
  14 #undef L__SIZE
  15 #undef L__tree
  16 #undef L__MASK_HIGH_BIT
  17 #undef L__LONG_BIT
  18 #undef L__BIT_ARR_DEFN
  19 #undef L__BIT_ARR_CLEAR
  20 #undef L__BIT_ARR_VAL
  21 #undef L__BIT_ARR_0
  22 #undef L__BIT_ARR_1
  23 #undef L__BIT_ARR_ALL
  24 #undef L__BIT_ARR_LONGS
  25 #undef L__IMPL_MASK
  26 #undef L__CHECK_READ_ERROR
  27 #undef L__CHECK_READ_ERROR_INV_DEPTH
  28 #undef L__SC
  29 #undef L__BALANCE_PARAM_PREFIX
  30
  31 #ifdef AVL_UNIQUE
  32
  33 #define L__ AVL_UNIQUE
  34
  35 #else
  36
  37 #define L__(X) X
  38
  39 #endif
  40
  41 /* Determine correct storage class for functions */
  42 #ifdef AVL_PRIVATE
  43
  44 #define L__SC static
  45
  46 #else
  47
  48 #define L__SC
  49
  50 #endif
  51
  52 #ifdef AVL_SIZE
  53
  54 #define L__SIZE AVL_SIZE
  55
  56 #else
  57
  58 #define L__SIZE unsigned long
  59
  60 #endif
  61
  62 #define L__MASK_HIGH_BIT ((int) ~ ((~ (unsigned) 0) >> 1))
  63
  64 /* ANSI C/ISO C++ require that a long have at least 32 bits.  Set
  65 ** L__EST_LONG_BIT to be the greatest multiple of 8 in the range
  66 ** 32 - 64 (inclusive) that is less than or equal to the number of
  67 ** bits in a long.
  68 */
  69
  70 #if (((LONG_MAX >> 31) >> 7) == 0)
  71
  72 #define L__EST_LONG_BIT 32
  73
  74 #elif (((LONG_MAX >> 31) >> 15) == 0)
  75
  76 #define L__EST_LONG_BIT 40
  77
  78 #elif (((LONG_MAX >> 31) >> 23) == 0)
  79
  80 #define L__EST_LONG_BIT 48
  81
  82 #elif (((LONG_MAX >> 31) >> 31) == 0)
  83
  84 #define L__EST_LONG_BIT 56
  85
  86 #else
  87
  88 #define L__EST_LONG_BIT 64
  89
  90 #endif
  91
  92 #define L__LONG_BIT (sizeof(long) * CHAR_BIT)
  93
  94 #if ((AVL_MAX_DEPTH) > L__EST_LONG_BIT)
  95
  96 /* The maximum depth may be greater than the number of bits in a long,
  97 ** so multiple longs are needed to hold a bit array indexed by node
  98 ** depth. */
  99
 100 #define L__BIT_ARR_LONGS (((AVL_MAX_DEPTH) + L__LONG_BIT - 1) / L__LONG_BIT)
 101
 102 #define L__BIT_ARR_DEFN(NAME) unsigned long NAME[L__BIT_ARR_LONGS];
 103
 104 #define L__BIT_ARR_CLEAR(NAME) memset(NAME, 0, sizeof(NAME));
 105
 106 #define L__BIT_ARR_VAL(BIT_ARR, BIT_NUM) \
 107   ((BIT_ARR)[(BIT_NUM) / L__LONG_BIT] & (1L << ((BIT_NUM) % L__LONG_BIT)))
 108
 109 #define L__BIT_ARR_0(BIT_ARR, BIT_NUM) \
 110   (BIT_ARR)[(BIT_NUM) / L__LONG_BIT] &= ~(1L << ((BIT_NUM) % L__LONG_BIT));
 111
 112 #define L__BIT_ARR_1(BIT_ARR, BIT_NUM) \
 113   (BIT_ARR)[(BIT_NUM) / L__LONG_BIT] |= 1L << ((BIT_NUM) % L__LONG_BIT);
 114
 115 #define L__BIT_ARR_ALL(BIT_ARR, BIT_VAL) \
 116   { int i = L__BIT_ARR_LONGS; do (BIT_ARR)[--i] = 0L - (BIT_VAL); while(i); }
 117
 118 #else /* The bit array can definitely fit in one long */
 119
 120 #define L__BIT_ARR_DEFN(NAME) unsigned long NAME;
 121
 122 #define L__BIT_ARR_CLEAR(NAME) NAME = 0;
 123
 124 #define L__BIT_ARR_VAL(BIT_ARR, BIT_NUM) ((BIT_ARR) & (1L << (BIT_NUM)))
 125
 126 #define L__BIT_ARR_0(BIT_ARR, BIT_NUM) (BIT_ARR) &= ~(1L << (BIT_NUM));
 127
 128 #define L__BIT_ARR_1(BIT_ARR, BIT_NUM) (BIT_ARR) |= 1L << (BIT_NUM);
 129
 130 #define L__BIT_ARR_ALL(BIT_ARR, BIT_VAL) (BIT_ARR) = 0L - (BIT_VAL);
 131
 132 #endif
 133
 134 #ifdef AVL_READ_ERRORS_HAPPEN
 135
 136 #define L__CHECK_READ_ERROR(ERROR_RETURN) \
 137 { if (AVL_READ_ERROR) return(ERROR_RETURN); }
 138
 139 #else
 140
 141 #define L__CHECK_READ_ERROR(ERROR_RETURN)
 142
 143 #endif
 144
 145 /* The presumed reason that an instantiation places additional fields
 146 ** inside the AVL tree structure is that the SET_ and GET_ macros
 147 ** need these fields.  The "balance" function does not explicitly use
 148 ** any fields in the AVL tree structure, so only pass an AVL tree
 149 ** structure pointer to "balance" if it has instantiation-specific
 150 ** fields that are (presumably) needed by the SET_/GET_ calls within
 151 ** "balance".
 152 */
 153 #ifdef AVL_INSIDE_STRUCT
 154
 155 #define L__BALANCE_PARAM_CALL_PREFIX L__tree,
 156 #define L__BALANCE_PARAM_DECL_PREFIX L__(avl) *L__tree,
 157
 158 #else
 159
 160 #define L__BALANCE_PARAM_CALL_PREFIX
 161 #define L__BALANCE_PARAM_DECL_PREFIX
 162
 163 #endif
 164
 165 #ifdef AVL_IMPL_MASK
 166
 167 #define L__IMPL_MASK (AVL_IMPL_MASK)
 168
 169 #else
 170
 171 /* Define all functions. */
 172 #define L__IMPL_MASK AVL_IMPL_ALL
 173
 174 #endif
 175
 176 #if (L__IMPL_MASK & AVL_IMPL_INIT)
 177
 178 L__SC void L__(init)(L__(avl) *L__tree) { AVL_SET_ROOT(L__tree, AVL_NULL); }
 179
 180 #endif
 181
 182 #if (L__IMPL_MASK & AVL_IMPL_IS_EMPTY)
 183
 184 L__SC int L__(is_empty)(L__(avl) *L__tree)
 185   { return(L__tree->root == AVL_NULL); }
 186
 187 #endif
 188
 189 /* Put the private balance function in the same compilation module as
 190 ** the insert function.  */
 191 #if (L__IMPL_MASK & AVL_IMPL_INSERT)
 192
 193 /* Balances subtree, returns handle of root node of subtree after balancing.
 194 */
 195 static L__SC AVL_HANDLE L__(balance)(L__BALANCE_PARAM_DECL_PREFIX AVL_HANDLE bal_h)
 196   {
 197     AVL_HANDLE deep_h;
 198
 199     /* Either the "greater than" or the "less than" subtree of
 200     ** this node has to be 2 levels deeper (or else it wouldn't
 201     ** need balancing).
 202     */
 203     if (AVL_GET_BALANCE_FACTOR(bal_h) > 0)
 204       {
 205         /* "Greater than" subtree is deeper. */
 206
 207         deep_h = AVL_GET_GREATER(bal_h, 1);
 208
 209         L__CHECK_READ_ERROR(AVL_NULL)
 210
 211         if (AVL_GET_BALANCE_FACTOR(deep_h) < 0)
 212           {
 213             int bf;
 214
 215             AVL_HANDLE old_h = bal_h;
 216             bal_h = AVL_GET_LESS(deep_h, 1);
 217             L__CHECK_READ_ERROR(AVL_NULL)
 218             AVL_SET_GREATER(old_h, AVL_GET_LESS(bal_h, 1))
 219             AVL_SET_LESS(deep_h, AVL_GET_GREATER(bal_h, 1))
 220             AVL_SET_LESS(bal_h, old_h)
 221             AVL_SET_GREATER(bal_h, deep_h)
 222
 223             bf = AVL_GET_BALANCE_FACTOR(bal_h);
 224             if (bf != 0)
 225               {
 226                 if (bf > 0)
 227                   {
 228                     AVL_SET_BALANCE_FACTOR(old_h, -1)
 229                     AVL_SET_BALANCE_FACTOR(deep_h, 0)
 230                   }
 231                 else
 232                   {
 233                     AVL_SET_BALANCE_FACTOR(deep_h, 1)
 234                     AVL_SET_BALANCE_FACTOR(old_h, 0)
 235                   }
 236                 AVL_SET_BALANCE_FACTOR(bal_h, 0)
 237               }
 238             else
 239               {
 240                 AVL_SET_BALANCE_FACTOR(old_h, 0)
 241                 AVL_SET_BALANCE_FACTOR(deep_h, 0)
 242               }
 243           }
 244         else
 245           {
 246             AVL_SET_GREATER(bal_h, AVL_GET_LESS(deep_h, 0))
 247             AVL_SET_LESS(deep_h, bal_h)
 248             if (AVL_GET_BALANCE_FACTOR(deep_h) == 0)
 249               {
 250                 AVL_SET_BALANCE_FACTOR(deep_h, -1)
 251                 AVL_SET_BALANCE_FACTOR(bal_h, 1)
 252               }
 253             else
 254               {
 255                 AVL_SET_BALANCE_FACTOR(deep_h, 0)
 256                 AVL_SET_BALANCE_FACTOR(bal_h, 0)
 257               }
 258             bal_h = deep_h;
 259           }
 260       }
 261     else
 262       {
 263         /* "Less than" subtree is deeper. */
 264
 265         deep_h = AVL_GET_LESS(bal_h, 1);
 266         L__CHECK_READ_ERROR(AVL_NULL)
 267
 268         if (AVL_GET_BALANCE_FACTOR(deep_h) > 0)
 269           {
 270             int bf;
 271             AVL_HANDLE old_h = bal_h;
 272             bal_h = AVL_GET_GREATER(deep_h, 1);
 273             L__CHECK_READ_ERROR(AVL_NULL)
 274             AVL_SET_LESS(old_h, AVL_GET_GREATER(bal_h, 0))
 275             AVL_SET_GREATER(deep_h, AVL_GET_LESS(bal_h, 0))
 276             AVL_SET_GREATER(bal_h, old_h)
 277             AVL_SET_LESS(bal_h, deep_h)
 278
 279             bf = AVL_GET_BALANCE_FACTOR(bal_h);
 280             if (bf != 0)
 281               {
 282                 if (bf < 0)
 283                   {
 284                     AVL_SET_BALANCE_FACTOR(old_h, 1)
 285                     AVL_SET_BALANCE_FACTOR(deep_h, 0)
 286                   }
 287                 else
 288                   {
 289                     AVL_SET_BALANCE_FACTOR(deep_h, -1)
 290                     AVL_SET_BALANCE_FACTOR(old_h, 0)
 291                   }
 292                 AVL_SET_BALANCE_FACTOR(bal_h, 0)
 293               }
 294             else
 295               {
 296                 AVL_SET_BALANCE_FACTOR(old_h, 0)
 297                 AVL_SET_BALANCE_FACTOR(deep_h, 0)
 298               }
 299           }
 300         else
 301           {
 302             AVL_SET_LESS(bal_h, AVL_GET_GREATER(deep_h, 0))
 303             AVL_SET_GREATER(deep_h, bal_h)
 304             if (AVL_GET_BALANCE_FACTOR(deep_h) == 0)
 305               {
 306                 AVL_SET_BALANCE_FACTOR(deep_h, 1)
 307                 AVL_SET_BALANCE_FACTOR(bal_h, -1)
 308               }
 309             else
 310               {
 311                 AVL_SET_BALANCE_FACTOR(deep_h, 0)
 312                 AVL_SET_BALANCE_FACTOR(bal_h, 0)
 313               }
 314             bal_h = deep_h;
 315           }
 316       }
 317
 318     return(bal_h);
 319   }
 320
 321 L__SC AVL_HANDLE L__(insert)(L__(avl) *L__tree, AVL_HANDLE h)
 322   {
 323     AVL_SET_LESS(h, AVL_NULL)
 324     AVL_SET_GREATER(h, AVL_NULL)
 325     AVL_SET_BALANCE_FACTOR(h, 0)
 326
 327     if (L__tree->root == AVL_NULL) {
 328       AVL_SET_ROOT(L__tree, h);
 329     } else
 330       {
 331         /* Last unbalanced node encountered in search for insertion point. */
 332         AVL_HANDLE unbal = AVL_NULL;
 333         /* Parent of last unbalanced node. */
 334         AVL_HANDLE parent_unbal = AVL_NULL;
 335         /* Balance factor of last unbalanced node. */
 336         int unbal_bf;
 337
 338         /* Zero-based depth in tree. */
 339         unsigned depth = 0, unbal_depth = 0;
 340
 341         /* Records a path into the tree.  If bit n is true, indicates
 342         ** take greater branch from the nth node in the path, otherwise
 343         ** take the less branch.  bit 0 gives branch from root, and
 344         ** so on. */
 345         L__BIT_ARR_DEFN(branch)
 346
 347         AVL_HANDLE hh = L__tree->root;
 348         AVL_HANDLE parent = AVL_NULL;
 349         int cmp;
 350
 351         L__BIT_ARR_CLEAR(branch)
 352
 353         do
 354           {
 355             if (AVL_GET_BALANCE_FACTOR(hh) != 0)
 356               {
 357                 unbal = hh;
 358                 parent_unbal = parent;
 359                 unbal_depth = depth;
 360               }
 361             cmp = AVL_COMPARE_NODE_NODE(h, hh);
 362             if (cmp == 0)
 363               /* Duplicate key. */
 364               return(hh);
 365             parent = hh;
 366             if (cmp > 0)
 367               {
 368                 hh = AVL_GET_GREATER(hh, 1);
 369                 L__BIT_ARR_1(branch, depth)
 370               }
 371             else
 372               {
 373                 hh = AVL_GET_LESS(hh, 1);
 374                 L__BIT_ARR_0(branch, depth)
 375               }
 376             L__CHECK_READ_ERROR(AVL_NULL)
 377             depth++;
 378           }
 379         while (hh != AVL_NULL);
 380
 381         /*  Add node to insert as leaf of tree. */
 382         if (cmp < 0)
 383           AVL_SET_LESS(parent, h)
 384         else
 385           AVL_SET_GREATER(parent, h)
 386
 387         depth = unbal_depth;
 388
 389         if (unbal == AVL_NULL)
 390           hh = L__tree->root;
 391         else
 392           {
 393             cmp = L__BIT_ARR_VAL(branch, depth) ? 1 : -1;
 394             depth++;
 395             unbal_bf = AVL_GET_BALANCE_FACTOR(unbal);
 396             if (cmp < 0)
 397               unbal_bf--;
 398             else  /* cmp > 0 */
 399               unbal_bf++;
 400             hh = cmp < 0 ? AVL_GET_LESS(unbal, 1) : AVL_GET_GREATER(unbal, 1);
 401             L__CHECK_READ_ERROR(AVL_NULL)
 402             if ((unbal_bf != -2) && (unbal_bf != 2))
 403               {
 404                 /* No rebalancing of tree is necessary. */
 405                 AVL_SET_BALANCE_FACTOR(unbal, unbal_bf)
 406                 unbal = AVL_NULL;
 407               }
 408           }
 409
 410         if (hh != AVL_NULL)
 411           while (h != hh)
 412             {
 413               cmp = L__BIT_ARR_VAL(branch, depth) ? 1 : -1;
 414               depth++;
 415               if (cmp < 0)
 416                 {
 417                   AVL_SET_BALANCE_FACTOR(hh, -1)
 418                   hh = AVL_GET_LESS(hh, 1);
 419                 }
 420               else /* cmp > 0 */
 421                 {
 422                   AVL_SET_BALANCE_FACTOR(hh, 1)
 423                   hh = AVL_GET_GREATER(hh, 1);
 424                 }
 425               L__CHECK_READ_ERROR(AVL_NULL)
 426             }
 427
 428         if (unbal != AVL_NULL)
 429           {
 430             unbal = L__(balance)(L__BALANCE_PARAM_CALL_PREFIX unbal);
 431             L__CHECK_READ_ERROR(AVL_NULL)
 432             if (parent_unbal == AVL_NULL)
 433               {
 434               AVL_SET_ROOT(L__tree, unbal);
 435               }
 436             else
 437               {
 438                 depth = unbal_depth - 1;
 439                 cmp = L__BIT_ARR_VAL(branch, depth) ? 1 : -1;
 440                 if (cmp < 0)
 441                   AVL_SET_LESS(parent_unbal, unbal)
 442                 else  /* cmp > 0 */
 443                   AVL_SET_GREATER(parent_unbal, unbal)
 444               }
 445           }
 446
 447       }
 448
 449     return(h);
 450   }
 451
 452 #endif
 453
 454 #if (L__IMPL_MASK & AVL_IMPL_SEARCH)
 455
 456 L__SC AVL_HANDLE L__(search)(L__(avl) *L__tree, AVL_KEY k, avl_search_type st)
 457   {
 458     int cmp, target_cmp;
 459     AVL_HANDLE match_h = AVL_NULL;
 460     AVL_HANDLE h = L__tree->root;
 461
 462     if (st & AVL_LESS)
 463       target_cmp = 1;
 464     else if (st & AVL_GREATER)
 465       target_cmp = -1;
 466     else
 467       target_cmp = 0;
 468
 469     while (h != AVL_NULL)
 470       {
 471         cmp = AVL_COMPARE_KEY_NODE(k, h);
 472         if (cmp == 0)
 473           {
 474             if (st & AVL_EQUAL)
 475               {
 476                 match_h = h;
 477                 break;
 478               }
 479             cmp = -target_cmp;
 480           }
 481         else if (target_cmp != 0)
 482           if (!((cmp ^ target_cmp) & L__MASK_HIGH_BIT))
 483             /* cmp and target_cmp are both positive or both negative. */
 484             match_h = h;
 485         h = cmp < 0 ? AVL_GET_LESS(h, 1) : AVL_GET_GREATER(h, 1);
 486         L__CHECK_READ_ERROR(AVL_NULL)
 487       }
 488
 489     return(match_h);
 490   }
 491
 492 #endif
 493
 494 #if (L__IMPL_MASK & AVL_IMPL_SEARCH_LEAST)
 495
 496 L__SC AVL_HANDLE L__(search_least)(L__(avl) *L__tree)
 497   {
 498     AVL_HANDLE h = L__tree->root;
 499     AVL_HANDLE parent = AVL_NULL;
 500
 501     while (h != AVL_NULL)
 502       {
 503         parent = h;
 504         h = AVL_GET_LESS(h, 1);
 505         L__CHECK_READ_ERROR(AVL_NULL)
 506       }
 507
 508     return(parent);
 509   }
 510
 511 #endif
 512
 513 L__SC AVL_HANDLE L__(search_root)(L__(avl) *L__tree)
 514   {
 515     return L__tree->root;
 516   }
 517
 518
 519 #if (L__IMPL_MASK & AVL_IMPL_SEARCH_GREATEST)
 520
 521 L__SC AVL_HANDLE L__(search_greatest)(L__(avl) *L__tree)
 522   {
 523     AVL_HANDLE h = L__tree->root;
 524     AVL_HANDLE parent = AVL_NULL;
 525
 526     while (h != AVL_NULL)
 527       {
 528         parent = h;
 529         h = AVL_GET_GREATER(h, 1);
 530         L__CHECK_READ_ERROR(AVL_NULL)
 531       }
 532
 533     return(parent);
 534   }
 535
 536 #endif
 537
 538 #if (L__IMPL_MASK & AVL_IMPL_REMOVE)
 539
 540 /* Prototype of balance function (called by remove) in case not in
 541 ** same compilation unit.
 542 */
 543 L__SC AVL_HANDLE L__(balance)(L__BALANCE_PARAM_DECL_PREFIX AVL_HANDLE bal_h);
 544
 545 L__SC AVL_HANDLE L__(remove)(L__(avl) *L__tree, AVL_KEY k)
 546   {
 547     /* Zero-based depth in tree. */
 548     unsigned depth = 0, rm_depth;
 549
 550     /* Records a path into the tree.  If bit n is true, indicates
 551     ** take greater branch from the nth node in the path, otherwise
 552     ** take the less branch.  bit 0 gives branch from root, and
 553     ** so on. */
 554     L__BIT_ARR_DEFN(branch)
 555
 556     AVL_HANDLE h = L__tree->root;
 557     AVL_HANDLE parent = AVL_NULL;
 558     AVL_HANDLE child;
 559     AVL_HANDLE path;
 560     int cmp, cmp_shortened_sub_with_path = 0;
 561     int reduced_depth;
 562     int bf;
 563     AVL_HANDLE rm;
 564     AVL_HANDLE parent_rm;
 565
 566     L__BIT_ARR_CLEAR(branch)
 567
 568     for ( ; ; )
 569       {
 570         if (h == AVL_NULL)
 571           /* No node in tree with given key. */
 572           return(AVL_NULL);
 573         cmp = AVL_COMPARE_KEY_NODE(k, h);
 574         if (cmp == 0)
 575           /* Found node to remove. */
 576           break;
 577         parent = h;
 578         if (cmp > 0)
 579           {
 580             h = AVL_GET_GREATER(h, 1);
 581             L__BIT_ARR_1(branch, depth)
 582           }
 583         else
 584           {
 585             h = AVL_GET_LESS(h, 1);
 586             L__BIT_ARR_0(branch, depth)
 587           }
 588         L__CHECK_READ_ERROR(AVL_NULL)
 589         depth++;
 590         cmp_shortened_sub_with_path = cmp;
 591       }
 592     rm = h;
 593     parent_rm = parent;
 594     rm_depth = depth;
 595
 596     /* If the node to remove is not a leaf node, we need to get a
 597     ** leaf node, or a node with a single leaf as its child, to put
 598     ** in the place of the node to remove.  We will get the greatest
 599     ** node in the less subtree (of the node to remove), or the least
 600     ** node in the greater subtree.  We take the leaf node from the
 601     ** deeper subtree, if there is one. */
 602
 603     if (AVL_GET_BALANCE_FACTOR(h) < 0)
 604       {
 605         child = AVL_GET_LESS(h, 1);
 606         L__BIT_ARR_0(branch, depth)
 607         cmp = -1;
 608       }
 609     else
 610       {
 611         child = AVL_GET_GREATER(h, 1);
 612         L__BIT_ARR_1(branch, depth)
 613         cmp = 1;
 614       }
 615     L__CHECK_READ_ERROR(AVL_NULL)
 616     depth++;
 617
 618     if (child != AVL_NULL)
 619       {
 620         cmp = -cmp;
 621         do
 622           {
 623             parent = h;
 624             h = child;
 625             if (cmp < 0)
 626               {
 627                 child = AVL_GET_LESS(h, 1);
 628                 L__BIT_ARR_0(branch, depth)
 629               }
 630             else
 631               {
 632                 child = AVL_GET_GREATER(h, 1);
 633                 L__BIT_ARR_1(branch, depth)
 634               }
 635             L__CHECK_READ_ERROR(AVL_NULL)
 636             depth++;
 637           }
 638         while (child != AVL_NULL);
 639
 640         if (parent == rm)
 641           /* Only went through do loop once.  Deleted node will be replaced
 642           ** in the tree structure by one of its immediate children. */
 643           cmp_shortened_sub_with_path = -cmp;
 644         else
 645           cmp_shortened_sub_with_path = cmp;
 646
 647         /* Get the handle of the opposite child, which may not be null. */
 648         child = cmp > 0 ? AVL_GET_LESS(h, 0) : AVL_GET_GREATER(h, 0);
 649       }
 650
 651     if (parent == AVL_NULL) {
 652       /* There were only 1 or 2 nodes in this tree. */
 653       AVL_SET_ROOT(L__tree, child);
 654     }
 655     else if (cmp_shortened_sub_with_path < 0)
 656       AVL_SET_LESS(parent, child)
 657     else
 658       AVL_SET_GREATER(parent, child)
 659
 660     /* "path" is the parent of the subtree being eliminated or reduced
 661     ** from a depth of 2 to 1.  If "path" is the node to be removed, we
 662     ** set path to the node we're about to poke into the position of the
 663     ** node to be removed. */
 664     path = parent == rm ? h : parent;
 665
 666     if (h != rm)
 667       {
 668         /* Poke in the replacement for the node to be removed. */
 669         AVL_SET_LESS(h, AVL_GET_LESS(rm, 0))
 670         AVL_SET_GREATER(h, AVL_GET_GREATER(rm, 0))
 671         AVL_SET_BALANCE_FACTOR(h, AVL_GET_BALANCE_FACTOR(rm))
 672         if (parent_rm == AVL_NULL) {
 673           AVL_SET_ROOT(L__tree, h);
 674         }
 675         else
 676           {
 677             depth = rm_depth - 1;
 678             if (L__BIT_ARR_VAL(branch, depth))
 679               AVL_SET_GREATER(parent_rm, h)
 680             else
 681               AVL_SET_LESS(parent_rm, h)
 682           }
 683       }
 684
 685     if (path != AVL_NULL)
 686       {
 687         /* Create a temporary linked list from the parent of the path node
 688         ** to the root node. */
 689         h = L__tree->root;
 690         parent = AVL_NULL;
 691         depth = 0;
 692         while (h != path)
 693           {
 694             if (L__BIT_ARR_VAL(branch, depth))
 695               {
 696                 child = AVL_GET_GREATER(h, 1);
 697                 AVL_SET_GREATER(h, parent)
 698               }
 699             else
 700               {
 701                 child = AVL_GET_LESS(h, 1);
 702                 AVL_SET_LESS(h, parent)
 703               }
 704             L__CHECK_READ_ERROR(AVL_NULL)
 705             depth++;
 706             parent = h;
 707             h = child;
 708           }
 709
 710         /* Climb from the path node to the root node using the linked
 711         ** list, restoring the tree structure and rebalancing as necessary.
 712         */
 713         reduced_depth = 1;
 714         cmp = cmp_shortened_sub_with_path;
 715         for ( ; ; )
 716           {
 717             if (reduced_depth)
 718               {
 719                 bf = AVL_GET_BALANCE_FACTOR(h);
 720                 if (cmp < 0)
 721                   bf++;
 722                 else  /* cmp > 0 */
 723                   bf--;
 724                 if ((bf == -2) || (bf == 2))
 725                   {
 726                     h = L__(balance)(L__BALANCE_PARAM_CALL_PREFIX h);
 727                     L__CHECK_READ_ERROR(AVL_NULL)
 728                     bf = AVL_GET_BALANCE_FACTOR(h);
 729                   }
 730                 else
 731                   AVL_SET_BALANCE_FACTOR(h, bf)
 732                 reduced_depth = (bf == 0);
 733               }
 734             if (parent == AVL_NULL)
 735               break;
 736             child = h;
 737             h = parent;
 738             depth--;
 739             cmp = L__BIT_ARR_VAL(branch, depth) ? 1 : -1;
 740             if (cmp < 0)
 741               {
 742                 parent = AVL_GET_LESS(h, 1);
 743                 AVL_SET_LESS(h, child)
 744               }
 745             else
 746               {
 747                 parent = AVL_GET_GREATER(h, 1);
 748                 AVL_SET_GREATER(h, child)
 749               }
 750             L__CHECK_READ_ERROR(AVL_NULL)
 751           }
 752         AVL_SET_ROOT(L__tree, h);
 753       }
 754
 755     return(rm);
 756   }
 757
 758 #endif
 759
 760 #if (L__IMPL_MASK & AVL_IMPL_SUBST)
 761
 762 L__SC AVL_HANDLE L__(subst)(L__(avl) *L__tree, AVL_HANDLE new_node)
 763   {
 764     AVL_HANDLE h = L__tree->root;
 765     AVL_HANDLE parent = AVL_NULL;
 766     int cmp, last_cmp = 0;
 767
 768     /* Search for node already in tree with same key. */
 769     for ( ; ; )
 770       {
 771         if (h == AVL_NULL)
 772           /* No node in tree with same key as new node. */
 773           return(AVL_NULL);
 774         cmp = AVL_COMPARE_NODE_NODE(new_node, h);
 775         if (cmp == 0)
 776           /* Found the node to substitute new one for. */
 777           break;
 778         last_cmp = cmp;
 779         parent = h;
 780         h = cmp < 0 ? AVL_GET_LESS(h, 1) : AVL_GET_GREATER(h, 1);
 781         L__CHECK_READ_ERROR(AVL_NULL)
 782       }
 783
 784     /* Copy tree housekeeping fields from node in tree to new node. */
 785     AVL_SET_LESS(new_node, AVL_GET_LESS(h, 0))
 786     AVL_SET_GREATER(new_node, AVL_GET_GREATER(h, 0))
 787     AVL_SET_BALANCE_FACTOR(new_node, AVL_GET_BALANCE_FACTOR(h))
 788
 789     if (parent == AVL_NULL)
 790      {
 791       /* New node is also new root. */
 792       AVL_SET_ROOT(L__tree, new_node);
 793      }
 794     else
 795       {
 796         /* Make parent point to new node. */
 797         if (last_cmp < 0)
 798           AVL_SET_LESS(parent, new_node)
 799         else
 800           AVL_SET_GREATER(parent, new_node)
 801       }
 802
 803     return(h);
 804   }
 805
 806 #endif
 807
 808 #ifdef AVL_BUILD_ITER_TYPE
 809
 810 #if (L__IMPL_MASK & AVL_IMPL_BUILD)
 811
 812 L__SC int L__(build)(
 813   L__(avl) *L__tree, AVL_BUILD_ITER_TYPE p, L__SIZE num_nodes)
 814   {
 815     /* Gives path to subtree being built.  If bit n is false, branch
 816     ** less from the node at depth n, if true branch greater. */
 817     L__BIT_ARR_DEFN(branch)
 818
 819     /* If bit n is true, then for the current subtree at depth n, its
 820     ** greater subtree has one more node than its less subtree. */
 821     L__BIT_ARR_DEFN(rem)
 822
 823     /* Depth of root node of current subtree. */
 824     unsigned depth = 0;
 825
 826     /* Number of nodes in current subtree. */
 827     L__SIZE num_sub = num_nodes;
 828
 829     /* The algorithm relies on a stack of nodes whose less subtree has
 830     ** been built, but whose greater subtree has not yet been built.
 831     ** The stack is implemented as linked list.  The nodes are linked
 832     ** together by having the "greater" handle of a node set to the
 833     ** next node in the list.  "less_parent" is the handle of the first
 834     ** node in the list. */
 835     AVL_HANDLE less_parent = AVL_NULL;
 836
 837     /* h is root of current subtree, child is one of its children. */
 838     AVL_HANDLE h;
 839     AVL_HANDLE child;
 840
 841     if (num_nodes == 0)
 842       {
 843         AVL_SET_ROOT(L__tree, AVL_NULL);
 844         return(1);
 845       }
 846
 847     L__BIT_ARR_CLEAR(branch)
 848     L__BIT_ARR_CLEAR(rem)
 849
 850     for ( ; ; )
 851       {
 852         while (num_sub > 2)
 853           {
 854             /* Subtract one for root of subtree. */
 855             num_sub--;
 856             if (num_sub & 1)
 857               L__BIT_ARR_1(rem, depth)
 858             else
 859               L__BIT_ARR_0(rem, depth)
 860             L__BIT_ARR_0(branch, depth)
 861             depth++;
 862             num_sub >>= 1;
 863           }
 864
 865         if (num_sub == 2)
 866           {
 867             /* Build a subtree with two nodes, slanting to greater.
 868             ** I arbitrarily chose to always have the extra node in the
 869             ** greater subtree when there is an odd number of nodes to
 870             ** split between the two subtrees. */
 871
 872             h = AVL_BUILD_ITER_VAL(p);
 873             L__CHECK_READ_ERROR(0)
 874             AVL_BUILD_ITER_INCR(p)
 875             child = AVL_BUILD_ITER_VAL(p);
 876             L__CHECK_READ_ERROR(0)
 877             AVL_BUILD_ITER_INCR(p)
 878             AVL_SET_LESS(child, AVL_NULL)
 879             AVL_SET_GREATER(child, AVL_NULL)
 880             AVL_SET_BALANCE_FACTOR(child, 0)
 881             AVL_SET_GREATER(h, child)
 882             AVL_SET_LESS(h, AVL_NULL)
 883             AVL_SET_BALANCE_FACTOR(h, 1)
 884           }
 885         else  /* num_sub == 1 */
 886           {
 887             /* Build a subtree with one node. */
 888
 889             h = AVL_BUILD_ITER_VAL(p);
 890             L__CHECK_READ_ERROR(0)
 891             AVL_BUILD_ITER_INCR(p)
 892             AVL_SET_LESS(h, AVL_NULL)
 893             AVL_SET_GREATER(h, AVL_NULL)
 894             AVL_SET_BALANCE_FACTOR(h, 0)
 895           }
 896
 897         while (depth)
 898           {
 899             depth--;
 900             if (!L__BIT_ARR_VAL(branch, depth))
 901               /* We've completed a less subtree. */
 902               break;
 903
 904             /* We've completed a greater subtree, so attach it to
 905             ** its parent (that is less than it).  We pop the parent
 906             ** off the stack of less parents. */
 907             child = h;
 908             h = less_parent;
 909             less_parent = AVL_GET_GREATER(h, 1);
 910             L__CHECK_READ_ERROR(0)
 911             AVL_SET_GREATER(h, child)
 912             /* num_sub = 2 * (num_sub - rem[depth]) + rem[depth] + 1 */
 913             num_sub <<= 1;
 914             num_sub += L__BIT_ARR_VAL(rem, depth) ? 0 : 1;
 915             if (num_sub & (num_sub - 1))
 916               /* num_sub is not a power of 2. */
 917               AVL_SET_BALANCE_FACTOR(h, 0)
 918             else
 919               /* num_sub is a power of 2. */
 920               AVL_SET_BALANCE_FACTOR(h, 1)
 921           }
 922
 923         if (num_sub == num_nodes)
 924           /* We've completed the full tree. */
 925           break;
 926
 927         /* The subtree we've completed is the less subtree of the
 928         ** next node in the sequence. */
 929
 930         child = h;
 931         h = AVL_BUILD_ITER_VAL(p);
 932         L__CHECK_READ_ERROR(0)
 933         AVL_BUILD_ITER_INCR(p)
 934         AVL_SET_LESS(h, child)
 935
 936         /* Put h into stack of less parents. */
 937         AVL_SET_GREATER(h, less_parent)
 938         less_parent = h;
 939
 940         /* Proceed to creating greater than subtree of h. */
 941         L__BIT_ARR_1(branch, depth)
 942         num_sub += L__BIT_ARR_VAL(rem, depth) ? 1 : 0;
 943         depth++;
 944
 945       } /* end for ( ; ; ) */
 946
 947     AVL_SET_ROOT(L__tree, h);
 948
 949     return(1);
 950   }
 951
 952 #endif
 953
 954 #endif
 955
 956 #if (L__IMPL_MASK & AVL_IMPL_INIT_ITER)
 957
 958 /* Initialize depth to invalid value, to indicate iterator is
 959 ** invalid.   (Depth is zero-base.)  It's not necessary to initialize
 960 ** iterators prior to passing them to the "start" function.
 961 */
 962 L__SC void L__(init_iter)(L__(iter) *iter) { iter->depth = ~0; }
 963
 964 #endif
 965
 966 #ifdef AVL_READ_ERRORS_HAPPEN
 967
 968 #define L__CHECK_READ_ERROR_INV_DEPTH \
 969 { if (AVL_READ_ERROR) { iter->depth = ~0; return; } }
 970
 971 #else
 972
 973 #define L__CHECK_READ_ERROR_INV_DEPTH
 974
 975 #endif
 976
 977 #if (L__IMPL_MASK & AVL_IMPL_START_ITER)
 978
 979 L__SC void L__(start_iter)(
 980   L__(avl) *L__tree, L__(iter) *iter, AVL_KEY k, avl_search_type st)
 981   {
 982     AVL_HANDLE h = L__tree->root;
 983     unsigned d = 0;
 984     int cmp, target_cmp;
 985
 986     /* Save the tree that we're going to iterate through in a
 987     ** member variable. */
 988     iter->tree_ = L__tree;
 989
 990     iter->depth = ~0;
 991
 992     if (h == AVL_NULL)
 993       /* Tree is empty. */
 994       return;
 995
 996     if (st & AVL_LESS)
 997       /* Key can be greater than key of starting node. */
 998       target_cmp = 1;
 999     else if (st & AVL_GREATER)
1000       /* Key can be less than key of starting node. */
1001       target_cmp = -1;
1002     else
1003       /* Key must be same as key of starting node. */
1004       target_cmp = 0;
1005
1006     for ( ; ; )
1007       {
1008         cmp = AVL_COMPARE_KEY_NODE(k, h);
1009         if (cmp == 0)
1010           {
1011             if (st & AVL_EQUAL)
1012               {
1013                 /* Equal node was sought and found as starting node. */
1014                 iter->depth = d;
1015                 break;
1016               }
1017             cmp = -target_cmp;
1018           }
1019         else if (target_cmp != 0)
1020           if (!((cmp ^ target_cmp) & L__MASK_HIGH_BIT))
1021             /* cmp and target_cmp are both negative or both positive. */
1022             iter->depth = d;
1023         h = cmp < 0 ? AVL_GET_LESS(h, 1) : AVL_GET_GREATER(h, 1);
1024         L__CHECK_READ_ERROR_INV_DEPTH
1025         if (h == AVL_NULL)
1026           break;
1027         if (cmp > 0)
1028           L__BIT_ARR_1(iter->branch, d)
1029         else
1030           L__BIT_ARR_0(iter->branch, d)
1031         iter->path_h[d++] = h;
1032       }
1033   }
1034
1035 #endif
1036
1037 #if (L__IMPL_MASK & AVL_IMPL_START_ITER_LEAST)
1038
1039 L__SC void L__(start_iter_least)(L__(avl) *L__tree, L__(iter) *iter)
1040   {
1041     AVL_HANDLE h = L__tree->root;
1042
1043     iter->tree_ = L__tree;
1044
1045     iter->depth = ~0;
1046
1047     L__BIT_ARR_ALL(iter->branch, 0)
1048
1049     while (h != AVL_NULL)
1050       {
1051         if (iter->depth != ~0)
1052           iter->path_h[iter->depth] = h;
1053         iter->depth++;
1054         h = AVL_GET_LESS(h, 1);
1055         L__CHECK_READ_ERROR_INV_DEPTH
1056       }
1057   }
1058
1059 #endif
1060
1061 #if (L__IMPL_MASK & AVL_IMPL_START_ITER_GREATEST)
1062
1063 L__SC void L__(start_iter_greatest)(L__(avl) *L__tree, L__(iter) *iter)
1064   {
1065     AVL_HANDLE h = L__tree->root;
1066
1067     iter->tree_ = L__tree;
1068
1069     iter->depth = ~0;
1070
1071     L__BIT_ARR_ALL(iter->branch, 1)
1072
1073     while (h != AVL_NULL)
1074       {
1075         if (iter->depth != ~0)
1076           iter->path_h[iter->depth] = h;
1077         iter->depth++;
1078         h = AVL_GET_GREATER(h, 1);
1079         L__CHECK_READ_ERROR_INV_DEPTH
1080       }
1081   }
1082
1083 #endif
1084
1085 #if (L__IMPL_MASK & AVL_IMPL_GET_ITER)
1086
1087 L__SC AVL_HANDLE L__(get_iter)(L__(iter) *iter)
1088   {
1089     if (iter->depth == ~0)
1090       return(AVL_NULL);
1091
1092     return(iter->depth == 0 ?
1093              iter->tree_->root : iter->path_h[iter->depth - 1]);
1094   }
1095
1096 #endif
1097
1098 #if (L__IMPL_MASK & AVL_IMPL_INCR_ITER)
1099
1100 L__SC void L__(incr_iter)(L__(iter) *iter)
1101   {
1102     #define L__tree (iter->tree_)
1103
1104     if (iter->depth != ~0)
1105       {
1106         AVL_HANDLE h =
1107           AVL_GET_GREATER((iter->depth == 0 ?
1108             iter->tree_->root : iter->path_h[iter->depth - 1]), 1);
1109         L__CHECK_READ_ERROR_INV_DEPTH
1110
1111         if (h == AVL_NULL)
1112           do
1113             {
1114               if (iter->depth == 0)
1115                 {
1116                   iter->depth = ~0;
1117                   break;
1118                 }
1119               iter->depth--;
1120             }
1121           while (L__BIT_ARR_VAL(iter->branch, iter->depth));
1122         else
1123           {
1124             L__BIT_ARR_1(iter->branch, iter->depth)
1125             iter->path_h[iter->depth++] = h;
1126             for ( ; ; )
1127               {
1128                 h = AVL_GET_LESS(h, 1);
1129                 L__CHECK_READ_ERROR_INV_DEPTH
1130                 if (h == AVL_NULL)
1131                   break;
1132                 L__BIT_ARR_0(iter->branch, iter->depth)
1133                 iter->path_h[iter->depth++] = h;
1134               }
1135           }
1136       }
1137
1138     #undef L__tree
1139   }
1140
1141 #endif
1142
1143 #if (L__IMPL_MASK & AVL_IMPL_DECR_ITER)
1144
1145 L__SC void L__(decr_iter)(L__(iter) *iter)
1146   {
1147     #define L__tree (iter->tree_)
1148
1149     if (iter->depth != ~0)
1150       {
1151         AVL_HANDLE h =
1152           AVL_GET_LESS((iter->depth == 0 ?
1153             iter->tree_->root : iter->path_h[iter->depth - 1]), 1);
1154         L__CHECK_READ_ERROR_INV_DEPTH
1155
1156         if (h == AVL_NULL)
1157           do
1158             {
1159               if (iter->depth == 0)
1160                 {
1161                   iter->depth = ~0;
1162                   break;
1163                 }
1164               iter->depth--;
1165             }
1166           while (!L__BIT_ARR_VAL(iter->branch, iter->depth));
1167         else
1168           {
1169             L__BIT_ARR_0(iter->branch, iter->depth)
1170             iter->path_h[iter->depth++] = h;
1171             for ( ; ; )
1172               {
1173                 h = AVL_GET_GREATER(h, 1);
1174                 L__CHECK_READ_ERROR_INV_DEPTH
1175                 if (h == AVL_NULL)
1176                   break;
1177                 L__BIT_ARR_1(iter->branch, iter->depth)
1178                 iter->path_h[iter->depth++] = h;
1179               }
1180           }
1181       }
1182
1183     #undef L__tree
1184   }
1185
1186 #endif
1187
1188 /* Tidy up the preprocessor symbol name space. */
1189 #undef L__
1190 #undef L__EST_LONG_BIT
1191 #undef L__SIZE
1192 #undef L__MASK_HIGH_BIT
1193 #undef L__LONG_BIT
1194 #undef L__BIT_ARR_DEFN
1195 #undef L__BIT_ARR_CLEAR
1196 #undef L__BIT_ARR_VAL
1197 #undef L__BIT_ARR_0
1198 #undef L__BIT_ARR_1
1199 #undef L__BIT_ARR_ALL
1200 #undef L__CHECK_READ_ERROR
1201 #undef L__CHECK_READ_ERROR_INV_DEPTH
1202 #undef L__BIT_ARR_LONGS
1203 #undef L__IMPL_MASK
1204 #undef L__CHECK_READ_ERROR
1205 #undef L__CHECK_READ_ERROR_INV_DEPTH
1206 #undef L__SC
1207 #undef L__BALANCE_PARAM_CALL_PREFIX
1208 #undef L__BALANCE_PARAM_DECL_PREFIX