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