1 #ifndef UBI_SPLAYTREE_H
2 #define UBI_SPLAYTREE_H
3 /* ========================================================================== **
6 * Copyright (C) 1993-1998 by Christopher R. Hertel
8 * Email: crh@ubiqx.mn.org
9 * -------------------------------------------------------------------------- **
11 * This module implements "splay" trees. Splay trees are binary trees
12 * that are rearranged (splayed) whenever a node is accessed. The
13 * splaying process *tends* to make the tree bushier (improves balance),
14 * and the nodes that are accessed most frequently *tend* to be closer to
17 * References: "Self-Adjusting Binary Search Trees", by Daniel Sleator and
18 * Robert Tarjan. Journal of the Association for Computing
19 * Machinery Vol 32, No. 3, July 1985 pp. 652-686
21 * See also: http://www.cs.cmu.edu/~sleator/
23 * -------------------------------------------------------------------------- **
25 * This library is free software; you can redistribute it and/or
26 * modify it under the terms of the GNU Library General Public
27 * License as published by the Free Software Foundation; either
28 * version 2 of the License, or (at your option) any later version.
30 * This library is distributed in the hope that it will be useful,
31 * but WITHOUT ANY WARRANTY; without even the implied warranty of
32 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
33 * Library General Public License for more details.
35 * You should have received a copy of the GNU Library General Public
36 * License along with this library; if not, write to the Free
37 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
39 * -------------------------------------------------------------------------- **
41 * Log: ubi_SplayTree.h,v
42 * Revision 4.4 1998/06/04 21:29:27 crh
43 * Upper-cased defined constants (eg UBI_BINTREE_H) in some header files.
44 * This is more "standard", and is what people expect. Weird, eh?
46 * Revision 4.3 1998/06/03 17:45:05 crh
47 * Further fiddling with sys_include.h. It's now in ubi_BinTree.h which is
48 * included by all of the binary tree files.
50 * Also fixed some warnings produced by lint on Irix 6.2, which doesn't seem
51 * to like syntax like this:
55 * The fix was to change lines like the above to:
59 * Which means the same thing.
61 * Reminder: Some of the ubi_tr* macros in ubi_BinTree.h are redefined in
62 * ubi_AVLtree.h and ubi_SplayTree.h. This allows easy swapping
63 * of tree types by simply changing a header. Unfortunately, the
64 * macro redefinitions in ubi_AVLtree.h and ubi_SplayTree.h will
65 * conflict if used together. You must either choose a single tree
66 * type, or use the underlying function calls directly. Compare
67 * the two header files for more information.
69 * Revision 4.2 1998/06/02 01:29:14 crh
70 * Changed ubi_null.h to sys_include.h to make it more generic.
72 * Revision 4.1 1998/05/20 04:37:54 crh
73 * The C file now includes ubi_null.h. See ubi_null.h for more info.
75 * Revision 4.0 1998/03/10 03:40:57 crh
76 * Minor comment changes. The revision number is now 4.0 to match the
77 * BinTree and AVLtree modules.
79 * Revision 2.7 1998/01/24 06:37:57 crh
80 * Added a URL for more information.
82 * Revision 2.6 1997/12/23 04:02:20 crh
83 * In this version, all constants & macros defined in the header file have
84 * the ubi_tr prefix. Also cleaned up anything that gcc complained about
85 * when run with '-pedantic -fsyntax-only -Wall'.
87 * Revision 2.5 1997/07/26 04:15:46 crh
88 * + Cleaned up a few minor syntax annoyances that gcc discovered for me.
89 * + Changed ubi_TRUE and ubi_FALSE to ubi_trTRUE and ubi_trFALSE.
91 * Revision 2.4 1997/06/03 05:22:56 crh
92 * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid causing
95 * Revision 2.3 1995/10/03 22:19:37 CRH
97 * Also, added the function ubi_sptSplay().
99 * Revision 2.1 95/03/09 23:55:04 CRH
100 * Added the ModuleID static string and function. These modules are now
103 * Revision 2.0 95/02/27 22:34:55 CRH
104 * This module was updated to match the interface changes made to the
105 * ubi_BinTree module. In particular, the interface to the Locate() function
106 * has changed. See ubi_BinTree for more information on changes and new
109 * The revision number was also upped to match ubi_BinTree.
112 * Revision 1.0 93/10/15 22:59:36 CRH
113 * With this revision, I have added a set of #define's that provide a single,
114 * standard API to all existing tree modules. Until now, each of the three
115 * existing modules had a different function and typedef prefix, as follows:
119 * ubi_AVLtree ubi_avl
120 * ubi_SplayTree ubi_spt
122 * To further complicate matters, only those portions of the base module
123 * (ubi_BinTree) that were superceeded in the new module had the new names.
124 * For example, if you were using ubi_SplayTree, the locate function was
125 * called "ubi_sptLocate", but the next and previous functions remained
126 * "ubi_btNext" and "ubi_btPrev".
128 * This was not too terrible if you were familiar with the modules and knew
129 * exactly which tree model you wanted to use. If you wanted to be able to
130 * change modules (for speed comparisons, etc), things could get messy very
133 * So, I have added a set of defined names that get redefined in any of the
134 * descendant modules. To use this standardized interface in your code,
135 * simply replace all occurances of "ubi_bt", "ubi_avl", and "ubi_spt" with
136 * "ubi_tr". The "ubi_tr" names will resolve to the correct function or
137 * datatype names for the module that you are using. Just remember to
138 * include the header for that module in your program file. Because these
139 * names are handled by the preprocessor, there is no added run-time
142 * Note that the original names do still exist, and can be used if you wish
143 * to write code directly to a specific module. This should probably only be
144 * done if you are planning to implement a new descendant type, such as
145 * red/black trees. CRH
147 * Revision 0.0 93/04/21 23:07:13 CRH
148 * Initial version, written by Christopher R. Hertel.
149 * This module implements Splay Trees using the ubi_BinTree module as a basis.
151 * ========================================================================== **
154 #include "ubi_BinTree.h" /* Base binary tree functions, types, etc. */
156 /* ========================================================================== **
157 * Function prototypes...
160 ubi_trBool ubi_sptInsert( ubi_btRootPtr RootPtr,
161 ubi_btNodePtr NewNode,
162 ubi_btItemPtr ItemPtr,
163 ubi_btNodePtr *OldNode );
164 /* ------------------------------------------------------------------------ **
165 * This function uses a non-recursive algorithm to add a new element to the
168 * Input: RootPtr - a pointer to the ubi_btRoot structure that indicates
169 * the root of the tree to which NewNode is to be added.
170 * NewNode - a pointer to an ubi_btNode structure that is NOT
172 * ItemPtr - A pointer to the sort key that is stored within
173 * *NewNode. ItemPtr MUST point to information stored
174 * in *NewNode or an EXACT DUPLICATE. The key data
175 * indicated by ItemPtr is used to place the new node
177 * OldNode - a pointer to an ubi_btNodePtr. When searching
178 * the tree, a duplicate node may be found. If
179 * duplicates are allowed, then the new node will
180 * be simply placed into the tree. If duplicates
181 * are not allowed, however, then one of two things
183 * 1) if overwritting *is not* allowed, this
184 * function will return FALSE (indicating that
185 * the new node could not be inserted), and
186 * *OldNode will point to the duplicate that is
188 * 2) if overwritting *is* allowed, then this
189 * function will swap **OldNode for *NewNode.
190 * In this case, *OldNode will point to the node
191 * that was removed (thus allowing you to free
193 * ** If you are using overwrite mode, ALWAYS **
194 * ** check the return value of this parameter! **
195 * Note: You may pass NULL in this parameter, the
196 * function knows how to cope. If you do this,
197 * however, there will be no way to return a
198 * pointer to an old (ie. replaced) node (which is
199 * a problem if you are using overwrite mode).
201 * Output: a boolean value indicating success or failure. The function
202 * will return FALSE if the node could not be added to the tree.
203 * Such failure will only occur if duplicates are not allowed,
204 * nodes cannot be overwritten, AND a duplicate key was found
206 * ------------------------------------------------------------------------ **
209 ubi_btNodePtr ubi_sptRemove( ubi_btRootPtr RootPtr, ubi_btNodePtr DeadNode );
210 /* ------------------------------------------------------------------------ **
211 * This function removes the indicated node from the tree.
213 * Input: RootPtr - A pointer to the header of the tree that contains
214 * the node to be removed.
215 * DeadNode - A pointer to the node that will be removed.
217 * Output: This function returns a pointer to the node that was removed
218 * from the tree (ie. the same as DeadNode).
220 * Note: The node MUST be in the tree indicated by RootPtr. If not,
221 * strange and evil things will happen to your trees.
222 * ------------------------------------------------------------------------ **
225 ubi_btNodePtr ubi_sptLocate( ubi_btRootPtr RootPtr,
226 ubi_btItemPtr FindMe,
227 ubi_trCompOps CompOp );
228 /* ------------------------------------------------------------------------ **
229 * The purpose of ubi_btLocate() is to find a node or set of nodes given
230 * a target value and a "comparison operator". The Locate() function is
231 * more flexible and (in the case of trees that may contain dupicate keys)
232 * more precise than the ubi_btFind() function. The latter is faster,
233 * but it only searches for exact matches and, if the tree contains
234 * duplicates, Find() may return a pointer to any one of the duplicate-
238 * RootPtr - A pointer to the header of the tree to be searched.
239 * FindMe - An ubi_btItemPtr that indicates the key for which to
241 * CompOp - One of the following:
242 * CompOp Return a pointer to the node with
243 * ------ ---------------------------------
244 * ubi_trLT - the last key value that is less
246 * ubi_trLE - the first key matching FindMe, or
247 * the last key that is less than
249 * ubi_trEQ - the first key matching FindMe.
250 * ubi_trGE - the first key matching FindMe, or the
251 * first key greater than FindMe.
252 * ubi_trGT - the first key greater than FindMe.
254 * A pointer to the node matching the criteria listed above under
255 * CompOp, or NULL if no node matched the criteria.
258 * In the case of trees with duplicate keys, Locate() will behave as
262 * Keys: 1 2 2 2 3 3 3 3 3 4 4 Keys: 1 1 2 2 2 4 4 5 5 5 6
266 * That is, when returning a pointer to a node with a key that is LESS
267 * THAN the target key (FindMe), Locate() will return a pointer to the
268 * LAST matching node.
269 * When returning a pointer to a node with a key that is GREATER
270 * THAN the target key (FindMe), Locate() will return a pointer to the
271 * FIRST matching node.
273 * See Also: ubi_btFind(), ubi_btFirstOf(), ubi_btLastOf().
274 * ------------------------------------------------------------------------ **
277 ubi_btNodePtr ubi_sptFind( ubi_btRootPtr RootPtr,
278 ubi_btItemPtr FindMe );
279 /* ------------------------------------------------------------------------ **
280 * This function performs a non-recursive search of a tree for any node
281 * matching a specific key.
284 * RootPtr - a pointer to the header of the tree to be searched.
285 * FindMe - a pointer to the key value for which to search.
288 * A pointer to a node with a key that matches the key indicated by
289 * FindMe, or NULL if no such node was found.
291 * Note: In a tree that allows duplicates, the pointer returned *might
292 * not* point to the (sequentially) first occurance of the
293 * desired key. In such a tree, it may be more useful to use
295 * ------------------------------------------------------------------------ **
298 void ubi_sptSplay( ubi_btRootPtr RootPtr,
299 ubi_btNodePtr SplayMe );
300 /* ------------------------------------------------------------------------ **
301 * This function allows you to splay the tree at a given node, thus moving
302 * the node to the top of the tree.
305 * RootPtr - a pointer to the header of the tree to be splayed.
306 * SplayMe - a pointer to a node within the tree. This will become
310 * Notes: This is an uncharacteristic function for this group of modules
311 * in that it provides access to the internal balancing routines,
312 * which would normally be hidden.
313 * Splaying the tree will not damage it (assuming that I've done
314 * *my* job), but there is overhead involved. I don't recommend
315 * that you use this function unless you understand the underlying
316 * Splay Tree principles involved.
317 * ------------------------------------------------------------------------ **
320 int ubi_sptModuleID( int size, char *list[] );
321 /* ------------------------------------------------------------------------ **
322 * Returns a set of strings that identify the module.
324 * Input: size - The number of elements in the array <list>.
325 * list - An array of pointers of type (char *). This array
326 * should, initially, be empty. This function will fill
327 * in the array with pointers to strings.
328 * Output: The number of elements of <list> that were used. If this value
329 * is less than <size>, the values of the remaining elements are
332 * Notes: Please keep in mind that the pointers returned indicate strings
333 * stored in static memory. Don't free() them, don't write over
334 * them, etc. Just read them.
335 * ------------------------------------------------------------------------ **
338 /* -------------------------------------------------------------------------- **
341 * This set of defines allows you to write programs that will use any of the
342 * implemented binary tree modules (currently BinTree, AVLtree, and SplayTree).
343 * Instead of using ubi_bt..., use ubi_tr..., and select the tree type by
344 * including the appropriate module header.
351 #undef ubi_trModuleID
353 #define ubi_trInsert( Rp, Nn, Ip, On ) \
354 ubi_sptInsert( (ubi_btRootPtr)(Rp), (ubi_btNodePtr)(Nn), \
355 (ubi_btItemPtr)(Ip), (ubi_btNodePtr *)(On) )
357 #define ubi_trRemove( Rp, Dn ) \
358 ubi_sptRemove( (ubi_btRootPtr)(Rp), (ubi_btNodePtr)(Dn) )
360 #define ubi_trLocate( Rp, Ip, Op ) \
361 ubi_sptLocate( (ubi_btRootPtr)(Rp), \
362 (ubi_btItemPtr)(Ip), \
363 (ubi_trCompOps)(Op) )
365 #define ubi_trFind( Rp, Ip ) \
366 ubi_sptFind( (ubi_btRootPtr)(Rp), (ubi_btItemPtr)(Ip) )
368 #define ubi_trModuleID( s, l ) ubi_sptModuleID( s, l )
370 /* ================================ The End ================================= */
371 #endif /* UBI_SPLAYTREE_H */