Removed all ubiqx includes from includes.h. So far, this was only a problem
[samba.git] / source3 / ubiqx / ubi_AVLtree.c
1 /* ========================================================================== **
2  *                              ubi_AVLtree.c
3  *
4  *  Copyright (C) 1991-1998 by Christopher R. Hertel
5  *
6  *  Email: crh@ubiqx.mn.org
7  * -------------------------------------------------------------------------- **
8  *
9  *  This module provides an implementation of AVL height balanced binary
10  *  trees.  (Adelson-Velskii, Landis 1962)
11  *
12  *  This file implements the core of the height-balanced (AVL) tree management
13  *  routines.  The header file, ubi_AVLtree.h, contains function prototypes
14  *  for all "exported" functions.
15  *
16  * -------------------------------------------------------------------------- **
17  *
18  *  This library is free software; you can redistribute it and/or
19  *  modify it under the terms of the GNU Library General Public
20  *  License as published by the Free Software Foundation; either
21  *  version 2 of the License, or (at your option) any later version.
22  *
23  *  This library is distributed in the hope that it will be useful,
24  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
25  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
26  *  Library General Public License for more details.
27  *
28  *  You should have received a copy of the GNU Library General Public
29  *  License along with this library; if not, write to the Free
30  *  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
31  *
32  * -------------------------------------------------------------------------- **
33  *
34  * Log: ubi_AVLtree.c,v 
35  * Revision 4.1  1998/05/20 04:35:50  crh
36  * The C file now includes ubi_null.h.  See ubi_null.h for more info.
37  *
38  * Revision 4.0  1998/03/10 03:37:09  crh
39  * Major changes.
40  * By adding the AVL balance field to the base ubi_btNode structure, I no
41  * longer need AVL-specific ReplaceNode(), SwapNodes(), and InitNode()
42  * functions.  The Remove() function is also simplified.  It's all much
43  * cleaner.
44  * This is rev. 4.0.  The 3.x series was dropped.
45  *
46  * Revision 2.5  1997/12/23 04:00:42  crh
47  * In this version, all constants & macros defined in the header file have
48  * the ubi_tr prefix.  Also cleaned up anything that gcc complained about
49  * when run with '-pedantic -fsyntax-only -Wall'.
50  *
51  * Revision 2.4  1997/07/26 04:36:20  crh
52  * Andrew Leppard, aka "Grazgur", discovered that I still had my brains tied
53  * on backwards with respect to node deletion.  I did some more digging and
54  * discovered that I was not changing the balance values correctly in the
55  * single rotation functions.  Double rotation was working correctly because
56  * the formula for changing the balance values is the same for insertion or
57  * deletion.  Not so for single rotation.
58  *
59  * I have tested the fix by loading the tree with over 44 thousand names,
60  * deleting 2,629 of them (all those in which the second character is 'u')
61  * and then walking the tree recursively to verify that the balance factor of
62  * each node is correct.  Passed.
63  *
64  * Thanks Andrew!
65  *
66  * Also:
67  * + Changed ubi_TRUE and ubi_FALSE to ubi_trTRUE and ubi_trFALSE.
68  * + Rewrote the ubi_tr<func> macros because they weren't doing what I'd
69  *   hoped they would do (see the bottom of the header file).  They work now.
70  *
71  * Revision 2.3  1997/06/03 04:41:35  crh
72  * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid causing
73  * problems.
74  *
75  * Revision 2.2  1995/10/03 22:16:01  CRH
76  * Ubisized!
77  *
78  * Revision 2.1  95/03/09  23:45:59  CRH
79  * Added the ModuleID static string and function.  These modules are now
80  * self-identifying.
81  * 
82  * Revision 2.0  95/03/05  14:10:51  CRH
83  * This revision of ubi_AVLtree coincides with revision 2.0 of ubi_BinTree,
84  * and so includes all of the changes to that module.  In addition, a bug in
85  * the node deletion process has been fixed.
86  *
87  * After rewriting the Locate() function in ubi_BinTree, I decided that it was
88  * time to overhaul this module.  In the process, I discovered a bug related
89  * to node deletion.  To fix the bug, I wrote function Debalance().  A quick
90  * glance will show that it is very similar to the Rebalance() function.  In
91  * previous versions of this module, I tried to include the functionality of
92  * Debalance() within Rebalance(), with poor results.
93  *
94  * Revision 1.0  93/10/15  22:58:56  CRH
95  * With this revision, I have added a set of #define's that provide a single,
96  * standard API to all existing tree modules.  Until now, each of the three
97  * existing modules had a different function and typedef prefix, as follows:
98  *
99  *       Module        Prefix
100  *     ubi_BinTree     ubi_bt
101  *     ubi_AVLtree     ubi_avl
102  *     ubi_SplayTree   ubi_spt
103  *
104  * To further complicate matters, only those portions of the base module
105  * (ubi_BinTree) that were superceeded in the new module had the new names.
106  * For example, if you were using ubi_SplayTree, the locate function was
107  * called "ubi_sptLocate", but the next and previous functions remained
108  * "ubi_btNext" and "ubi_btPrev".
109  *
110  * This was not too terrible if you were familiar with the modules and knew
111  * exactly which tree model you wanted to use.  If you wanted to be able to
112  * change modules (for speed comparisons, etc), things could get messy very
113  * quickly.
114  *
115  * So, I have added a set of defined names that get redefined in any of the
116  * descendant modules.  To use this standardized interface in your code,
117  * simply replace all occurances of "ubi_bt", "ubi_avl", and "ubi_spt" with
118  * "ubi_tr".  The "ubi_tr" names will resolve to the correct function or
119  * datatype names for the module that you are using.  Just remember to
120  * include the header for that module in your program file.  Because these
121  * names are handled by the preprocessor, there is no added run-time
122  * overhead.
123  *
124  * Note that the original names do still exist, and can be used if you wish
125  * to write code directly to a specific module.  This should probably only be
126  * done if you are planning to implement a new descendant type, such as
127  * red/black trees.  CRH
128  *
129  *  V0.0 - May, 1990   -  Written by Christopher R. Hertel (CRH).
130  *
131  *  ========================================================================= **
132  */
133
134 #include "ubi_null.h"     /* ubiqx NULL source.       */
135 #include "ubi_AVLtree.h"  /* Header for THIS module.  */
136
137 /* ========================================================================== **
138  * Static data.
139  */
140
141 static char ModuleID[] = "ubi_AVLtree\n\
142 \tRevision: 4.1 \n\
143 \tDate: 1998/05/20 04:35:50 \n\
144 \tAuthor: crh \n";
145
146 /* ========================================================================== **
147  * The next set of functions are the AVL balancing routines.  There are left
148  * and right, single and double rotations.  The rotation routines handle the
149  * rotations and reconnect all tree pointers that might get confused by the
150  * rotations.  A pointer to the new subtree root node is returned.
151  *
152  * Note that L1 and R1 are identical, except that all the RIGHTs and LEFTs
153  * are reversed.  The same is true for L2 and R2.  I'm sure that there is
154  * a clever way to reduce the amount of code by combining these functions,
155  * but it might involve additional overhead, and it would probably be a pain
156  * to read, debug, etc.
157  * -------------------------------------------------------------------------- **
158  */
159
160 static ubi_btNodePtr L1( ubi_btNodePtr p )
161   /* ------------------------------------------------------------------------ **
162    * Single rotate left.
163    *
164    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
165    *  Output: A pointer to the new root of the same subtree (now that node
166    *          p has been moved).
167    * ------------------------------------------------------------------------ **
168    */
169   {
170   ubi_btNodePtr tmp;
171
172   tmp                      = p->Link[ubi_trRIGHT];
173   p->Link[ubi_trRIGHT]     = tmp->Link[ubi_trLEFT];
174   tmp->Link[ubi_trLEFT]    = p;
175
176   tmp->Link[ubi_trPARENT]  = p->Link[ubi_trPARENT];
177   tmp->gender              = p->gender;
178   if(tmp->Link[ubi_trPARENT])
179     (tmp->Link[ubi_trPARENT])->Link[(int)(tmp->gender)] = tmp;
180   p->Link[ubi_trPARENT]    = tmp;
181   p->gender                = ubi_trLEFT;
182   if( p->Link[ubi_trRIGHT] )
183     {
184     p->Link[ubi_trRIGHT]->Link[ubi_trPARENT] = p;
185     (p->Link[ubi_trRIGHT])->gender           = ubi_trRIGHT;
186     }
187   p->balance -= ubi_trNormalize( tmp->balance );
188   (tmp->balance)--;
189   return( tmp );
190   } /* L1 */
191
192 static ubi_btNodePtr R1( ubi_btNodePtr p )
193   /* ------------------------------------------------------------------------ **
194    * Single rotate right.
195    *
196    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
197    *  Output: A pointer to the new root of the same subtree (now that node
198    *          p has been moved).
199    * ------------------------------------------------------------------------ **
200    */
201   {
202   ubi_btNodePtr tmp;
203
204   tmp                      = p->Link[ubi_trLEFT];
205   p->Link[ubi_trLEFT]      = tmp->Link[ubi_trRIGHT];
206   tmp->Link[ubi_trRIGHT]   = p;
207
208   tmp->Link[ubi_trPARENT]  = p->Link[ubi_trPARENT];
209   tmp->gender              = p->gender;
210   if(tmp->Link[ubi_trPARENT])
211     (tmp->Link[ubi_trPARENT])->Link[(int)(tmp->gender)] = tmp;
212   p->Link[ubi_trPARENT]    = tmp;
213   p->gender                = ubi_trRIGHT;
214   if(p->Link[ubi_trLEFT])
215     {
216     p->Link[ubi_trLEFT]->Link[ubi_trPARENT]  = p;
217     p->Link[ubi_trLEFT]->gender              = ubi_trLEFT;
218     }
219   p->balance -= ubi_trNormalize( tmp->balance );
220   (tmp->balance)++;
221   return( tmp );
222   } /* R1 */
223
224 static ubi_btNodePtr L2( ubi_btNodePtr tree )
225   /* ------------------------------------------------------------------------ **
226    * Double rotate left.
227    *
228    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
229    *  Output: A pointer to the new root of the same subtree (now that node
230    *          p has been moved).
231    * ------------------------------------------------------------------------ **
232    */
233   {
234   ubi_btNodePtr tmp, newroot;
235
236   tmp                         = tree->Link[ubi_trRIGHT];
237   newroot                     = tmp->Link[ubi_trLEFT];
238   tmp->Link[ubi_trLEFT]       = newroot->Link[ubi_trRIGHT];
239   newroot->Link[ubi_trRIGHT]  = tmp;
240   tree->Link[ubi_trRIGHT]     = newroot->Link[ubi_trLEFT];
241   newroot->Link[ubi_trLEFT]   = tree;
242
243   newroot->Link[ubi_trPARENT] = tree->Link[ubi_trPARENT];
244   newroot->gender             = tree->gender;
245   tree->Link[ubi_trPARENT]    = newroot;
246   tree->gender                = ubi_trLEFT;
247   tmp->Link[ubi_trPARENT]     = newroot;
248   tmp->gender                 = ubi_trRIGHT;
249
250   if( tree->Link[ubi_trRIGHT] )
251     {
252     tree->Link[ubi_trRIGHT]->Link[ubi_trPARENT] = tree;
253     tree->Link[ubi_trRIGHT]->gender             = ubi_trRIGHT;
254     }
255   if( tmp->Link[ubi_trLEFT] )
256     {
257     tmp->Link[ubi_trLEFT]->Link[ubi_trPARENT]   = tmp;
258     tmp->Link[ubi_trLEFT]->gender               = ubi_trLEFT;
259     }
260   if(newroot->Link[ubi_trPARENT])
261     newroot->Link[ubi_trPARENT]->Link[(int)(newroot->gender)] = newroot;
262
263   switch( newroot->balance )
264     {
265     case ubi_trLEFT :
266       tree->balance = ubi_trEQUAL; tmp->balance = ubi_trRIGHT; break;
267     case ubi_trEQUAL:
268       tree->balance = ubi_trEQUAL; tmp->balance = ubi_trEQUAL; break;
269     case ubi_trRIGHT:
270       tree->balance = ubi_trLEFT;  tmp->balance = ubi_trEQUAL; break;
271     }
272   newroot->balance = ubi_trEQUAL;
273   return( newroot );
274   } /* L2 */
275
276 static ubi_btNodePtr R2( ubi_btNodePtr tree )
277   /* ------------------------------------------------------------------------ **
278    * Double rotate right.
279    *
280    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
281    *  Output: A pointer to the new root of the same subtree (now that node
282    *          p has been moved).
283    * ------------------------------------------------------------------------ **
284    */
285   {
286   ubi_btNodePtr tmp, newroot;
287
288   tmp                         = tree->Link[ubi_trLEFT];
289   newroot                     = tmp->Link[ubi_trRIGHT];
290   tmp->Link[ubi_trRIGHT]      = newroot->Link[ubi_trLEFT];
291   newroot->Link[ubi_trLEFT]   = tmp;
292   tree->Link[ubi_trLEFT]      = newroot->Link[ubi_trRIGHT];
293   newroot->Link[ubi_trRIGHT]  = tree;
294
295   newroot->Link[ubi_trPARENT] = tree->Link[ubi_trPARENT];
296   newroot->gender             = tree->gender;
297   tree->Link[ubi_trPARENT]    = newroot;
298   tree->gender                = ubi_trRIGHT;
299   tmp->Link[ubi_trPARENT]     = newroot;
300   tmp->gender                 = ubi_trLEFT;
301
302   if( tree->Link[ubi_trLEFT] )
303     {
304     tree->Link[ubi_trLEFT]->Link[ubi_trPARENT]  = tree;
305     tree->Link[ubi_trLEFT]->gender              = ubi_trLEFT;
306     }
307   if( tmp->Link[ubi_trRIGHT] )
308     {
309     tmp->Link[ubi_trRIGHT]->Link[ubi_trPARENT]  = tmp;
310     tmp->Link[ubi_trRIGHT]->gender              = ubi_trRIGHT;
311     }
312   if(newroot->Link[ubi_trPARENT])
313     newroot->Link[ubi_trPARENT]->Link[(int)(newroot->gender)] = newroot;
314
315   switch( newroot->balance )
316     {
317     case ubi_trLEFT  :
318       tree->balance = ubi_trRIGHT; tmp->balance = ubi_trEQUAL; break;
319     case ubi_trEQUAL :
320       tree->balance = ubi_trEQUAL; tmp->balance = ubi_trEQUAL; break;
321     case ubi_trRIGHT :
322       tree->balance = ubi_trEQUAL; tmp->balance = ubi_trLEFT;  break;
323     }
324   newroot->balance = ubi_trEQUAL;
325   return( newroot );
326   } /* R2 */
327
328
329 static ubi_btNodePtr Adjust( ubi_btNodePtr p, char LorR )
330   /* ------------------------------------------------------------------------ **
331    * Adjust the balance value at node *p.  If necessary, rotate the subtree
332    * rooted at p.
333    *
334    *  Input:  p    -  A pointer to the node to be adjusted.  One of the
335    *                  subtrees of this node has changed height, so the
336    *                  balance value at this node must be adjusted, possibly
337    *                  by rotating the tree at this node.
338    *          LorR -  Indicates the TALLER subtree.
339    *
340    *  Output: A pointer to the (possibly new) root node of the subtree.
341    *
342    *  Notes:  This function may be called after a node has been added *or*
343    *          deleted, so LorR indicates the TALLER subtree.
344    * ------------------------------------------------------------------------ **
345    */
346   {
347   if( p->balance != LorR )
348     p->balance += ubi_trNormalize(LorR);
349   else
350     {
351     char tallerbal;  /* Balance value of the root of the taller subtree of p. */
352
353     tallerbal = p->Link[(int)LorR]->balance;
354     if( ( ubi_trEQUAL == tallerbal ) || ( p->balance == tallerbal ) )
355       p = ( (ubi_trLEFT==LorR) ? R1(p) : L1(p) );   /* single rotation */
356     else
357       p = ( (ubi_trLEFT==LorR) ? R2(p) : L2(p) );   /* double rotation */
358     }
359   return( p );
360   } /* Adjust */
361
362 static ubi_btNodePtr Rebalance( ubi_btNodePtr Root,
363                                 ubi_btNodePtr subtree,
364                                 char          LorR )
365   /* ------------------------------------------------------------------------ **
366    * Rebalance the tree following an insertion.
367    *
368    *  Input:  Root    - A pointer to the root node of the whole tree.
369    *          subtree - A pointer to the node that has just gained a new
370    *                    child.
371    *          LorR    - Gender of the child that has just been gained.
372    *
373    *  Output: A pointer to the (possibly new) root of the AVL tree.
374    *          Rebalancing the tree moves nodes around a bit, so the node
375    *          that *was* the root, may not be the root when we're finished.
376    *
377    *  Notes:  Rebalance() must walk up the tree from where we are (which is
378    *          where the latest change occurred), rebalancing the subtrees
379    *          along the way.  The rebalancing operation can stop if the
380    *          change at the current subtree root won't affect the rest of
381    *          the tree.  In the case of an addition, if a subtree root's
382    *          balance becomes EQUAL, then we know that the height of that
383    *          subtree has not changed, so we can exit.
384    * ------------------------------------------------------------------------ **
385    */
386   {
387   while( subtree )
388     {
389     subtree = Adjust( subtree, LorR );
390     if( ubi_trPARENT == subtree->gender )
391       return( subtree );
392     if( ubi_trEQUAL == subtree->balance )
393       return( Root );
394     LorR = subtree->gender;
395     subtree = subtree->Link[ubi_trPARENT];
396     }
397   return( Root );
398   } /* Rebalance */
399
400 static ubi_btNodePtr Debalance( ubi_btNodePtr Root,
401                                 ubi_btNodePtr subtree,
402                                 char          LorR )
403   /* ------------------------------------------------------------------------ **
404    * Rebalance the tree following a deletion.
405    *
406    *  Input:  Root    - A pointer to the root node of the whole tree.
407    *          subtree - A pointer to the node who's child has just "left the
408    *                    nest".
409    *          LorR    - Gender of the child that left.
410    *
411    *  Output: A pointer to the (possibly new) root of the AVL tree.
412    *          Rebalancing the tree moves nodes around a bit, so the node
413    *          that *was* the root, may not be the root when we're finished.
414    *
415    *  Notes:  Debalance() is subtly different from Rebalance() (above) in
416    *          two respects.
417    *            * When it calls Adjust(), it passes the *opposite* of LorR.
418    *              This is because LorR, as passed into Debalance() indicates
419    *              the shorter subtree.  As we move up the tree, LorR is
420    *              assigned the gender of the node that we are leaving (i.e.,
421    *              the subtree that we just rebalanced).
422    *            * We know that a subtree has not changed height if the
423    *              balance becomes LEFT or RIGHT.  This is the *opposite* of
424    *              what happens in Rebalance().
425    * ------------------------------------------------------------------------ **
426    */
427   {
428   while( subtree )
429     {
430     subtree = Adjust( subtree, ubi_trRevWay(LorR) );
431     if( ubi_trPARENT == subtree->gender )
432       return( subtree );
433     if( ubi_trEQUAL != subtree->balance )
434       return( Root );
435     LorR = subtree->gender;
436     subtree = subtree->Link[ubi_trPARENT];
437     }
438   return( Root );
439   } /* Debalance */
440
441 /* ========================================================================== **
442  *         Public, exported (ie. not static-ly declared) functions...
443  * -------------------------------------------------------------------------- **
444  */
445
446 ubi_trBool ubi_avlInsert( ubi_btRootPtr  RootPtr,
447                           ubi_btNodePtr  NewNode,
448                           ubi_btItemPtr  ItemPtr,
449                           ubi_btNodePtr *OldNode )
450   /* ------------------------------------------------------------------------ **
451    * This function uses a non-recursive algorithm to add a new element to
452    * the tree.
453    *
454    *  Input:   RootPtr  -  a pointer to the ubi_btRoot structure that indicates
455    *                       the root of the tree to which NewNode is to be added.
456    *           NewNode  -  a pointer to an ubi_btNode structure that is NOT
457    *                       part of any tree.
458    *           ItemPtr  -  A pointer to the sort key that is stored within
459    *                       *NewNode.  ItemPtr MUST point to information stored
460    *                       in *NewNode or an EXACT DUPLICATE.  The key data
461    *                       indicated by ItemPtr is used to place the new node
462    *                       into the tree.
463    *           OldNode  -  a pointer to an ubi_btNodePtr.  When searching
464    *                       the tree, a duplicate node may be found.  If
465    *                       duplicates are allowed, then the new node will
466    *                       be simply placed into the tree.  If duplicates
467    *                       are not allowed, however, then one of two things
468    *                       may happen.
469    *                       1) if overwritting *is not* allowed, this
470    *                          function will return FALSE (indicating that
471    *                          the new node could not be inserted), and
472    *                          *OldNode will point to the duplicate that is
473    *                          still in the tree.
474    *                       2) if overwritting *is* allowed, then this
475    *                          function will swap **OldNode for *NewNode.
476    *                          In this case, *OldNode will point to the node
477    *                          that was removed (thus allowing you to free
478    *                          the node).
479    *                          **  If you are using overwrite mode, ALWAYS  **
480    *                          ** check the return value of this parameter! **
481    *                 Note: You may pass NULL in this parameter, the
482    *                       function knows how to cope.  If you do this,
483    *                       however, there will be no way to return a
484    *                       pointer to an old (ie. replaced) node (which is
485    *                       a problem if you are using overwrite mode).
486    *
487    *  Output:  a boolean value indicating success or failure.  The function
488    *           will return FALSE if the node could not be added to the tree.
489    *           Such failure will only occur if duplicates are not allowed,
490    *           nodes cannot be overwritten, AND a duplicate key was found
491    *           within the tree.
492    * ------------------------------------------------------------------------ **
493    */
494   {
495   ubi_btNodePtr OtherP;
496
497   if( !(OldNode) )
498     OldNode = &OtherP;
499   if( ubi_btInsert( RootPtr,
500                     (ubi_btNodePtr)NewNode,
501                     ItemPtr,
502                     (ubi_btNodePtr *)OldNode ) )
503     {
504     if( (*OldNode) )
505       NewNode->balance = (*OldNode)->balance;
506     else
507       {
508       NewNode->balance = ubi_trEQUAL;
509       RootPtr->root = (ubi_btNodePtr)Rebalance( (ubi_btNodePtr)RootPtr->root,
510                                                 NewNode->Link[ubi_trPARENT],
511                                                 NewNode->gender );
512       }
513     return( ubi_trTRUE );
514     }
515   return( ubi_trFALSE );      /* Failure: could not replace an existing node. */
516   } /* ubi_avlInsert */
517
518 ubi_btNodePtr ubi_avlRemove( ubi_btRootPtr  RootPtr,
519                              ubi_btNodePtr  DeadNode )
520   /* ------------------------------------------------------------------------ **
521    * This function removes the indicated node from the tree, after which the
522    * tree is rebalanced.
523    *
524    *  Input:  RootPtr  -  A pointer to the header of the tree that contains
525    *                      the node to be removed.
526    *          DeadNode -  A pointer to the node that will be removed.
527    *
528    *  Output: This function returns a pointer to the node that was removed
529    *          from the tree (ie. the same as DeadNode).
530    *
531    *  Note:   The node MUST be in the tree indicated by RootPtr.  If not,
532    *          strange and evil things will happen to your trees.
533    *
534    * ------------------------------------------------------------------------ **
535    */
536   {
537   /* Let the base binary tree module do the removal, then rebalance. */
538   if( ubi_btRemove( RootPtr, DeadNode ) )
539     RootPtr->root = Debalance( RootPtr->root,
540                                DeadNode->Link[ubi_trPARENT],
541                                DeadNode->gender );
542   return( DeadNode );
543   } /* ubi_avlRemove */
544
545 int ubi_avlModuleID( int size, char *list[] )
546   /* ------------------------------------------------------------------------ **
547    * Returns a set of strings that identify the module.
548    *
549    *  Input:  size  - The number of elements in the array <list>.
550    *          list  - An array of pointers of type (char *).  This array
551    *                  should, initially, be empty.  This function will fill
552    *                  in the array with pointers to strings.
553    *  Output: The number of elements of <list> that were used.  If this value
554    *          is less than <size>, the values of the remaining elements are
555    *          not guaranteed.
556    *
557    *  Notes:  Please keep in mind that the pointers returned indicate strings
558    *          stored in static memory.  Don't free() them, don't write over
559    *          them, etc.  Just read them.
560    * ------------------------------------------------------------------------ **
561    */
562   {
563   if( size > 0 )
564     {
565     list[0] = ModuleID;
566     if( size > 1 )
567       return( 1 + ubi_btModuleID( --size, &(list[1]) ) );
568     return( 1 );
569     }
570   return( 0 );
571   } /* ubi_avlModuleID */
572
573 /* ============================== The End ============================== */