00001 /* ========================================================================== ** 00002 * $Id$ 00003 * 00004 * ubi_SplayTree.c 00005 * 00006 * Copyright (C) 1993-1998 by Christopher R. Hertel 00007 * 00008 * Email: crh@ubiqx.mn.org 00009 * -------------------------------------------------------------------------- ** 00010 * 00011 * This module implements "splay" trees. Splay trees are binary trees 00012 * that are rearranged (splayed) whenever a node is accessed. The 00013 * splaying process *tends* to make the tree bushier (improves balance), 00014 * and the nodes that are accessed most frequently *tend* to be closer to 00015 * the top. 00016 * 00017 * References: "Self-Adjusting Binary Search Trees", by Daniel Sleator and 00018 * Robert Tarjan. Journal of the Association for Computing 00019 * Machinery Vol 32, No. 3, July 1985 pp. 652-686 00020 * 00021 * See also: http://www.cs.cmu.edu/~sleator/ 00022 * 00023 * -------------------------------------------------------------------------- ** 00024 * 00025 * This library is free software; you can redistribute it and/or 00026 * modify it under the terms of the GNU Library General Public 00027 * License as published by the Free Software Foundation; either 00028 * version 2 of the License, or (at your option) any later version. 00029 * 00030 * This library is distributed in the hope that it will be useful, 00031 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00032 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00033 * Library General Public License for more details. 00034 * 00035 * You should have received a copy of the GNU Library General Public 00036 * License along with this library; if not, write to the Free 00037 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00038 * 00039 * ========================================================================== ** 00040 */ 00041 00042 #ifdef HAVE_CONFIG_H 00043 #include "config.h" 00044 #endif 00045 00046 #include "ubi_SplayTree.h" /* Header for THIS module. */ 00047 00048 /* ========================================================================== ** 00049 * Static data. 00050 */ 00051 00052 static char ModuleID[] = "ubi_SplayTree\n\ 00053 \t$Revision$\n\ 00054 \t$Date$\n\ 00055 \t$Author$\n"; 00056 00057 00058 /* ========================================================================== ** 00059 * Private functions... 00060 */ 00061 /* This is no longer private */ 00062 void Rotate( ubi_btNodePtr p ) 00063 /* ------------------------------------------------------------------------ ** 00064 * This function performs a single rotation, moving node *p up one level 00065 * in the tree. 00066 * 00067 * Input: p - a pointer to an ubi_btNode in a tree. 00068 * 00069 * Output: None. 00070 * 00071 * Notes: This implements a single rotation in either direction (left 00072 * or right). This is the basic building block of all splay 00073 * tree rotations. 00074 * ------------------------------------------------------------------------ ** 00075 */ 00076 { 00077 ubi_btNodePtr parentp; 00078 ubi_btNodePtr tmp; 00079 char way; 00080 char revway; 00081 00082 parentp = p->Link[ubi_trPARENT]; /* Find parent. */ 00083 00084 if( parentp ) /* If no parent, then we're already the root. */ 00085 { 00086 way = p->gender; 00087 revway = ubi_trRevWay(way); 00088 tmp = p->Link[(int)revway]; 00089 00090 parentp->Link[(int)way] = tmp; 00091 if( tmp ) 00092 { 00093 tmp->Link[ubi_trPARENT] = parentp; 00094 tmp->gender = way; 00095 } 00096 00097 tmp = parentp->Link[ubi_trPARENT]; 00098 p->Link[ubi_trPARENT] = tmp; 00099 p->gender = parentp->gender; 00100 if( tmp ) 00101 tmp->Link[(int)(p->gender)] = p; 00102 00103 parentp->Link[ubi_trPARENT] = p; 00104 parentp->gender = revway; 00105 p->Link[(int)revway] = parentp; 00106 } 00107 } /* Rotate */ 00108 00109 static ubi_btNodePtr Splay( ubi_btNodePtr SplayWithMe ) 00110 /* ------------------------------------------------------------------------ ** 00111 * Move the node indicated by SplayWithMe to the root of the tree by 00112 * splaying the tree. 00113 * 00114 * Input: SplayWithMe - A pointer to an ubi_btNode within a tree. 00115 * 00116 * Output: A pointer to the root of the splay tree (i.e., the same as 00117 * SplayWithMe). 00118 * ------------------------------------------------------------------------ ** 00119 */ 00120 { 00121 ubi_btNodePtr parent; 00122 00123 while( NULL != (parent = SplayWithMe->Link[ubi_trPARENT]) ) 00124 { 00125 if( parent->gender == SplayWithMe->gender ) /* Zig-Zig */ 00126 Rotate( parent ); 00127 else 00128 { 00129 if( ubi_trEQUAL != parent->gender ) /* Zig-Zag */ 00130 Rotate( SplayWithMe ); 00131 } 00132 Rotate( SplayWithMe ); /* Zig */ 00133 } /* while */ 00134 return( SplayWithMe ); 00135 } /* Splay */ 00136 00137 /* ========================================================================== ** 00138 * Exported utilities. 00139 */ 00140 00141 ubi_trBool ubi_sptInsert( ubi_btRootPtr RootPtr, 00142 ubi_btNodePtr NewNode, 00143 ubi_btItemPtr ItemPtr, 00144 ubi_btNodePtr *OldNode ) 00145 /* ------------------------------------------------------------------------ ** 00146 * This function uses a non-recursive algorithm to add a new element to the 00147 * splay tree. 00148 * 00149 * Input: RootPtr - a pointer to the ubi_btRoot structure that indicates 00150 * the root of the tree to which NewNode is to be added. 00151 * NewNode - a pointer to an ubi_btNode structure that is NOT 00152 * part of any tree. 00153 * ItemPtr - A pointer to the sort key that is stored within 00154 * *NewNode. ItemPtr MUST point to information stored 00155 * in *NewNode or an EXACT DUPLICATE. The key data 00156 * indicated by ItemPtr is used to place the new node 00157 * into the tree. 00158 * OldNode - a pointer to an ubi_btNodePtr. When searching 00159 * the tree, a duplicate node may be found. If 00160 * duplicates are allowed, then the new node will 00161 * be simply placed into the tree. If duplicates 00162 * are not allowed, however, then one of two things 00163 * may happen. 00164 * 1) if overwritting *is not* allowed, this 00165 * function will return FALSE (indicating that 00166 * the new node could not be inserted), and 00167 * *OldNode will point to the duplicate that is 00168 * still in the tree. 00169 * 2) if overwritting *is* allowed, then this 00170 * function will swap **OldNode for *NewNode. 00171 * In this case, *OldNode will point to the node 00172 * that was removed (thus allowing you to free 00173 * the node). 00174 * ** If you are using overwrite mode, ALWAYS ** 00175 * ** check the return value of this parameter! ** 00176 * Note: You may pass NULL in this parameter, the 00177 * function knows how to cope. If you do this, 00178 * however, there will be no way to return a 00179 * pointer to an old (ie. replaced) node (which is 00180 * a problem if you are using overwrite mode). 00181 * 00182 * Output: a boolean value indicating success or failure. The function 00183 * will return FALSE if the node could not be added to the tree. 00184 * Such failure will only occur if duplicates are not allowed, 00185 * nodes cannot be overwritten, AND a duplicate key was found 00186 * within the tree. 00187 * ------------------------------------------------------------------------ ** 00188 */ 00189 { 00190 ubi_btNodePtr OtherP; 00191 00192 if( !(OldNode) ) 00193 OldNode = &OtherP; 00194 00195 if( ubi_btInsert( RootPtr, NewNode, ItemPtr, OldNode ) ) 00196 { 00197 RootPtr->root = Splay( NewNode ); 00198 return( ubi_trTRUE ); 00199 } 00200 00201 /* Splay the unreplacable, duplicate keyed, unique, old node. */ 00202 RootPtr->root = Splay( (*OldNode) ); 00203 return( ubi_trFALSE ); 00204 } /* ubi_sptInsert */ 00205 00206 ubi_btNodePtr ubi_sptRemove( ubi_btRootPtr RootPtr, ubi_btNodePtr DeadNode ) 00207 /* ------------------------------------------------------------------------ ** 00208 * This function removes the indicated node from the tree. 00209 * 00210 * Input: RootPtr - A pointer to the header of the tree that contains 00211 * the node to be removed. 00212 * DeadNode - A pointer to the node that will be removed. 00213 * 00214 * Output: This function returns a pointer to the node that was removed 00215 * from the tree (ie. the same as DeadNode). 00216 * 00217 * Note: The node MUST be in the tree indicated by RootPtr. If not, 00218 * strange and evil things will happen to your trees. 00219 * ------------------------------------------------------------------------ ** 00220 */ 00221 { 00222 ubi_btNodePtr p; 00223 00224 (void)Splay( DeadNode ); /* Move dead node to root. */ 00225 if( NULL != (p = DeadNode->Link[ubi_trLEFT]) ) 00226 { /* If left subtree exists... */ 00227 ubi_btNodePtr q = DeadNode->Link[ubi_trRIGHT]; 00228 00229 p->Link[ubi_trPARENT] = NULL; /* Left subtree node becomes root.*/ 00230 p->gender = ubi_trPARENT; 00231 p = ubi_btLast( p ); /* Find rightmost left node... */ 00232 p->Link[ubi_trRIGHT] = q; /* ...attach right tree. */ 00233 if( q ) 00234 q->Link[ubi_trPARENT] = p; 00235 RootPtr->root = Splay( p ); /* Resplay at p. */ 00236 } 00237 else 00238 { 00239 if( NULL != (p = DeadNode->Link[ubi_trRIGHT]) ) 00240 { /* No left, but right subtree exists... */ 00241 p->Link[ubi_trPARENT] = NULL; /* Right subtree root becomes... */ 00242 p->gender = ubi_trPARENT; /* ...overall tree root. */ 00243 RootPtr->root = p; 00244 } 00245 else 00246 RootPtr->root = NULL; /* No subtrees => empty tree. */ 00247 } 00248 00249 (RootPtr->count)--; /* Decrement node count. */ 00250 return( DeadNode ); /* Return pointer to pruned node. */ 00251 } /* ubi_sptRemove */ 00252 00253 ubi_btNodePtr ubi_sptLocate( ubi_btRootPtr RootPtr, 00254 ubi_btItemPtr FindMe, 00255 ubi_trCompOps CompOp ) 00256 /* ------------------------------------------------------------------------ ** 00257 * The purpose of ubi_btLocate() is to find a node or set of nodes given 00258 * a target value and a "comparison operator". The Locate() function is 00259 * more flexible and (in the case of trees that may contain dupicate keys) 00260 * more precise than the ubi_btFind() function. The latter is faster, 00261 * but it only searches for exact matches and, if the tree contains 00262 * duplicates, Find() may return a pointer to any one of the duplicate- 00263 * keyed records. 00264 * 00265 * Input: 00266 * RootPtr - A pointer to the header of the tree to be searched. 00267 * FindMe - An ubi_btItemPtr that indicates the key for which to 00268 * search. 00269 * CompOp - One of the following: 00270 * CompOp Return a pointer to the node with 00271 * ------ --------------------------------- 00272 * ubi_trLT - the last key value that is less 00273 * than FindMe. 00274 * ubi_trLE - the first key matching FindMe, or 00275 * the last key that is less than 00276 * FindMe. 00277 * ubi_trEQ - the first key matching FindMe. 00278 * ubi_trGE - the first key matching FindMe, or the 00279 * first key greater than FindMe. 00280 * ubi_trGT - the first key greater than FindMe. 00281 * Output: 00282 * A pointer to the node matching the criteria listed above under 00283 * CompOp, or NULL if no node matched the criteria. 00284 * 00285 * Notes: 00286 * In the case of trees with duplicate keys, Locate() will behave as 00287 * follows: 00288 * 00289 * Find: 3 Find: 3 00290 * Keys: 1 2 2 2 3 3 3 3 3 4 4 Keys: 1 1 2 2 2 4 4 5 5 5 6 00291 * ^ ^ ^ ^ ^ 00292 * LT EQ GT LE GE 00293 * 00294 * That is, when returning a pointer to a node with a key that is LESS 00295 * THAN the target key (FindMe), Locate() will return a pointer to the 00296 * LAST matching node. 00297 * When returning a pointer to a node with a key that is GREATER 00298 * THAN the target key (FindMe), Locate() will return a pointer to the 00299 * FIRST matching node. 00300 * 00301 * See Also: ubi_btFind(), ubi_btFirstOf(), ubi_btLastOf(). 00302 * ------------------------------------------------------------------------ ** 00303 */ 00304 { 00305 ubi_btNodePtr p; 00306 00307 p = ubi_btLocate( RootPtr, FindMe, CompOp ); 00308 if( p ) 00309 RootPtr->root = Splay( p ); 00310 return( p ); 00311 } /* ubi_sptLocate */ 00312 00313 ubi_btNodePtr ubi_sptFind( ubi_btRootPtr RootPtr, 00314 ubi_btItemPtr FindMe ) 00315 /* ------------------------------------------------------------------------ ** 00316 * This function performs a non-recursive search of a tree for any node 00317 * matching a specific key. 00318 * 00319 * Input: 00320 * RootPtr - a pointer to the header of the tree to be searched. 00321 * FindMe - a pointer to the key value for which to search. 00322 * 00323 * Output: 00324 * A pointer to a node with a key that matches the key indicated by 00325 * FindMe, or NULL if no such node was found. 00326 * 00327 * Note: In a tree that allows duplicates, the pointer returned *might 00328 * not* point to the (sequentially) first occurance of the 00329 * desired key. In such a tree, it may be more useful to use 00330 * ubi_sptLocate(). 00331 * ------------------------------------------------------------------------ ** 00332 */ 00333 { 00334 ubi_btNodePtr p; 00335 00336 p = ubi_btFind( RootPtr, FindMe ); 00337 if( p ) 00338 RootPtr->root = Splay( p ); 00339 return( p ); 00340 } /* ubi_sptFind */ 00341 00342 void ubi_sptSplay( ubi_btRootPtr RootPtr, 00343 ubi_btNodePtr SplayMe ) 00344 /* ------------------------------------------------------------------------ ** 00345 * This function allows you to splay the tree at a given node, thus moving 00346 * the node to the top of the tree. 00347 * 00348 * Input: 00349 * RootPtr - a pointer to the header of the tree to be splayed. 00350 * SplayMe - a pointer to a node within the tree. This will become 00351 * the new root node. 00352 * Output: None. 00353 * 00354 * Notes: This is an uncharacteristic function for this group of modules 00355 * in that it provides access to the internal balancing routines, 00356 * which would normally be hidden. 00357 * Splaying the tree will not damage it (assuming that I've done 00358 * *my* job), but there is overhead involved. I don't recommend 00359 * that you use this function unless you understand the underlying 00360 * Splay Tree principles involved. 00361 * ------------------------------------------------------------------------ ** 00362 */ 00363 { 00364 RootPtr->root = Splay( SplayMe ); 00365 } /* ubi_sptSplay */ 00366 00367 int ubi_sptModuleID( int size, char *list[] ) 00368 /* ------------------------------------------------------------------------ ** 00369 * Returns a set of strings that identify the module. 00370 * 00371 * Input: size - The number of elements in the array <list>. 00372 * list - An array of pointers of type (char *). This array 00373 * should, initially, be empty. This function will fill 00374 * in the array with pointers to strings. 00375 * Output: The number of elements of <list> that were used. If this value 00376 * is less than <size>, the values of the remaining elements are 00377 * not guaranteed. 00378 * 00379 * Notes: Please keep in mind that the pointers returned indicate strings 00380 * stored in static memory. Don't free() them, don't write over 00381 * them, etc. Just read them. 00382 * ------------------------------------------------------------------------ ** 00383 */ 00384 { 00385 if( size > 0 ) 00386 { 00387 list[0] = ModuleID; 00388 if( size > 1 ) 00389 return( 1 + ubi_btModuleID( --size, &(list[1]) ) ); 00390 return( 1 ); 00391 } 00392 return( 0 ); 00393 } /* ubi_sptModuleID */ 00394 00395 /* ================================ The End ================================= */ 00396
1.4.2