rom/exec/avl.c

   1 /* indent -blC -bli0 -npcs -ncs -i4 -bad -bap avl.c */
   2 /*
   3     Copyright (c) 2008, The AROS Development Team. All rights reserved.
   4
   5 #Description: @AROS.Exec.AVL@
   6
   7 <chapter title="Exec AVL Trees">
   8
   9 <p>FIXME explain it</p>
  10
  11 </chapter>
  12
  13 */
  14
  15 #include <proto/exec.h>
  16 #include <exec/avl.h>
  17
  18 /* don't think this works inside exec.library */
  19 #define D(x)
  20
  21 #define LEFT (0)
  22 #define RIGHT (1)
  23
  24 /* internal functions */
  25 /* Re-Links the parent of subroot, properly handling the root-node.
  26    The old parent is supplied in parent */
  27 static inline int
  28 link_parent(struct AVLNode **root, const struct AVLNode *scan,
  29             struct AVLNode *subroot, struct AVLNode *parent)
  30 {
  31     int dir;
  32
  33     if (parent == NULL)
  34     {
  35         *root = subroot;
  36         subroot->avl_parent = NULL;
  37         dir = -1;
  38     }
  39     else
  40     {
  41         dir = parent->avl_link[1] == scan;
  42         parent->avl_link[dir] = subroot;
  43         subroot->avl_parent = parent;
  44     }
  45
  46     return dir;
  47 }
  48
  49 /* Perform a single rotation about next in the given direction.
  50    Note that this will be inlined with hard-coded dirs */
  51 static inline struct AVLNode *
  52 rotate_single(struct AVLNode *scan, struct AVLNode *next, const int dir)
  53 {
  54     struct AVLNode *subroot = next;
  55     const int other = dir == 0;
  56
  57     D(printf("single %s about %p\n", dir == 0 ? "left" : "right", subroot));
  58
  59     scan->avl_link[other] = next->avl_link[dir];
  60     if (next->avl_link[dir] != NULL)
  61         next->avl_link[dir]->avl_parent = scan;
  62     next->avl_link[dir] = scan;
  63     scan->avl_parent = next;
  64
  65     return subroot;
  66 }
  67
  68 /* Peform a double rotation about scan and then next in a given direction
  69    Note that this will be in-lined with hard-coded dirs */
  70 static inline struct AVLNode *
  71 rotate_double(struct AVLNode *scan, struct AVLNode *next, const int dir)
  72 {
  73     struct AVLNode *subroot = next->avl_link[dir];
  74     const int other = dir == 0;
  75
  76     D(printf("double %s about %p\n", dir == 0 ? "left" : "right", subroot));
  77
  78     next->avl_link[dir] = subroot->avl_link[other];
  79     if (subroot->avl_link[other] != NULL)
  80         subroot->avl_link[other]->avl_parent = next;
  81     subroot->avl_link[other] = next;
  82     scan->avl_link[other] = subroot->avl_link[dir];
  83     if (subroot->avl_link[dir] != NULL)
  84         subroot->avl_link[dir]->avl_parent = scan;
  85     subroot->avl_link[dir] = scan;
  86
  87     next->avl_parent = subroot;
  88     scan->avl_parent = subroot;
  89
  90     return subroot;
  91 }
  92
  93 /*****************************************************************************
  94
  95     NAME */
  96
  97     AROS_LH3I(struct AVLNode *, AVL_AddNode,
  98
  99 /*  SYNOPSIS */
 100           AROS_LHA(struct AVLNode **, root, A0),
 101           AROS_LHA(struct AVLNode *, node, A1),
 102           AROS_LHA(AVLNODECOMP, func, A2),
 103 /*  LOCATION */
 104           struct ExecBase *, SysBase, 142, Exec)
 105 /*  FUNCTION
 106         Add a new node to an AVL tree.
 107
 108     INPUTS
 109         Root  - The root node of the tree to which the new node will be added.
 110                 Initially and if the tree is empty, this will be NULL.
 111
 112         Node  - The new node to add.  Any key information must alread be
 113                 initialised.
 114
 115         Func  - A key comparison function.  It will be passed 2 nodes,
 116                 node1 and node2 to compare and must return <0, 0 or >0 to
 117                 reflect node1 < node2, node1 == node, or node1 > node2
 118                 respectively.
 119
 120     RESULT
 121         NULL if the node was added to the tree, or a pointer to a node with the
 122         same key which already exists in the tree.
 123
 124     NOTES
 125         AVL trees are balanced binary search trees.  This implementation is
 126         based on embedding the struct AVLNode within your own data object
 127         and providing custom comparison functions wherever they are needed.
 128
 129         Two comparison functions are needed for different cases.  It is entirely
 130         up to the application as to how it interprets the nodes and compares
 131         the keys.
 132
 133         AVLNODECOMP is used to compare the keys of two nodes.
 134
 135         typedef LONG *AVLNODECOMP(const struct AVLNode *avlnode1,
 136                                   const struct AVLNode *avlnode2);
 137                 D0                A0, A1
 138
 139         AVLKEYCOMP is used to compare a key to a node.
 140
 141         typedef LONG *AVLKEYCOMP(const struct AVLNode *avlnode,
 142                                  AVLKey key);
 143                 D0               A0, A1
 144
 145         These functions must return the same sense for the same key values.
 146         That is,
 147             <0  if key of avlnode1 <  key of avlnode2
 148                 if key of avlnode  <  key
 149              0  if key of avlnode1 == key of avlnode2
 150                 if key of avlnode  == key
 151             >0  if key of avlnode1 >  key of avlnode2
 152                 if key of avlnode  <  key
 153
 154         Since this function returns the existing node if the keys match,
 155         this function can be used to efficiently add items to the tree or
 156         update existing items without requiring additional lookups.
 157
 158     EXAMPLE
 159         This is a fragment which counts the occurances of every word in a file.
 160         Also note that this example embeds the struct AVLNode data at
 161         the start of the structure, so simple casts suffice for translating
 162         AVLNode to ExampleNode addresses.
 163
 164         struct ExampleNode {
 165             struct AVLNode avl;
 166             STRPTR key;
 167             ULONG count;
 168         };
 169
 170         static LONG ExampleNodeComp(const struct AVLNode *a1, const struct AVLNode *a2)
 171         {
 172             const struct ExampleNode *e1 = (const struct ExampleNode *)a1;
 173             const struct ExampleNode *e2 = (const struct ExampleNode *)e2;
 174
 175             return strcmp(a1->key, a2->key);
 176         }
 177
 178         static LONG ExampleKeyComp(const struct AVLNode *a1, AVLKey key)
 179         {
 180             const struct ExampleNode *e1 = (const struct ExampleNode *)a1;
 181             char *skey = key;
 182
 183             return strcmp(a1->key, skey);
 184         }
 185
 186         void CountWords(wordfile)
 187         {
 188             struct ExampleNode *node;
 189             struct AVLNode *root = NULL, *check;
 190
 191             node = AllocMem(sizeof(struct ExampleNode), 0);
 192             node->count = 1;
 193
 194             while (node->key = read_word(wordfile)) {
 195                 check = AVL_AddNode(&root, &node->avl, ExampleNodecomp);
 196
 197                 if (check != NULL) {
 198                     struct ExampleNode *work = (struct ExampleNode *)check;
 199
 200                     check->count += 1;
 201                 } else {
 202                     free(node->key);
 203                     node = AllocMem(sizeof(struct ExampleNode), 0);
 204                     node->count = 1;
 205                 }
 206             }
 207             FreeMem(node, sizeof(struct ExampleNode));
 208         }
 209
 210     BUGS
 211
 212     SEE ALSO
 213         AVL_FindNode(), AVL_FindNextNodeByKey(), AVL_FindPrevNodeByKey(),
 214         AVL_RemNodeByAddress(), AVL_RemNodeByKey()
 215
 216     INTERNALS
 217 ******************************************************************************/
 218 {
 219     AROS_LIBFUNC_INIT;
 220
 221     int dir;
 222     struct AVLNode *next = *root;
 223     struct AVLNode *scan;
 224     struct AVLNode *child;
 225
 226     /* Simple case - empty tree */
 227     if (next == NULL)
 228     {
 229         *root = node;
 230         node->avl_link[0] = node->avl_link[1] = node->avl_parent = NULL;
 231         node->avl_balance = 0;
 232         return NULL;
 233     }
 234
 235     /* find insertion point */
 236     do
 237     {
 238         LONG cmp;
 239
 240         scan = next;
 241         cmp = AROS_UFC2(LONG, func,
 242                         AROS_UFCA(const struct AVLNode *, scan, A0),
 243                         AROS_UFCA(const struct AVLNode *, node, A1));
 244         if (cmp == 0)
 245             return (struct AVLNode *)scan;
 246
 247         dir = cmp < 0;
 248         next = scan->avl_link[dir];
 249     }
 250     while (next != NULL);
 251
 252     /* insert */
 253     node->avl_parent = scan;
 254     scan->avl_link[dir] = node;
 255     node->avl_link[0] = node->avl_link[1] = NULL;
 256     node->avl_balance = 0;
 257
 258     /* update balance factors */
 259     while (1)
 260     {
 261         LONG bal = (dir * 2 - 1) + scan->avl_balance;
 262         struct AVLNode *parent;
 263         struct AVLNode *subroot;
 264
 265         switch (bal)
 266         {
 267         case 0:
 268             scan->avl_balance = bal;
 269             return NULL;
 270
 271         case 2:
 272             parent = scan->avl_parent;
 273             next = scan->avl_link[1];
 274
 275             switch (next->avl_balance)
 276             {
 277             case -1:
 278                 subroot = rotate_double(scan, next, LEFT);
 279
 280                 if (subroot->avl_balance == 1)
 281                 {
 282                     scan->avl_balance = -1;
 283                     next->avl_balance = 0;
 284                 }
 285                 else if (subroot->avl_balance == -1)
 286                 {
 287                     scan->avl_balance = 0;
 288                     next->avl_balance = 1;
 289                 }
 290                 else
 291                 {
 292                     scan->avl_balance = next->avl_balance = 0;
 293                 }
 294
 295                 subroot->avl_balance = 0;
 296                 break;
 297             default:
 298                 subroot = rotate_single(scan, next, LEFT);
 299
 300                 scan->avl_balance = next->avl_balance = 0;
 301                 break;
 302             }
 303
 304             link_parent(root, scan, subroot, parent);
 305             return NULL;
 306
 307         case -2:
 308             parent = scan->avl_parent;
 309             next = scan->avl_link[0];
 310
 311             switch (next->avl_balance)
 312             {
 313             case 1:
 314                 subroot = rotate_double(scan, next, RIGHT);
 315
 316                 if (subroot->avl_balance == -1)
 317                 {
 318                     scan->avl_balance = 1;
 319                     next->avl_balance = 0;
 320                 }
 321                 else if (subroot->avl_balance == 1)
 322                 {
 323                     scan->avl_balance = 0;
 324                     next->avl_balance = -1;
 325                 }
 326                 else
 327                 {
 328                     scan->avl_balance = next->avl_balance = 0;
 329                 }
 330
 331                 subroot->avl_balance = 0;
 332                 break;
 333             default:
 334                 subroot = rotate_single(scan, next, RIGHT);
 335
 336                 scan->avl_balance = next->avl_balance = 0;
 337                 break;
 338             }
 339
 340             link_parent(root, scan, subroot, parent);
 341             return NULL;
 342
 343         default:
 344             scan->avl_balance = bal;
 345
 346             child = scan;
 347             scan = scan->avl_parent;
 348             if (scan == NULL)
 349                 return NULL;
 350
 351             dir = scan->avl_link[1] == child;
 352             break;
 353         }
 354     }
 355
 356     return NULL;
 357
 358     AROS_LIBFUNC_EXIT;
 359 }                               /* AVL_AddNode */
 360
 361 /*****************************************************************************
 362
 363     NAME */
 364
 365     AROS_LH2I(struct AVLNode *, AVL_RemNodeByAddress,
 366
 367 /*  SYNOPSIS */
 368           AROS_LHA(struct AVLNode **, Root, A0),
 369           AROS_LHA(struct AVLNode *, Node, A1),
 370 /*  LOCATION */
 371           struct ExecBase *, SysBase, 143, Exec)
 372 /*  FUNCTION
 373         Remove a given node from the tree.
 374
 375     INPUTS
 376         Root - A pointer to a pointer to the root node of the tree.
 377
 378         Node - A struct AVLNode to remove.  The node must be present
 379                in the tree.
 380
 381     RESULT
 382         Node is returned.
 383
 384     NOTES
 385         Removing a node may require multiple rebalancing steps
 386         in the tree.  Each step however runs in constant time
 387         and no more than 1.44log(n) steps will be required.
 388
 389     EXAMPLE
 390         See AVL_FindNextNodeByAddress(), AVL_FindPrevNodeByAddress()
 391
 392     BUGS
 393
 394     SEE ALSO
 395         AVL_AddNode(), AVL_FindNode(), AVL_FindNextNodeByAddress(),
 396         AVL_FindPrevNodeByAddress()
 397
 398     INTERNALS
 399 ******************************************************************************/
 400 {
 401     AROS_LIBFUNC_INIT;
 402
 403     struct AVLNode *scan;
 404     struct AVLNode *node = (struct AVLNode *)Node;
 405     struct AVLNode **root = (struct AVLNode **)Root;
 406     int dir;
 407
 408     if (node->avl_link[0] == NULL)
 409     {
 410         if (node->avl_link[1] == NULL)
 411         {
 412             if (node->avl_parent == NULL)
 413             {
 414                 /* removed last node */
 415                 *root = NULL;
 416                 return Node;
 417             }
 418             else
 419             {
 420                 /* removed a leaf */
 421                 scan = node->avl_parent;
 422                 dir = scan->avl_link[1] == node;
 423                 scan->avl_link[dir] = NULL;
 424                 D(printf("removed leaf dir = %d\n", dir));
 425             }
 426         }
 427         else
 428         {
 429             if (node->avl_parent == NULL)
 430             {
 431                 /* removed root left-leaf node */
 432                 *root = node->avl_link[1];
 433                 node->avl_link[1]->avl_parent = NULL;
 434                 return Node;
 435             }
 436             else
 437             {
 438                 /* removed a left-leaf */
 439                 scan = node->avl_parent;
 440                 dir = scan->avl_link[1] == node;
 441                 scan->avl_link[dir] = node->avl_link[1];
 442                 node->avl_link[1]->avl_parent = scan;
 443                 D(printf("removed left leaf dir =%d\n", dir));
 444             }
 445         }
 446     }
 447     else
 448     {
 449         if (node->avl_link[1] == NULL)
 450         {
 451             if (node->avl_parent == NULL)
 452             {
 453                 /* removed root right-leaf node */
 454                 *root = node->avl_link[0];
 455                 node->avl_link[0]->avl_parent = NULL;
 456                 return Node;
 457             }
 458             else
 459             {
 460                 /* removed a right-leaf */
 461                 scan = node->avl_parent;
 462                 dir = scan->avl_link[1] == node;
 463                 scan->avl_link[dir] = node->avl_link[0];
 464                 node->avl_link[0]->avl_parent = scan;
 465                 D(printf("removed right leaf dir=%d\n", dir));
 466             }
 467         }
 468         else
 469         {
 470             /* removing a non-leaf node - swap it with a leaf node and 'remove' that instead */
 471             struct AVLNode *toremove = (struct AVLNode *)AVL_FindPrevNodeByAddress(Node);       // do we do prev/next based on balance factor? */
 472
 473             D(printf("removing non-leaf key ... %p\n", toremove));
 474
 475             /* remove the leaf node */
 476             scan = toremove->avl_parent;
 477
 478             if (scan == node)
 479             {
 480                 /* special case - immediate child of what we're removing */
 481                 toremove->avl_link[1] = node->avl_link[1];
 482                 if (node->avl_link[1] != NULL)
 483                     node->avl_link[1]->avl_parent = toremove;
 484                 dir = 0;
 485                 scan = toremove;
 486                 D(printf("  removed immediate child\n"));
 487             }
 488             else
 489             {
 490                 dir = toremove->avl_parent->avl_link[1] == toremove;
 491                 toremove->avl_parent->avl_link[dir] = toremove->avl_link[0];
 492                 if (toremove->avl_link[0] != NULL)
 493                     toremove->avl_link[0]->avl_parent = toremove->avl_parent;
 494
 495                 /* swap it with the removed node */
 496                 toremove->avl_link[0] = node->avl_link[0];
 497                 if (node->avl_link[0] != NULL)
 498                     node->avl_link[0]->avl_parent = toremove;
 499                 toremove->avl_link[1] = node->avl_link[1];
 500                 if (node->avl_link[1] != NULL)
 501                     node->avl_link[1]->avl_parent = toremove;
 502                 D(printf("  removed distant child\n"));
 503             }
 504             toremove->avl_balance = node->avl_balance;
 505             toremove->avl_parent = node->avl_parent;
 506             if (node->avl_parent == NULL)
 507                 *root = toremove;
 508             else
 509                 node->avl_parent->avl_link[node->avl_parent->avl_link[1] ==
 510                                            node] = toremove;
 511
 512             D(printf("removed key, tree is now:\n"));
 513             D(dumptree(*root, 0));
 514         }
 515     }
 516
 517     /* rebalance from 'scan' up */
 518     while (1)
 519     {
 520         int bal = scan->avl_balance - (dir * 2 - 1);
 521         struct AVLNode *next;
 522         struct AVLNode *parent;
 523         struct AVLNode *subroot = NULL;
 524
 525         switch (bal)
 526         {
 527         case 0:
 528             scan->avl_balance = bal;
 529
 530             parent = scan->avl_parent;
 531             if (parent == NULL)
 532                 return Node;
 533
 534             dir = parent->avl_link[1] == scan;
 535             scan = parent;
 536             break;
 537
 538         case -1:
 539         case 1:
 540             scan->avl_balance = bal;
 541             return Node;
 542
 543         case 2:
 544             parent = scan->avl_parent;
 545             next = scan->avl_link[1];
 546
 547             switch (next->avl_balance)
 548             {
 549             case 0:
 550                 subroot = rotate_single(scan, next, LEFT);
 551                 scan->avl_balance = 1;
 552                 next->avl_balance = -1;
 553                 // stop
 554                 link_parent(root, scan, subroot, parent);
 555                 return Node;
 556             case 1:
 557                 subroot = rotate_single(scan, next, LEFT);
 558                 scan->avl_balance = 0;
 559                 next->avl_balance = 0;
 560                 // keep going
 561                 break;
 562             case -1:
 563                 subroot = rotate_double(scan, next, LEFT);
 564
 565                 if (subroot->avl_balance == 1)
 566                 {
 567                     scan->avl_balance = -1;
 568                     next->avl_balance = 0;
 569                 }
 570                 else if (subroot->avl_balance == -1)
 571                 {
 572                     scan->avl_balance = 0;
 573                     next->avl_balance = 1;
 574                 }
 575                 else
 576                 {
 577                     scan->avl_balance = 0;
 578                     next->avl_balance = 0;
 579                 }
 580
 581                 subroot->avl_balance = 0;
 582                 // keep going
 583                 break;
 584             }
 585
 586             dir = link_parent(root, scan, subroot, parent);
 587             if (dir == -1)
 588                 return Node;
 589
 590             scan = parent;
 591             break;
 592
 593         case -2:
 594             parent = scan->avl_parent;
 595             next = scan->avl_link[0];
 596
 597             switch (next->avl_balance)
 598             {
 599             case 0:
 600                 subroot = rotate_single(scan, next, RIGHT);
 601                 scan->avl_balance = -1;
 602                 next->avl_balance = 1;
 603                 // stop
 604                 link_parent(root, scan, subroot, parent);
 605                 return Node;
 606             case -1:
 607                 subroot = rotate_single(scan, next, RIGHT);
 608                 scan->avl_balance = next->avl_balance = 0;
 609                 // keep going
 610                 break;
 611             case +1:
 612                 subroot = rotate_double(scan, next, RIGHT);
 613
 614                 if (subroot->avl_balance == -1)
 615                 {
 616                     scan->avl_balance = 1;
 617                     next->avl_balance = 0;
 618                 }
 619                 else if (subroot->avl_balance == 1)
 620                 {
 621                     scan->avl_balance = 0;
 622                     next->avl_balance = -1;
 623                 }
 624                 else
 625                 {
 626                     scan->avl_balance = 0;
 627                     next->avl_balance = 0;
 628                 }
 629
 630                 subroot->avl_balance = 0;
 631                 // keep going
 632                 break;
 633             }
 634
 635             dir = link_parent(root, scan, subroot, parent);
 636             if (dir == -1)
 637                 return Node;
 638
 639             scan = parent;
 640             break;
 641         }
 642     }
 643
 644     AROS_LIBFUNC_EXIT;
 645 }                               /* AVL_RemNodeByAddress */
 646
 647 /*****************************************************************************
 648
 649     NAME */
 650
 651     AROS_LH3I(struct AVLNode *, AVL_RemNodeByKey,
 652
 653 /*  SYNOPSIS */
 654           AROS_LHA(struct AVLNode **, root, A0),
 655           AROS_LHA(AVLKey, key, A1), AROS_LHA(AVLKEYCOMP, func, A2),
 656 /*  LOCATION */
 657           struct ExecBase *, SysBase, 144, Exec)
 658 /*  FUNCTION
 659         Looks up a node in the tree by key, and removes it if it
 660         is found.
 661
 662     INPUTS
 663         Root - A pointer to a pointer to the root node of the AVL tree.
 664
 665         key  - The key to search for.
 666
 667         func - An AVLKEYCOMP function used to compare the key and nodes
 668                in the tree.
 669
 670     RESULT
 671         If the key was present in the tree, then a pointer to the node
 672         for that key.  Otherwise NULL if no such key existed in the
 673         tree.
 674
 675     NOTES
 676         See AVL_RemNodeByAddress().
 677
 678     EXAMPLE
 679
 680     BUGS
 681
 682     SEE ALSO
 683         AVL_AddNode(), AVL_RemNodeByAddress()
 684
 685     INTERNALS
 686 ******************************************************************************/
 687 {
 688     AROS_LIBFUNC_INIT;
 689
 690     struct AVLNode *node;
 691
 692     node = AVL_FindNode(*root, key, func);
 693
 694     if (node != NULL)
 695         node = AVL_RemNodeByAddress(root, node);
 696
 697     return node;
 698
 699     AROS_LIBFUNC_EXIT;
 700 }                               /* AVL_RemNodeByKey */
 701
 702 /*****************************************************************************
 703
 704     NAME */
 705
 706     AROS_LH3I(struct AVLNode *, AVL_FindNode,
 707
 708 /*  SYNOPSIS */
 709           AROS_LHA(const struct AVLNode *, Root, A0),
 710           AROS_LHA(AVLKey, key, A1), AROS_LHA(AVLKEYCOMP, func, A2),
 711 /*  LOCATION */
 712           struct ExecBase *, SysBase, 145, Exec)
 713 /*  FUNCTION
 714         Find an entry in the AVL tree by key.
 715
 716     INPUTS
 717         Root - The root of the AVL tree.
 718
 719         key  - The key to search.
 720
 721         func - The AVLKEYCOMP key comparision function for this tree.
 722
 723     RESULT
 724         A pointer to the node matching key if it exists in the
 725         tree, or NULL if no such node exists.
 726
 727     NOTES
 728
 729     EXAMPLE
 730         node = (struct ExampleNode *)AVL_FindNode(root, "aros", ExampleKeyComp);
 731         if (node)
 732             printf(" `%s' occurs %d times\n", node->key, node->count);
 733
 734     BUGS
 735
 736     SEE ALSO
 737         AVL_AddNode(), AVL_RemNodeByAddress(), AVL_FindNextNodeByAddress(),
 738         AVL_FindPrevNodeByAddress()
 739
 740     INTERNALS
 741 ******************************************************************************/
 742 {
 743     AROS_LIBFUNC_INIT;
 744
 745     struct AVLNode *node = (struct AVLNode *)Root;
 746     LONG cmp;
 747
 748     while (node != NULL &&
 749            (cmp = AROS_UFC2(LONG, func,
 750                         AROS_UFCA(const struct AVLNode *, node, A0),
 751                         AROS_UFCA(AVLKey,                 key,  A1))) != 0)
 752     {
 753         node = node->avl_link[cmp < 0];
 754     }
 755
 756     return (struct AVLNode *)node;
 757
 758     AROS_LIBFUNC_EXIT;
 759 }                               /* AVL_FindNode */
 760
 761 /*****************************************************************************
 762
 763     NAME */
 764
 765     AROS_LH1I(struct AVLNode *, AVL_FindPrevNodeByAddress,
 766
 767 /*  SYNOPSIS */
 768           AROS_LHA(const struct AVLNode *, Node, A0),
 769 /*  LOCATION */
 770           struct ExecBase *, SysBase, 146, Exec)
 771 /*  FUNCTION
 772         Perform an inverse-order traversal to the previous node in the tree.
 773
 774     INPUTS
 775         Node - The current node.  The node must be present in the tree.
 776
 777     RESULT
 778         The next-least node in the tree, or NULL if Node was already
 779         the lowest valued node in the tree.
 780
 781     NOTES
 782         This implementation uses a parent pointer to avoid needing
 783         a stack or state to track it's current position in the tree.
 784
 785         Although this operation is typically O(1), in the worst case it
 786         iterate the full depth of the tree - approximately 1.44Log(N).
 787
 788     EXAMPLE
 789         ... inverse-order traversal of all nodes
 790         node = (struct ExampleNode *)AVL_FindLastNode(root);
 791         while (node) {
 792             printf(" %s\n", node->key);
 793             node = (struct ExampleNode *)AVL_FindPrevNodeByAddress(node);
 794         }
 795
 796         ... inverse-order traversal of all nodes - with safe deletion
 797         node = (struct ExampleNode *)AVL_FindLastNode(root);
 798         prev = (struct ExampleNode *)AVL_FindPrevNodeByAddress(node);
 799         while (node) {
 800             printf(" %s\n", node->key);
 801
 802             if (DELETE_NODE(node))
 803                 AVL_RemNodeByAddress(&root, node);
 804
 805             node = prev;
 806             prev = (struct ExampleNode *)AVL_FindPrevNodeByAddress(node);
 807         }
 808
 809     BUGS
 810
 811     SEE ALSO
 812         AVL_AddNode(), AVL_RemNodeByAddress(), AVL_FindLastNode()
 813
 814     INTERNALS
 815 ******************************************************************************/
 816 {
 817     AROS_LIBFUNC_INIT;
 818
 819     const struct AVLNode *node = (const struct AVLNode *)Node;
 820     const struct AVLNode *prev;
 821
 822     prev = node->avl_link[0];
 823     if (prev != NULL)
 824     {
 825         do
 826         {
 827             node = prev;
 828             prev = prev->avl_link[1];
 829         }
 830         while (prev);
 831     }
 832     else
 833     {
 834         do
 835         {
 836             prev = node;
 837             node = node->avl_parent;
 838         }
 839         while (node != NULL && node->avl_link[1] != prev);
 840     }
 841
 842     return (struct AVLNode *)node;
 843
 844     AROS_LIBFUNC_EXIT;
 845 }                               /* AVL_FindPrevNodeByAddress */
 846
 847 /*****************************************************************************
 848
 849     NAME */
 850
 851     AROS_LH3I(struct AVLNode *, AVL_FindPrevNodeByKey,
 852
 853 /*  SYNOPSIS */
 854           AROS_LHA(const struct AVLNode *, root, A0),
 855           AROS_LHA(AVLKey, key, A1), AROS_LHA(AVLKEYCOMP, func, A2),
 856 /*  LOCATION */
 857           struct ExecBase *, SysBase, 147, Exec)
 858 /*  FUNCTION
 859         Find the node matching the key, or if such a node does not exist,
 860         then the node with the next-lowest value.
 861
 862     INPUTS
 863         Root - The root of the AVL tree.
 864
 865         key  - The key to search.
 866
 867         func - The AVLKEYCOMP key comparision function for this tree.
 868
 869     RESULT
 870         A pointer to the struct AVLNode which matches this key, or
 871         if that key is not present in the tree, the next lowest node.
 872         Or NULL if key is lower than the key of any node in the tree.
 873
 874     NOTES
 875         This is only O(1.44log(n)) in the worst case.
 876
 877     EXAMPLE
 878
 879     BUGS
 880
 881     SEE ALSO
 882         AVL_AddNode(), AVL_FindNextNodeByAddress(), AVL_FindLastNode()
 883
 884     INTERNALS
 885 ******************************************************************************/
 886 {
 887     AROS_LIBFUNC_INIT;
 888
 889     struct AVLNode *node = (struct AVLNode *)root;
 890     struct AVLNode *lesser = NULL;
 891     LONG cmp;
 892
 893     while (node != NULL &&
 894            (cmp = AROS_UFC2(LONG, func,
 895                         AROS_UFCA(const struct AVLNode *, node, A0),
 896                         AROS_UFCA(AVLKey,                 key,  A1))) != 0)
 897     {
 898         if (cmp < 0)
 899             lesser = node;
 900         node = node->avl_link[cmp < 0];
 901     }
 902
 903     return (struct AVLNode *)(node != NULL ? node : lesser);
 904
 905     AROS_LIBFUNC_EXIT;
 906 }                               /* AVL_FindPrevNodeByKey */
 907
 908 /*****************************************************************************
 909
 910     NAME */
 911
 912     AROS_LH1I(struct AVLNode *, AVL_FindNextNodeByAddress,
 913
 914 /*  SYNOPSIS */
 915           AROS_LHA(const struct AVLNode *, Node, A0),
 916 /*  LOCATION */
 917           struct ExecBase *, SysBase, 148, Exec)
 918 /*  FUNCTION
 919         Perform an in-order traversal to the next node in the tree.
 920
 921     INPUTS
 922         Node - The current node.  The node must be present in the tree.
 923
 924     RESULT
 925         The next-greatest node in the tree, or NULL if Node was already
 926         the highest valued node in the tree.
 927
 928     NOTES
 929         This implementation uses a parent pointer to avoid needing
 930         a stack or state to track it's current position in the tree.
 931
 932         Although this operation is typically O(1), in the worst case it
 933         iterate the full depth of the tree - approximately 1.44Log(N).
 934
 935     EXAMPLE
 936         ... in-order traversal of all nodes
 937         node = (struct ExampleNode *)AVL_FindFirstNode(root);
 938         while (node) {
 939             printf(" %s\n", node->key);
 940             node = (struct ExampleNode *)AVL_FindNextNodeByAddress(node);
 941         }
 942
 943         ... in-order traversal of all nodes - with safe deletion
 944         node = (struct ExampleNode *)AVL_FindFirstNode(root);
 945         next = (struct ExampleNode *)AVL_FindNextNodeByAddress(node);
 946         while (node) {
 947             printf(" %s\n", node->key);
 948
 949             if (DELETE_NODE(node))
 950                 AVL_RemNodeByAddress(&root, node);
 951
 952             node = next;
 953             next = (struct ExampleNode *)AVL_FindNextNodeByAddress(node);
 954         }
 955
 956     BUGS
 957
 958     SEE ALSO
 959         AVL_AddNode(), AVL_RemNodeByAddress(), AVL_FindFirstNode()
 960
 961     INTERNALS
 962 ******************************************************************************/
 963 {
 964     AROS_LIBFUNC_INIT;
 965
 966     const struct AVLNode *node = (const struct AVLNode *)Node;
 967     const struct AVLNode *next;
 968
 969     next = node->avl_link[1];
 970     if (next != NULL)
 971     {
 972         do
 973         {
 974             node = next;
 975             next = node->avl_link[0];
 976         }
 977         while (next != NULL);
 978     }
 979     else
 980     {
 981         do
 982         {
 983             next = node;
 984             node = node->avl_parent;
 985         }
 986         while (node != NULL && node->avl_link[1] == next);
 987     }
 988
 989     return (struct AVLNode *)node;
 990
 991     AROS_LIBFUNC_EXIT;
 992 }                               /* AVL_FindNextNodeByAddress */
 993
 994 /*****************************************************************************
 995
 996     NAME */
 997
 998     AROS_LH3I(struct AVLNode *, AVL_FindNextNodeByKey,
 999
1000 /*  SYNOPSIS */
1001           AROS_LHA(const struct AVLNode *, Root, A0),
1002           AROS_LHA(AVLKey, key, A1), AROS_LHA(AVLKEYCOMP, func, A2),
1003 /*  LOCATION */
1004           struct ExecBase *, SysBase, 149, Exec)
1005 /*  FUNCTION
1006         Find the node matching the key, or if such a node does not exist,
1007         then the node with the next-highest value.
1008
1009     INPUTS
1010         Root - The root of the AVL tree.
1011
1012         key  - The key to search.
1013
1014         func - The AVLKEYCOMP key comparision function for this tree.
1015
1016     RESULT
1017         A pointer to the struct AVLNode which matches this key, or
1018         if that key is not present in the tree, the next highest node.
1019         Or NULL if key is higher than the key of any node in the tree.
1020
1021     NOTES
1022         This is only O(1.44log(n)) in the worst case.
1023
1024     EXAMPLE
1025
1026     BUGS
1027
1028     SEE ALSO
1029         AVL_AddNode(), AVL_FindNextNodeByAddress(), AVL_FindLastNode()
1030
1031     INTERNALS
1032 ******************************************************************************/
1033 {
1034     AROS_LIBFUNC_INIT;
1035
1036     struct AVLNode *node = (struct AVLNode *)Root;
1037     struct AVLNode *greater = NULL;
1038     LONG cmp;
1039
1040     while (node != NULL &&
1041            (cmp = AROS_UFC2(LONG, func,
1042                         AROS_UFCA(const struct AVLNode *, node, A0),
1043                         AROS_UFCA(AVLKey,                 key,  A1))) != 0)
1044     {
1045         if (cmp > 0)
1046             greater = node;
1047         node = node->avl_link[cmp < 0];
1048     }
1049
1050     return (struct AVLNode *)(node != NULL ? node : greater);
1051
1052     AROS_LIBFUNC_EXIT;
1053 }                               /* AVL_FindNextNodeByKey */
1054
1055 /*****************************************************************************
1056
1057     NAME */
1058
1059     AROS_LH1I(struct AVLNode *, AVL_FindFirstNode,
1060
1061 /*  SYNOPSIS */
1062           AROS_LHA(const struct AVLNode *, Root, A0),
1063 /*  LOCATION */
1064           struct ExecBase *, SysBase, 150, Exec)
1065 /*  FUNCTION
1066         Find the smallest node in an AVL tree.
1067
1068     INPUTS
1069         Root - The root node of the AVL tree.
1070
1071     RESULT
1072         NULL if the tree is empty (i.e. Root is NULL), or the node
1073         which contains the least value in the tree as determined by
1074         the comparision function used to add the node.
1075
1076     NOTES
1077         AVL trees are balanced but not minimal.  This operation
1078         must iterate the full depth of the tree on one side -
1079         approximately 1.44Log(N).
1080
1081     EXAMPLE
1082         See AVL_FindNextNodeByAddress()
1083
1084     BUGS
1085
1086     SEE ALSO
1087         AVL_AddNode(), AVL_FindNextNodeByAddress()
1088
1089     INTERNALS
1090 ******************************************************************************/
1091 {
1092     AROS_LIBFUNC_INIT;
1093
1094     struct AVLNode *node = (struct AVLNode *)Root;
1095
1096     if (node != NULL)
1097         while (node->avl_link[0] != NULL)
1098             node = node->avl_link[0];
1099
1100     return (struct AVLNode *)node;
1101
1102     AROS_LIBFUNC_EXIT;
1103 }                               /* AVL_FindFirstNode */
1104
1105 /*****************************************************************************
1106
1107     NAME */
1108
1109     AROS_LH1I(struct AVLNode *, AVL_FindLastNode,
1110
1111 /*  SYNOPSIS */
1112           AROS_LHA(const struct AVLNode *, Root, A0),
1113 /*  LOCATION */
1114           struct ExecBase *, SysBase, 151, Exec)
1115 /*  FUNCTION
1116         Find the largest node in an AVL tree.
1117
1118     INPUTS
1119         Root - The root node of the AVL tree.
1120
1121     RESULT
1122         NULL if the tree is empty (i.e. Root is NULL), or the node
1123         which contains the greatest value in the tree as determined by
1124         the comparision function used to add the node.
1125
1126     NOTES
1127         AVL trees are balanced but not minimal.  This operation
1128         must iterate the full depth of the tree on one side -
1129         approximately 1.44Log(N).
1130
1131     EXAMPLE
1132         See AVL_FindPrevNodeByAddress()
1133
1134     BUGS
1135
1136     SEE ALSO
1137         AVL_AddNode(), AVL_FindPrevNodeByAddress()
1138
1139     INTERNALS
1140 ******************************************************************************/
1141 {
1142     AROS_LIBFUNC_INIT;
1143
1144     struct AVLNode *node = (struct AVLNode *)Root;
1145
1146     if (node != NULL)
1147         while (node->avl_link[1] != NULL)
1148             node = node->avl_link[1];
1149
1150     return (struct AVLNode *)node;
1151
1152     AROS_LIBFUNC_EXIT;
1153 }                               /* AVL_FindLastNode */