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