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