1 /* ========================================================================== **
4 * Copyright (C) 1991-1997 by Christopher R. Hertel
6 * Email: crh@ubiqx.mn.org
7 * -------------------------------------------------------------------------- **
9 * This module provides an implementation of AVL height balanced binary
10 * trees. (Adelson-Velskii, Landis 1962)
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.
16 * -------------------------------------------------------------------------- **
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.
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.
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.
32 * -------------------------------------------------------------------------- **
34 * Revision 2.4 1997/07/26 04:36:20 crh
35 * Andrew Leppard, aka "Grazgur", discovered that I still had my brains tied
36 * on backwards with respect to node deletion. I did some more digging and
37 * discovered that I was not changing the balance values correctly in the
38 * single rotation functions. Double rotation was working correctly because
39 * the formula for changing the balance values is the same for insertion or
40 * deletion. Not so for single rotation.
42 * I have tested the fix by loading the tree with over 44 thousand names,
43 * deleting 2,629 of them (all those in which the second character is 'u')
44 * and then walking the tree recursively to verify that the balance factor of
45 * each node is correct. Passed.
50 * + Changed ubi_TRUE and ubi_FALSE to ubi_trTRUE and ubi_trFALSE.
51 * + Rewrote the ubi_tr<func> macros because they weren't doing what I'd
52 * hoped they would do (see the bottom of the header file). They work now.
54 * Revision 2.3 1997/06/03 04:41:35 crh
55 * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid causing
58 * Revision 2.2 1995/10/03 22:16:01 CRH
61 * Revision 2.1 95/03/09 23:45:59 CRH
62 * Added the ModuleID static string and function. These modules are now
65 * Revision 2.0 95/03/05 14:10:51 CRH
66 * This revision of ubi_AVLtree coincides with revision 2.0 of ubi_BinTree,
67 * and so includes all of the changes to that module. In addition, a bug in
68 * the node deletion process has been fixed.
70 * After rewriting the Locate() function in ubi_BinTree, I decided that it was
71 * time to overhaul this module. In the process, I discovered a bug related
72 * to node deletion. To fix the bug, I wrote function Debalance(). A quick
73 * glance will show that it is very similar to the Rebalance() function. In
74 * previous versions of this module, I tried to include the functionality of
75 * Debalance() within Rebalance(), with poor results.
77 * Revision 1.0 93/10/15 22:58:56 CRH
78 * With this revision, I have added a set of #define's that provide a single,
79 * standard API to all existing tree modules. Until now, each of the three
80 * existing modules had a different function and typedef prefix, as follows:
85 * ubi_SplayTree ubi_spt
87 * To further complicate matters, only those portions of the base module
88 * (ubi_BinTree) that were superceeded in the new module had the new names.
89 * For example, if you were using ubi_AVLtree, the AVL node structure was
90 * named "ubi_avlNode", but the root structure was still "ubi_btRoot". Using
91 * SplayTree, the locate function was called "ubi_sptLocate", but the next
92 * and previous functions remained "ubi_btNext" and "ubi_btPrev".
94 * This was not too terrible if you were familiar with the modules and knew
95 * exactly which tree model you wanted to use. If you wanted to be able to
96 * change modules (for speed comparisons, etc), things could get messy very
99 * So, I have added a set of defined names that get redefined in any of the
100 * descendant modules. To use this standardized interface in your code,
101 * simply replace all occurances of "ubi_bt", "ubi_avl", and "ubi_spt" with
102 * "ubi_tr". The "ubi_tr" names will resolve to the correct function or
103 * datatype names for the module that you are using. Just remember to
104 * include the header for that module in your program file. Because these
105 * names are handled by the preprocessor, there is no added run-time
108 * Note that the original names do still exist, and can be used if you wish
109 * to write code directly to a specific module. This should probably only be
110 * done if you are planning to implement a new descendant type, such as
111 * red/black trees. CRH
113 * V0.0 - May, 1990 - Written by Christopher R. Hertel (CRH).
115 * ========================================================================= **
118 #include "ubi_AVLtree.h" /* Header for THIS module. */
119 #include <stdlib.h> /* Standard C definitions, etc. */
121 /* ========================================================================== **
125 static char ModuleID
[] = "ubi_AVLtree\n\
127 \tDate: 1997/07/26 04:36:20\n\
130 /* ========================================================================== **
131 * The next set of functions are the AVL balancing routines. There are left
132 * and right, single and double rotations. The rotation routines handle the
133 * rotations and reconnect all tree pointers that might get confused by the
134 * rotations. A pointer to the new subtree root node is returned.
136 * Note that L1 and R1 are identical, except that all the RIGHTs and LEFTs
137 * are reversed. The same is true for L2 and R2. I'm sure that there is
138 * a clever way to reduce the amount of code by combining these functions,
139 * but it might involve additional overhead, and it would probably be a pain
140 * to read, debug, etc.
141 * -------------------------------------------------------------------------- **
144 static ubi_avlNodePtr
L1( ubi_avlNodePtr p
)
145 /* ------------------------------------------------------------------------ **
146 * Single rotate left.
148 * Input: p - Pointer to the root of a tree (possibly a subtree).
149 * Output: A pointer to the new root of the same subtree (now that node
151 * ------------------------------------------------------------------------ **
156 tmp
= p
->Link
[RIGHT
];
157 p
->Link
[RIGHT
] = tmp
->Link
[LEFT
];
160 tmp
->Link
[PARENT
] = p
->Link
[PARENT
];
161 tmp
->gender
= p
->gender
;
162 if(tmp
->Link
[PARENT
])
163 (tmp
->Link
[PARENT
])->Link
[(tmp
->gender
)] = tmp
;
164 p
->Link
[PARENT
] = tmp
;
168 p
->Link
[RIGHT
]->Link
[PARENT
] = p
;
169 (p
->Link
[RIGHT
])->gender
= RIGHT
;
171 p
->balance
-= Normalize( tmp
->balance
);
176 static ubi_avlNodePtr
R1( ubi_avlNodePtr p
)
177 /* ------------------------------------------------------------------------ **
178 * Single rotate right.
180 * Input: p - Pointer to the root of a tree (possibly a subtree).
181 * Output: A pointer to the new root of the same subtree (now that node
183 * ------------------------------------------------------------------------ **
189 p
->Link
[LEFT
] = tmp
->Link
[RIGHT
];
190 tmp
->Link
[RIGHT
] = p
;
192 tmp
->Link
[PARENT
] = p
->Link
[PARENT
];
193 tmp
->gender
= p
->gender
;
194 if(tmp
->Link
[PARENT
])
195 (tmp
->Link
[PARENT
])->Link
[(tmp
->gender
)] = tmp
;
196 p
->Link
[PARENT
] = tmp
;
200 p
->Link
[LEFT
]->Link
[PARENT
] = p
;
201 p
->Link
[LEFT
]->gender
= LEFT
;
203 p
->balance
-= Normalize( tmp
->balance
);
208 static ubi_avlNodePtr
L2( ubi_avlNodePtr tree
)
209 /* ------------------------------------------------------------------------ **
210 * Double rotate left.
212 * Input: p - Pointer to the root of a tree (possibly a subtree).
213 * Output: A pointer to the new root of the same subtree (now that node
215 * ------------------------------------------------------------------------ **
218 ubi_avlNodePtr tmp
, newroot
;
220 tmp
= tree
->Link
[RIGHT
];
221 newroot
= tmp
->Link
[LEFT
];
222 tmp
->Link
[LEFT
] = newroot
->Link
[RIGHT
];
223 newroot
->Link
[RIGHT
] = tmp
;
224 tree
->Link
[RIGHT
] = newroot
->Link
[LEFT
];
225 newroot
->Link
[LEFT
] = tree
;
227 newroot
->Link
[PARENT
] = tree
->Link
[PARENT
];
228 newroot
->gender
= tree
->gender
;
229 tree
->Link
[PARENT
] = newroot
;
231 tmp
->Link
[PARENT
] = newroot
;
234 if( tree
->Link
[RIGHT
] )
236 tree
->Link
[RIGHT
]->Link
[PARENT
] = tree
;
237 tree
->Link
[RIGHT
]->gender
= RIGHT
;
239 if( tmp
->Link
[LEFT
] )
241 tmp
->Link
[LEFT
]->Link
[PARENT
] = tmp
;
242 tmp
->Link
[LEFT
]->gender
= LEFT
;
244 if(newroot
->Link
[PARENT
])
245 newroot
->Link
[PARENT
]->Link
[newroot
->gender
] = newroot
;
247 switch( newroot
->balance
)
250 tree
->balance
= EQUAL
; tmp
->balance
= RIGHT
; break;
252 tree
->balance
= EQUAL
; tmp
->balance
= EQUAL
; break;
254 tree
->balance
= LEFT
; tmp
->balance
= EQUAL
; break;
256 newroot
->balance
= EQUAL
;
260 static ubi_avlNodePtr
R2( ubi_avlNodePtr tree
)
261 /* ------------------------------------------------------------------------ **
262 * Double rotate right.
264 * Input: p - Pointer to the root of a tree (possibly a subtree).
265 * Output: A pointer to the new root of the same subtree (now that node
267 * ------------------------------------------------------------------------ **
270 ubi_avlNodePtr tmp
, newroot
;
272 tmp
= tree
->Link
[LEFT
];
273 newroot
= tmp
->Link
[RIGHT
];
274 tmp
->Link
[RIGHT
] = newroot
->Link
[LEFT
];
275 newroot
->Link
[LEFT
] = tmp
;
276 tree
->Link
[LEFT
] = newroot
->Link
[RIGHT
];
277 newroot
->Link
[RIGHT
] = tree
;
279 newroot
->Link
[PARENT
] = tree
->Link
[PARENT
];
280 newroot
->gender
= tree
->gender
;
281 tree
->Link
[PARENT
] = newroot
;
282 tree
->gender
= RIGHT
;
283 tmp
->Link
[PARENT
] = newroot
;
286 if( tree
->Link
[LEFT
] )
288 tree
->Link
[LEFT
]->Link
[PARENT
] = tree
;
289 tree
->Link
[LEFT
]->gender
= LEFT
;
291 if( tmp
->Link
[RIGHT
] )
293 tmp
->Link
[RIGHT
]->Link
[PARENT
] = tmp
;
294 tmp
->Link
[RIGHT
]->gender
= RIGHT
;
296 if(newroot
->Link
[PARENT
])
297 newroot
->Link
[PARENT
]->Link
[newroot
->gender
] = newroot
;
299 switch( newroot
->balance
)
302 tree
->balance
= RIGHT
; tmp
->balance
= EQUAL
; break;
304 tree
->balance
= EQUAL
; tmp
->balance
= EQUAL
; break;
306 tree
->balance
= EQUAL
; tmp
->balance
= LEFT
; break;
308 newroot
->balance
= EQUAL
;
313 static ubi_avlNodePtr
Adjust( ubi_avlNodePtr p
, char LorR
)
314 /* ------------------------------------------------------------------------ **
315 * Adjust the balance value at node *p. If necessary, rotate the subtree
318 * Input: p - A pointer to the node to be adjusted. One of the
319 * subtrees of this node has changed height, so the
320 * balance value at this node must be adjusted, possibly
321 * by rotating the tree at this node.
322 * LorR - Indicates the TALLER subtree.
324 * Output: A pointer to the (possibly new) root node of the subtree.
326 * Notes: This function may be called after a node has been added *or*
327 * deleted, so LorR indicates the TALLER subtree.
328 * ------------------------------------------------------------------------ **
331 if( p
->balance
!= LorR
)
332 p
->balance
+= Normalize(LorR
);
335 char tallerbal
; /* Balance value of the root of the taller subtree of p. */
337 tallerbal
= p
->Link
[LorR
]->balance
;
338 if( ( EQUAL
== tallerbal
) || ( p
->balance
== tallerbal
) )
339 p
= ( (LEFT
==LorR
) ? R1(p
) : L1(p
) ); /* single rotation */
341 p
= ( (LEFT
==LorR
) ? R2(p
) : L2(p
) ); /* double rotation */
346 static ubi_avlNodePtr
Rebalance( ubi_avlNodePtr Root
,
347 ubi_avlNodePtr subtree
,
349 /* ------------------------------------------------------------------------ **
350 * Rebalance the tree following an insertion.
352 * Input: Root - A pointer to the root node of the whole tree.
353 * subtree - A pointer to the node that has just gained a new
355 * LorR - Gender of the child that has just been gained.
357 * Output: A pointer to the (possibly new) root of the AVL tree.
358 * Rebalancing the tree moves nodes around a bit, so the node
359 * that *was* the root, may not be the root when we're finished.
361 * Notes: Rebalance() must walk up the tree from where we are (which is
362 * where the latest change occurred), rebalancing the subtrees
363 * along the way. The rebalancing operation can stop if the
364 * change at the current subtree root won't affect the rest of
365 * the tree. In the case of an addition, if a subtree root's
366 * balance becomes EQUAL, then we know that the height of that
367 * subtree has not changed, so we can exit.
368 * ------------------------------------------------------------------------ **
373 subtree
= Adjust( subtree
, LorR
);
374 if( PARENT
== subtree
->gender
)
376 if( EQUAL
== subtree
->balance
)
378 LorR
= subtree
->gender
;
379 subtree
= subtree
->Link
[PARENT
];
384 static ubi_avlNodePtr
Debalance( ubi_avlNodePtr Root
,
385 ubi_avlNodePtr subtree
,
387 /* ------------------------------------------------------------------------ **
388 * Rebalance the tree following a deletion.
390 * Input: Root - A pointer to the root node of the whole tree.
391 * subtree - A pointer to the node who's child has just "left the
393 * LorR - Gender of the child that left.
395 * Output: A pointer to the (possibly new) root of the AVL tree.
396 * Rebalancing the tree moves nodes around a bit, so the node
397 * that *was* the root, may not be the root when we're finished.
399 * Notes: Debalance() is subtly different from Rebalance() (above) in
401 * * When it calls Adjust(), it passes the *opposite* of LorR.
402 * This is because LorR, as passed into Debalance() indicates
403 * the shorter subtree. As we move up the tree, LorR is
404 * assigned the gender of the node that we are leaving (i.e.,
405 * the subtree that we just rebalanced).
406 * * We know that a subtree has not changed height if the
407 * balance becomes LEFT or RIGHT. This is the *opposite* of
408 * what happens in Rebalance().
409 * ------------------------------------------------------------------------ **
414 subtree
= Adjust( subtree
, RevWay(LorR
) );
415 if( PARENT
== subtree
->gender
)
417 if( EQUAL
!= subtree
->balance
)
419 LorR
= subtree
->gender
;
420 subtree
= subtree
->Link
[PARENT
];
426 /* -------------------------------------------------------------------------- **
427 * The next two functions are used for general tree manipulation. They are
428 * each slightly different from their ubi_BinTree counterparts.
429 * -------------------------------------------------------------------------- **
432 static void ReplaceNode( ubi_avlNodePtr
*parent
,
433 ubi_avlNodePtr oldnode
,
434 ubi_avlNodePtr newnode
)
435 /* ------------------------------------------------------------------------ **
436 * Remove node oldnode from the tree, replacing it with node newnode.
439 * parent - A pointer to he parent pointer of the node to be
440 * replaced. <parent> may point to the Link[] field of
441 * a parent node, or it may indicate the root pointer at
442 * the top of the tree.
443 * oldnode - A pointer to the node that is to be replaced.
444 * newnode - A pointer to the node that is to be installed in the
445 * place of <*oldnode>.
447 * Notes: Don't forget to free oldnode.
448 * The only difference between this function and the ubi_bt
449 * version is that the node size is sizeof( ubi_avlNode ), not
450 * sizeof( ubi_btNode ).
451 * ------------------------------------------------------------------------ **
455 register int avlNodeSize
= sizeof( ubi_avlNode
);
457 for( i
= 0; i
< avlNodeSize
; i
++ )
458 ((unsigned char *)newnode
)[i
] = ((unsigned char *)oldnode
)[i
];
461 if(oldnode
->Link
[LEFT
] )
462 (oldnode
->Link
[LEFT
])->Link
[PARENT
] = newnode
;
463 if(oldnode
->Link
[RIGHT
] )
464 (oldnode
->Link
[RIGHT
])->Link
[PARENT
] = newnode
;
467 static void SwapNodes( ubi_btRootPtr RootPtr
,
468 ubi_avlNodePtr Node1
,
469 ubi_avlNodePtr Node2
)
470 /* ------------------------------------------------------------------------ **
471 * This function swaps two nodes in the tree. Node1 will take the place of
472 * Node2, and Node2 will fill in the space left vacant by Node 1.
475 * RootPtr - pointer to the tree header structure for this tree.
477 * > These are the two nodes which are to be swapped.
481 * This function does a three step swap, using a dummy node as a place
482 * holder. This function is used by ubi_avlRemove().
483 * The only difference between this function and its ubi_bt counterpart
484 * is that the nodes are ubi_avlNodes, not ubi_btNodes.
485 * ------------------------------------------------------------------------ **
488 ubi_avlNodePtr
*Parent
;
490 ubi_avlNodePtr dummy_p
= &dummy
;
492 if( Node1
->Link
[PARENT
] )
493 Parent
= &((Node1
->Link
[PARENT
])->Link
[Node1
->gender
]);
495 Parent
= (ubi_avlNodePtr
*)&(RootPtr
->root
);
496 ReplaceNode( Parent
, Node1
, dummy_p
);
498 if( Node2
->Link
[PARENT
] )
499 Parent
= &((Node2
->Link
[PARENT
])->Link
[Node2
->gender
]);
501 Parent
= (ubi_avlNodePtr
*)&(RootPtr
->root
);
502 ReplaceNode( Parent
, Node2
, Node1
);
504 if( dummy_p
->Link
[PARENT
] )
505 Parent
= &((dummy_p
->Link
[PARENT
])->Link
[dummy_p
->gender
]);
507 Parent
= (ubi_avlNodePtr
*)&(RootPtr
->root
);
508 ReplaceNode( Parent
, dummy_p
, Node2
);
512 /* ========================================================================== **
513 * Public, exported (ie. not static-ly declared) functions...
514 * -------------------------------------------------------------------------- **
517 ubi_avlNodePtr
ubi_avlInitNode( ubi_avlNodePtr NodePtr
)
518 /* ------------------------------------------------------------------------ **
519 * Initialize a tree node.
521 * Input: NodePtr - pointer to a ubi_btNode structure to be
523 * Output: a pointer to the initialized ubi_avlNode structure (ie. the
524 * same as the input pointer).
525 * ------------------------------------------------------------------------ **
528 (void)ubi_btInitNode( (ubi_btNodePtr
)NodePtr
);
529 NodePtr
->balance
= EQUAL
;
531 } /* ubi_avlInitNode */
533 ubi_trBool
ubi_avlInsert( ubi_btRootPtr RootPtr
,
534 ubi_avlNodePtr NewNode
,
535 ubi_btItemPtr ItemPtr
,
536 ubi_avlNodePtr
*OldNode
)
537 /* ------------------------------------------------------------------------ **
538 * This function uses a non-recursive algorithm to add a new element to
541 * Input: RootPtr - a pointer to the ubi_btRoot structure that indicates
542 * the root of the tree to which NewNode is to be added.
543 * NewNode - a pointer to an ubi_avlNode structure that is NOT
545 * ItemPtr - A pointer to the sort key that is stored within
546 * *NewNode. ItemPtr MUST point to information stored
547 * in *NewNode or an EXACT DUPLICATE. The key data
548 * indicated by ItemPtr is used to place the new node
550 * OldNode - a pointer to an ubi_btNodePtr. When searching
551 * the tree, a duplicate node may be found. If
552 * duplicates are allowed, then the new node will
553 * be simply placed into the tree. If duplicates
554 * are not allowed, however, then one of two things
556 * 1) if overwritting *is not* allowed, this
557 * function will return FALSE (indicating that
558 * the new node could not be inserted), and
559 * *OldNode will point to the duplicate that is
561 * 2) if overwritting *is* allowed, then this
562 * function will swap **OldNode for *NewNode.
563 * In this case, *OldNode will point to the node
564 * that was removed (thus allowing you to free
566 * ** If you are using overwrite mode, ALWAYS **
567 * ** check the return value of this parameter! **
568 * Note: You may pass NULL in this parameter, the
569 * function knows how to cope. If you do this,
570 * however, there will be no way to return a
571 * pointer to an old (ie. replaced) node (which is
572 * a problem if you are using overwrite mode).
574 * Output: a boolean value indicating success or failure. The function
575 * will return FALSE if the node could not be added to the tree.
576 * Such failure will only occur if duplicates are not allowed,
577 * nodes cannot be overwritten, AND a duplicate key was found
579 * ------------------------------------------------------------------------ **
582 ubi_avlNodePtr OtherP
;
584 if( !(OldNode
) ) OldNode
= &OtherP
;
585 if( ubi_btInsert( RootPtr
,
586 (ubi_btNodePtr
)NewNode
,
588 (ubi_btNodePtr
*)OldNode
) )
591 NewNode
->balance
= (*OldNode
)->balance
;
594 NewNode
->balance
= EQUAL
;
595 RootPtr
->root
= (ubi_btNodePtr
)Rebalance( (ubi_avlNodePtr
)RootPtr
->root
,
596 NewNode
->Link
[PARENT
],
599 return( ubi_trTRUE
);
601 return( ubi_trFALSE
); /* Failure: could not replace an existing node. */
602 } /* ubi_avlInsert */
604 ubi_avlNodePtr
ubi_avlRemove( ubi_btRootPtr RootPtr
,
605 ubi_avlNodePtr DeadNode
)
606 /* ------------------------------------------------------------------------ **
607 * This function removes the indicated node from the tree, after which the
608 * tree is rebalanced.
610 * Input: RootPtr - A pointer to the header of the tree that contains
611 * the node to be removed.
612 * DeadNode - A pointer to the node that will be removed.
614 * Output: This function returns a pointer to the node that was removed
615 * from the tree (ie. the same as DeadNode).
617 * Note: The node MUST be in the tree indicated by RootPtr. If not,
618 * strange and evil things will happen to your trees.
619 * ------------------------------------------------------------------------ **
625 /* if the node has both left and right subtrees, then we have to swap
626 * it with another node.
628 if( (DeadNode
->Link
[LEFT
]) && (DeadNode
->Link
[RIGHT
]) )
629 SwapNodes( RootPtr
, DeadNode
, ubi_trPrev( DeadNode
) );
631 /* The parent of the node to be deleted may be another node, or it may be
632 * the root of the tree. Since we're not sure, it's best just to have
633 * a pointer to the parent pointer, whatever it is.
635 if( DeadNode
->Link
[PARENT
] )
636 parentp
= (ubi_btNodePtr
*)
637 &((DeadNode
->Link
[PARENT
])->Link
[(DeadNode
->gender
)]);
639 parentp
= &( RootPtr
->root
);
641 /* Now link the parent to the only grand-child. Patch up the gender and
642 * such, and rebalance.
644 if( EQUAL
== DeadNode
->balance
)
648 p
= (ubi_btNodePtr
)(DeadNode
->Link
[(DeadNode
->balance
)]);
649 p
->Link
[PARENT
] = (ubi_btNodePtr
)DeadNode
->Link
[PARENT
];
650 p
->gender
= DeadNode
->gender
;
653 RootPtr
->root
= (ubi_btNodePtr
)Debalance( (ubi_avlNodePtr
)RootPtr
->root
,
654 DeadNode
->Link
[PARENT
],
659 } /* ubi_avlRemove */
661 int ubi_avlModuleID( int size
, char *list
[] )
662 /* ------------------------------------------------------------------------ **
663 * Returns a set of strings that identify the module.
665 * Input: size - The number of elements in the array <list>.
666 * list - An array of pointers of type (char *). This array
667 * should, initially, be empty. This function will fill
668 * in the array with pointers to strings.
669 * Output: The number of elements of <list> that were used. If this value
670 * is less than <size>, the values of the remaining elements are
673 * Notes: Please keep in mind that the pointers returned indicate strings
674 * stored in static memory. Don't free() them, don't write over
675 * them, etc. Just read them.
676 * ------------------------------------------------------------------------ **
683 return( 1 + ubi_btModuleID( --size
, &(list
[1]) ) );
687 } /* ubi_avlModuleID */
689 /* ============================== The End ============================== */