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

Last change on this file since 55 was 55, checked in by umoeller, 24 years ago

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