| blob | 43ca1a98716479b309c93951a17449c8144c23dc |
1 #ifndef UBI_BINTREE_H
2 #define UBI_BINTREE_H
3 /* ========================================================================== **
4 * ubi_BinTree.h
5 *
6 * Copyright (C) 1991-1998 by Christopher R. Hertel
7 *
8 * Email: crh@ubiqx.mn.org
9 * -------------------------------------------------------------------------- **
10 *
11 * This module implements a simple binary tree.
12 *
13 * -------------------------------------------------------------------------- **
14 *
15 * This library is free software; you can redistribute it and/or
16 * modify it under the terms of the GNU Library General Public
17 * License as published by the Free Software Foundation; either
18 * version 2 of the License, or (at your option) any later version.
19 *
20 * This library is distributed in the hope that it will be useful,
21 * but WITHOUT ANY WARRANTY; without even the implied warranty of
22 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
23 * Library General Public License for more details.
24 *
25 * You should have received a copy of the GNU Library General Public
26 * License along with this library; if not, write to the Free
27 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
28 *
29 * -------------------------------------------------------------------------- **
30 *
31 * Log: ubi_BinTree.h,v
32 * Revision 4.12 2004/06/06 04:51:56 crh
33 * Fixed a small typo in ubi_BinTree.c (leftover testing cruft).
34 * Did a small amount of formatting touchup to ubi_BinTree.h.
35 *
36 * Revision 4.11 2004/06/06 03:14:09 crh
37 * Rewrote the ubi_btLeafNode() function. It now takes several paths in an
38 * effort to find a deeper leaf node. There is a small amount of extra
39 * overhead, but it is limited.
40 *
41 * Revision 4.10 2000/06/06 20:38:40 crh
42 * In the ReplaceNode() function, the old node header was being copied
43 * to the new node header using a byte-by-byte copy. This was causing
44 * the 'insure' software testing program to report a memory leak. The
45 * fix was to do a simple assignement: *newnode = *oldnode;
46 * This quieted the (errant) memory leak reports and is probably a bit
47 * faster than the bytewise copy.
48 *
49 * Revision 4.9 2000/01/08 23:24:30 crh
50 * Clarified a variety of if( pointer ) lines, replacing them with
51 * if( NULL != pointer ). This is more correct, and I have heard
52 * of at least one (obscure?) system out there that uses a non-zero
53 * value for NULL.
54 * Also, speed improvement in Neighbor(). It was comparing pointers
55 * when it could have compared two gender values. The pointer
56 * comparison was somewhat indirect (does pointer equal the pointer
57 * of the parent of the node pointed to by pointer). Urq.
58 *
59 * Revision 4.8 1999/09/22 03:40:30 crh
60 * Modified ubi_btTraverse() and ubi_btKillTree(). They now return an
61 * unsigned long indicating the number of nodes processed. The change
62 * is subtle. An empty tree formerly returned False, and now returns
63 * zero.
64 *
65 * Revision 4.7 1998/10/21 06:15:07 crh
66 * Fixed bugs in FirstOf() and LastOf() reported by Massimo Campostrini.
67 * See function comments.
68 *
69 * Revision 4.6 1998/07/25 17:02:10 crh
70 * Added the ubi_trNewTree() macro.
71 *
72 * Revision 4.5 1998/06/04 21:29:27 crh
73 * Upper-cased defined constants (eg UBI_BINTREE_H) in some header files.
74 * This is more "standard", and is what people expect. Weird, eh?
75 *
76 * Revision 4.4 1998/06/03 17:42:46 crh
77 * Further fiddling with sys_include.h. It's now in ubi_BinTree.h which is
78 * included by all of the binary tree files.
79 *
80 * Reminder: Some of the ubi_tr* macros in ubi_BinTree.h are redefined in
81 * ubi_AVLtree.h and ubi_SplayTree.h. This allows easy swapping
82 * of tree types by simply changing a header. Unfortunately, the
83 * macro redefinitions in ubi_AVLtree.h and ubi_SplayTree.h will
84 * conflict if used together. You must either choose a single tree
85 * type, or use the underlying function calls directly. Compare
86 * the two header files for more information.
87 *
88 * Revision 4.3 1998/06/02 01:28:43 crh
89 * Changed ubi_null.h to sys_include.h to make it more generic.
90 *
91 * Revision 4.2 1998/05/20 04:32:36 crh
92 * The C file now includes ubi_null.h. See ubi_null.h for more info.
93 * Also, the balance and gender fields of the node were declared as
94 * signed char. As I understand it, at least one SunOS or Solaris
95 * compiler doesn't like "signed char". The declarations were
96 * wrong anyway, so I changed them to simple "char".
97 *
98 * Revision 4.1 1998/03/31 06:13:47 crh
99 * Thomas Aglassinger sent E'mail pointing out errors in the
100 * dereferencing of function pointers, and a missing typecast.
101 * Thanks, Thomas!
102 *
103 * Revision 4.0 1998/03/10 03:16:04 crh
104 * Added the AVL field 'balance' to the ubi_btNode structure. This means
105 * that all BinTree modules now use the same basic node structure, which
106 * greatly simplifies the AVL module.
107 * Decided that this was a big enough change to justify a new major revision
108 * number. 3.0 was an error, so we're at 4.0.
109 *
110 * Revision 2.6 1998/01/24 06:27:30 crh
111 * Added ubi_trCount() macro.
112 *
113 * Revision 2.5 1997/12/23 03:59:21 crh
114 * In this version, all constants & macros defined in the header file have
115 * the ubi_tr prefix. Also cleaned up anything that gcc complained about
116 * when run with '-pedantic -fsyntax-only -Wall'.
117 *
118 * Revision 2.4 1997/07/26 04:11:14 crh
119 * + Just to be annoying I changed ubi_TRUE and ubi_FALSE to ubi_trTRUE
120 * and ubi_trFALSE.
121 * + There is now a type ubi_trBool to go with ubi_trTRUE and ubi_trFALSE.
122 * + There used to be something called "ubi_TypeDefs.h". I got rid of it.
123 * + Added function ubi_btLeafNode().
124 *
125 * Revision 2.3 1997/06/03 05:15:27 crh
126 * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid conflicts.
127 * Also changed the interface to function InitTree(). See the comments
128 * for this function for more information.
129 *
130 * Revision 2.2 1995/10/03 22:00:40 CRH
131 * Ubisized!
132 *
133 * Revision 2.1 95/03/09 23:43:46 CRH
134 * Added the ModuleID static string and function. These modules are now
135 * self-identifying.
136 *
137 * Revision 2.0 95/02/27 22:00:33 CRH
138 * Revision 2.0 of this program includes the following changes:
139 *
140 * 1) A fix to a major typo in the RepaceNode() function.
141 * 2) The addition of the static function Border().
142 * 3) The addition of the public functions FirstOf() and LastOf(), which
143 * use Border(). These functions are used with trees that allow
144 * duplicate keys.
145 * 4) A complete rewrite of the Locate() function. Locate() now accepts
146 * a "comparison" operator.
147 * 5) Overall enhancements to both code and comments.
148 *
149 * I decided to give this a new major rev number because the interface has
150 * changed. In particular, there are two new functions, and changes to the
151 * Locate() function.
152 *
153 * Revision 1.0 93/10/15 22:55:04 CRH
154 * With this revision, I have added a set of #define's that provide a single,
155 * standard API to all existing tree modules. Until now, each of the three
156 * existing modules had a different function and typedef prefix, as follows:
157 *
158 * Module Prefix
159 * ubi_BinTree ubi_bt
160 * ubi_AVLtree ubi_avl
161 * ubi_SplayTree ubi_spt
162 *
163 * To further complicate matters, only those portions of the base module
164 * (ubi_BinTree) that were superceeded in the new module had the new names.
165 * For example, if you were using ubi_SplayTree, the locate function was
166 * called "ubi_sptLocate", but the next and previous functions remained
167 * "ubi_btNext" and "ubi_btPrev".
168 *
169 * This was not too terrible if you were familiar with the modules and knew
170 * exactly which tree model you wanted to use. If you wanted to be able to
171 * change modules (for speed comparisons, etc), things could get messy very
172 * quickly.
173 *
174 * So, I have added a set of defined names that get redefined in any of the
175 * descendant modules. To use this standardized interface in your code,
176 * simply replace all occurances of "ubi_bt", "ubi_avl", and "ubi_spt" with
177 * "ubi_tr". The "ubi_tr" names will resolve to the correct function or
178 * datatype names for the module that you are using. Just remember to
179 * include the header for that module in your program file. Because these
180 * names are handled by the preprocessor, there is no added run-time
181 * overhead.
182 *
183 * Note that the original names do still exist, and can be used if you wish
184 * to write code directly to a specific module. This should probably only be
185 * done if you are planning to implement a new descendant type, such as
186 * red/black trees. CRH
187 *
188 * V0.0 - June, 1991 - Written by Christopher R. Hertel (CRH).
189 *
190 * ========================================================================== **
191 */
194 * modules to the host environment and the project
195 * with which the modules will be used. See
196 * sys_include.h for more info.
197 */
199 /* -------------------------------------------------------------------------- **
200 * Macros and constants.
201 *
202 * General purpose:
203 * ubi_trTRUE - Boolean TRUE.
204 * ubi_trFALSE - Boolean FALSE.
205 *
206 * Flags used in the tree header:
207 * ubi_trOVERWRITE - This flag indicates that an existing node may be
208 * overwritten by a new node with a matching key.
209 * ubi_trDUPKEY - This flag indicates that the tree allows duplicate
210 * keys. If the tree does allow duplicates, the
211 * overwrite flag is ignored.
212 *
213 * Node link array index constants: (Each node has an array of three
214 * pointers. One to the left, one to the right, and one back to the
215 * parent.)
216 * ubi_trLEFT - Left child pointer.
217 * ubi_trPARENT - Parent pointer.
218 * ubi_trRIGHT - Right child pointer.
219 * ubi_trEQUAL - Synonym for PARENT.
220 *
221 * ubi_trCompOps: These values are used in the ubi_trLocate() function.
222 * ubi_trLT - request the first instance of the greatest key less than
223 * the search key.
224 * ubi_trLE - request the first instance of the greatest key that is less
225 * than or equal to the search key.
226 * ubi_trEQ - request the first instance of key that is equal to the
227 * search key.
228 * ubi_trGE - request the first instance of a key that is greater than
229 * or equal to the search key.
230 * ubi_trGT - request the first instance of the first key that is greater
231 * than the search key.
232 * -------------------------------------------------------------------------- **
233 */
235 #define ubi_trTRUE 0xFF
236 #define ubi_trFALSE 0x00
241 /* Pointer array index constants... */
242 #define ubi_trLEFT 0x00
243 #define ubi_trPARENT 0x01
244 #define ubi_trRIGHT 0x02
245 #define ubi_trEQUAL ubi_trPARENT
249 ubi_trLE,
250 ubi_trEQ,
251 ubi_trGE,
252 ubi_trGT
255 /* -------------------------------------------------------------------------- **
256 * These three macros allow simple manipulation of pointer index values (LEFT,
257 * RIGHT, and PARENT).
258 *
259 * Normalize() - converts {LEFT, PARENT, RIGHT} into {-1, 0 ,1}. C
260 * uses {negative, zero, positive} values to indicate
261 * {less than, equal to, greater than}.
262 * AbNormal() - converts {negative, zero, positive} to {LEFT, PARENT,
263 * RIGHT} (opposite of Normalize()). Note: C comparison
264 * functions, such as strcmp(), return {negative, zero,
265 * positive} values, which are not necessarily {-1, 0,
266 * 1}. This macro uses the the ubi_btSgn() function to
267 * compensate.
268 * RevWay() - converts LEFT to RIGHT and RIGHT to LEFT. PARENT (EQUAL)
269 * is left as is.
270 * -------------------------------------------------------------------------- **
271 */
273 #define ubi_trNormalize(W) ((char)( (W) - ubi_trEQUAL ))
274 #define ubi_trAbNormal(W) ((char)( ((char)ubi_btSgn( (long)(W) )) \
275 + ubi_trEQUAL ))
276 #define ubi_trRevWay(W) ((char)( ubi_trEQUAL - ((W) - ubi_trEQUAL) ))
278 /* -------------------------------------------------------------------------- **
279 * These macros allow us to quickly read the values of the OVERWRITE and
280 * DUPlicate KEY bits of the tree root flags field.
281 * -------------------------------------------------------------------------- **
282 */
284 #define ubi_trDups_OK(A) \
285 ((ubi_trDUPKEY & ((A)->flags))?(ubi_trTRUE):(ubi_trFALSE))
286 #define ubi_trOvwt_OK(A) \
287 ((ubi_trOVERWRITE & ((A)->flags))?(ubi_trTRUE):(ubi_trFALSE))
289 /* -------------------------------------------------------------------------- **
290 * Additional Macros...
291 *
292 * ubi_trCount() - Given a pointer to a tree root, this macro returns the
293 * number of nodes currently in the tree.
294 *
295 * ubi_trNewTree() - This macro makes it easy to declare and initialize a
296 * tree header in one step. The line
297 *
298 * static ubi_trNewTree( MyTree, cmpfn, ubi_trDUPKEY );
299 *
300 * is equivalent to
301 *
302 * static ubi_trRoot MyTree[1]
303 * = {{ NULL, cmpfn, 0, ubi_trDUPKEY }};
304 *
305 * -------------------------------------------------------------------------- **
306 */
308 #define ubi_trCount( R ) (((ubi_trRootPtr)(R))->count)
310 #define ubi_trNewTree( N, C, F ) ubi_trRoot (N)[1] = {{ NULL, (C), 0, (F) }}
312 /* -------------------------------------------------------------------------- **
313 * Typedefs...
314 *
315 * ubi_trBool - Your typcial true or false...
316 *
317 * Item Pointer: The ubi_btItemPtr is a generic pointer. It is used to
318 * indicate a key that is being searched for within the tree.
319 * Searching occurs whenever the ubi_trFind(), ubi_trLocate(),
320 * or ubi_trInsert() functions are called.
321 * -------------------------------------------------------------------------- **
322 */
328 /* ------------------------------------------------------------------------- **
329 * Binary Tree Node Structure: This structure defines the basic elements of
330 * the tree nodes. In general you *SHOULD NOT PLAY WITH THESE FIELDS*!
331 * But, of course, I have to put the structure into this header so that
332 * you can use it as a building block.
333 *
334 * The fields are as follows:
335 * Link - an array of pointers. These pointers are manipulated by
336 * the BT routines. The pointers indicate the left and right
337 * child nodes and the parent node. By keeping track of the
338 * parent pointer, we avoid the need for recursive routines or
339 * hand-tooled stacks to keep track of our path back to the
340 * root. The use of these pointers is subject to change without
341 * notice.
342 * gender - a one-byte field indicating whether the node is the RIGHT or
343 * LEFT child of its parent. If the node is the root of the
344 * tree, gender will be PARENT.
345 * balance - only used by the AVL tree module. This field indicates
346 * the height balance at a given node. See ubi_AVLtree for
347 * details.
348 *
349 * ------------------------------------------------------------------------- **
350 */
360 /* ------------------------------------------------------------------------- **
361 * The next three typedefs define standard function types used by the binary
362 * tree management routines. In particular:
363 *
364 * ubi_btCompFunc is a pointer to a comparison function. Comparison
365 * functions are passed an ubi_btItemPtr and an
366 * ubi_btNodePtr. They return a value that is (<0), 0,
367 * or (>0) to indicate that the Item is (respectively)
368 * "less than", "equal to", or "greater than" the Item
369 * contained within the node. (See ubi_btInitTree()).
370 * ubi_btActionRtn is a pointer to a function that may be called for each
371 * node visited when performing a tree traversal (see
372 * ubi_btTraverse()). The function will be passed two
373 * parameters: the first is a pointer to a node in the
374 * tree, the second is a generic pointer that may point to
375 * anything that you like.
376 * ubi_btKillNodeRtn is a pointer to a function that will deallocate the
377 * memory used by a node (see ubi_btKillTree()). Since
378 * memory management is left up to you, deallocation may
379 * mean anything that you want it to mean. Just remember
380 * that the tree *will* be destroyed and that none of the
381 * node pointers will be valid any more.
382 * ------------------------------------------------------------------------- **
383 */
391 /* -------------------------------------------------------------------------- **
392 * Tree Root Structure: This structure gives us a convenient handle for
393 * accessing whole binary trees. The fields are:
394 * root - A pointer to the root node of the tree.
395 * count - A count of the number of nodes stored in the tree.
396 * cmp - A pointer to the comparison routine to be used when building or
397 * searching the tree.
398 * flags - A set of bit flags. Two flags are currently defined:
399 *
400 * ubi_trOVERWRITE - If set, this flag indicates that a new node should
401 * (bit 0x01) overwrite an old node if the two have identical
402 * keys (ie., the keys are equal).
403 * ubi_trDUPKEY - If set, this flag indicates that the tree is
404 * (bit 0x02) allowed to contain nodes with duplicate keys.
405 *
406 * NOTE: ubi_trInsert() tests ubi_trDUPKEY before ubi_trOVERWRITE.
407 *
408 * All of these values are set when you initialize the root structure by
409 * calling ubi_trInitTree().
410 * -------------------------------------------------------------------------- **
411 */
423 /* -------------------------------------------------------------------------- **
424 * Function Prototypes.
425 */
428 /* ------------------------------------------------------------------------ **
429 * Return the sign of x; {negative,zero,positive} ==> {-1, 0, 1}.
430 *
431 * Input: x - a signed long integer value.
432 *
433 * Output: the "sign" of x, represented as follows:
434 * -1 == negative
435 * 0 == zero (no sign)
436 * 1 == positive
437 *
438 * Note: This utility is provided in order to facilitate the conversion
439 * of C comparison function return values into BinTree direction
440 * values: {LEFT, PARENT, EQUAL}. It is INCORPORATED into the
441 * AbNormal() conversion macro!
442 *
443 * ------------------------------------------------------------------------ **
444 */
447 /* ------------------------------------------------------------------------ **
448 * Initialize a tree node.
449 *
450 * Input: a pointer to a ubi_btNode structure to be initialized.
451 * Output: a pointer to the initialized ubi_btNode structure (ie. the
452 * same as the input pointer).
453 * ------------------------------------------------------------------------ **
454 */
457 ubi_btCompFunc CompFunc,
459 /* ------------------------------------------------------------------------ **
460 * Initialize the fields of a Tree Root header structure.
461 *
462 * Input: RootPtr - a pointer to an ubi_btRoot structure to be
463 * initialized.
464 * CompFunc - a pointer to a comparison function that will be used
465 * whenever nodes in the tree must be compared against
466 * outside values.
467 * Flags - One bytes worth of flags. Flags include
468 * ubi_trOVERWRITE and ubi_trDUPKEY. See the header
469 * file for more info.
470 *
471 * Output: a pointer to the initialized ubi_btRoot structure (ie. the
472 * same value as RootPtr).
473 *
474 * Note: The interface to this function has changed from that of
475 * previous versions. The <Flags> parameter replaces two
476 * boolean parameters that had the same basic effect.
477 * ------------------------------------------------------------------------ **
478 */
481 ubi_btNodePtr NewNode,
482 ubi_btItemPtr ItemPtr,
484 /* ------------------------------------------------------------------------ **
485 * This function uses a non-recursive algorithm to add a new element to the
486 * tree.
487 *
488 * Input: RootPtr - a pointer to the ubi_btRoot structure that indicates
489 * the root of the tree to which NewNode is to be added.
490 * NewNode - a pointer to an ubi_btNode structure that is NOT
491 * part of any tree.
492 * ItemPtr - A pointer to the sort key that is stored within
493 * *NewNode. ItemPtr MUST point to information stored
494 * in *NewNode or an EXACT DUPLICATE. The key data
495 * indicated by ItemPtr is used to place the new node
496 * into the tree.
497 * OldNode - a pointer to an ubi_btNodePtr. When searching
498 * the tree, a duplicate node may be found. If
499 * duplicates are allowed, then the new node will
500 * be simply placed into the tree. If duplicates
501 * are not allowed, however, then one of two things
502 * may happen.
503 * 1) if overwritting *is not* allowed, this
504 * function will return FALSE (indicating that
505 * the new node could not be inserted), and
506 * *OldNode will point to the duplicate that is
507 * still in the tree.
508 * 2) if overwritting *is* allowed, then this
509 * function will swap **OldNode for *NewNode.
510 * In this case, *OldNode will point to the node
511 * that was removed (thus allowing you to free
512 * the node).
513 * ** If you are using overwrite mode, ALWAYS **
514 * ** check the return value of this parameter! **
515 * Note: You may pass NULL in this parameter, the
516 * function knows how to cope. If you do this,
517 * however, there will be no way to return a
518 * pointer to an old (ie. replaced) node (which is
519 * a problem if you are using overwrite mode).
520 *
521 * Output: a boolean value indicating success or failure. The function
522 * will return FALSE if the node could not be added to the tree.
523 * Such failure will only occur if duplicates are not allowed,
524 * nodes cannot be overwritten, AND a duplicate key was found
525 * within the tree.
526 * ------------------------------------------------------------------------ **
527 */
530 ubi_btNodePtr DeadNode );
531 /* ------------------------------------------------------------------------ **
532 * This function removes the indicated node from the tree.
533 *
534 * Input: RootPtr - A pointer to the header of the tree that contains
535 * the node to be removed.
536 * DeadNode - A pointer to the node that will be removed.
537 *
538 * Output: This function returns a pointer to the node that was removed
539 * from the tree (ie. the same as DeadNode).
540 *
541 * Note: The node MUST be in the tree indicated by RootPtr. If not,
542 * strange and evil things will happen to your trees.
543 * ------------------------------------------------------------------------ **
544 */
547 ubi_btItemPtr FindMe,
548 ubi_trCompOps CompOp );
549 /* ------------------------------------------------------------------------ **
550 * The purpose of ubi_btLocate() is to find a node or set of nodes given
551 * a target value and a "comparison operator". The Locate() function is
552 * more flexible and (in the case of trees that may contain dupicate keys)
553 * more precise than the ubi_btFind() function. The latter is faster,
554 * but it only searches for exact matches and, if the tree contains
555 * duplicates, Find() may return a pointer to any one of the duplicate-
556 * keyed records.
557 *
558 * Input:
559 * RootPtr - A pointer to the header of the tree to be searched.
560 * FindMe - An ubi_btItemPtr that indicates the key for which to
561 * search.
562 * CompOp - One of the following:
563 * CompOp Return a pointer to the node with
564 * ------ ---------------------------------
565 * ubi_trLT - the last key value that is less
566 * than FindMe.
567 * ubi_trLE - the first key matching FindMe, or
568 * the last key that is less than
569 * FindMe.
570 * ubi_trEQ - the first key matching FindMe.
571 * ubi_trGE - the first key matching FindMe, or the
572 * first key greater than FindMe.
573 * ubi_trGT - the first key greater than FindMe.
574 * Output:
575 * A pointer to the node matching the criteria listed above under
576 * CompOp, or NULL if no node matched the criteria.
577 *
578 * Notes:
579 * In the case of trees with duplicate keys, Locate() will behave as
580 * follows:
581 *
582 * Find: 3 Find: 3
583 * Keys: 1 2 2 2 3 3 3 3 3 4 4 Keys: 1 1 2 2 2 4 4 5 5 5 6
584 * ^ ^ ^ ^ ^
585 * LT EQ GT LE GE
586 *
587 * That is, when returning a pointer to a node with a key that is LESS
588 * THAN the target key (FindMe), Locate() will return a pointer to the
589 * LAST matching node.
590 * When returning a pointer to a node with a key that is GREATER
591 * THAN the target key (FindMe), Locate() will return a pointer to the
592 * FIRST matching node.
593 *
594 * See Also: ubi_btFind(), ubi_btFirstOf(), ubi_btLastOf().
595 * ------------------------------------------------------------------------ **
596 */
599 ubi_btItemPtr FindMe );
600 /* ------------------------------------------------------------------------ **
601 * This function performs a non-recursive search of a tree for any node
602 * matching a specific key.
603 *
604 * Input:
605 * RootPtr - a pointer to the header of the tree to be searched.
606 * FindMe - a pointer to the key value for which to search.
607 *
608 * Output:
609 * A pointer to a node with a key that matches the key indicated by
610 * FindMe, or NULL if no such node was found.
611 *
612 * Note: In a tree that allows duplicates, the pointer returned *might
613 * not* point to the (sequentially) first occurance of the
614 * desired key. In such a tree, it may be more useful to use
615 * ubi_btLocate().
616 * ------------------------------------------------------------------------ **
617 */
620 /* ------------------------------------------------------------------------ **
621 * Given the node indicated by P, find the (sorted order) Next node in the
622 * tree.
623 * Input: P - a pointer to a node that exists in a binary tree.
624 * Output: A pointer to the "next" node in the tree, or NULL if P pointed
625 * to the "last" node in the tree or was NULL.
626 * ------------------------------------------------------------------------ **
627 */
630 /* ------------------------------------------------------------------------ **
631 * Given the node indicated by P, find the (sorted order) Previous node in
632 * the tree.
633 * Input: P - a pointer to a node that exists in a binary tree.
634 * Output: A pointer to the "previous" node in the tree, or NULL if P
635 * pointed to the "first" node in the tree or was NULL.
636 * ------------------------------------------------------------------------ **
637 */
640 /* ------------------------------------------------------------------------ **
641 * Given the node indicated by P, find the (sorted order) First node in the
642 * subtree of which *P is the root.
643 * Input: P - a pointer to a node that exists in a binary tree.
644 * Output: A pointer to the "first" node in a subtree that has *P as its
645 * root. This function will return NULL only if P is NULL.
646 * Note: In general, you will be passing in the value of the root field
647 * of an ubi_btRoot structure.
648 * ------------------------------------------------------------------------ **
649 */
652 /* ------------------------------------------------------------------------ **
653 * Given the node indicated by P, find the (sorted order) Last node in the
654 * subtree of which *P is the root.
655 * Input: P - a pointer to a node that exists in a binary tree.
656 * Output: A pointer to the "last" node in a subtree that has *P as its
657 * root. This function will return NULL only if P is NULL.
658 * Note: In general, you will be passing in the value of the root field
659 * of an ubi_btRoot structure.
660 * ------------------------------------------------------------------------ **
661 */
664 ubi_btItemPtr MatchMe,
665 ubi_btNodePtr p );
666 /* ------------------------------------------------------------------------ **
667 * Given a tree that a allows duplicate keys, and a pointer to a node in
668 * the tree, this function will return a pointer to the first (traversal
669 * order) node with the same key value.
670 *
671 * Input: RootPtr - A pointer to the root of the tree.
672 * MatchMe - A pointer to the key value. This should probably
673 * point to the key within node *p.
674 * p - A pointer to a node in the tree.
675 * Output: A pointer to the first node in the set of nodes with keys
676 * matching <FindMe>.
677 * Notes: Node *p MUST be in the set of nodes with keys matching
678 * <FindMe>. If not, this function will return NULL.
679 *
680 * 4.7: Bug found & fixed by Massimo Campostrini,
681 * Istituto Nazionale di Fisica Nucleare, Sezione di Pisa.
682 *
683 * ------------------------------------------------------------------------ **
684 */
687 ubi_btItemPtr MatchMe,
688 ubi_btNodePtr p );
689 /* ------------------------------------------------------------------------ **
690 * Given a tree that a allows duplicate keys, and a pointer to a node in
691 * the tree, this function will return a pointer to the last (traversal
692 * order) node with the same key value.
693 *
694 * Input: RootPtr - A pointer to the root of the tree.
695 * MatchMe - A pointer to the key value. This should probably
696 * point to the key within node *p.
697 * p - A pointer to a node in the tree.
698 * Output: A pointer to the last node in the set of nodes with keys
699 * matching <FindMe>.
700 * Notes: Node *p MUST be in the set of nodes with keys matching
701 * <FindMe>. If not, this function will return NULL.
702 *
703 * 4.7: Bug found & fixed by Massimo Campostrini,
704 * Istituto Nazionale di Fisica Nucleare, Sezione di Pisa.
705 *
706 * ------------------------------------------------------------------------ **
707 */
710 ubi_btActionRtn EachNode,
712 /* ------------------------------------------------------------------------ **
713 * Traverse a tree in sorted order (non-recursively). At each node, call
714 * (*EachNode)(), passing a pointer to the current node, and UserData as the
715 * second parameter.
716 *
717 * Input: RootPtr - a pointer to an ubi_btRoot structure that indicates
718 * the tree to be traversed.
719 * EachNode - a pointer to a function to be called at each node
720 * as the node is visited.
721 * UserData - a generic pointer that may point to anything that
722 * you choose.
723 *
724 * Output: A count of the number of nodes visited. This will be zero
725 * if the tree is empty.
726 *
727 * ------------------------------------------------------------------------ **
728 */
732 ubi_btKillNodeRtn FreeNode );
733 /* ------------------------------------------------------------------------ **
734 * Delete an entire tree (non-recursively) and reinitialize the ubi_btRoot
735 * structure. Return a count of the number of nodes deleted.
736 *
737 * Input: RootPtr - a pointer to an ubi_btRoot structure that indicates
738 * the root of the tree to delete.
739 * FreeNode - a function that will be called for each node in the
740 * tree to deallocate the memory used by the node.
741 *
742 * Output: The number of nodes removed from the tree.
743 * A value of 0 will be returned if:
744 * - The tree actually contains 0 entries.
745 * - the value of <RootPtr> is NULL, in which case the tree is
746 * assumed to be empty
747 * - the value of <FreeNode> is NULL, in which case entries
748 * cannot be removed, so 0 is returned. *Make sure that you
749 * provide a valid value for <FreeNode>*.
750 * In all other cases, you should get a positive value equal to
751 * the value of RootPtr->count upon entry.
752 *
753 * ------------------------------------------------------------------------ **
754 */
757 /* ------------------------------------------------------------------------ **
758 * Returns a pointer to a leaf node.
759 *
760 * Input: leader - Pointer to a node at which to start the descent.
761 *
762 * Output: A pointer to a leaf node, selected in a somewhat arbitrary
763 * manner but with an effort to dig deep.
764 *
765 * Notes: I wrote this function because I was using splay trees as a
766 * database cache. The cache had a maximum size on it, and I
767 * needed a way of choosing a node to sacrifice if the cache
768 * became full. In a splay tree, less recently accessed nodes
769 * tend toward the bottom of the tree, meaning that leaf nodes
770 * are good candidates for removal. (I really can't think of
771 * any other reason to use this function.)
772 * + In a simple binary tree, or in an AVL tree, the most recently
773 * added nodes tend to be nearer the bottom, making this a *bad*
774 * way to choose which node to remove from the cache.
775 * + Randomizing the traversal order is probably a good idea. You
776 * can improve the randomization of leaf node selection by passing
777 * in pointers to nodes other than the root node each time. A
778 * pointer to any node in the tree will do. Of course, if you
779 * pass a pointer to a leaf node you'll get the same thing back.
780 * + In an unbalanced splay tree, if you simply traverse downward
781 * until you hit a leaf node it is possible to accidentally
782 * stumble onto a short path. The result will be a leaf node
783 * that is actually very high in the tree--possibly a very
784 * recently accessed node. Not good. This function can follow
785 * multiple paths in an effort to find a leaf node deeper
786 * in the tree. Following a single path, of course, is the
787 * fastest way to find a leaf node. A complete traversal would
788 * be sure to find the deepest leaf but would be very costly in
789 * terms of time. This function uses a compromise that has
790 * worked well in testing.
791 *
792 * ------------------------------------------------------------------------ **
793 */
797 /* ------------------------------------------------------------------------ **
798 * Returns a set of strings that identify the module.
799 *
800 * Input: size - The number of elements in the array <list>.
801 * list - An array of pointers of type (char *). This array
802 * should, initially, be empty. This function will fill
803 * in the array with pointers to strings.
804 * Output: The number of elements of <list> that were used. If this value
805 * is less than <size>, the values of the remaining elements are
806 * not guaranteed.
807 *
808 * Notes: Please keep in mind that the pointers returned indicate strings
809 * stored in static memory. Don't free() them, don't write over
810 * them, etc. Just read them.
811 * ------------------------------------------------------------------------ **
812 */
814 /* -------------------------------------------------------------------------- **
815 * Masquarade...
816 *
817 * This set of defines allows you to write programs that will use any of the
818 * implemented binary tree modules (currently BinTree, AVLtree, and SplayTree).
819 * Instead of using ubi_bt..., use ubi_tr..., and select the tree type by
820 * including the appropriate module header.
821 */
823 #define ubi_trItemPtr ubi_btItemPtr
825 #define ubi_trNode ubi_btNode
826 #define ubi_trNodePtr ubi_btNodePtr
828 #define ubi_trRoot ubi_btRoot
829 #define ubi_trRootPtr ubi_btRootPtr
831 #define ubi_trCompFunc ubi_btCompFunc
832 #define ubi_trActionRtn ubi_btActionRtn
833 #define ubi_trKillNodeRtn ubi_btKillNodeRtn
835 #define ubi_trSgn( x ) ubi_btSgn( x )
837 #define ubi_trInitNode( Np ) ubi_btInitNode( (ubi_btNodePtr)(Np) )
839 #define ubi_trInitTree( Rp, Cf, Fl ) \
840 ubi_btInitTree( (ubi_btRootPtr)(Rp), (ubi_btCompFunc)(Cf), (Fl) )
842 #define ubi_trInsert( Rp, Nn, Ip, On ) \
843 ubi_btInsert( (ubi_btRootPtr)(Rp), (ubi_btNodePtr)(Nn), \
844 (ubi_btItemPtr)(Ip), (ubi_btNodePtr *)(On) )
846 #define ubi_trRemove( Rp, Dn ) \
847 ubi_btRemove( (ubi_btRootPtr)(Rp), (ubi_btNodePtr)(Dn) )
849 #define ubi_trLocate( Rp, Ip, Op ) \
850 ubi_btLocate( (ubi_btRootPtr)(Rp), \
851 (ubi_btItemPtr)(Ip), \
852 (ubi_trCompOps)(Op) )
854 #define ubi_trFind( Rp, Ip ) \
855 ubi_btFind( (ubi_btRootPtr)(Rp), (ubi_btItemPtr)(Ip) )
857 #define ubi_trNext( P ) ubi_btNext( (ubi_btNodePtr)(P) )
859 #define ubi_trPrev( P ) ubi_btPrev( (ubi_btNodePtr)(P) )
861 #define ubi_trFirst( P ) ubi_btFirst( (ubi_btNodePtr)(P) )
863 #define ubi_trLast( P ) ubi_btLast( (ubi_btNodePtr)(P) )
865 #define ubi_trFirstOf( Rp, Ip, P ) \
866 ubi_btFirstOf( (ubi_btRootPtr)(Rp), \
867 (ubi_btItemPtr)(Ip), \
868 (ubi_btNodePtr)(P) )
870 #define ubi_trLastOf( Rp, Ip, P ) \
871 ubi_btLastOf( (ubi_btRootPtr)(Rp), \
872 (ubi_btItemPtr)(Ip), \
873 (ubi_btNodePtr)(P) )
875 #define ubi_trTraverse( Rp, En, Ud ) \
876 ubi_btTraverse((ubi_btRootPtr)(Rp), (ubi_btActionRtn)(En), (void *)(Ud))
878 #define ubi_trKillTree( Rp, Fn ) \
879 ubi_btKillTree( (ubi_btRootPtr)(Rp), (ubi_btKillNodeRtn)(Fn) )
881 #define ubi_trLeafNode( Nd ) \
882 ubi_btLeafNode( (ubi_btNodePtr)(Nd) )
884 #define ubi_trModuleID( s, l ) ubi_btModuleID( s, l )
886 /* ========================================================================== */