| blob | e4fac796a91621d40f51fdf4aad299c657523bbf |
1 #ifndef UBI_SPLAYTREE_H
2 #define UBI_SPLAYTREE_H
3 /* ========================================================================== **
4 * ubi_SplayTree.h
5 *
6 * Copyright (C) 1993-1998 by Christopher R. Hertel
7 *
8 * Email: crh@ubiqx.mn.org
9 * -------------------------------------------------------------------------- **
10 *
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
15 * the top.
16 *
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
20 *
21 * See also: http://www.cs.cmu.edu/~sleator/
22 *
23 * -------------------------------------------------------------------------- **
24 *
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.
29 *
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.
34 *
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.
38 *
39 * -------------------------------------------------------------------------- **
40 *
41 * Log: ubi_SplayTree.h,v
42 * Revision 4.5 2000/01/08 23:26:49 crh
43 * Added ubi_trSplay() macro, which does a type cast for us.
44 *
45 * Revision 4.4 1998/06/04 21:29:27 crh
46 * Upper-cased defined constants (eg UBI_BINTREE_H) in some header files.
47 * This is more "standard", and is what people expect. Weird, eh?
48 *
49 * Revision 4.3 1998/06/03 17:45:05 crh
50 * Further fiddling with sys_include.h. It's now in ubi_BinTree.h which is
51 * included by all of the binary tree files.
52 *
53 * Also fixed some warnings produced by lint on Irix 6.2, which doesn't seem
54 * to like syntax like this:
55 *
56 * if( (a = b) )
57 *
58 * The fix was to change lines like the above to:
59 *
60 * if( 0 != (a=b) )
61 *
62 * Which means the same thing.
63 *
64 * Reminder: Some of the ubi_tr* macros in ubi_BinTree.h are redefined in
65 * ubi_AVLtree.h and ubi_SplayTree.h. This allows easy swapping
66 * of tree types by simply changing a header. Unfortunately, the
67 * macro redefinitions in ubi_AVLtree.h and ubi_SplayTree.h will
68 * conflict if used together. You must either choose a single tree
69 * type, or use the underlying function calls directly. Compare
70 * the two header files for more information.
71 *
72 * Revision 4.2 1998/06/02 01:29:14 crh
73 * Changed ubi_null.h to sys_include.h to make it more generic.
74 *
75 * Revision 4.1 1998/05/20 04:37:54 crh
76 * The C file now includes ubi_null.h. See ubi_null.h for more info.
77 *
78 * Revision 4.0 1998/03/10 03:40:57 crh
79 * Minor comment changes. The revision number is now 4.0 to match the
80 * BinTree and AVLtree modules.
81 *
82 * Revision 2.7 1998/01/24 06:37:57 crh
83 * Added a URL for more information.
84 *
85 * Revision 2.6 1997/12/23 04:02:20 crh
86 * In this version, all constants & macros defined in the header file have
87 * the ubi_tr prefix. Also cleaned up anything that gcc complained about
88 * when run with '-pedantic -fsyntax-only -Wall'.
89 *
90 * Revision 2.5 1997/07/26 04:15:46 crh
91 * + Cleaned up a few minor syntax annoyances that gcc discovered for me.
92 * + Changed ubi_TRUE and ubi_FALSE to ubi_trTRUE and ubi_trFALSE.
93 *
94 * Revision 2.4 1997/06/03 05:22:56 crh
95 * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid causing
96 * problems.
97 *
98 * Revision 2.3 1995/10/03 22:19:37 CRH
99 * Ubisized!
100 * Also, added the function ubi_sptSplay().
101 *
102 * Revision 2.1 95/03/09 23:55:04 CRH
103 * Added the ModuleID static string and function. These modules are now
104 * self-identifying.
105 *
106 * Revision 2.0 95/02/27 22:34:55 CRH
107 * This module was updated to match the interface changes made to the
108 * ubi_BinTree module. In particular, the interface to the Locate() function
109 * has changed. See ubi_BinTree for more information on changes and new
110 * functions.
111 *
112 * The revision number was also upped to match ubi_BinTree.
113 *
114 *
115 * Revision 1.0 93/10/15 22:59:36 CRH
116 * With this revision, I have added a set of #define's that provide a single,
117 * standard API to all existing tree modules. Until now, each of the three
118 * existing modules had a different function and typedef prefix, as follows:
119 *
120 * Module Prefix
121 * ubi_BinTree ubi_bt
122 * ubi_AVLtree ubi_avl
123 * ubi_SplayTree ubi_spt
124 *
125 * To further complicate matters, only those portions of the base module
126 * (ubi_BinTree) that were superceeded in the new module had the new names.
127 * For example, if you were using ubi_SplayTree, the locate function was
128 * called "ubi_sptLocate", but the next and previous functions remained
129 * "ubi_btNext" and "ubi_btPrev".
130 *
131 * This was not too terrible if you were familiar with the modules and knew
132 * exactly which tree model you wanted to use. If you wanted to be able to
133 * change modules (for speed comparisons, etc), things could get messy very
134 * quickly.
135 *
136 * So, I have added a set of defined names that get redefined in any of the
137 * descendant modules. To use this standardized interface in your code,
138 * simply replace all occurances of "ubi_bt", "ubi_avl", and "ubi_spt" with
139 * "ubi_tr". The "ubi_tr" names will resolve to the correct function or
140 * datatype names for the module that you are using. Just remember to
141 * include the header for that module in your program file. Because these
142 * names are handled by the preprocessor, there is no added run-time
143 * overhead.
144 *
145 * Note that the original names do still exist, and can be used if you wish
146 * to write code directly to a specific module. This should probably only be
147 * done if you are planning to implement a new descendant type, such as
148 * red/black trees. CRH
149 *
150 * Revision 0.0 93/04/21 23:07:13 CRH
151 * Initial version, written by Christopher R. Hertel.
152 * This module implements Splay Trees using the ubi_BinTree module as a basis.
153 *
154 * ========================================================================== **
155 */
159 /* ========================================================================== **
160 * Function prototypes...
161 */
164 ubi_btNodePtr NewNode,
165 ubi_btItemPtr ItemPtr,
167 /* ------------------------------------------------------------------------ **
168 * This function uses a non-recursive algorithm to add a new element to the
169 * splay tree.
170 *
171 * Input: RootPtr - a pointer to the ubi_btRoot structure that indicates
172 * the root of the tree to which NewNode is to be added.
173 * NewNode - a pointer to an ubi_btNode structure that is NOT
174 * part of any tree.
175 * ItemPtr - A pointer to the sort key that is stored within
176 * *NewNode. ItemPtr MUST point to information stored
177 * in *NewNode or an EXACT DUPLICATE. The key data
178 * indicated by ItemPtr is used to place the new node
179 * into the tree.
180 * OldNode - a pointer to an ubi_btNodePtr. When searching
181 * the tree, a duplicate node may be found. If
182 * duplicates are allowed, then the new node will
183 * be simply placed into the tree. If duplicates
184 * are not allowed, however, then one of two things
185 * may happen.
186 * 1) if overwritting *is not* allowed, this
187 * function will return FALSE (indicating that
188 * the new node could not be inserted), and
189 * *OldNode will point to the duplicate that is
190 * still in the tree.
191 * 2) if overwritting *is* allowed, then this
192 * function will swap **OldNode for *NewNode.
193 * In this case, *OldNode will point to the node
194 * that was removed (thus allowing you to free
195 * the node).
196 * ** If you are using overwrite mode, ALWAYS **
197 * ** check the return value of this parameter! **
198 * Note: You may pass NULL in this parameter, the
199 * function knows how to cope. If you do this,
200 * however, there will be no way to return a
201 * pointer to an old (ie. replaced) node (which is
202 * a problem if you are using overwrite mode).
203 *
204 * Output: a boolean value indicating success or failure. The function
205 * will return FALSE if the node could not be added to the tree.
206 * Such failure will only occur if duplicates are not allowed,
207 * nodes cannot be overwritten, AND a duplicate key was found
208 * within the tree.
209 * ------------------------------------------------------------------------ **
210 */
213 /* ------------------------------------------------------------------------ **
214 * This function removes the indicated node from the tree.
215 *
216 * Input: RootPtr - A pointer to the header of the tree that contains
217 * the node to be removed.
218 * DeadNode - A pointer to the node that will be removed.
219 *
220 * Output: This function returns a pointer to the node that was removed
221 * from the tree (ie. the same as DeadNode).
222 *
223 * Note: The node MUST be in the tree indicated by RootPtr. If not,
224 * strange and evil things will happen to your trees.
225 * ------------------------------------------------------------------------ **
226 */
229 ubi_btItemPtr FindMe,
230 ubi_trCompOps CompOp );
231 /* ------------------------------------------------------------------------ **
232 * The purpose of ubi_btLocate() is to find a node or set of nodes given
233 * a target value and a "comparison operator". The Locate() function is
234 * more flexible and (in the case of trees that may contain dupicate keys)
235 * more precise than the ubi_btFind() function. The latter is faster,
236 * but it only searches for exact matches and, if the tree contains
237 * duplicates, Find() may return a pointer to any one of the duplicate-
238 * keyed records.
239 *
240 * Input:
241 * RootPtr - A pointer to the header of the tree to be searched.
242 * FindMe - An ubi_btItemPtr that indicates the key for which to
243 * search.
244 * CompOp - One of the following:
245 * CompOp Return a pointer to the node with
246 * ------ ---------------------------------
247 * ubi_trLT - the last key value that is less
248 * than FindMe.
249 * ubi_trLE - the first key matching FindMe, or
250 * the last key that is less than
251 * FindMe.
252 * ubi_trEQ - the first key matching FindMe.
253 * ubi_trGE - the first key matching FindMe, or the
254 * first key greater than FindMe.
255 * ubi_trGT - the first key greater than FindMe.
256 * Output:
257 * A pointer to the node matching the criteria listed above under
258 * CompOp, or NULL if no node matched the criteria.
259 *
260 * Notes:
261 * In the case of trees with duplicate keys, Locate() will behave as
262 * follows:
263 *
264 * Find: 3 Find: 3
265 * 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 * ^ ^ ^ ^ ^
267 * LT EQ GT LE GE
268 *
269 * That is, when returning a pointer to a node with a key that is LESS
270 * THAN the target key (FindMe), Locate() will return a pointer to the
271 * LAST matching node.
272 * When returning a pointer to a node with a key that is GREATER
273 * THAN the target key (FindMe), Locate() will return a pointer to the
274 * FIRST matching node.
275 *
276 * See Also: ubi_btFind(), ubi_btFirstOf(), ubi_btLastOf().
277 * ------------------------------------------------------------------------ **
278 */
281 ubi_btItemPtr FindMe );
282 /* ------------------------------------------------------------------------ **
283 * This function performs a non-recursive search of a tree for any node
284 * matching a specific key.
285 *
286 * Input:
287 * RootPtr - a pointer to the header of the tree to be searched.
288 * FindMe - a pointer to the key value for which to search.
289 *
290 * Output:
291 * A pointer to a node with a key that matches the key indicated by
292 * FindMe, or NULL if no such node was found.
293 *
294 * Note: In a tree that allows duplicates, the pointer returned *might
295 * not* point to the (sequentially) first occurance of the
296 * desired key. In such a tree, it may be more useful to use
297 * ubi_sptLocate().
298 * ------------------------------------------------------------------------ **
299 */
302 ubi_btNodePtr SplayMe );
303 /* ------------------------------------------------------------------------ **
304 * This function allows you to splay the tree at a given node, thus moving
305 * the node to the top of the tree.
306 *
307 * Input:
308 * RootPtr - a pointer to the header of the tree to be splayed.
309 * SplayMe - a pointer to a node within the tree. This will become
310 * the new root node.
311 * Output: None.
312 *
313 * Notes: This is an uncharacteristic function for this group of modules
314 * in that it provides access to the internal balancing routines,
315 * which would normally be hidden.
316 * Splaying the tree will not damage it (assuming that I've done
317 * *my* job), but there is overhead involved. I don't recommend
318 * that you use this function unless you understand the underlying
319 * Splay Tree principles involved.
320 * ------------------------------------------------------------------------ **
321 */
324 /* ------------------------------------------------------------------------ **
325 * Returns a set of strings that identify the module.
326 *
327 * Input: size - The number of elements in the array <list>.
328 * list - An array of pointers of type (char *). This array
329 * should, initially, be empty. This function will fill
330 * in the array with pointers to strings.
331 * Output: The number of elements of <list> that were used. If this value
332 * is less than <size>, the values of the remaining elements are
333 * not guaranteed.
334 *
335 * Notes: Please keep in mind that the pointers returned indicate strings
336 * stored in static memory. Don't free() them, don't write over
337 * them, etc. Just read them.
338 * ------------------------------------------------------------------------ **
339 */
341 /* -------------------------------------------------------------------------- **
342 * Masquarade...
343 *
344 * This set of defines allows you to write programs that will use any of the
345 * implemented binary tree modules (currently BinTree, AVLtree, and SplayTree).
346 * Instead of using ubi_bt..., use ubi_tr..., and select the tree type by
347 * including the appropriate module header.
348 */
350 #undef ubi_trInsert
351 #undef ubi_trRemove
352 #undef ubi_trLocate
353 #undef ubi_trFind
354 #undef ubi_trModuleID
356 #define ubi_trInsert( Rp, Nn, Ip, On ) \
357 ubi_sptInsert( (ubi_btRootPtr)(Rp), (ubi_btNodePtr)(Nn), \
358 (ubi_btItemPtr)(Ip), (ubi_btNodePtr *)(On) )
360 #define ubi_trRemove( Rp, Dn ) \
361 ubi_sptRemove( (ubi_btRootPtr)(Rp), (ubi_btNodePtr)(Dn) )
363 #define ubi_trLocate( Rp, Ip, Op ) \
364 ubi_sptLocate( (ubi_btRootPtr)(Rp), \
365 (ubi_btItemPtr)(Ip), \
366 (ubi_trCompOps)(Op) )
368 #define ubi_trFind( Rp, Ip ) \
369 ubi_sptFind( (ubi_btRootPtr)(Rp), (ubi_btItemPtr)(Ip) )
371 #define ubi_trSplay( Rp, Sm ) \
372 ubi_sptSplay( (ubi_btRootPtr)(Rp), (ubi_btNodePtr)(Sm) )
374 #define ubi_trModuleID( s, l ) ubi_sptModuleID( s, l )
376 /* ================================ The End ================================= */