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