1/* ========================================================================== ** 2 * ubi_SplayTree.c 3 * 4 * Copyright (C) 1993-1998 by Christopher R. Hertel 5 * 6 * Email: crh@ubiqx.mn.org 7 * -------------------------------------------------------------------------- ** 8 * 9 * This module implements "splay" trees. Splay trees are binary trees 10 * that are rearranged (splayed) whenever a node is accessed. The 11 * splaying process *tends* to make the tree bushier (improves balance), 12 * and the nodes that are accessed most frequently *tend* to be closer to 13 * the top. 14 * 15 * References: "Self-Adjusting Binary Search Trees", by Daniel Sleator and 16 * Robert Tarjan. Journal of the Association for Computing 17 * Machinery Vol 32, No. 3, July 1985 pp. 652-686 18 * 19 * See also: http://www.cs.cmu.edu/~sleator/ 20 * 21 * -------------------------------------------------------------------------- ** 22 * 23 * This library is free software; you can redistribute it and/or 24 * modify it under the terms of the GNU Library General Public 25 * License as published by the Free Software Foundation; either 26 * version 2 of the License, or (at your option) any later version. 27 * 28 * This library is distributed in the hope that it will be useful, 29 * but WITHOUT ANY WARRANTY; without even the implied warranty of 30 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 31 * Library General Public License for more details. 32 * 33 * You should have received a copy of the GNU Library General Public 34 * License along with this library; if not, write to the Free 35 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 36 * 37 * -------------------------------------------------------------------------- ** 38 * 39 * $Log: ubi_SplayTree.c,v $ 40 * Revision 4.5 2000/01/08 23:26:49 crh 41 * Added ubi_trSplay() macro, which does a type cast for us. 42 * 43 * Revision 4.4 1998/06/04 21:29:27 crh 44 * Upper-cased defined constants (eg UBI_BINTREE_H) in some header files. 45 * This is more "standard", and is what people expect. Weird, eh? 46 * 47 * Revision 4.3 1998/06/03 17:45:05 crh 48 * Further fiddling with sys_include.h. It's now in ubi_BinTree.h which is 49 * included by all of the binary tree files. 50 * 51 * Also fixed some warnings produced by lint on Irix 6.2, which doesn't seem 52 * to like syntax like this: 53 * 54 * if( (a = b) ) 55 * 56 * The fix was to change lines like the above to: 57 * 58 * if( 0 != (a=b) ) 59 * 60 * Which means the same thing. 61 * 62 * Reminder: Some of the ubi_tr* macros in ubi_BinTree.h are redefined in 63 * ubi_AVLtree.h and ubi_SplayTree.h. This allows easy swapping 64 * of tree types by simply changing a header. Unfortunately, the 65 * macro redefinitions in ubi_AVLtree.h and ubi_SplayTree.h will 66 * conflict if used together. You must either choose a single tree 67 * type, or use the underlying function calls directly. Compare 68 * the two header files for more information. 69 * 70 * Revision 4.2 1998/06/02 01:29:14 crh 71 * Changed ubi_null.h to sys_include.h to make it more generic. 72 * 73 * Revision 4.1 1998/05/20 04:37:54 crh 74 * The C file now includes ubi_null.h. See ubi_null.h for more info. 75 * 76 * Revision 4.0 1998/03/10 03:41:33 crh 77 * Minor comment changes. The revision number is now 4.0 to match the 78 * BinTree and AVLtree modules. 79 * 80 * Revision 2.7 1998/01/24 06:37:08 crh 81 * Added a URL for more information. 82 * 83 * Revision 2.6 1997/12/23 04:01:12 crh 84 * In this version, all constants & macros defined in the header file have 85 * the ubi_tr prefix. Also cleaned up anything that gcc complained about 86 * when run with '-pedantic -fsyntax-only -Wall'. 87 * 88 * Revision 2.5 1997/07/26 04:15:42 crh 89 * + Cleaned up a few minor syntax annoyances that gcc discovered for me. 90 * + Changed ubi_TRUE and ubi_FALSE to ubi_trTRUE and ubi_trFALSE. 91 * 92 * Revision 2.4 1997/06/03 04:42:21 crh 93 * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid causing 94 * problems. 95 * 96 * Revision 2.3 1995/10/03 22:19:07 CRH 97 * Ubisized! 98 * Also, added the function ubi_sptSplay(). 99 * 100 * Revision 2.1 95/03/09 23:54:42 CRH 101 * Added the ModuleID static string and function. These modules are now 102 * self-identifying. 103 * 104 * Revision 2.0 95/02/27 22:34:46 CRH 105 * This module was updated to match the interface changes made to the 106 * ubi_BinTree module. In particular, the interface to the Locate() function 107 * has changed. See ubi_BinTree for more information on changes and new 108 * functions. 109 * 110 * The revision number was also upped to match ubi_BinTree. 111 * 112 * Revision 1.1 93/10/18 20:35:16 CRH 113 * I removed the hard-coded logical device names from the include file 114 * specifications. CRH 115 * 116 * Revision 1.0 93/10/15 23:00:15 CRH 117 * With this revision, I have added a set of #define's that provide a single, 118 * standard API to all existing tree modules. Until now, each of the three 119 * existing modules had a different function and typedef prefix, as follows: 120 * 121 * Module Prefix 122 * ubi_BinTree ubi_bt 123 * ubi_AVLtree ubi_avl 124 * ubi_SplayTree ubi_spt 125 * 126 * To further complicate matters, only those portions of the base module 127 * (ubi_BinTree) that were superceeded in the new module had the new names. 128 * For example, if you were using ubi_SplayTree, the locate function was 129 * called "ubi_sptLocate", but the next and previous functions remained 130 * "ubi_btNext" and "ubi_btPrev". 131 * 132 * This was not too terrible if you were familiar with the modules and knew 133 * exactly which tree model you wanted to use. If you wanted to be able to 134 * change modules (for speed comparisons, etc), things could get messy very 135 * quickly. 136 * 137 * So, I have added a set of defined names that get redefined in any of the 138 * descendant modules. To use this standardized interface in your code, 139 * simply replace all occurances of "ubi_bt", "ubi_avl", and "ubi_spt" with 140 * "ubi_tr". The "ubi_tr" names will resolve to the correct function or 141 * datatype names for the module that you are using. Just remember to 142 * include the header for that module in your program file. Because these 143 * names are handled by the preprocessor, there is no added run-time 144 * overhead. 145 * 146 * Note that the original names do still exist, and can be used if you wish 147 * to write code directly to a specific module. This should probably only be 148 * done if you are planning to implement a new descendant type, such as 149 * red/black trees. CRH 150 * 151 * Revision 0.1 93/04/25 22:03:32 CRH 152 * Simply changed the <exec/types.h> #include reference the .c file to 153 * use <stdlib.h> instead. The latter is portable, the former is not. 154 * 155 * Revision 0.0 93/04/21 23:05:52 CRH 156 * Initial version, written by Christopher R. Hertel. 157 * This module implements Splay Trees using the ubi_BinTree module as a basis. 158 * 159 * ========================================================================== ** 160 */ 161 162#include "stdafx.h" 163 164#include "ubi_SplayTree.h" /* Header for THIS module. */ 165 166/* ========================================================================== ** 167 * Static data. 168 */ 169 170static char ModuleID[] = "ubi_SplayTree\n\ 171\t$Revision: 4.5 $\n\ 172\t$Date: 2000/01/08 23:26:49 $\n\ 173\t$Author: crh $\n"; 174 175 176/* ========================================================================== ** 177 * Private functions... 178 */ 179 180static void Rotate( ubi_btNodePtr p ) 181 /* ------------------------------------------------------------------------ ** 182 * This function performs a single rotation, moving node *p up one level 183 * in the tree. 184 * 185 * Input: p - a pointer to an ubi_btNode in a tree. 186 * 187 * Output: None. 188 * 189 * Notes: This implements a single rotation in either direction (left 190 * or right). This is the basic building block of all splay 191 * tree rotations. 192 * ------------------------------------------------------------------------ ** 193 */ 194 { 195 ubi_btNodePtr parentp; 196 ubi_btNodePtr tmp; 197 char way; 198 char revway; 199 200 parentp = p->Link[ubi_trPARENT]; /* Find parent. */ 201 202 if( parentp ) /* If no parent, then we're already the root. */ 203 { 204 way = p->gender; 205 revway = ubi_trRevWay(way); 206 tmp = p->Link[(int)revway]; 207 208 parentp->Link[(int)way] = tmp; 209 if( tmp ) 210 { 211 tmp->Link[ubi_trPARENT] = parentp; 212 tmp->gender = way; 213 } 214 215 tmp = parentp->Link[ubi_trPARENT]; 216 p->Link[ubi_trPARENT] = tmp; 217 p->gender = parentp->gender; 218 if( tmp ) 219 tmp->Link[(int)(p->gender)] = p; 220 221 parentp->Link[ubi_trPARENT] = p; 222 parentp->gender = revway; 223 p->Link[(int)revway] = parentp; 224 } 225 } /* Rotate */ 226 227static ubi_btNodePtr Splay( ubi_btNodePtr SplayWithMe ) 228 /* ------------------------------------------------------------------------ ** 229 * Move the node indicated by SplayWithMe to the root of the tree by 230 * splaying the tree. 231 * 232 * Input: SplayWithMe - A pointer to an ubi_btNode within a tree. 233 * 234 * Output: A pointer to the root of the splay tree (i.e., the same as 235 * SplayWithMe). 236 * ------------------------------------------------------------------------ ** 237 */ 238 { 239 ubi_btNodePtr parent; 240 241 while( NULL != (parent = SplayWithMe->Link[ubi_trPARENT]) ) 242 { 243 if( parent->gender == SplayWithMe->gender ) /* Zig-Zig */ 244 Rotate( parent ); 245 else 246 { 247 if( ubi_trEQUAL != parent->gender ) /* Zig-Zag */ 248 Rotate( SplayWithMe ); 249 } 250 Rotate( SplayWithMe ); /* Zig */ 251 } /* while */ 252 return( SplayWithMe ); 253 } /* Splay */ 254 255/* ========================================================================== ** 256 * Exported utilities. 257 */ 258 259ubi_trBool ubi_sptInsert( ubi_btRootPtr RootPtr, 260 ubi_btNodePtr NewNode, 261 ubi_btItemPtr ItemPtr, 262 ubi_btNodePtr *OldNode ) 263 /* ------------------------------------------------------------------------ ** 264 * This function uses a non-recursive algorithm to add a new element to the 265 * splay tree. 266 * 267 * Input: RootPtr - a pointer to the ubi_btRoot structure that indicates 268 * the root of the tree to which NewNode is to be added. 269 * NewNode - a pointer to an ubi_btNode structure that is NOT 270 * part of any tree. 271 * ItemPtr - A pointer to the sort key that is stored within 272 * *NewNode. ItemPtr MUST point to information stored 273 * in *NewNode or an EXACT DUPLICATE. The key data 274 * indicated by ItemPtr is used to place the new node 275 * into the tree. 276 * OldNode - a pointer to an ubi_btNodePtr. When searching 277 * the tree, a duplicate node may be found. If 278 * duplicates are allowed, then the new node will 279 * be simply placed into the tree. If duplicates 280 * are not allowed, however, then one of two things 281 * may happen. 282 * 1) if overwritting *is not* allowed, this 283 * function will return FALSE (indicating that 284 * the new node could not be inserted), and 285 * *OldNode will point to the duplicate that is 286 * still in the tree. 287 * 2) if overwritting *is* allowed, then this 288 * function will swap **OldNode for *NewNode. 289 * In this case, *OldNode will point to the node 290 * that was removed (thus allowing you to free 291 * the node). 292 * ** If you are using overwrite mode, ALWAYS ** 293 * ** check the return value of this parameter! ** 294 * Note: You may pass NULL in this parameter, the 295 * function knows how to cope. If you do this, 296 * however, there will be no way to return a 297 * pointer to an old (ie. replaced) node (which is 298 * a problem if you are using overwrite mode). 299 * 300 * Output: a boolean value indicating success or failure. The function 301 * will return FALSE if the node could not be added to the tree. 302 * Such failure will only occur if duplicates are not allowed, 303 * nodes cannot be overwritten, AND a duplicate key was found 304 * within the tree. 305 * ------------------------------------------------------------------------ ** 306 */ 307 { 308 ubi_btNodePtr OtherP; 309 310 if( !(OldNode) ) 311 OldNode = &OtherP; 312 313 if( ubi_btInsert( RootPtr, NewNode, ItemPtr, OldNode ) ) 314 { 315 RootPtr->root = Splay( NewNode ); 316 return( ubi_trTRUE ); 317 } 318 319 /* Splay the unreplacable, duplicate keyed, unique, old node. */ 320 RootPtr->root = Splay( (*OldNode) ); 321 return( ubi_trFALSE ); 322 } /* ubi_sptInsert */ 323 324ubi_btNodePtr ubi_sptRemove( ubi_btRootPtr RootPtr, ubi_btNodePtr DeadNode ) 325 /* ------------------------------------------------------------------------ ** 326 * This function removes the indicated node from the tree. 327 * 328 * Input: RootPtr - A pointer to the header of the tree that contains 329 * the node to be removed. 330 * DeadNode - A pointer to the node that will be removed. 331 * 332 * Output: This function returns a pointer to the node that was removed 333 * from the tree (ie. the same as DeadNode). 334 * 335 * Note: The node MUST be in the tree indicated by RootPtr. If not, 336 * strange and evil things will happen to your trees. 337 * ------------------------------------------------------------------------ ** 338 */ 339 { 340 ubi_btNodePtr p; 341 342 (void)Splay( DeadNode ); /* Move dead node to root. */ 343 if( NULL != (p = DeadNode->Link[ubi_trLEFT]) ) 344 { /* If left subtree exists... */ 345 ubi_btNodePtr q = DeadNode->Link[ubi_trRIGHT]; 346 347 p->Link[ubi_trPARENT] = NULL; /* Left subtree node becomes root.*/ 348 p->gender = ubi_trPARENT; 349 p = ubi_btLast( p ); /* Find rightmost left node... */ 350 p->Link[ubi_trRIGHT] = q; /* ...attach right tree. */ 351 if( q ) 352 q->Link[ubi_trPARENT] = p; 353 RootPtr->root = Splay( p ); /* Resplay at p. */ 354 } 355 else 356 { 357 if( NULL != (p = DeadNode->Link[ubi_trRIGHT]) ) 358 { /* No left, but right subtree exists... */ 359 p->Link[ubi_trPARENT] = NULL; /* Right subtree root becomes... */ 360 p->gender = ubi_trPARENT; /* ...overall tree root. */ 361 RootPtr->root = p; 362 } 363 else 364 RootPtr->root = NULL; /* No subtrees => empty tree. */ 365 } 366 367 (RootPtr->count)--; /* Decrement node count. */ 368 return( DeadNode ); /* Return pointer to pruned node. */ 369 } /* ubi_sptRemove */ 370 371ubi_btNodePtr ubi_sptLocate( ubi_btRootPtr RootPtr, 372 ubi_btItemPtr FindMe, 373 ubi_trCompOps CompOp ) 374 /* ------------------------------------------------------------------------ ** 375 * The purpose of ubi_btLocate() is to find a node or set of nodes given 376 * a target value and a "comparison operator". The Locate() function is 377 * more flexible and (in the case of trees that may contain dupicate keys) 378 * more precise than the ubi_btFind() function. The latter is faster, 379 * but it only searches for exact matches and, if the tree contains 380 * duplicates, Find() may return a pointer to any one of the duplicate- 381 * keyed records. 382 * 383 * Input: 384 * RootPtr - A pointer to the header of the tree to be searched. 385 * FindMe - An ubi_btItemPtr that indicates the key for which to 386 * search. 387 * CompOp - One of the following: 388 * CompOp Return a pointer to the node with 389 * ------ --------------------------------- 390 * ubi_trLT - the last key value that is less 391 * than FindMe. 392 * ubi_trLE - the first key matching FindMe, or 393 * the last key that is less than 394 * FindMe. 395 * ubi_trEQ - the first key matching FindMe. 396 * ubi_trGE - the first key matching FindMe, or the 397 * first key greater than FindMe. 398 * ubi_trGT - the first key greater than FindMe. 399 * Output: 400 * A pointer to the node matching the criteria listed above under 401 * CompOp, or NULL if no node matched the criteria. 402 * 403 * Notes: 404 * In the case of trees with duplicate keys, Locate() will behave as 405 * follows: 406 * 407 * Find: 3 Find: 3 408 * Keys: 1 2 2 2 3 3 3 3 3 4 4 Keys: 1 1 2 2 2 4 4 5 5 5 6 409 * ^ ^ ^ ^ ^ 410 * LT EQ GT LE GE 411 * 412 * That is, when returning a pointer to a node with a key that is LESS 413 * THAN the target key (FindMe), Locate() will return a pointer to the 414 * LAST matching node. 415 * When returning a pointer to a node with a key that is GREATER 416 * THAN the target key (FindMe), Locate() will return a pointer to the 417 * FIRST matching node. 418 * 419 * See Also: ubi_btFind(), ubi_btFirstOf(), ubi_btLastOf(). 420 * ------------------------------------------------------------------------ ** 421 */ 422 { 423 ubi_btNodePtr p; 424 425 p = ubi_btLocate( RootPtr, FindMe, CompOp ); 426 if( p ) 427 RootPtr->root = Splay( p ); 428 return( p ); 429 } /* ubi_sptLocate */ 430 431ubi_btNodePtr ubi_sptFind( ubi_btRootPtr RootPtr, 432 ubi_btItemPtr FindMe ) 433 /* ------------------------------------------------------------------------ ** 434 * This function performs a non-recursive search of a tree for any node 435 * matching a specific key. 436 * 437 * Input: 438 * RootPtr - a pointer to the header of the tree to be searched. 439 * FindMe - a pointer to the key value for which to search. 440 * 441 * Output: 442 * A pointer to a node with a key that matches the key indicated by 443 * FindMe, or NULL if no such node was found. 444 * 445 * Note: In a tree that allows duplicates, the pointer returned *might 446 * not* point to the (sequentially) first occurance of the 447 * desired key. In such a tree, it may be more useful to use 448 * ubi_sptLocate(). 449 * ------------------------------------------------------------------------ ** 450 */ 451 { 452 ubi_btNodePtr p; 453 454 p = ubi_btFind( RootPtr, FindMe ); 455 if( p ) 456 RootPtr->root = Splay( p ); 457 return( p ); 458 } /* ubi_sptFind */ 459 460void ubi_sptSplay( ubi_btRootPtr RootPtr, 461 ubi_btNodePtr SplayMe ) 462 /* ------------------------------------------------------------------------ ** 463 * This function allows you to splay the tree at a given node, thus moving 464 * the node to the top of the tree. 465 * 466 * Input: 467 * RootPtr - a pointer to the header of the tree to be splayed. 468 * SplayMe - a pointer to a node within the tree. This will become 469 * the new root node. 470 * Output: None. 471 * 472 * Notes: This is an uncharacteristic function for this group of modules 473 * in that it provides access to the internal balancing routines, 474 * which would normally be hidden. 475 * Splaying the tree will not damage it (assuming that I've done 476 * *my* job), but there is overhead involved. I don't recommend 477 * that you use this function unless you understand the underlying 478 * Splay Tree principles involved. 479 * ------------------------------------------------------------------------ ** 480 */ 481 { 482 RootPtr->root = Splay( SplayMe ); 483 } /* ubi_sptSplay */ 484 485int ubi_sptModuleID( int size, char *list[] ) 486 /* ------------------------------------------------------------------------ ** 487 * Returns a set of strings that identify the module. 488 * 489 * Input: size - The number of elements in the array <list>. 490 * list - An array of pointers of type (char *). This array 491 * should, initially, be empty. This function will fill 492 * in the array with pointers to strings. 493 * Output: The number of elements of <list> that were used. If this value 494 * is less than <size>, the values of the remaining elements are 495 * not guaranteed. 496 * 497 * Notes: Please keep in mind that the pointers returned indicate strings 498 * stored in static memory. Don't free() them, don't write over 499 * them, etc. Just read them. 500 * ------------------------------------------------------------------------ ** 501 */ 502 { 503 if( size > 0 ) 504 { 505 list[0] = ModuleID; 506 if( size > 1 ) 507 return( 1 + ubi_btModuleID( --size, &(list[1]) ) ); 508 return( 1 ); 509 } 510 return( 0 ); 511 } /* ubi_sptModuleID */ 512 513/* ================================ The End ================================= */ 514