source: trunk/src/helpers/tree.c@ 13

Last change on this file since 13 was 13, checked in by umoeller, 25 years ago

Updates for V0.9.6.
  • Property svn:eol-style set to CRLF
  • Property svn:keywords set to Author Date Id Revision
File size: 27.5 KB
Line 
1
2/*
3 *@@sourcefile tree.c:
4 * contains helper functions for maintaining 'Red-Black' balanced
5 * binary trees.
6 * See explanations below.
7 *
8 * This file is all new with V0.9.5 (2000-09-29) [umoeller].
9 *
10 * Usage: All C programs; not OS/2-specific.
11 *
12 * Function prefixes (new with V0.81):
13 * -- tree* tree helper functions
14 *
15 * This has been taken from the Standard Function Library (SFL)
16 * by iMatix Corporation and changed to user the "id" member for
17 * tree sorting/comparison. This implementation is released
18 * under the GPL.
19 *
20 * <B>Using binary trees</B>
21 *
22 * You can use any structure as elements in a tree, provided
23 * that the first member in the structure is a TREE structure
24 * (i.e. it has the left, right, parent, id, and colour members).
25 * The tree functions don't care what follows.
26 *
27 * So the implementation here is slightly different from the
28 * linked lists in linklist.c, because the LISTNODE structs
29 * only have pointers to the data. By contrast, the TREE structs
30 * are expected to contain the data themselves. See treeInsertID()
31 * for a sample.
32 *
33 * Each TREE node does not only contain data, but also an
34 * "id" field. The order of nodes in the tree is determined
35 * by calling a node comparison function provided by the caller
36 * (which you must write). This takes two "id" values and must
37 * return:
38 *
39 + 0: id1 == id2
40 + -1: id1 < id2
41 + +1: id1 > id2
42 *
43 * Initialize the root of the tree with treeInit(). Then
44 * add nodes to the tree with treeInsertID() and remove nodes
45 * with treeDelete().
46 *
47 * You can test whether a tree is empty by comparing its
48 * root with TREE_NULL.
49 *
50 * Compared to linked lists (as implemented by linklist.c),
51 * trees allow for much faster searching.
52 *
53 * Assuming a linked list contains N items, then searching the
54 * list for an item will take an average of N/2 comparisons
55 * and even N comparisons if the item cannot be found (unless
56 * you keep the list sorted, but linklist.c doesn't do this).
57 *
58 * According to "Algorithms in C", a search in a balanced
59 * "red-black" binary tree takes about lg N comparisons on
60 * average, and insertions take less than one rotation on
61 * average.
62 *
63 * Example: You need to build a list of files, and you
64 * will search the list frequently according to the file
65 * handles. This would make the handle an ideal "id" field.
66 *
67 * Differences compared to linklist.c:
68 *
69 * -- Trees are considerably slower when inserting and removing
70 * nodes because the tree has to be rebalanced every time
71 * a node changes. By contrast, trees are much faster finding
72 * nodes because the tree is always sorted.
73 *
74 * -- You must always supply a comparison function to allow the
75 * tree functions to sort the tree.
76 *
77 * -- As opposed to a LISTNODE, the TREE structure (which
78 * represents a tree node) does not contain a data pointer,
79 * as said above.
80 *
81 *@@added V0.9.5 (2000-09-29) [umoeller]
82 *@@header "helpers\tree.h"
83 */
84
85/*
86 * Written: 97/11/18 Jonathan Schultz <jonathan@imatix.com>
87 * Revised: 98/12/08 Jonathan Schultz <jonathan@imatix.com>
88 *
89 * Copyright (C) 1991-99 iMatix Corporation.
90 * Copyright (C) 2000 Ulrich M”ller.
91 * This file is part of the XWorkplace source package.
92 * XWorkplace is free software; you can redistribute it and/or modify
93 * it under the terms of the GNU General Public License as published
94 * by the Free Software Foundation, in version 2 as it comes in the
95 * "COPYING" file of the XWorkplace main distribution.
96 * This program is distributed in the hope that it will be useful,
97 * but WITHOUT ANY WARRANTY; without even the implied warranty of
98 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
99 * GNU General Public License for more details.
100 */
101
102/*
103 *@@category: Helpers\C helpers\Red-black balanced binary trees
104 */
105
106#include "setup.h"
107#include "helpers\tree.h"
108
109// Constants
110TREE TREE_EMPTY = {TREE_NULL, TREE_NULL, NULL, BLACK};
111
112// Internal function prototypes
113static void insert_fixup(TREE **root, TREE *tree);
114static void rotate_left(TREE **root, TREE *tree);
115static void rotate_right(TREE **root, TREE *tree);
116static void delete_fixup(TREE **root, TREE *tree);
117
118/*
119 *@@ treeInit:
120 * initializes an empty tree. The data on the
121 * tree will be invalid, and no memory will be
122 * freed.
123 *
124 * Usage:
125 + TREE *TreeRoot;
126 + treeInit(&TreeRoot);
127 */
128
129void treeInit(TREE **root)
130{
131 *root = TREE_NULL;
132}
133
134/*
135 *@@ treeInsertID:
136 * inserts a node into an existing tree.
137 *
138 * Note: A tree node MUST contain a TREE structure
139 * at the beginning for the tree functions to work.
140 * So to create a tree node with usable data, do this:
141 *
142 + typedef _MYTREENODE
143 + {
144 + // TREE must be at beginning
145 + TREE Tree;
146 + // now use whatever you want
147 + CHAR szMyExtraData[100];
148 + } MYTREENODE, *PMYTREENODE;
149 *
150 * When calling the tree functions, manually cast your
151 * MYTREENODE pointers to (TREE*).
152 *
153 * This function initialises the node pointers and colour
154 * in the TREE structure to correct values, so the caller
155 * does not have to worry about those.
156 *
157 * However you must initialize the TREE.id member correctly
158 * so that your comparison function can compare on that
159 * to find the correct place in the tree to insert the node.
160 *
161 * Usage:
162 + TREE *TreeRoot;
163 + treeInit(&TreeRoot);
164 +
165 + PMYTREENODE pTreeItem = malloc(sizeof(MYTREENODE));
166 + pTreeItem->Tree.id = 1;
167 +
168 + treeInsertID(&TreeRoot,
169 + (TREE*)pTreeItem,
170 + fnCompare, // your comparison function
171 + FALSE);
172 *
173 * Returns:
174 *
175 * -- TREE_OK: OK, item inserted.
176 *
177 * -- TREE_DUPLICATE: if (fAllowDuplicates == FALSE), this is
178 * returned if a tree item with the specified ID already
179 * exists.
180 */
181
182int treeInsertID(TREE **root, // in: root of tree
183 TREE *tree, // in: new tree node
184 FNTREE_COMPARE_IDS *comp, // in: comparison function
185 BOOL fAllowDuplicates) // in: whether duplicates with the same ID are allowed
186{
187 TREE
188 *current,
189 *parent;
190 int
191 last_comp = 0;
192
193 // find where node belongs
194 current = *root;
195 parent = NULL;
196 while (current != TREE_NULL)
197 {
198 parent = current;
199 last_comp = comp(tree->id, current->id);
200 switch (last_comp)
201 {
202 case -1: current = current->left; break;
203 case 1: current = current->right; break;
204 default: if (fAllowDuplicates)
205 current = current->left;
206 else
207 return TREE_DUPLICATE;
208
209 }
210 }
211
212 // setup new node
213 ((TREE *) tree)->parent = parent;
214 ((TREE *) tree)->left = TREE_NULL;
215 ((TREE *) tree)->right = TREE_NULL;
216 ((TREE *) tree)->colour = RED;
217
218 // insert node in tree
219 if (parent)
220 switch (last_comp)
221 {
222 case 1: parent->right = tree; break;
223 default: parent->left = tree;
224 }
225 else
226 *root = tree;
227
228 insert_fixup(root, tree);
229 return(TREE_OK);
230}
231
232/*
233 *@@ treeInsertNode:
234 * similar to treeInsertID, but this uses
235 * a comparision function which compares
236 * nodes.
237 */
238
239int treeInsertNode(TREE **root, // in: root of tree
240 TREE *tree, // in: new tree node
241 FNTREE_COMPARE_NODES *comp, // in: comparison function
242 BOOL fAllowDuplicates) // in: whether duplicates with the same ID are allowed
243{
244 TREE
245 *current,
246 *parent;
247 int
248 last_comp = 0;
249
250 // find where node belongs
251 current = *root;
252 parent = NULL;
253 while (current != TREE_NULL)
254 {
255 parent = current;
256 last_comp = comp(tree, current);
257 switch (last_comp)
258 {
259 case -1: current = current->left; break;
260 case 1: current = current->right; break;
261 default: if (fAllowDuplicates)
262 current = current->left;
263 else
264 return TREE_DUPLICATE;
265
266 }
267 }
268
269 // setup new node
270 ((TREE *) tree)->parent = parent;
271 ((TREE *) tree)->left = TREE_NULL;
272 ((TREE *) tree)->right = TREE_NULL;
273 ((TREE *) tree)->colour = RED;
274
275 // insert node in tree
276 if (parent)
277 switch (last_comp)
278 {
279 case 1: parent->right = tree; break;
280 default: parent->left = tree;
281 }
282 else
283 *root = tree;
284
285 insert_fixup(root, tree);
286 return(TREE_OK);
287}
288
289/*
290 * insert_fixup:
291 * maintains the Red-Black tree balance after a node has been inserted.
292 *
293 * Private function.
294 */
295
296static void insert_fixup(TREE **root,
297 TREE *tree)
298{
299 TREE *uncle;
300
301 // check red-black properties
302 while ((tree != *root)
303 && (tree->parent->colour == RED))
304 {
305 // we have a violation
306 if (tree->parent == tree->parent->parent->left)
307 {
308 uncle = tree->parent->parent->right;
309 if (uncle->colour == RED)
310 {
311 // uncle is RED
312 tree ->parent->colour = BLACK;
313 uncle->colour = BLACK;
314 tree ->parent->parent->colour = RED;
315
316 tree = tree->parent->parent;
317 }
318 else
319 {
320 // uncle is BLACK
321 if (tree == tree->parent->right)
322 {
323 // make tree a left child
324 tree = tree->parent;
325 rotate_left (root, tree);
326 }
327
328 // recolor and rotate
329 tree->parent->colour = BLACK;
330 tree->parent->parent->colour = RED;
331 rotate_right (root, tree->parent->parent);
332 }
333 }
334 else
335 {
336 // mirror image of above code
337 uncle = tree->parent->parent->left;
338 if (uncle->colour == RED)
339 {
340 // uncle is RED
341 tree ->parent->colour = BLACK;
342 uncle->colour = BLACK;
343 tree ->parent->parent->colour = RED;
344
345 tree = tree->parent->parent;
346 }
347 else
348 {
349 // uncle is BLACK
350 if (tree == tree->parent->left)
351 {
352 tree = tree->parent;
353 rotate_right (root, tree);
354 }
355 tree->parent->colour = BLACK;
356 tree->parent->parent->colour = RED;
357 rotate_left (root, tree->parent->parent);
358 }
359 }
360 }
361 (*root)->colour = BLACK;
362}
363
364/*
365 * rotate_left:
366 * rotates tree to left.
367 *
368 * Private function.
369 */
370
371static void rotate_left(TREE **root,
372 TREE *tree)
373{
374 TREE *other = tree->right;
375
376 // establish tree->right link
377 tree->right = other->left;
378 if (other->left != TREE_NULL)
379 other->left->parent = tree;
380
381 // establish other->parent link
382 if (other != TREE_NULL)
383 other->parent = tree->parent;
384
385 if (tree->parent)
386 {
387 if (tree == tree->parent->left)
388 tree->parent->left = other;
389 else
390 tree->parent->right = other;
391 }
392 else
393 *root = other;
394
395 // link tree and other
396 other->left = tree;
397 if (tree != TREE_NULL)
398 tree->parent = other;
399}
400
401/*
402 * rotate_right:
403 * rotates tree to right.
404 *
405 * Private function.
406 */
407
408static void rotate_right(TREE **root,
409 TREE *tree)
410{
411 TREE *other;
412
413 other = tree->left;
414
415 // establish tree->left link
416 tree->left = other->right;
417 if (other->right != TREE_NULL)
418 other->right->parent = tree;
419
420 // establish other->parent link
421 if (other != TREE_NULL)
422 other->parent = tree->parent;
423
424 if (tree->parent)
425 {
426 if (tree == tree->parent->right)
427 tree->parent->right = other;
428 else
429 tree->parent->left = other;
430 }
431 else
432 *root = other;
433
434 // link tree and other
435 other->right = tree;
436 if (tree != TREE_NULL)
437 tree->parent = other;
438}
439
440/*
441 *@@ treeDelete:
442 * deletes a node from a tree. Does not deallocate any memory.
443 *
444 * Returns:
445 *
446 * -- TREE_OK: node deleted.
447 * -- TREE_INVALID_NODE: tree node not found.
448 */
449
450int treeDelete(TREE **root, // in: root of tree
451 TREE *tree) // in: tree node to delete
452{
453 int irc = TREE_OK;
454
455 TREE
456 *youngest, *descendent;
457 TREE_COLOUR
458 colour;
459
460 if ( (!tree)
461 || (tree == TREE_NULL)
462 )
463 return TREE_INVALID_NODE;
464
465 if ( (((TREE *) tree)->left == TREE_NULL)
466 || (((TREE *) tree)->right == TREE_NULL)
467 )
468 // descendent has a TREE_NULL node as a child
469 descendent = tree;
470 else
471 {
472 // find tree successor with a TREE_NULL node as a child
473 descendent = ((TREE *) tree)->right;
474 while (descendent->left != TREE_NULL)
475 descendent = descendent->left;
476 }
477
478 // youngest is descendent's only child, if there is one, else TREE_NULL
479 if (descendent->left != TREE_NULL)
480 youngest = descendent->left;
481 else
482 youngest = descendent->right;
483
484 // remove descendent from the parent chain
485 if (youngest != TREE_NULL)
486 youngest->parent = descendent->parent;
487 if (descendent->parent)
488 {
489 if (descendent == descendent->parent->left)
490 descendent->parent->left = youngest;
491 else
492 descendent->parent->right = youngest;
493 }
494 else
495 *root = youngest;
496
497 colour = descendent->colour;
498
499 if (descendent != (TREE *) tree)
500 {
501 // Conceptually what we are doing here is moving the data from
502 // descendent to tree. In fact we do this by linking descendent
503 // into the structure in the place of tree.
504 descendent->left = ((TREE *) tree)->left;
505 descendent->right = ((TREE *) tree)->right;
506 descendent->parent = ((TREE *) tree)->parent;
507 descendent->colour = ((TREE *) tree)->colour;
508
509 if (descendent->parent)
510 {
511 if (tree == descendent->parent->left)
512 descendent->parent->left = descendent;
513 else
514 descendent->parent->right = descendent;
515 }
516 else
517 *root = descendent;
518
519 if (descendent->left != TREE_NULL)
520 descendent->left->parent = descendent;
521
522 if (descendent->right != TREE_NULL)
523 descendent->right->parent = descendent;
524 }
525
526 if ( (youngest != TREE_NULL)
527 && (colour == BLACK))
528 delete_fixup (root, youngest);
529
530 return (irc);
531}
532
533/*
534 *@@ delete_fixup:
535 * maintains Red-Black tree balance after deleting a node.
536 *
537 * Private function.
538 */
539
540static void delete_fixup(TREE **root,
541 TREE *tree)
542{
543 TREE
544 *sibling;
545
546 while (tree != *root && tree->colour == BLACK)
547 {
548 if (tree == tree->parent->left)
549 {
550 sibling = tree->parent->right;
551 if (sibling->colour == RED)
552 {
553 sibling->colour = BLACK;
554 tree->parent->colour = RED;
555 rotate_left (root, tree->parent);
556 sibling = tree->parent->right;
557 }
558 if ((sibling->left->colour == BLACK)
559 && (sibling->right->colour == BLACK))
560 {
561 sibling->colour = RED;
562 tree = tree->parent;
563 }
564 else
565 {
566 if (sibling->right->colour == BLACK)
567 {
568 sibling->left->colour = BLACK;
569 sibling->colour = RED;
570 rotate_right (root, sibling);
571 sibling = tree->parent->right;
572 }
573 sibling->colour = tree->parent->colour;
574 tree->parent->colour = BLACK;
575 sibling->right->colour = BLACK;
576 rotate_left (root, tree->parent);
577 tree = *root;
578 }
579 }
580 else
581 {
582 sibling = tree->parent->left;
583 if (sibling->colour == RED)
584 {
585 sibling->colour = BLACK;
586 tree->parent->colour = RED;
587 rotate_right (root, tree->parent);
588 sibling = tree->parent->left;
589 }
590 if ((sibling->right->colour == BLACK)
591 && (sibling->left->colour == BLACK))
592 {
593 sibling->colour = RED;
594 tree = tree->parent;
595 }
596 else
597 {
598 if (sibling->left->colour == BLACK)
599 {
600 sibling->right->colour = BLACK;
601 sibling->colour = RED;
602 rotate_left (root, sibling);
603 sibling = tree->parent->left;
604 }
605 sibling->colour = tree->parent->colour;
606 tree->parent->colour = BLACK;
607 sibling->left->colour = BLACK;
608 rotate_right (root, tree->parent);
609 tree = *root;
610 }
611 }
612 }
613 tree->colour = BLACK;
614}
615
616/*
617 *@@ treeFindEQID:
618 * finds a node with ID exactly matching that provided.
619 * To find a tree node, your comparison function must
620 * compare the tree node IDs.
621 */
622
623void* treeFindEQID(TREE **root,
624 unsigned long id,
625 FNTREE_COMPARE_IDS *comp)
626{
627 TREE
628 *current = *root,
629 *found;
630
631 found = NULL;
632 while (current != TREE_NULL)
633 switch (comp(current->id, id))
634 {
635 case -1: current = current->right; break;
636 case 1: current = current->left; break;
637 default: found = current; // In case of duplicates,
638 current = current->left; // get the first one.
639 }
640
641 return found;
642}
643
644/*
645 *@@ treeFindGEID:
646 * finds a node with ID greater than or equal to provided.
647 * To find a tree node, your comparison function must
648 * compare the tree node IDs.
649 */
650
651void* treeFindGEID(TREE **root,
652 unsigned long idFind,
653 FNTREE_COMPARE_IDS *comp)
654{
655 TREE
656 *current = *root,
657 *found;
658
659 found = NULL;
660 while (current != TREE_NULL)
661 switch (comp(current->id, idFind))
662 {
663 case -1: current = current->right; break;
664 default: found = current;
665 current = current->left;
666 }
667
668 return found;
669}
670
671/*
672 *@@ treeFindEQNode:
673 * finds a node with ID exactly matching that provided.
674 * To find a tree node, your comparison function must
675 * compare the tree nodes.
676 */
677
678void* treeFindEQNode(TREE **root,
679 TREE *nodeFind,
680 FNTREE_COMPARE_NODES *comp)
681{
682 TREE
683 *current = *root,
684 *found;
685
686 found = NULL;
687 while (current != TREE_NULL)
688 switch (comp(current, nodeFind))
689 {
690 case -1: current = current->right; break;
691 case 1: current = current->left; break;
692 default: found = current; // In case of duplicates,
693 current = current->left; // get the first one.
694 }
695
696 return found;
697}
698
699/*
700 *@@ treeFindGENode:
701 * finds a node with ID greater than or equal to provided.
702 * To find a tree node, your comparison function must
703 * compare the tree nodes.
704 */
705
706void* treeFindGENode(TREE **root,
707 TREE *nodeFind,
708 FNTREE_COMPARE_NODES *comp)
709{
710 TREE
711 *current = *root,
712 *found;
713
714 found = NULL;
715 while (current != TREE_NULL)
716 switch (comp(current, nodeFind))
717 {
718 case -1: current = current->right; break;
719 default: found = current;
720 current = current->left;
721 }
722
723 return found;
724}
725
726/*
727 *@@ treeFindLTNode:
728 * finds a node with Node less than provided.
729 * To find a tree node, your comparison function must
730 * compare the tree nodes.
731 */
732
733void* treeFindLTNode(TREE **root,
734 TREE *nodeFind,
735 FNTREE_COMPARE_NODES *comp)
736{
737 TREE
738 *current = *root,
739 *found;
740
741 found = NULL;
742 while (current != TREE_NULL)
743 switch (comp(current, nodeFind))
744 {
745 case -1: found = current;
746 current = current->right; break;
747 default: current = current->left;
748 }
749
750 return found;
751}
752
753/*
754 *@@ treeFindLENode:
755 * finds a node with Node less than or equal to provided.
756 * To find a tree node, your comparison function must
757 * compare the tree nodes.
758 */
759
760void* treeFindLENode(TREE **root,
761 TREE *nodeFind,
762 FNTREE_COMPARE_NODES *comp)
763{
764 TREE
765 *current = *root,
766 *found;
767
768 found = NULL;
769 while (current != TREE_NULL)
770 switch (comp(current, nodeFind))
771 {
772 case 1 : current = current->left; break;
773 default: found = current;
774 current = current->right;
775 }
776
777 return found;
778}
779
780/*
781 *@@ treeFindGTNode:
782 * finds a node with Node greater than provided.
783 * To find a tree node, your comparison function must
784 * compare the tree nodes.
785 */
786
787void* treeFindGTNode(TREE **root,
788 TREE *nodeFind,
789 FNTREE_COMPARE_NODES *comp)
790{
791 TREE
792 *current = *root,
793 *found;
794
795 found = NULL;
796 while (current != TREE_NULL)
797 switch (comp(current, nodeFind))
798 {
799 case 1 : found = current;
800 current = current->left; break;
801 default: current = current->right;
802 }
803
804 return found;
805}
806
807/*
808 *@@ treeFindEQID:
809 * finds a node with data exactly matching that provided.
810 * To find a tree node, your comparison function must
811 * compare a tree member with external data.
812 *
813 * This is useful for finding a tree item from a string ID.
814 *
815 * Make sure to use treeInsertNode and compare according
816 * to a string member, and then write a second compare
817 * function for this function which compares the string
818 * member to an external string.
819 */
820
821void* treeFindEQData(TREE **root,
822 void *pData,
823 FNTREE_COMPARE_DATA *comp)
824{
825 TREE *current = *root,
826 *found = NULL;
827
828 while (current != TREE_NULL)
829 switch (comp(current, pData))
830 {
831 case -1: current = current->right; break;
832 case 1: current = current->left; break;
833 default: found = current; // In case of duplicates,
834 current = current->left; // get the first one.
835 }
836
837 return found;
838}
839
840/*
841 *@@ treeTraverse:
842 * traverses the specified tree, calling a processing function
843 * for each tree node.
844 *
845 * The processing function ("process") must be declared as
846 * follows:
847 *
848 + void fnProcess(TREE *t, // current tree node
849 + void *pUser); // user data
850 *
851 * and will receive the "pUser" parameter, which you can use
852 * as a data pointer to some structure for whatever you like.
853 *
854 * "method" specifies in which order the nodes are traversed.
855 * This can be:
856 *
857 * -- 1: current node first, then left node, then right node.
858 * -- 2: left node first, then right node, then current node.
859 * -- other: left node first, then current node, then right node.
860 */
861
862void treeTraverse(TREE *tree, // in: root of tree
863 TREE_PROCESS *process, // in: callback for each node
864 void *pUser, // in: user param for callback
865 int method) // in: traversal mode
866{
867 if ((!tree)
868 || (tree == TREE_NULL))
869 return;
870
871 if (method == 1)
872 {
873 process(tree, pUser);
874 treeTraverse (((TREE *) tree)->left, process, pUser, method);
875 treeTraverse (((TREE *) tree)->right, process, pUser, method);
876 }
877 else if (method == 2)
878 {
879 treeTraverse (((TREE *) tree)->left, process, pUser, method);
880 treeTraverse (((TREE *) tree)->right, process, pUser, method);
881 process(tree, pUser);
882 }
883 else
884 {
885 treeTraverse (((TREE *) tree)->left, process, pUser, method);
886 process(tree, pUser);
887 treeTraverse (((TREE *) tree)->right, process, pUser, method);
888 }
889}
890
891/*
892 *@@ treeFirst:
893 * finds and returns the first node in a (sub-)tree.
894 */
895
896void* treeFirst(TREE *tree)
897{
898 TREE
899 *current;
900
901 if ((!tree)
902 || (tree == TREE_NULL))
903 return NULL;
904
905 current = tree;
906 while (current->left != TREE_NULL)
907 current = current->left;
908
909 return current;
910}
911
912/*
913 *@@ treeLast:
914 * finds and returns the last node in a (sub-)tree.
915 */
916
917void* treeLast(TREE *tree)
918{
919 TREE
920 *current;
921
922 if ((!tree)
923 || (tree == TREE_NULL))
924 return NULL;
925
926 current = tree;
927 while (current->right != TREE_NULL)
928 current = current->right;
929
930 return current;
931}
932
933/*
934 *@@ treeNext:
935 * finds and returns the next node in a tree.
936 */
937
938void* treeNext(TREE *tree)
939{
940 TREE
941 *current,
942 *child;
943
944 if ((!tree)
945 || (tree == TREE_NULL))
946 return NULL;
947
948 current = tree;
949 if (current->right != TREE_NULL)
950 return treeFirst (current->right);
951 else
952 {
953 current = tree;
954 child = TREE_NULL;
955 while ((current->parent)
956 && (current->right == child))
957 {
958 child = current;
959 current = current->parent;
960 }
961 if (current->right != child)
962 return current;
963 else
964 return NULL;
965 }
966}
967
968/*
969 *@@ treePrev:
970 * finds and returns the previous node in a tree.
971 */
972
973void* treePrev(TREE *tree)
974{
975 TREE
976 *current,
977 *child;
978
979 if ((!tree)
980 || (tree == TREE_NULL))
981 return NULL;
982
983 current = tree;
984 if (current->left != TREE_NULL)
985 return treeLast (current->left);
986 else
987 {
988 current = tree;
989 child = TREE_NULL;
990 while ((current->parent)
991 && (current->left == child))
992 {
993 child = current;
994 current = current->parent;
995 }
996 if (current->left != child)
997 return current;
998 else
999 return NULL;
1000 }
1001}
1002
1003
Note: See TracBrowser for help on using the repository browser.