revert between 56095 -> 55830 in arch
[AROS.git] / rom / exec / avl.c
blobbab3a4ec17c8a3b100f9014aa8d447698832c836
1 /* indent -blC -bli0 -npcs -ncs -i4 -bad -bap avl.c */
2 /*
3 Copyright (c) 2008, The AROS Development Team. All rights reserved.
5 #Description: @AROS.Exec.AVL@
7 <chapter title="Exec AVL Trees">
9 <p>FIXME explain it</p>
11 </chapter>
15 #include <proto/exec.h>
16 #include <exec/avl.h>
18 /* don't think this works inside exec.library */
19 #define D(x)
21 #define LEFT (0)
22 #define RIGHT (1)
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)
31 int dir;
33 if (parent == NULL)
35 *root = subroot;
36 subroot->avl_parent = NULL;
37 dir = -1;
39 else
41 dir = parent->avl_link[1] == scan;
42 parent->avl_link[dir] = subroot;
43 subroot->avl_parent = parent;
46 return dir;
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)
54 struct AVLNode *subroot = next;
55 const int other = dir == 0;
57 D(printf("single %s about %p\n", dir == 0 ? "left" : "right", subroot));
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;
65 return subroot;
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)
73 struct AVLNode *subroot = next->avl_link[dir];
74 const int other = dir == 0;
76 D(printf("double %s about %p\n", dir == 0 ? "left" : "right", subroot));
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;
87 next->avl_parent = subroot;
88 scan->avl_parent = subroot;
90 return subroot;
93 /*****************************************************************************
95 NAME */
97 AROS_LH3I(struct AVLNode *, AVL_AddNode,
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.
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.
112 Node - The new node to add. Any key information must alread be
113 initialised.
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.
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.
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.
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.
133 AVLNODECOMP is used to compare the keys of two nodes.
135 typedef LONG *AVLNODECOMP(const struct AVLNode *avlnode1,
136 const struct AVLNode *avlnode2);
137 D0 A0, A1
139 AVLKEYCOMP is used to compare a key to a node.
141 typedef LONG *AVLKEYCOMP(const struct AVLNode *avlnode,
142 AVLKey key);
143 D0 A0, A1
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
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.
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.
164 struct ExampleNode {
165 struct AVLNode avl;
166 STRPTR key;
167 ULONG count;
170 static LONG ExampleNodeComp(const struct AVLNode *a1, const struct AVLNode *a2)
172 const struct ExampleNode *e1 = (const struct ExampleNode *)a1;
173 const struct ExampleNode *e2 = (const struct ExampleNode *)e2;
175 return strcmp(a1->key, a2->key);
178 static LONG ExampleKeyComp(const struct AVLNode *a1, AVLKey key)
180 const struct ExampleNode *e1 = (const struct ExampleNode *)a1;
181 char *skey = key;
183 return strcmp(a1->key, skey);
186 void CountWords(wordfile)
188 struct ExampleNode *node;
189 struct AVLNode *root = NULL, *check;
191 node = AllocMem(sizeof(struct ExampleNode), 0);
192 node->count = 1;
194 while (node->key = read_word(wordfile)) {
195 check = AVL_AddNode(&root, &node->avl, ExampleNodecomp);
197 if (check != NULL) {
198 struct ExampleNode *work = (struct ExampleNode *)check;
200 check->count += 1;
201 } else {
202 free(node->key);
203 node = AllocMem(sizeof(struct ExampleNode), 0);
204 node->count = 1;
207 FreeMem(node, sizeof(struct ExampleNode));
210 BUGS
212 SEE ALSO
213 AVL_FindNode(), AVL_FindNextNodeByKey(), AVL_FindPrevNodeByKey(),
214 AVL_RemNodeByAddress(), AVL_RemNodeByKey()
216 INTERNALS
217 ******************************************************************************/
219 AROS_LIBFUNC_INIT;
221 int dir;
222 struct AVLNode *next = *root;
223 struct AVLNode *scan;
224 struct AVLNode *child;
226 /* Simple case - empty tree */
227 if (next == NULL)
229 *root = node;
230 node->avl_link[0] = node->avl_link[1] = node->avl_parent = NULL;
231 node->avl_balance = 0;
232 return NULL;
235 /* find insertion point */
238 LONG cmp;
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;
247 dir = cmp < 0;
248 next = scan->avl_link[dir];
250 while (next != NULL);
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;
258 /* update balance factors */
259 while (1)
261 LONG bal = (dir * 2 - 1) + scan->avl_balance;
262 struct AVLNode *parent;
263 struct AVLNode *subroot;
265 switch (bal)
267 case 0:
268 scan->avl_balance = bal;
269 return NULL;
271 case 2:
272 parent = scan->avl_parent;
273 next = scan->avl_link[1];
275 switch (next->avl_balance)
277 case -1:
278 subroot = rotate_double(scan, next, LEFT);
280 if (subroot->avl_balance == 1)
282 scan->avl_balance = -1;
283 next->avl_balance = 0;
285 else if (subroot->avl_balance == -1)
287 scan->avl_balance = 0;
288 next->avl_balance = 1;
290 else
292 scan->avl_balance = next->avl_balance = 0;
295 subroot->avl_balance = 0;
296 break;
297 default:
298 subroot = rotate_single(scan, next, LEFT);
300 scan->avl_balance = next->avl_balance = 0;
301 break;
304 link_parent(root, scan, subroot, parent);
305 return NULL;
307 case -2:
308 parent = scan->avl_parent;
309 next = scan->avl_link[0];
311 switch (next->avl_balance)
313 case 1:
314 subroot = rotate_double(scan, next, RIGHT);
316 if (subroot->avl_balance == -1)
318 scan->avl_balance = 1;
319 next->avl_balance = 0;
321 else if (subroot->avl_balance == 1)
323 scan->avl_balance = 0;
324 next->avl_balance = -1;
326 else
328 scan->avl_balance = next->avl_balance = 0;
331 subroot->avl_balance = 0;
332 break;
333 default:
334 subroot = rotate_single(scan, next, RIGHT);
336 scan->avl_balance = next->avl_balance = 0;
337 break;
340 link_parent(root, scan, subroot, parent);
341 return NULL;
343 default:
344 scan->avl_balance = bal;
346 child = scan;
347 scan = scan->avl_parent;
348 if (scan == NULL)
349 return NULL;
351 dir = scan->avl_link[1] == child;
352 break;
356 return NULL;
358 AROS_LIBFUNC_EXIT;
359 } /* AVL_AddNode */
361 /*****************************************************************************
363 NAME */
365 AROS_LH2I(struct AVLNode *, AVL_RemNodeByAddress,
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.
375 INPUTS
376 Root - A pointer to a pointer to the root node of the tree.
378 Node - A struct AVLNode to remove. The node must be present
379 in the tree.
381 RESULT
382 Node is returned.
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.
389 EXAMPLE
390 See AVL_FindNextNodeByAddress(), AVL_FindPrevNodeByAddress()
392 BUGS
394 SEE ALSO
395 AVL_AddNode(), AVL_FindNode(), AVL_FindNextNodeByAddress(),
396 AVL_FindPrevNodeByAddress()
398 INTERNALS
399 ******************************************************************************/
401 AROS_LIBFUNC_INIT;
403 struct AVLNode *scan;
404 struct AVLNode *node = (struct AVLNode *)Node;
405 struct AVLNode **root = (struct AVLNode **)Root;
406 int dir;
408 if (node->avl_link[0] == NULL)
410 if (node->avl_link[1] == NULL)
412 if (node->avl_parent == NULL)
414 /* removed last node */
415 *root = NULL;
416 return Node;
418 else
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));
427 else
429 if (node->avl_parent == NULL)
431 /* removed root left-leaf node */
432 *root = node->avl_link[1];
433 node->avl_link[1]->avl_parent = NULL;
434 return Node;
436 else
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));
447 else
449 if (node->avl_link[1] == NULL)
451 if (node->avl_parent == NULL)
453 /* removed root right-leaf node */
454 *root = node->avl_link[0];
455 node->avl_link[0]->avl_parent = NULL;
456 return Node;
458 else
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));
468 else
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? */
473 D(printf("removing non-leaf key ... %p\n", toremove));
475 /* remove the leaf node */
476 scan = toremove->avl_parent;
478 if (scan == node)
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"));
488 else
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;
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"));
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;
512 D(printf("removed key, tree is now:\n"));
513 D(dumptree(*root, 0));
517 /* rebalance from 'scan' up */
518 while (1)
520 int bal = scan->avl_balance - (dir * 2 - 1);
521 struct AVLNode *next;
522 struct AVLNode *parent;
523 struct AVLNode *subroot = NULL;
525 switch (bal)
527 case 0:
528 scan->avl_balance = bal;
530 parent = scan->avl_parent;
531 if (parent == NULL)
532 return Node;
534 dir = parent->avl_link[1] == scan;
535 scan = parent;
536 break;
538 case -1:
539 case 1:
540 scan->avl_balance = bal;
541 return Node;
543 case 2:
544 parent = scan->avl_parent;
545 next = scan->avl_link[1];
547 switch (next->avl_balance)
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);
565 if (subroot->avl_balance == 1)
567 scan->avl_balance = -1;
568 next->avl_balance = 0;
570 else if (subroot->avl_balance == -1)
572 scan->avl_balance = 0;
573 next->avl_balance = 1;
575 else
577 scan->avl_balance = 0;
578 next->avl_balance = 0;
581 subroot->avl_balance = 0;
582 // keep going
583 break;
586 dir = link_parent(root, scan, subroot, parent);
587 if (dir == -1)
588 return Node;
590 scan = parent;
591 break;
593 case -2:
594 parent = scan->avl_parent;
595 next = scan->avl_link[0];
597 switch (next->avl_balance)
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);
614 if (subroot->avl_balance == -1)
616 scan->avl_balance = 1;
617 next->avl_balance = 0;
619 else if (subroot->avl_balance == 1)
621 scan->avl_balance = 0;
622 next->avl_balance = -1;
624 else
626 scan->avl_balance = 0;
627 next->avl_balance = 0;
630 subroot->avl_balance = 0;
631 // keep going
632 break;
635 dir = link_parent(root, scan, subroot, parent);
636 if (dir == -1)
637 return Node;
639 scan = parent;
640 break;
644 AROS_LIBFUNC_EXIT;
645 } /* AVL_RemNodeByAddress */
647 /*****************************************************************************
649 NAME */
651 AROS_LH3I(struct AVLNode *, AVL_RemNodeByKey,
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.
662 INPUTS
663 Root - A pointer to a pointer to the root node of the AVL tree.
665 key - The key to search for.
667 func - An AVLKEYCOMP function used to compare the key and nodes
668 in the tree.
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.
675 NOTES
676 See AVL_RemNodeByAddress().
678 EXAMPLE
680 BUGS
682 SEE ALSO
683 AVL_AddNode(), AVL_RemNodeByAddress()
685 INTERNALS
686 ******************************************************************************/
688 AROS_LIBFUNC_INIT;
690 struct AVLNode *node;
692 node = AVL_FindNode(*root, key, func);
694 if (node != NULL)
695 node = AVL_RemNodeByAddress(root, node);
697 return node;
699 AROS_LIBFUNC_EXIT;
700 } /* AVL_RemNodeByKey */
702 /*****************************************************************************
704 NAME */
706 AROS_LH3I(struct AVLNode *, AVL_FindNode,
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.
716 INPUTS
717 Root - The root of the AVL tree.
719 key - The key to search.
721 func - The AVLKEYCOMP key comparision function for this tree.
723 RESULT
724 A pointer to the node matching key if it exists in the
725 tree, or NULL if no such node exists.
727 NOTES
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);
734 BUGS
736 SEE ALSO
737 AVL_AddNode(), AVL_RemNodeByAddress(), AVL_FindNextNodeByAddress(),
738 AVL_FindPrevNodeByAddress()
740 INTERNALS
741 ******************************************************************************/
743 AROS_LIBFUNC_INIT;
745 struct AVLNode *node = (struct AVLNode *)Root;
746 LONG cmp;
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)
753 node = node->avl_link[cmp < 0];
756 return (struct AVLNode *)node;
758 AROS_LIBFUNC_EXIT;
759 } /* AVL_FindNode */
761 /*****************************************************************************
763 NAME */
765 AROS_LH1I(struct AVLNode *, AVL_FindPrevNodeByAddress,
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.
774 INPUTS
775 Node - The current node. The node must be present in the tree.
777 RESULT
778 The next-least node in the tree, or NULL if Node was already
779 the lowest valued node in the tree.
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.
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).
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);
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);
802 if (DELETE_NODE(node))
803 AVL_RemNodeByAddress(&root, node);
805 node = prev;
806 prev = (struct ExampleNode *)AVL_FindPrevNodeByAddress(node);
809 BUGS
811 SEE ALSO
812 AVL_AddNode(), AVL_RemNodeByAddress(), AVL_FindLastNode()
814 INTERNALS
815 ******************************************************************************/
817 AROS_LIBFUNC_INIT;
819 const struct AVLNode *node = (const struct AVLNode *)Node;
820 const struct AVLNode *prev;
822 prev = node->avl_link[0];
823 if (prev != NULL)
827 node = prev;
828 prev = prev->avl_link[1];
830 while (prev);
832 else
836 prev = node;
837 node = node->avl_parent;
839 while (node != NULL && node->avl_link[1] != prev);
842 return (struct AVLNode *)node;
844 AROS_LIBFUNC_EXIT;
845 } /* AVL_FindPrevNodeByAddress */
847 /*****************************************************************************
849 NAME */
851 AROS_LH3I(struct AVLNode *, AVL_FindPrevNodeByKey,
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.
862 INPUTS
863 Root - The root of the AVL tree.
865 key - The key to search.
867 func - The AVLKEYCOMP key comparision function for this tree.
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.
874 NOTES
875 This is only O(1.44log(n)) in the worst case.
877 EXAMPLE
879 BUGS
881 SEE ALSO
882 AVL_AddNode(), AVL_FindNextNodeByAddress(), AVL_FindLastNode()
884 INTERNALS
885 ******************************************************************************/
887 AROS_LIBFUNC_INIT;
889 struct AVLNode *node = (struct AVLNode *)root;
890 struct AVLNode *lesser = NULL;
891 LONG cmp;
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)
898 if (cmp < 0)
899 lesser = node;
900 node = node->avl_link[cmp < 0];
903 return (struct AVLNode *)(node != NULL ? node : lesser);
905 AROS_LIBFUNC_EXIT;
906 } /* AVL_FindPrevNodeByKey */
908 /*****************************************************************************
910 NAME */
912 AROS_LH1I(struct AVLNode *, AVL_FindNextNodeByAddress,
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.
921 INPUTS
922 Node - The current node. The node must be present in the tree.
924 RESULT
925 The next-greatest node in the tree, or NULL if Node was already
926 the highest valued node in the tree.
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.
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).
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);
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);
949 if (DELETE_NODE(node))
950 AVL_RemNodeByAddress(&root, node);
952 node = next;
953 next = (struct ExampleNode *)AVL_FindNextNodeByAddress(node);
956 BUGS
958 SEE ALSO
959 AVL_AddNode(), AVL_RemNodeByAddress(), AVL_FindFirstNode()
961 INTERNALS
962 ******************************************************************************/
964 AROS_LIBFUNC_INIT;
966 const struct AVLNode *node = (const struct AVLNode *)Node;
967 const struct AVLNode *next;
969 next = node->avl_link[1];
970 if (next != NULL)
974 node = next;
975 next = node->avl_link[0];
977 while (next != NULL);
979 else
983 next = node;
984 node = node->avl_parent;
986 while (node != NULL && node->avl_link[1] == next);
989 return (struct AVLNode *)node;
991 AROS_LIBFUNC_EXIT;
992 } /* AVL_FindNextNodeByAddress */
994 /*****************************************************************************
996 NAME */
998 AROS_LH3I(struct AVLNode *, AVL_FindNextNodeByKey,
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.
1009 INPUTS
1010 Root - The root of the AVL tree.
1012 key - The key to search.
1014 func - The AVLKEYCOMP key comparision function for this tree.
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.
1021 NOTES
1022 This is only O(1.44log(n)) in the worst case.
1024 EXAMPLE
1026 BUGS
1028 SEE ALSO
1029 AVL_AddNode(), AVL_FindNextNodeByAddress(), AVL_FindLastNode()
1031 INTERNALS
1032 ******************************************************************************/
1034 AROS_LIBFUNC_INIT;
1036 struct AVLNode *node = (struct AVLNode *)Root;
1037 struct AVLNode *greater = NULL;
1038 LONG cmp;
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)
1045 if (cmp > 0)
1046 greater = node;
1047 node = node->avl_link[cmp < 0];
1050 return (struct AVLNode *)(node != NULL ? node : greater);
1052 AROS_LIBFUNC_EXIT;
1053 } /* AVL_FindNextNodeByKey */
1055 /*****************************************************************************
1057 NAME */
1059 AROS_LH1I(struct AVLNode *, AVL_FindFirstNode,
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.
1068 INPUTS
1069 Root - The root node of the AVL tree.
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.
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).
1081 EXAMPLE
1082 See AVL_FindNextNodeByAddress()
1084 BUGS
1086 SEE ALSO
1087 AVL_AddNode(), AVL_FindNextNodeByAddress()
1089 INTERNALS
1090 ******************************************************************************/
1092 AROS_LIBFUNC_INIT;
1094 struct AVLNode *node = (struct AVLNode *)Root;
1096 if (node != NULL)
1097 while (node->avl_link[0] != NULL)
1098 node = node->avl_link[0];
1100 return (struct AVLNode *)node;
1102 AROS_LIBFUNC_EXIT;
1103 } /* AVL_FindFirstNode */
1105 /*****************************************************************************
1107 NAME */
1109 AROS_LH1I(struct AVLNode *, AVL_FindLastNode,
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.
1118 INPUTS
1119 Root - The root node of the AVL tree.
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.
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).
1131 EXAMPLE
1132 See AVL_FindPrevNodeByAddress()
1134 BUGS
1136 SEE ALSO
1137 AVL_AddNode(), AVL_FindPrevNodeByAddress()
1139 INTERNALS
1140 ******************************************************************************/
1142 AROS_LIBFUNC_INIT;
1144 struct AVLNode *node = (struct AVLNode *)Root;
1146 if (node != NULL)
1147 while (node->avl_link[1] != NULL)
1148 node = node->avl_link[1];
1150 return (struct AVLNode *)node;
1152 AROS_LIBFUNC_EXIT;
1153 } /* AVL_FindLastNode */