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