1 /* splay.c - code for splay trees Version of August 18, 2001.
2
3 This file is not meant to be compiled separately, but to be
4 #included into other programs. Use it like this:
5
6 1. Define a node type SPLAYNODE. It must be a structure that
7 contains at least the pointer fields left, right and parent of
8 type SPLAYNODE*.
9 Also define a macro SPLAYNODESIZE giving the size of an object
10 of type SPLAYNODE, unless sizeof(SPLAYNODE) is adequate.
11
12 2. Declare a variable of type SPLAYNODE* to point to the root
13 of the tree, and initialise it to NULL.
14
15 3. Declare SCAN_ARGS to be the additional arguments needed for
16 splay_scan(), including a leading comma.
17
18 4. Declare ACTION(p) for what splay_scan() should do for node p.
19
20 5. Declare INSERT_ARGS to be the additional arguments needed
21 for splay_insert(), including a leading comma.
22
23 6. Declare COMPARE(p) to compare INSERT_ARGS or LOOKUP_ARGS to the
24 contents of node p. <0, 0, >0 if INSERT_ARGS is greater, equal,
25 less, than p. This has to be an expression with a value, so you will
26 need to make it a procedure call if the comparison is complicated.
27
28 If you are using something like strcmp, the correct order is
29 strcmp( INSERT_ARGS, p ).
30
31 7. Declare PRESENT(p) for what to do if INSERT_ARGS is already
32 present, in node p. There is a spare int variable i available.
33 Typically, this might update some data in the node p.
34
35 8. Declare NOT_PRESENT(p) for what to do if INSERT_ARGS is not
36 in the tree and p is a fresh node to hold it. No need to set
37 the left, right, and parent fields. Use i here too if you like.
38 Typically, this might initialise the data in node p.
39
40 PRESENT(p) and NOT_PRESENT(p) should not manipulate the
41 tree pointers. However, each of them can include a
42 return if you don't want to change the tree. In the
43 case of NOT_PRESENT(p), do free(p) before returning.
44
45 In the case of PRESENT(p), it is also legal to delete the
46 node from the tree using SCAN_DELETE(to_root,p). In that
47 case you MUST return immediately afterwards.
48
49 9. Declare LOOKUP_ARGS to be the additional arguments needed
50 for splay_lookup(), including a leading comma. The default
51 for LOOKUP_ARGS is to be the same as INSERT_ARGS.
52
53 10. #include "splay.c"
54
55
56 Calls:
57
58 Suppose "root" is name of the variable described in step 2.
59
60 There is no need to initialise the tree. Step 2 did that already.
61
62 To insert something in the tree:
63 splay_insert(&root, ...stuff...)
64 where "stuff" is the stuff you want to insert, declared as INSERT_ARGS.
65 If the key (some part of the stuff decided by you) is present in an
66 existing tree node p, PRESENT(p) is executed. Otherwise, a new tree
67 node p is created and NOT_PRESENT(p) is executed.
68
69 To look up something in the tree:
70 splay_lookup(&root, ...stuff...)
71 where "stuff" is the stuff you want to find, declared as LOOKUP_ARGS.
72 It will return a pointer to the tree node with the right key, or NULL
73 if there is no such tree node.
74
75 To do something for each node of the tree:
76 splay_scan(root, ...stuff...)
77 where "stuff" is anything you like (including nothing). This will
78 execute ACTION(p) for each node p in inorder.
79
80 To delete the node p (which MUST be in the tree:
81 splay_delete(&root, p)
82 Nothing happens if p is NULL, so you can use
83 splay_delete(&root, splay_lookup(&root, ...stuff...))
84 to delete a node, if any, containing stuff.
85
86 It is possible to have splay trees of several types in the same
87 program. Just include "splay.c" several times, with the procedure
88 names SPLAY, SPLAY_SCAN, SPLAY_LOOKUP, SPLAY_INSERT, SPLAY_DELETE
89 defined to distinct names. You have to redefine them all even if
90 you aren't using them all.
91 */
92
93 #define S_A 0
94 #define S_L 1
95 #define S_R 2
96 #define S_LL 3
97 #define S_LR 4
98 #define S_RL 5
99 #define S_RR 6
100
101 #ifndef SPLAYNODESIZE
102 #define SPLAYNODESIZE sizeof(SPLAYNODE)
103 #endif
104
105 #ifndef LOOKUP_ARGS
106 #define LOOKUP_ARGS INSERT_ARGS
107 #endif
108
109 #ifndef SPLAY
110 #define SPLAY splay
111 #define SPLAY_SCAN splay_scan
112 #define SPLAY_LOOKUP splay_lookup
113 #define SPLAY_INSERT splay_insert
114 #define SPLAY_DELETE splay_delete
115 #endif
116
117 /*********************************************************************/
118
119 void
SPLAY_SCAN(SPLAYNODE * root SCAN_ARGS)120 SPLAY_SCAN(SPLAYNODE *root SCAN_ARGS)
121 /* Do ACTION(p) for each node of the tree, in inorder. Nonrecursive! */
122 {
123 int code;
124 SPLAYNODE *p;
125
126 p = root;
127 code = S_A;
128
129 while (p)
130 {
131 switch (code) /* deliberate flow-ons */
132 {
133 case S_A:
134 if (p->left)
135 {
136 p = p->left;
137 break;
138 }
139 case S_L:
140 ACTION(p);
141 if (p->right)
142 {
143 p = p->right;
144 code = S_A;
145 break;
146 }
147 case S_R:
148 if (p->parent && p->parent->left == p) code = S_L;
149 else code = S_R;
150 p = p->parent;
151 break;
152 }
153 }
154 }
155
156 /*********************************************************************/
157
158 static void
SPLAY(SPLAYNODE * p)159 SPLAY(SPLAYNODE *p)
160 /* Splay the node p. It becomes the new root. */
161 {
162 SPLAYNODE *q,*r,*s;
163 SPLAYNODE *a,*b,*c;
164 int code;
165
166 #define LCHILD(x,y) {(x)->left = y; if (y) (y)->parent = x;}
167 #define RCHILD(x,y) {(x)->right = y; if (y) (y)->parent = x;}
168
169 while (p->parent)
170 {
171 a = p->left;
172 b = p->right;
173 q = p->parent;
174 if (q->left == p)
175 {
176 code = S_L;
177 c = q->right;
178 }
179 else
180 {
181 code = S_R;
182 c = q->left;
183 }
184 r = q->parent;
185 if (r)
186 {
187 if (r->left == q) code = (code == S_L ? S_LL : S_LR);
188 else code = (code == S_L ? S_RL : S_RR);
189 s = r->parent;
190 p->parent = s;
191 if (s)
192 {
193 if (s->left == r) s->left = p;
194 else s->right = p;
195 }
196 }
197 else
198 {
199 p->parent = NULL;
200 }
201
202 switch (code)
203 {
204 case S_L:
205 RCHILD(p,q);
206 LCHILD(q,b);
207 break;
208 case S_R:
209 LCHILD(p,q);
210 RCHILD(q,a);
211 break;
212 case S_LL:
213 RCHILD(p,q);
214 RCHILD(q,r);
215 LCHILD(q,b);
216 LCHILD(r,c);
217 break;
218 case S_RR:
219 LCHILD(p,q);
220 LCHILD(q,r);
221 RCHILD(r,c);
222 RCHILD(q,a);
223 break;
224 case S_LR:
225 LCHILD(p,q);
226 RCHILD(p,r);
227 RCHILD(q,a);
228 LCHILD(r,b);
229 break;
230 case S_RL:
231 LCHILD(p,r);
232 RCHILD(p,q);
233 RCHILD(r,a);
234 LCHILD(q,b);
235 break;
236 }
237 }
238 }
239
240 /*********************************************************************/
241
242 void
SPLAY_INSERT(SPLAYNODE ** to_root INSERT_ARGS)243 SPLAY_INSERT(SPLAYNODE **to_root INSERT_ARGS)
244 /* Do insertion operation. On return, the object being inserted
245 is at the root of the tree regardless of whether a new node
246 needed to be created for it. */
247 {
248 int i,cmp;
249 SPLAYNODE *p,*ppar,*new_node;
250
251 p = *to_root;
252 cmp = 0;
253
254 while (p != NULL)
255 {
256 cmp = COMPARE(p);
257 if (cmp == 0)
258 {
259 PRESENT(p);
260 SPLAY(p);
261 *to_root = p;
262 return;
263 }
264 else if (cmp < 0)
265 {
266 ppar = p;
267 p = p->left;
268 }
269 else
270 {
271 ppar = p;
272 p = p->right;
273 }
274 }
275
276 if ((new_node = (SPLAYNODE*)malloc(SPLAYNODESIZE)) == NULL)
277 {
278 fprintf(stderr,">E malloc failed in splay_insert()\n");
279 exit(1);
280 }
281
282 NOT_PRESENT(new_node);
283
284 new_node->left = new_node->right = NULL;
285
286 if (cmp == 0)
287 {
288 *to_root = new_node;
289 new_node->parent = NULL;
290 }
291 else if (cmp < 0)
292 {
293 ppar->left = new_node;
294 new_node->parent = ppar;
295 }
296 else
297 {
298 ppar->right = new_node;
299 new_node->parent = ppar;
300 }
301
302 SPLAY(new_node);
303 *to_root = new_node;
304 }
305
306 /*********************************************************************/
307
308 SPLAYNODE*
SPLAY_LOOKUP(SPLAYNODE ** to_root LOOKUP_ARGS)309 SPLAY_LOOKUP(SPLAYNODE **to_root LOOKUP_ARGS)
310 /* Do a look-up operation. If found, return a pointer to the
311 node containing it. If not, return NULL. */
312 {
313 int i,cmp;
314 SPLAYNODE *p;
315
316 p = *to_root;
317 cmp = 0;
318
319 while (p != NULL)
320 {
321 cmp = COMPARE(p);
322 if (cmp == 0)
323 {
324 SPLAY(p);
325 *to_root = p;
326 return p;
327 }
328 else if (cmp < 0)
329 p = p->left;
330 else
331 p = p->right;
332 }
333
334 return NULL;
335 }
336
337 /*********************************************************************/
338
339 void
SPLAY_DELETE(SPLAYNODE ** to_root,SPLAYNODE * p)340 SPLAY_DELETE(SPLAYNODE **to_root, SPLAYNODE *p)
341 /* Remove node p from the tree and free it. */
342 {
343 SPLAYNODE *q;
344
345 if (p == NULL) return;
346
347 SPLAY(p);
348 *to_root = p;
349
350 /* Now we have to delete the root. */
351
352 /* No right child (includes no children). */
353
354 if (!p->right)
355 {
356 *to_root = p->left;
357 if (p->left) p->left->parent = NULL;
358 free(p);
359 return;
360 }
361
362 /* right child but no left child */
363
364 if (!p->left)
365 {
366 *to_root = p->right;
367 p->right->parent = NULL;
368 free(p);
369 return;
370 }
371
372 /* both children exist */
373
374 for (q = p->left; q->right; q = q->right) {}
375
376 if (q->left) q->left->parent = q->parent;
377 if (q->parent == p) q->parent->left = q->left;
378 else q->parent->right = q->left;
379
380 q->left = p->left;
381 q->right = p->right;
382 q->parent = NULL;
383 if (p->left) p->left->parent = q;
384 if (p->right) p->right->parent = q;
385 *to_root = q;
386 free(p);
387 }
388
389 /*********************************************************************/
390
391 /* The following shows the tree structure for debugging purposes.
392 If you define SPLAY_DUMP you must also define DUMP_ARGS,
393 DUMP_LEFT, DUMP_RIGHT and DUMP_ACTION(p). */
394
395 #ifdef SPLAY_DUMP
396 void
SPLAY_DUMP(SPLAYNODE * p DUMP_ARGS)397 SPLAY_DUMP(SPLAYNODE *p DUMP_ARGS)
398 {
399 int i;
400
401 if (p == NULL) return;
402
403 if (p->right && p->right->parent != p)
404 fprintf(stderr,"parent misaligned at %p-%p ************\n",p,p->right);
405 if (p->left && p->left->parent != p)
406 fprintf(stderr,"parent misaligned at %p-%p ************\n",p,p->left);
407
408 SPLAY_DUMP(p->right DUMP_RIGHT);
409 DUMP_ACTION(p);
410 SPLAY_DUMP(p->left DUMP_LEFT);
411 }
412 #endif
413