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