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.5 2000/01/08 23:26:49 crh
43
* Added ubi_trSplay() macro, which does a type cast for us.
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?
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.
53
* Also fixed some warnings produced by lint on Irix 6.2, which doesn't seem
54
* to like syntax like this:
58
* The fix was to change lines like the above to:
62
* Which means the same thing.
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.
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.
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.
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.
82
* Revision 2.7 1998/01/24 06:37:57 crh
83
* Added a URL for more information.
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'.
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.
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
98
* Revision 2.3 1995/10/03 22:19:37 CRH
100
* Also, added the function ubi_sptSplay().
102
* Revision 2.1 95/03/09 23:55:04 CRH
103
* Added the ModuleID static string and function. These modules are now
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
112
* The revision number was also upped to match ubi_BinTree.
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:
122
* ubi_AVLtree ubi_avl
123
* ubi_SplayTree ubi_spt
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".
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
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
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
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.
154
* ========================================================================== **
157
#include "ubi_BinTree.h" /* Base binary tree functions, types, etc. */
159
/* ========================================================================== **
160
* Function prototypes...
163
ubi_trBool ubi_sptInsert( ubi_btRootPtr RootPtr,
164
ubi_btNodePtr NewNode,
165
ubi_btItemPtr ItemPtr,
166
ubi_btNodePtr *OldNode );
167
/* ------------------------------------------------------------------------ **
168
* This function uses a non-recursive algorithm to add a new element to the
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
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
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
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
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
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).
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
209
* ------------------------------------------------------------------------ **
212
ubi_btNodePtr ubi_sptRemove( ubi_btRootPtr RootPtr, ubi_btNodePtr DeadNode );
213
/* ------------------------------------------------------------------------ **
214
* This function removes the indicated node from the tree.
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.
220
* Output: This function returns a pointer to the node that was removed
221
* from the tree (ie. the same as DeadNode).
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
* ------------------------------------------------------------------------ **
228
ubi_btNodePtr ubi_sptLocate( ubi_btRootPtr RootPtr,
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-
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
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
249
* ubi_trLE - the first key matching FindMe, or
250
* the last key that is less than
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.
257
* A pointer to the node matching the criteria listed above under
258
* CompOp, or NULL if no node matched the criteria.
261
* In the case of trees with duplicate keys, Locate() will behave as
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
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.
276
* See Also: ubi_btFind(), ubi_btFirstOf(), ubi_btLastOf().
277
* ------------------------------------------------------------------------ **
280
ubi_btNodePtr ubi_sptFind( ubi_btRootPtr RootPtr,
281
ubi_btItemPtr FindMe );
282
/* ------------------------------------------------------------------------ **
283
* This function performs a non-recursive search of a tree for any node
284
* matching a specific key.
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.
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.
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
298
* ------------------------------------------------------------------------ **
301
void ubi_sptSplay( ubi_btRootPtr RootPtr,
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.
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
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
* ------------------------------------------------------------------------ **
323
int ubi_sptModuleID( int size, char *list[] );
324
/* ------------------------------------------------------------------------ **
325
* Returns a set of strings that identify the module.
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
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
* ------------------------------------------------------------------------ **
341
/* -------------------------------------------------------------------------- **
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.
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 ================================= */
377
#endif /* UBI_SPLAYTREE_H */
added
removed
source/ubiqx/ubi_SplayTree.h
