source/ubiqx/ubi_BinTree.c

   1 /* ========================================================================== **
   2  *                              ubi_BinTree.c
   3  *
   4  *  Copyright (C) 1991-1998 by Christopher R. Hertel
   5  *
   6  *  Email:  crh@ubiqx.mn.org
   7  * -------------------------------------------------------------------------- **
   8  *
   9  *  This module implements a simple binary tree.
  10  *
  11  * -------------------------------------------------------------------------- **
  12  *
  13  *  This library is free software; you can redistribute it and/or
  14  *  modify it under the terms of the GNU Library General Public
  15  *  License as published by the Free Software Foundation; either
  16  *  version 2 of the License, or (at your option) any later version.
  17  *
  18  *  This library is distributed in the hope that it will be useful,
  19  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  21  *  Library General Public License for more details.
  22  *
  23  *  You should have received a copy of the GNU Library General Public
  24  *  License along with this library; if not, write to the Free
  25  *  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  26  *
  27  * -------------------------------------------------------------------------- **
  28  *
  29  * Log: ubi_BinTree.c,v
  30  * Revision 4.10  2000/06/06 20:38:40  crh
  31  * In the ReplaceNode() function, the old node header was being copied
  32  * to the new node header using a byte-by-byte copy.  This was causing
  33  * the 'insure' software testing program to report a memory leak.  The
  34  * fix was to do a simple assignement: *newnode = *oldnode;
  35  * This quieted the (errant) memory leak reports and is probably a bit
  36  * faster than the bytewise copy.
  37  *
  38  * Revision 4.9  2000/01/08 23:24:30  crh
  39  * Clarified a variety of if( pointer ) lines, replacing them with
  40  * if( NULL != pointer ).  This is more correct, and I have heard
  41  * of at least one (obscure?) system out there that uses a non-zero
  42  * value for NULL.
  43  * Also, speed improvement in Neighbor().  It was comparing pointers
  44  * when it could have compared two gender values.  The pointer
  45  * comparison was somewhat indirect (does pointer equal the pointer
  46  * of the parent of the node pointed to by pointer).  Urq.
  47  *
  48  * Revision 4.8  1999/09/22 03:40:30  crh
  49  * Modified ubi_btTraverse() and ubi_btKillTree().  They now return an
  50  * unsigned long indicating the number of nodes processed.  The change
  51  * is subtle.  An empty tree formerly returned False, and now returns
  52  * zero.
  53  *
  54  * Revision 4.7  1998/10/21 06:14:42  crh
  55  * Fixed bugs in FirstOf() and LastOf() reported by Massimo Campostrini.
  56  * See function comments.
  57  *
  58  * Revision 4.6  1998/07/25 17:02:10  crh
  59  * Added the ubi_trNewTree() macro.
  60  *
  61  * Revision 4.5  1998/06/04 21:29:27  crh
  62  * Upper-cased defined constants (eg UBI_BINTREE_H) in some header files.
  63  * This is more "standard", and is what people expect.  Weird, eh?
  64  *
  65  * Revision 4.4  1998/06/03 17:42:46  crh
  66  * Further fiddling with sys_include.h.  It's now in ubi_BinTree.h which is
  67  * included by all of the binary tree files.
  68  *
  69  * Reminder: Some of the ubi_tr* macros in ubi_BinTree.h are redefined in
  70  *           ubi_AVLtree.h and ubi_SplayTree.h.  This allows easy swapping
  71  *           of tree types by simply changing a header.  Unfortunately, the
  72  *           macro redefinitions in ubi_AVLtree.h and ubi_SplayTree.h will
  73  *           conflict if used together.  You must either choose a single tree
  74  *           type, or use the underlying function calls directly.  Compare
  75  *           the two header files for more information.
  76  *
  77  * Revision 4.3  1998/06/02 01:28:43  crh
  78  * Changed ubi_null.h to sys_include.h to make it more generic.
  79  *
  80  * Revision 4.2  1998/05/20 04:32:36  crh
  81  * The C file now includes ubi_null.h.  See ubi_null.h for more info.
  82  * Also, the balance and gender fields of the node were declared as
  83  * signed char.  As I understand it, at least one SunOS or Solaris
  84  * compiler doesn't like "signed char".  The declarations were
  85  * wrong anyway, so I changed them to simple "char".
  86  *
  87  * Revision 4.1  1998/03/31 06:11:57  crh
  88  * Thomas Aglassinger sent E'mail pointing out errors in the
  89  * dereferencing of function pointers, and a missing typecast.
  90  * Thanks, Thomas!
  91  *
  92  * Revision 4.0  1998/03/10 03:19:22  crh
  93  * Added the AVL field 'balance' to the ubi_btNode structure.  This means
  94  * that all BinTree modules now use the same basic node structure, which
  95  * greatly simplifies the AVL module.
  96  * Decided that this was a big enough change to justify a new major revision
  97  * number.  3.0 was an error, so we're at 4.0.
  98  *
  99  * Revision 2.6  1998/01/24 06:27:46  crh
 100  * Added ubi_trCount() macro.
 101  *
 102  * Revision 2.5  1997/12/23 03:56:29  crh
 103  * In this version, all constants & macros defined in the header file have
 104  * the ubi_tr prefix.  Also cleaned up anything that gcc complained about
 105  * when run with '-pedantic -fsyntax-only -Wall'.
 106  *
 107  * Revision 2.4  1997/07/26 04:11:10  crh
 108  * + Just to be annoying I changed ubi_TRUE and ubi_FALSE to ubi_trTRUE
 109  *   and ubi_trFALSE.
 110  * + There is now a type ubi_trBool to go with ubi_trTRUE and ubi_trFALSE.
 111  * + There used to be something called "ubi_TypeDefs.h".  I got rid of it.
 112  * + Added function ubi_btLeafNode().
 113  *
 114  * Revision 2.3  1997/06/03 05:16:17  crh
 115  * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid conflicts.
 116  * Also changed the interface to function InitTree().  See the comments
 117  * for this function for more information.
 118  *
 119  * Revision 2.2  1995/10/03 22:00:07  CRH
 120  * Ubisized!
 121  *
 122  * Revision 2.1  95/03/09  23:37:10  CRH
 123  * Added the ModuleID static string and function.  These modules are now
 124  * self-identifying.
 125  *
 126  * Revision 2.0  95/02/27  22:00:17  CRH
 127  * Revision 2.0 of this program includes the following changes:
 128  *
 129  *     1)  A fix to a major typo in the RepaceNode() function.
 130  *     2)  The addition of the static function Border().
 131  *     3)  The addition of the public functions FirstOf() and LastOf(), which
 132  *         use Border(). These functions are used with trees that allow
 133  *         duplicate keys.
 134  *     4)  A complete rewrite of the Locate() function.  Locate() now accepts
 135  *         a "comparison" operator.
 136  *     5)  Overall enhancements to both code and comments.
 137  *
 138  * I decided to give this a new major rev number because the interface has
 139  * changed.  In particular, there are two new functions, and changes to the
 140  * Locate() function.
 141  *
 142  * Revision 1.0  93/10/15  22:44:59  CRH
 143  * With this revision, I have added a set of #define's that provide a single,
 144  * standard API to all existing tree modules.  Until now, each of the three
 145  * existing modules had a different function and typedef prefix, as follows:
 146  *
 147  *       Module        Prefix
 148  *     ubi_BinTree     ubi_bt
 149  *     ubi_AVLtree     ubi_avl
 150  *     ubi_SplayTree   ubi_spt
 151  *
 152  * To further complicate matters, only those portions of the base module
 153  * (ubi_BinTree) that were superceeded in the new module had the new names.
 154  * For example, if you were using ubi_SplayTree, the locate function was
 155  * called "ubi_sptLocate", but the next and previous functions remained
 156  * "ubi_btNext" and "ubi_btPrev".
 157  *
 158  * This was not too terrible if you were familiar with the modules and knew
 159  * exactly which tree model you wanted to use.  If you wanted to be able to
 160  * change modules (for speed comparisons, etc), things could get messy very
 161  * quickly.
 162  *
 163  * So, I have added a set of defined names that get redefined in any of the
 164  * descendant modules.  To use this standardized interface in your code,
 165  * simply replace all occurances of "ubi_bt", "ubi_avl", and "ubi_spt" with
 166  * "ubi_tr".  The "ubi_tr" names will resolve to the correct function or
 167  * datatype names for the module that you are using.  Just remember to
 168  * include the header for that module in your program file.  Because these
 169  * names are handled by the preprocessor, there is no added run-time
 170  * overhead.
 171  *
 172  * Note that the original names do still exist, and can be used if you wish
 173  * to write code directly to a specific module.  This should probably only be
 174  * done if you are planning to implement a new descendant type, such as
 175  * red/black trees.  CRH
 176  *
 177  *  V0.0 - June, 1991   -  Written by Christopher R. Hertel (CRH).
 178  *
 179  * ========================================================================== **
 180  */
 181
 182 #include "ubi_BinTree.h"  /* Header for this module.   */
 183
 184 /* ========================================================================== **
 185  * Static data.
 186  */
 187
 188 static char ModuleID[] = "ubi_BinTree\n\
 189 \tRevision: 4.10 \n\
 190 \tDate: 2000/06/06 20:38:40 \n\
 191 \tAuthor: crh \n";
 192
 193 /* ========================================================================== **
 194  * Internal (private) functions.
 195  */
 196
 197 static ubi_btNodePtr qFind( ubi_btCompFunc cmp,
 198                             ubi_btItemPtr  FindMe,
 199                    register ubi_btNodePtr  p )
 200   /* ------------------------------------------------------------------------ **
 201    * This function performs a non-recursive search of a tree for a node
 202    * matching a specific key.  It is called "qFind()" because it is
 203    * faster that TreeFind (below).
 204    *
 205    *  Input:
 206    *     cmp      -  a pointer to the tree's comparison function.
 207    *     FindMe   -  a pointer to the key value for which to search.
 208    *     p        -  a pointer to the starting point of the search.  <p>
 209    *                 is considered to be the root of a subtree, and only
 210    *                 the subtree will be searched.
 211    *
 212    *  Output:
 213    *     A pointer to a node with a key that matches the key indicated by
 214    *     FindMe, or NULL if no such node was found.
 215    *
 216    *  Note:   In a tree that allows duplicates, the pointer returned *might
 217    *          not* point to the (sequentially) first occurance of the
 218    *          desired key.
 219    * ------------------------------------------------------------------------ **
 220    */
 221   {
 222   int tmp;
 223
 224   while( (NULL != p)
 225       && ((tmp = ubi_trAbNormal( (*cmp)(FindMe, p) )) != ubi_trEQUAL) )
 226     p = p->Link[tmp];
 227
 228   return( p );
 229   } /* qFind */
 230
 231 static ubi_btNodePtr TreeFind( ubi_btItemPtr  findme,
 232                                ubi_btNodePtr  p,
 233                                ubi_btNodePtr *parentp,
 234                                char          *gender,
 235                                ubi_btCompFunc CmpFunc )
 236   /* ------------------------------------------------------------------------ **
 237    * TreeFind() searches a tree for a given value (findme).  It will return a
 238    * pointer to the target node, if found, or NULL if the target node was not
 239    * found.
 240    *
 241    * TreeFind() also returns, via parameters, a pointer to the parent of the
 242    * target node, and a LEFT or RIGHT value indicating which child of the
 243    * parent is the target node.  *If the target is not found*, then these
 244    * values indicate the place at which the target *should be found*.  This
 245    * is useful when inserting a new node into a tree or searching for nodes
 246    * "near" the target node.
 247    *
 248    * The parameters are:
 249    *
 250    *  findme   -  is a pointer to the key information to be searched for.
 251    *  p        -  points to the root of the tree to be searched.
 252    *  parentp  -  will return a pointer to a pointer to the !parent! of the
 253    *              target node, which can be especially usefull if the target
 254    *              was not found.
 255    *  gender   -  returns LEFT or RIGHT to indicate which child of *parentp
 256    *              was last searched.
 257    *  CmpFunc  -  points to the comparison function.
 258    *
 259    * This function is called by ubi_btLocate() and ubi_btInsert().
 260    * ------------------------------------------------------------------------ **
 261    */
 262   {
 263   register ubi_btNodePtr tmp_p      = p;
 264   ubi_btNodePtr          tmp_pp     = NULL;
 265   char                   tmp_gender = ubi_trEQUAL;
 266   int                    tmp_cmp;
 267
 268   while( (NULL != tmp_p)
 269      && (ubi_trEQUAL != (tmp_cmp = ubi_trAbNormal((*CmpFunc)(findme, tmp_p)))) )
 270     {
 271     tmp_pp     = tmp_p;                 /* Keep track of previous node. */
 272     tmp_gender = (char)tmp_cmp;         /* Keep track of sex of child.  */
 273     tmp_p      = tmp_p->Link[tmp_cmp];  /* Go to child. */
 274     }
 275   *parentp = tmp_pp;                /* Return results. */
 276   *gender  = tmp_gender;
 277   return( tmp_p );
 278   } /* TreeFind */
 279
 280 static void ReplaceNode( ubi_btNodePtr *parent,
 281                          ubi_btNodePtr  oldnode,
 282                          ubi_btNodePtr  newnode )
 283   /* ------------------------------------------------------------------------ **
 284    * Remove node oldnode from the tree, replacing it with node newnode.
 285    *
 286    * Input:
 287    *  parent   - A pointer to he parent pointer of the node to be
 288    *             replaced.  <parent> may point to the Link[] field of
 289    *             a parent node, or it may indicate the root pointer at
 290    *             the top of the tree.
 291    *  oldnode  - A pointer to the node that is to be replaced.
 292    *  newnode  - A pointer to the node that is to be installed in the
 293    *             place of <*oldnode>.
 294    *
 295    * Notes:    Don't forget to free oldnode.
 296    *           Also, this function used to have a really nasty typo
 297    *           bug.  "oldnode" and "newnode" were swapped in the line
 298    *           that now reads:
 299    *     ((unsigned char *)newnode)[i] = ((unsigned char *)oldnode)[i];
 300    *           Bleah!
 301    * ------------------------------------------------------------------------ **
 302    */
 303   {
 304   *newnode = *oldnode;  /* Copy node internals to new node. */
 305
 306   (*parent) = newnode;  /* Old node's parent points to new child. */
 307   /* Now tell the children about their new step-parent. */
 308   if( oldnode->Link[ubi_trLEFT] )
 309     (oldnode->Link[ubi_trLEFT])->Link[ubi_trPARENT] = newnode;
 310   if( oldnode->Link[ubi_trRIGHT] )
 311     (oldnode->Link[ubi_trRIGHT])->Link[ubi_trPARENT] = newnode;
 312   } /* ReplaceNode */
 313
 314 static void SwapNodes( ubi_btRootPtr RootPtr,
 315                        ubi_btNodePtr Node1,
 316                        ubi_btNodePtr Node2 )
 317   /* ------------------------------------------------------------------------ **
 318    * This function swaps two nodes in the tree.  Node1 will take the place of
 319    * Node2, and Node2 will fill in the space left vacant by Node 1.
 320    *
 321    * Input:
 322    *  RootPtr  - pointer to the tree header structure for this tree.
 323    *  Node1    - \
 324    *              > These are the two nodes which are to be swapped.
 325    *  Node2    - /
 326    *
 327    * Notes:
 328    *  This function does a three step swap, using a dummy node as a place
 329    *  holder.  This function is used by ubi_btRemove().
 330    * ------------------------------------------------------------------------ **
 331    */
 332   {
 333   ubi_btNodePtr *Parent;
 334   ubi_btNode     dummy;
 335   ubi_btNodePtr  dummy_p = &dummy;
 336
 337   /* Replace Node 1 with the dummy, thus removing Node1 from the tree. */
 338   if( NULL != Node1->Link[ubi_trPARENT] )
 339     Parent = &((Node1->Link[ubi_trPARENT])->Link[(int)(Node1->gender)]);
 340   else
 341     Parent = &(RootPtr->root);
 342   ReplaceNode( Parent, Node1, dummy_p );
 343
 344   /* Swap Node 1 with Node 2, placing Node 1 back into the tree. */
 345   if( NULL != Node2->Link[ubi_trPARENT] )
 346     Parent = &((Node2->Link[ubi_trPARENT])->Link[(int)(Node2->gender)]);
 347   else
 348     Parent = &(RootPtr->root);
 349   ReplaceNode( Parent, Node2, Node1 );
 350
 351   /* Swap Node 2 and the dummy, thus placing Node 2 back into the tree. */
 352   if( NULL != dummy_p->Link[ubi_trPARENT] )
 353     Parent = &((dummy_p->Link[ubi_trPARENT])->Link[(int)(dummy_p->gender)]);
 354   else
 355     Parent = &(RootPtr->root);
 356   ReplaceNode( Parent, dummy_p, Node2 );
 357   } /* SwapNodes */
 358
 359 /* -------------------------------------------------------------------------- **
 360  * These routines allow you to walk through the tree, forwards or backwards.
 361  */
 362
 363 static ubi_btNodePtr SubSlide( register ubi_btNodePtr P,
 364                                register int           whichway )
 365   /* ------------------------------------------------------------------------ **
 366    * Slide down the side of a subtree.
 367    *
 368    * Given a starting node, this function returns a pointer to the LEFT-, or
 369    * RIGHT-most descendent, *or* (if whichway is PARENT) to the tree root.
 370    *
 371    *  Input:  P         - a pointer to a starting place.
 372    *          whichway  - the direction (LEFT, RIGHT, or PARENT) in which to
 373    *                      travel.
 374    *  Output: A pointer to a node that is either the root, or has no
 375    *          whichway-th child but is within the subtree of P.  Note that
 376    *          the return value may be the same as P.  The return value *will
 377    *          be* NULL if P is NULL.
 378    * ------------------------------------------------------------------------ **
 379    */
 380   {
 381
 382   if( NULL != P )
 383     while( NULL != P->Link[ whichway ] )
 384       P = P->Link[ whichway ];
 385   return( P );
 386   } /* SubSlide */
 387
 388 static ubi_btNodePtr Neighbor( register ubi_btNodePtr P,
 389                                register int           whichway )
 390   /* ------------------------------------------------------------------------ **
 391    * Given starting point p, return the (key order) next or preceeding node
 392    * in the tree.
 393    *
 394    *  Input:  P         - Pointer to our starting place node.
 395    *          whichway  - the direction in which to travel to find the
 396    *                      neighbor, i.e., the RIGHT neighbor or the LEFT
 397    *                      neighbor.
 398    *
 399    *  Output: A pointer to the neighboring node, or NULL if P was NULL.
 400    *
 401    *  Notes:  If whichway is PARENT, the results are unpredictable.
 402    * ------------------------------------------------------------------------ **
 403    */
 404   {
 405   if( P )
 406     {
 407     if( NULL != P->Link[ whichway ] )
 408       return( SubSlide( P->Link[ whichway ], (char)ubi_trRevWay(whichway) ) );
 409     else
 410       while( NULL != P->Link[ ubi_trPARENT ] )
 411         {
 412         if( whichway == P->gender )
 413           P = P->Link[ ubi_trPARENT ];
 414         else
 415           return( P->Link[ ubi_trPARENT ] );
 416         }
 417     }
 418   return( NULL );
 419   } /* Neighbor */
 420
 421 static ubi_btNodePtr Border( ubi_btRootPtr RootPtr,
 422                              ubi_btItemPtr FindMe,
 423                              ubi_btNodePtr p,
 424                              int           whichway )
 425   /* ------------------------------------------------------------------------ **
 426    * Given starting point p, which has a key value equal to *FindMe, locate
 427    * the first (index order) node with the same key value.
 428    *
 429    * This function is useful in trees that have can have duplicate keys.
 430    * For example, consider the following tree:
 431    *     Tree                                                      Traversal
 432    *       2    If <p> points to the root and <whichway> is RIGHT,     3
 433    *      / \    then the return value will be a pointer to the       / \
 434    *     2   2    RIGHT child of the root node.  The tree on         2   5
 435    *    /   / \    the right shows the order of traversal.          /   / \
 436    *   1   2   3                                                   1   4   6
 437    *
 438    *  Input:  RootPtr   - Pointer to the tree root structure.
 439    *          FindMe    - Key value for comparisons.
 440    *          p         - Pointer to the starting-point node.
 441    *          whichway  - the direction in which to travel to find the
 442    *                      neighbor, i.e., the RIGHT neighbor or the LEFT
 443    *                      neighbor.
 444    *
 445    *  Output: A pointer to the first (index, or "traversal", order) node with
 446    *          a Key value that matches *FindMe.
 447    *
 448    *  Notes:  If whichway is PARENT, or if the tree does not allow duplicate
 449    *          keys, this function will return <p>.
 450    * ------------------------------------------------------------------------ **
 451    */
 452   {
 453   register ubi_btNodePtr q;
 454
 455   /* Exit if there's nothing that can be done. */
 456   if( !ubi_trDups_OK( RootPtr ) || (ubi_trPARENT == whichway) )
 457     return( p );
 458
 459   /* First, if needed, move up the tree.  We need to get to the root of the
 460    * subtree that contains all of the matching nodes.
 461    */
 462   q = p->Link[ubi_trPARENT];
 463   while( (NULL != q)
 464       && (ubi_trEQUAL == ubi_trAbNormal( (*(RootPtr->cmp))(FindMe, q) )) )
 465     {
 466     p = q;
 467     q = p->Link[ubi_trPARENT];
 468     }
 469
 470   /* Next, move back down in the "whichway" direction. */
 471   q = p->Link[whichway];
 472   while( NULL != q )
 473     {
 474     q = qFind( RootPtr->cmp, FindMe, q );
 475     if( q )
 476       {
 477       p = q;
 478       q = p->Link[whichway];
 479       }
 480     }
 481   return( p );
 482   } /* Border */
 483
 484
 485 /* ========================================================================== **
 486  * Exported utilities.
 487  */
 488
 489 long ubi_btSgn( register long x )
 490   /* ------------------------------------------------------------------------ **
 491    * Return the sign of x; {negative,zero,positive} ==> {-1, 0, 1}.
 492    *
 493    *  Input:  x - a signed long integer value.
 494    *
 495    *  Output: the "sign" of x, represented as follows:
 496    *            -1 == negative
 497    *             0 == zero (no sign)
 498    *             1 == positive
 499    *
 500    * Note: This utility is provided in order to facilitate the conversion
 501    *       of C comparison function return values into BinTree direction
 502    *       values: {LEFT, PARENT, EQUAL}.  It is INCORPORATED into the
 503    *       ubi_trAbNormal() conversion macro!
 504    *
 505    * ------------------------------------------------------------------------ **
 506    */
 507   {
 508   return( (x)?((x>0)?(1):(-1)):(0) );
 509   } /* ubi_btSgn */
 510
 511 ubi_btNodePtr ubi_btInitNode( ubi_btNodePtr NodePtr )
 512   /* ------------------------------------------------------------------------ **
 513    * Initialize a tree node.
 514    *
 515    *  Input:  a pointer to a ubi_btNode structure to be initialized.
 516    *  Output: a pointer to the initialized ubi_btNode structure (ie. the
 517    *          same as the input pointer).
 518    * ------------------------------------------------------------------------ **
 519    */
 520   {
 521   NodePtr->Link[ ubi_trLEFT ]   = NULL;
 522   NodePtr->Link[ ubi_trPARENT ] = NULL;
 523   NodePtr->Link[ ubi_trRIGHT ]  = NULL;
 524   NodePtr->gender               = ubi_trEQUAL;
 525   NodePtr->balance              = ubi_trEQUAL;
 526   return( NodePtr );
 527   } /* ubi_btInitNode */
 528
 529 ubi_btRootPtr ubi_btInitTree( ubi_btRootPtr   RootPtr,
 530                               ubi_btCompFunc  CompFunc,
 531                               char            Flags )
 532   /* ------------------------------------------------------------------------ **
 533    * Initialize the fields of a Tree Root header structure.
 534    *
 535    *  Input:   RootPtr   - a pointer to an ubi_btRoot structure to be
 536    *                       initialized.
 537    *           CompFunc  - a pointer to a comparison function that will be used
 538    *                       whenever nodes in the tree must be compared against
 539    *                       outside values.
 540    *           Flags     - One bytes worth of flags.  Flags include
 541    *                       ubi_trOVERWRITE and ubi_trDUPKEY.  See the header
 542    *                       file for more info.
 543    *
 544    *  Output:  a pointer to the initialized ubi_btRoot structure (ie. the
 545    *           same value as RootPtr).
 546    *
 547    *  Note:    The interface to this function has changed from that of
 548    *           previous versions.  The <Flags> parameter replaces two
 549    *           boolean parameters that had the same basic effect.
 550    *
 551    * ------------------------------------------------------------------------ **
 552    */
 553   {
 554   if( RootPtr )
 555     {
 556     RootPtr->root   = NULL;
 557     RootPtr->count  = 0L;
 558     RootPtr->cmp    = CompFunc;
 559     RootPtr->flags  = (Flags & ubi_trDUPKEY) ? ubi_trDUPKEY : Flags;
 560     }                 /* There are only two supported flags, and they are
 561                        * mutually exclusive.  ubi_trDUPKEY takes precedence
 562                        * over ubi_trOVERWRITE.
 563                        */
 564   return( RootPtr );
 565   } /* ubi_btInitTree */
 566
 567 ubi_trBool ubi_btInsert( ubi_btRootPtr  RootPtr,
 568                          ubi_btNodePtr  NewNode,
 569                          ubi_btItemPtr  ItemPtr,
 570                          ubi_btNodePtr *OldNode )
 571   /* ------------------------------------------------------------------------ **
 572    * This function uses a non-recursive algorithm to add a new element to the
 573    * tree.
 574    *
 575    *  Input:   RootPtr  -  a pointer to the ubi_btRoot structure that indicates
 576    *                       the root of the tree to which NewNode is to be added.
 577    *           NewNode  -  a pointer to an ubi_btNode structure that is NOT
 578    *                       part of any tree.
 579    *           ItemPtr  -  A pointer to the sort key that is stored within
 580    *                       *NewNode.  ItemPtr MUST point to information stored
 581    *                       in *NewNode or an EXACT DUPLICATE.  The key data
 582    *                       indicated by ItemPtr is used to place the new node
 583    *                       into the tree.
 584    *           OldNode  -  a pointer to an ubi_btNodePtr.  When searching
 585    *                       the tree, a duplicate node may be found.  If
 586    *                       duplicates are allowed, then the new node will
 587    *                       be simply placed into the tree.  If duplicates
 588    *                       are not allowed, however, then one of two things
 589    *                       may happen.
 590    *                       1) if overwritting *is not* allowed, this
 591    *                          function will return FALSE (indicating that
 592    *                          the new node could not be inserted), and
 593    *                          *OldNode will point to the duplicate that is
 594    *                          still in the tree.
 595    *                       2) if overwritting *is* allowed, then this
 596    *                          function will swap **OldNode for *NewNode.
 597    *                          In this case, *OldNode will point to the node
 598    *                          that was removed (thus allowing you to free
 599    *                          the node).
 600    *                          **  If you are using overwrite mode, ALWAYS  **
 601    *                          ** check the return value of this parameter! **
 602    *                 Note: You may pass NULL in this parameter, the
 603    *                       function knows how to cope.  If you do this,
 604    *                       however, there will be no way to return a
 605    *                       pointer to an old (ie. replaced) node (which is
 606    *                       a problem if you are using overwrite mode).
 607    *
 608    *  Output:  a boolean value indicating success or failure.  The function
 609    *           will return FALSE if the node could not be added to the tree.
 610    *           Such failure will only occur if duplicates are not allowed,
 611    *           nodes cannot be overwritten, AND a duplicate key was found
 612    *           within the tree.
 613    * ------------------------------------------------------------------------ **
 614    */
 615   {
 616   ubi_btNodePtr OtherP,
 617                 parent = NULL;
 618   char          tmp;
 619
 620   if( NULL == OldNode ) /* If they didn't give us a pointer, supply our own.  */
 621     OldNode = &OtherP;
 622
 623   (void)ubi_btInitNode( NewNode );     /* Init the new node's BinTree fields. */
 624
 625   /* Find a place for the new node. */
 626   *OldNode = TreeFind(ItemPtr, (RootPtr->root), &parent, &tmp, (RootPtr->cmp));
 627
 628   /* Now add the node to the tree... */
 629   if( NULL == (*OldNode) )  /* The easy one: we have a space for a new node!  */
 630     {
 631     if( NULL == parent )
 632       RootPtr->root = NewNode;
 633     else
 634       {
 635       parent->Link[(int)tmp]      = NewNode;
 636       NewNode->Link[ubi_trPARENT] = parent;
 637       NewNode->gender             = tmp;
 638       }
 639     (RootPtr->count)++;
 640     return( ubi_trTRUE );
 641     }
 642
 643   /* If we reach this point, we know that a duplicate node exists.  This
 644    * section adds the node to the tree if duplicate keys are allowed.
 645    */
 646   if( ubi_trDups_OK(RootPtr) )    /* Key exists, add duplicate */
 647     {
 648     ubi_btNodePtr q;
 649
 650     tmp = ubi_trRIGHT;
 651     q = (*OldNode);
 652     *OldNode = NULL;
 653     while( NULL != q )
 654       {
 655       parent = q;
 656       if( tmp == ubi_trEQUAL )
 657         tmp = ubi_trRIGHT;
 658       q = q->Link[(int)tmp];
 659       if ( q )
 660         tmp = ubi_trAbNormal( (*(RootPtr->cmp))(ItemPtr, q) );
 661       }
 662     parent->Link[(int)tmp]       = NewNode;
 663     NewNode->Link[ubi_trPARENT]  = parent;
 664     NewNode->gender              = tmp;
 665     (RootPtr->count)++;
 666     return( ubi_trTRUE );
 667     }
 668
 669   /* If we get to *this* point, we know that we are not allowed to have
 670    * duplicate nodes, but our node keys match, so... may we replace the
 671    * old one?
 672    */
 673   if( ubi_trOvwt_OK(RootPtr) )    /* Key exists, we replace */
 674     {
 675     if( NULL == parent )
 676       ReplaceNode( &(RootPtr->root), *OldNode, NewNode );
 677     else
 678       ReplaceNode( &(parent->Link[(int)((*OldNode)->gender)]),
 679                    *OldNode, NewNode );
 680     return( ubi_trTRUE );
 681     }
 682
 683   return( ubi_trFALSE );      /* Failure: could not replace an existing node. */
 684   } /* ubi_btInsert */
 685
 686 ubi_btNodePtr ubi_btRemove( ubi_btRootPtr RootPtr,
 687                             ubi_btNodePtr DeadNode )
 688   /* ------------------------------------------------------------------------ **
 689    * This function removes the indicated node from the tree.
 690    *
 691    *  Input:   RootPtr  -  A pointer to the header of the tree that contains
 692    *                       the node to be removed.
 693    *           DeadNode -  A pointer to the node that will be removed.
 694    *
 695    *  Output:  This function returns a pointer to the node that was removed
 696    *           from the tree (ie. the same as DeadNode).
 697    *
 698    *  Note:    The node MUST be in the tree indicated by RootPtr.  If not,
 699    *           strange and evil things will happen to your trees.
 700    * ------------------------------------------------------------------------ **
 701    */
 702   {
 703   ubi_btNodePtr p,
 704                *parentp;
 705   int           tmp;
 706
 707   /* if the node has both left and right subtrees, then we have to swap
 708    * it with another node.  The other node we choose will be the Prev()ious
 709    * node, which is garunteed to have no RIGHT child.
 710    */
 711   if( (NULL != DeadNode->Link[ubi_trLEFT])
 712    && (NULL != DeadNode->Link[ubi_trRIGHT]) )
 713     SwapNodes( RootPtr, DeadNode, ubi_btPrev( DeadNode ) );
 714
 715   /* The parent of the node to be deleted may be another node, or it may be
 716    * the root of the tree.  Since we're not sure, it's best just to have
 717    * a pointer to the parent pointer, whatever it is.
 718    */
 719   if( NULL == DeadNode->Link[ubi_trPARENT] )
 720     parentp = &( RootPtr->root );
 721   else
 722     parentp = &((DeadNode->Link[ubi_trPARENT])->Link[(int)(DeadNode->gender)]);
 723
 724   /* Now link the parent to the only grand-child and patch up the gender. */
 725   tmp = ((DeadNode->Link[ubi_trLEFT])?ubi_trLEFT:ubi_trRIGHT);
 726
 727   p = (DeadNode->Link[tmp]);
 728   if( NULL != p )
 729     {
 730     p->Link[ubi_trPARENT] = DeadNode->Link[ubi_trPARENT];
 731     p->gender       = DeadNode->gender;
 732     }
 733   (*parentp) = p;
 734
 735   /* Finished, reduce the node count and return. */
 736   (RootPtr->count)--;
 737   return( DeadNode );
 738   } /* ubi_btRemove */
 739
 740 ubi_btNodePtr ubi_btLocate( ubi_btRootPtr RootPtr,
 741                             ubi_btItemPtr FindMe,
 742                             ubi_trCompOps CompOp )
 743   /* ------------------------------------------------------------------------ **
 744    * The purpose of ubi_btLocate() is to find a node or set of nodes given
 745    * a target value and a "comparison operator".  The Locate() function is
 746    * more flexible and (in the case of trees that may contain dupicate keys)
 747    * more precise than the ubi_btFind() function.  The latter is faster,
 748    * but it only searches for exact matches and, if the tree contains
 749    * duplicates, Find() may return a pointer to any one of the duplicate-
 750    * keyed records.
 751    *
 752    *  Input:
 753    *     RootPtr  -  A pointer to the header of the tree to be searched.
 754    *     FindMe   -  An ubi_btItemPtr that indicates the key for which to
 755    *                 search.
 756    *     CompOp   -  One of the following:
 757    *                    CompOp     Return a pointer to the node with
 758    *                    ------     ---------------------------------
 759    *                   ubi_trLT - the last key value that is less
 760    *                              than FindMe.
 761    *                   ubi_trLE - the first key matching FindMe, or
 762    *                              the last key that is less than
 763    *                              FindMe.
 764    *                   ubi_trEQ - the first key matching FindMe.
 765    *                   ubi_trGE - the first key matching FindMe, or the
 766    *                              first key greater than FindMe.
 767    *                   ubi_trGT - the first key greater than FindMe.
 768    *  Output:
 769    *     A pointer to the node matching the criteria listed above under
 770    *     CompOp, or NULL if no node matched the criteria.
 771    *
 772    *  Notes:
 773    *     In the case of trees with duplicate keys, Locate() will behave as
 774    *     follows:
 775    *
 776    *     Find:  3                       Find: 3
 777    *     Keys:  1 2 2 2 3 3 3 3 3 4 4   Keys: 1 1 2 2 2 4 4 5 5 5 6
 778    *                  ^ ^         ^                   ^ ^
 779    *                 LT EQ        GT                 LE GE
 780    *
 781    *     That is, when returning a pointer to a node with a key that is LESS
 782    *     THAN the target key (FindMe), Locate() will return a pointer to the
 783    *     LAST matching node.
 784    *     When returning a pointer to a node with a key that is GREATER
 785    *     THAN the target key (FindMe), Locate() will return a pointer to the
 786    *     FIRST matching node.
 787    *
 788    *  See Also: ubi_btFind(), ubi_btFirstOf(), ubi_btLastOf().
 789    * ------------------------------------------------------------------------ **
 790    */
 791   {
 792   register ubi_btNodePtr p;
 793   ubi_btNodePtr   parent;
 794   char            whichkid;
 795
 796   /* Start by searching for a matching node. */
 797   p = TreeFind( FindMe,
 798                 RootPtr->root,
 799                 &parent,
 800                 &whichkid,
 801                 RootPtr->cmp );
 802
 803   if( NULL != p )    /* If we have found a match, we can resolve as follows:  */
 804     {
 805     switch( CompOp )
 806       {
 807       case ubi_trLT:            /* It's just a jump to the left...  */
 808         p = Border( RootPtr, FindMe, p, ubi_trLEFT );
 809         return( Neighbor( p, ubi_trLEFT ) );
 810       case ubi_trGT:            /* ...and then a jump to the right. */
 811         p = Border( RootPtr, FindMe, p, ubi_trRIGHT );
 812         return( Neighbor( p, ubi_trRIGHT ) );
 813       default:
 814         p = Border( RootPtr, FindMe, p, ubi_trLEFT );
 815         return( p );
 816       }
 817     }
 818
 819   /* Else, no match. */
 820   if( ubi_trEQ == CompOp )    /* If we were looking for an exact match... */
 821     return( NULL );           /* ...forget it.                            */
 822
 823   /* We can still return a valid result for GT, GE, LE, and LT.
 824    * <parent> points to a node with a value that is either just before or
 825    * just after the target value.
 826    * Remaining possibilities are LT and GT (including LE & GE).
 827    */
 828   if( (ubi_trLT == CompOp) || (ubi_trLE == CompOp) )
 829     return( (ubi_trLEFT == whichkid) ? Neighbor( parent, whichkid ) : parent );
 830   else
 831     return( (ubi_trRIGHT == whichkid) ? Neighbor( parent, whichkid ) : parent );
 832   } /* ubi_btLocate */
 833
 834 ubi_btNodePtr ubi_btFind( ubi_btRootPtr RootPtr,
 835                           ubi_btItemPtr FindMe )
 836   /* ------------------------------------------------------------------------ **
 837    * This function performs a non-recursive search of a tree for any node
 838    * matching a specific key.
 839    *
 840    *  Input:
 841    *     RootPtr  -  a pointer to the header of the tree to be searched.
 842    *     FindMe   -  a pointer to the key value for which to search.
 843    *
 844    *  Output:
 845    *     A pointer to a node with a key that matches the key indicated by
 846    *     FindMe, or NULL if no such node was found.
 847    *
 848    *  Note:   In a tree that allows duplicates, the pointer returned *might
 849    *          not* point to the (sequentially) first occurance of the
 850    *          desired key.  In such a tree, it may be more useful to use
 851    *          ubi_btLocate().
 852    * ------------------------------------------------------------------------ **
 853    */
 854   {
 855   return( qFind( RootPtr->cmp, FindMe, RootPtr->root ) );
 856   } /* ubi_btFind */
 857
 858 ubi_btNodePtr ubi_btNext( ubi_btNodePtr P )
 859   /* ------------------------------------------------------------------------ **
 860    * Given the node indicated by P, find the (sorted order) Next node in the
 861    * tree.
 862    *  Input:   P  -  a pointer to a node that exists in a binary tree.
 863    *  Output:  A pointer to the "next" node in the tree, or NULL if P pointed
 864    *           to the "last" node in the tree or was NULL.
 865    * ------------------------------------------------------------------------ **
 866    */
 867   {
 868   return( Neighbor( P, ubi_trRIGHT ) );
 869   } /* ubi_btNext */
 870
 871 ubi_btNodePtr ubi_btPrev( ubi_btNodePtr P )
 872   /* ------------------------------------------------------------------------ **
 873    * Given the node indicated by P, find the (sorted order) Previous node in
 874    * the tree.
 875    *  Input:   P  -  a pointer to a node that exists in a binary tree.
 876    *  Output:  A pointer to the "previous" node in the tree, or NULL if P
 877    *           pointed to the "first" node in the tree or was NULL.
 878    * ------------------------------------------------------------------------ **
 879    */
 880   {
 881   return( Neighbor( P, ubi_trLEFT ) );
 882   } /* ubi_btPrev */
 883
 884 ubi_btNodePtr ubi_btFirst( ubi_btNodePtr P )
 885   /* ------------------------------------------------------------------------ **
 886    * Given the node indicated by P, find the (sorted order) First node in the
 887    * subtree of which *P is the root.
 888    *  Input:   P  -  a pointer to a node that exists in a binary tree.
 889    *  Output:  A pointer to the "first" node in a subtree that has *P as its
 890    *           root.  This function will return NULL only if P is NULL.
 891    *  Note:    In general, you will be passing in the value of the root field
 892    *           of an ubi_btRoot structure.
 893    * ------------------------------------------------------------------------ **
 894    */
 895   {
 896   return( SubSlide( P, ubi_trLEFT ) );
 897   } /* ubi_btFirst */
 898
 899 ubi_btNodePtr ubi_btLast( ubi_btNodePtr P )
 900   /* ------------------------------------------------------------------------ **
 901    * Given the node indicated by P, find the (sorted order) Last node in the
 902    * subtree of which *P is the root.
 903    *  Input:   P  -  a pointer to a node that exists in a binary tree.
 904    *  Output:  A pointer to the "last" node in a subtree that has *P as its
 905    *           root.  This function will return NULL only if P is NULL.
 906    *  Note:    In general, you will be passing in the value of the root field
 907    *           of an ubi_btRoot structure.
 908    * ------------------------------------------------------------------------ **
 909    */
 910   {
 911   return( SubSlide( P, ubi_trRIGHT ) );
 912   } /* ubi_btLast */
 913
 914 ubi_btNodePtr ubi_btFirstOf( ubi_btRootPtr RootPtr,
 915                              ubi_btItemPtr MatchMe,
 916                              ubi_btNodePtr p )
 917   /* ------------------------------------------------------------------------ **
 918    * Given a tree that a allows duplicate keys, and a pointer to a node in
 919    * the tree, this function will return a pointer to the first (traversal
 920    * order) node with the same key value.
 921    *
 922    *  Input:  RootPtr - A pointer to the root of the tree.
 923    *          MatchMe - A pointer to the key value.  This should probably
 924    *                    point to the key within node *p.
 925    *          p       - A pointer to a node in the tree.
 926    *  Output: A pointer to the first node in the set of nodes with keys
 927    *          matching <FindMe>.
 928    *  Notes:  Node *p MUST be in the set of nodes with keys matching
 929    *          <FindMe>.  If not, this function will return NULL.
 930    *
 931    *          4.7: Bug found & fixed by Massimo Campostrini,
 932    *               Istituto Nazionale di Fisica Nucleare, Sezione di Pisa.
 933    *
 934    * ------------------------------------------------------------------------ **
 935    */
 936   {
 937   /* If our starting point is invalid, return NULL. */
 938   if( (NULL == p)
 939    || (ubi_trEQUAL != ubi_trAbNormal( (*(RootPtr->cmp))( MatchMe, p ) )) )
 940     return( NULL );
 941   return( Border( RootPtr, MatchMe, p, ubi_trLEFT ) );
 942   } /* ubi_btFirstOf */
 943
 944 ubi_btNodePtr ubi_btLastOf( ubi_btRootPtr RootPtr,
 945                             ubi_btItemPtr MatchMe,
 946                             ubi_btNodePtr p )
 947   /* ------------------------------------------------------------------------ **
 948    * Given a tree that a allows duplicate keys, and a pointer to a node in
 949    * the tree, this function will return a pointer to the last (traversal
 950    * order) node with the same key value.
 951    *
 952    *  Input:  RootPtr - A pointer to the root of the tree.
 953    *          MatchMe - A pointer to the key value.  This should probably
 954    *                    point to the key within node *p.
 955    *          p       - A pointer to a node in the tree.
 956    *  Output: A pointer to the last node in the set of nodes with keys
 957    *          matching <FindMe>.
 958    *  Notes:  Node *p MUST be in the set of nodes with keys matching
 959    *          <FindMe>.  If not, this function will return NULL.
 960    *
 961    *          4.7: Bug found & fixed by Massimo Campostrini,
 962    *               Istituto Nazionale di Fisica Nucleare, Sezione di Pisa.
 963    *
 964    * ------------------------------------------------------------------------ **
 965    */
 966   {
 967   /* If our starting point is invalid, return NULL. */
 968   if( (NULL != p)
 969    || (ubi_trEQUAL != ubi_trAbNormal( (*(RootPtr->cmp))( MatchMe, p ) )) )
 970     return( NULL );
 971   return( Border( RootPtr, MatchMe, p, ubi_trRIGHT ) );
 972   } /* ubi_btLastOf */
 973
 974 unsigned long ubi_btTraverse( ubi_btRootPtr   RootPtr,
 975                               ubi_btActionRtn EachNode,
 976                               void           *UserData )
 977   /* ------------------------------------------------------------------------ **
 978    * Traverse a tree in sorted order (non-recursively).  At each node, call
 979    * (*EachNode)(), passing a pointer to the current node, and UserData as the
 980    * second parameter.
 981    *
 982    *  Input:   RootPtr  -  a pointer to an ubi_btRoot structure that indicates
 983    *                       the tree to be traversed.
 984    *           EachNode -  a pointer to a function to be called at each node
 985    *                       as the node is visited.
 986    *           UserData -  a generic pointer that may point to anything that
 987    *                       you choose.
 988    *
 989    *  Output:  A count of the number of nodes visited.  This will be zero
 990    *           if the tree is empty.
 991    *
 992    * ------------------------------------------------------------------------ **
 993    */
 994   {
 995   ubi_btNodePtr p = ubi_btFirst( RootPtr->root );
 996   unsigned long count = 0;
 997
 998   while( NULL != p )
 999     {
1000     (*EachNode)( p, UserData );
1001     count++;
1002     p = ubi_btNext( p );
1003     }
1004   return( count );
1005   } /* ubi_btTraverse */
1006
1007 unsigned long ubi_btKillTree( ubi_btRootPtr     RootPtr,
1008                               ubi_btKillNodeRtn FreeNode )
1009   /* ------------------------------------------------------------------------ **
1010    * Delete an entire tree (non-recursively) and reinitialize the ubi_btRoot
1011    * structure.  Return a count of the number of nodes deleted.
1012    *
1013    *  Input:   RootPtr  -  a pointer to an ubi_btRoot structure that indicates
1014    *                       the root of the tree to delete.
1015    *           FreeNode -  a function that will be called for each node in the
1016    *                       tree to deallocate the memory used by the node.
1017    *
1018    *  Output:  The number of nodes removed from the tree.
1019    *           A value of 0 will be returned if:
1020    *           - The tree actually contains 0 entries.
1021    *           - the value of <RootPtr> is NULL, in which case the tree is
1022    *             assumed to be empty
1023    *           - the value of <FreeNode> is NULL, in which case entries
1024    *             cannot be removed, so 0 is returned.  *Make sure that you
1025    *             provide a valid value for <FreeNode>*.
1026    *           In all other cases, you should get a positive value equal to
1027    *           the value of RootPtr->count upon entry.
1028    *
1029    * ------------------------------------------------------------------------ **
1030    */
1031   {
1032   ubi_btNodePtr p, q;
1033   unsigned long count = 0;
1034
1035   if( (NULL == RootPtr) || (NULL == FreeNode) )
1036     return( 0 );
1037
1038   p = ubi_btFirst( RootPtr->root );
1039   while( NULL != p )
1040     {
1041     q = p;
1042     while( q->Link[ubi_trRIGHT] )
1043       q = SubSlide( q->Link[ubi_trRIGHT], ubi_trLEFT );
1044     p = q->Link[ubi_trPARENT];
1045     if( NULL != p )
1046       p->Link[ ((p->Link[ubi_trLEFT] == q)?ubi_trLEFT:ubi_trRIGHT) ] = NULL;
1047     (*FreeNode)((void *)q);
1048     count++;
1049     }
1050
1051   /* overkill... */
1052   (void)ubi_btInitTree( RootPtr,
1053                         RootPtr->cmp,
1054                         RootPtr->flags );
1055   return( count );
1056   } /* ubi_btKillTree */
1057
1058 ubi_btNodePtr ubi_btLeafNode( ubi_btNodePtr leader )
1059   /* ------------------------------------------------------------------------ **
1060    * Returns a pointer to a leaf node.
1061    *
1062    *  Input:  leader  - Pointer to a node at which to start the descent.
1063    *
1064    *  Output: A pointer to a leaf node selected in a somewhat arbitrary
1065    *          manner.
1066    *
1067    *  Notes:  I wrote this function because I was using splay trees as a
1068    *          database cache.  The cache had a maximum size on it, and I
1069    *          needed a way of choosing a node to sacrifice if the cache
1070    *          became full.  In a splay tree, less recently accessed nodes
1071    *          tend toward the bottom of the tree, meaning that leaf nodes
1072    *          are good candidates for removal.  (I really can't think of
1073    *          any other reason to use this function.)
1074    *        + In a simple binary tree or an AVL tree, the most recently
1075    *          added nodes tend to be nearer the bottom, making this a *bad*
1076    *          way to choose which node to remove from the cache.
1077    *        + Randomizing the traversal order is probably a good idea.  You
1078    *          can improve the randomization of leaf node selection by passing
1079    *          in pointers to nodes other than the root node each time.  A
1080    *          pointer to any node in the tree will do.  Of course, if you
1081    *          pass a pointer to a leaf node you'll get the same thing back.
1082    *
1083    * ------------------------------------------------------------------------ **
1084    */
1085   {
1086   ubi_btNodePtr follower = NULL;
1087   int           whichway = ubi_trLEFT;
1088
1089   while( NULL != leader )
1090     {
1091     follower = leader;
1092     leader   = follower->Link[ whichway ];
1093     if( NULL == leader )
1094       {
1095       whichway = ubi_trRevWay( whichway );
1096       leader   = follower->Link[ whichway ];
1097       }
1098     }
1099
1100   return( follower );
1101   } /* ubi_btLeafNode */
1102
1103 int ubi_btModuleID( int size, char *list[] )
1104   /* ------------------------------------------------------------------------ **
1105    * Returns a set of strings that identify the module.
1106    *
1107    *  Input:  size  - The number of elements in the array <list>.
1108    *          list  - An array of pointers of type (char *).  This array
1109    *                  should, initially, be empty.  This function will fill
1110    *                  in the array with pointers to strings.
1111    *  Output: The number of elements of <list> that were used.  If this value
1112    *          is less than <size>, the values of the remaining elements are
1113    *          not guaranteed.
1114    *
1115    *  Notes:  Please keep in mind that the pointers returned indicate strings
1116    *          stored in static memory.  Don't free() them, don't write over
1117    *          them, etc.  Just read them.
1118    * ------------------------------------------------------------------------ **
1119    */
1120   {
1121   if( size > 0 )
1122     {
1123     list[0] = ModuleID;
1124     if( size > 1 )
1125       list[1] = NULL;
1126     return( 1 );
1127     }
1128   return( 0 );
1129   } /* ubi_btModuleID */
1130
1131
1132 /* ========================================================================== */