1 /* A splay-tree datatype.
2 Copyright (C) 1998-2023 Free Software Foundation, Inc.
3 Contributed by Mark Mitchell (mark@markmitchell.com).
4
5 This file is part of GNU CC.
6
7 GNU CC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
10 any later version.
11
12 GNU CC is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING. If not, write to
19 the Free Software Foundation, 51 Franklin Street - Fifth Floor,
20 Boston, MA 02110-1301, USA. */
21
22 /* For an easily readable description of splay-trees, see:
23
24 Lewis, Harry R. and Denenberg, Larry. Data Structures and Their
25 Algorithms. Harper-Collins, Inc. 1991. */
26
27 #ifdef HAVE_CONFIG_H
28 #include "config.h"
29 #endif
30
31 #ifdef HAVE_STDLIB_H
32 #include <stdlib.h>
33 #endif
34 #ifdef HAVE_STRING_H
35 #include <string.h>
36 #endif
37
38 #include <stdio.h>
39
40 #include "libiberty.h"
41 #include "splay-tree.h"
42
43 static void splay_tree_delete_helper (splay_tree, splay_tree_node);
44 static inline void rotate_left (splay_tree_node *,
45 splay_tree_node, splay_tree_node);
46 static inline void rotate_right (splay_tree_node *,
47 splay_tree_node, splay_tree_node);
48 static void splay_tree_splay (splay_tree, splay_tree_key);
49 static int splay_tree_foreach_helper (splay_tree_node,
50 splay_tree_foreach_fn, void*);
51
52 /* Deallocate NODE (a member of SP), and all its sub-trees. */
53
54 static void
55 splay_tree_delete_helper (splay_tree sp, splay_tree_node node)
56 {
57 splay_tree_node pending = 0;
58 splay_tree_node active = 0;
59
60 if (!node)
61 return;
62
63 #define KDEL(x) if (sp->delete_key) (*sp->delete_key)(x);
64 #define VDEL(x) if (sp->delete_value) (*sp->delete_value)(x);
65
66 KDEL (node->key);
67 VDEL (node->value);
68
69 /* We use the "key" field to hold the "next" pointer. */
70 node->key = (splay_tree_key)pending;
71 pending = (splay_tree_node)node;
72
73 /* Now, keep processing the pending list until there aren't any
74 more. This is a little more complicated than just recursing, but
75 it doesn't toast the stack for large trees. */
76
77 while (pending)
78 {
79 active = pending;
80 pending = 0;
81 while (active)
82 {
83 splay_tree_node temp;
84
85 /* active points to a node which has its key and value
86 deallocated, we just need to process left and right. */
87
88 if (active->left)
89 {
90 KDEL (active->left->key);
91 VDEL (active->left->value);
92 active->left->key = (splay_tree_key)pending;
93 pending = (splay_tree_node)(active->left);
94 }
95 if (active->right)
96 {
97 KDEL (active->right->key);
98 VDEL (active->right->value);
99 active->right->key = (splay_tree_key)pending;
100 pending = (splay_tree_node)(active->right);
101 }
102
103 temp = active;
104 active = (splay_tree_node)(temp->key);
105 (*sp->deallocate) ((char*) temp, sp->allocate_data);
106 }
107 }
108 #undef KDEL
109 #undef VDEL
110 }
111
112 /* Rotate the edge joining the left child N with its parent P. PP is the
113 grandparents' pointer to P. */
114
115 static inline void
116 rotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
117 {
118 splay_tree_node tmp;
119 tmp = n->right;
120 n->right = p;
121 p->left = tmp;
122 *pp = n;
123 }
124
125 /* Rotate the edge joining the right child N with its parent P. PP is the
126 grandparents' pointer to P. */
127
128 static inline void
129 rotate_right (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
130 {
131 splay_tree_node tmp;
132 tmp = n->left;
133 n->left = p;
134 p->right = tmp;
135 *pp = n;
136 }
137
138 /* Bottom up splay of key. */
139
140 static void
141 splay_tree_splay (splay_tree sp, splay_tree_key key)
142 {
143 if (sp->root == 0)
144 return;
145
146 do {
147 int cmp1, cmp2;
148 splay_tree_node n, c;
149
150 n = sp->root;
151 cmp1 = (*sp->comp) (key, n->key);
152
153 /* Found. */
154 if (cmp1 == 0)
155 return;
156
157 /* Left or right? If no child, then we're done. */
158 if (cmp1 < 0)
159 c = n->left;
160 else
161 c = n->right;
162 if (!c)
163 return;
164
165 /* Next one left or right? If found or no child, we're done
166 after one rotation. */
167 cmp2 = (*sp->comp) (key, c->key);
168 if (cmp2 == 0
169 || (cmp2 < 0 && !c->left)
170 || (cmp2 > 0 && !c->right))
171 {
172 if (cmp1 < 0)
173 rotate_left (&sp->root, n, c);
174 else
175 rotate_right (&sp->root, n, c);
176 return;
177 }
178
179 /* Now we have the four cases of double-rotation. */
180 if (cmp1 < 0 && cmp2 < 0)
181 {
182 rotate_left (&n->left, c, c->left);
183 rotate_left (&sp->root, n, n->left);
184 }
185 else if (cmp1 > 0 && cmp2 > 0)
186 {
187 rotate_right (&n->right, c, c->right);
188 rotate_right (&sp->root, n, n->right);
189 }
190 else if (cmp1 < 0 && cmp2 > 0)
191 {
192 rotate_right (&n->left, c, c->right);
193 rotate_left (&sp->root, n, n->left);
194 }
195 else if (cmp1 > 0 && cmp2 < 0)
196 {
197 rotate_left (&n->right, c, c->left);
198 rotate_right (&sp->root, n, n->right);
199 }
200 } while (1);
201 }
202
203 /* Call FN, passing it the DATA, for every node below NODE, all of
204 which are from SP, following an in-order traversal. If FN every
205 returns a non-zero value, the iteration ceases immediately, and the
206 value is returned. Otherwise, this function returns 0. */
207
208 static int
209 splay_tree_foreach_helper (splay_tree_node node,
210 splay_tree_foreach_fn fn, void *data)
211 {
212 int val;
213 splay_tree_node *stack;
214 int stack_ptr, stack_size;
215
216 /* A non-recursive implementation is used to avoid filling the stack
217 for large trees. Splay trees are worst case O(n) in the depth of
218 the tree. */
219
220 #define INITIAL_STACK_SIZE 100
221 stack_size = INITIAL_STACK_SIZE;
222 stack_ptr = 0;
223 stack = XNEWVEC (splay_tree_node, stack_size);
224 val = 0;
225
226 for (;;)
227 {
228 while (node != NULL)
229 {
230 if (stack_ptr == stack_size)
231 {
232 stack_size *= 2;
233 stack = XRESIZEVEC (splay_tree_node, stack, stack_size);
234 }
235 stack[stack_ptr++] = node;
236 node = node->left;
237 }
238
239 if (stack_ptr == 0)
240 break;
241
242 node = stack[--stack_ptr];
243
244 val = (*fn) (node, data);
245 if (val)
246 break;
247
248 node = node->right;
249 }
250
251 XDELETEVEC (stack);
252 return val;
253 }
254
255 /* An allocator and deallocator based on xmalloc. */
256 static void *
257 splay_tree_xmalloc_allocate (int size, void *data ATTRIBUTE_UNUSED)
258 {
259 return (void *) xmalloc (size);
260 }
261
262 static void
263 splay_tree_xmalloc_deallocate (void *object, void *data ATTRIBUTE_UNUSED)
264 {
265 free (object);
266 }
267
268
269 /* Allocate a new splay tree, using COMPARE_FN to compare nodes,
270 DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
271 values. Use xmalloc to allocate the splay tree structure, and any
272 nodes added. */
273
274 splay_tree
275 splay_tree_new (splay_tree_compare_fn compare_fn,
276 splay_tree_delete_key_fn delete_key_fn,
277 splay_tree_delete_value_fn delete_value_fn)
278 {
279 return (splay_tree_new_with_allocator
280 (compare_fn, delete_key_fn, delete_value_fn,
281 splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate, 0));
282 }
283
284
285 /* Allocate a new splay tree, using COMPARE_FN to compare nodes,
286 DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
287 values. */
288
289 splay_tree
290 splay_tree_new_with_allocator (splay_tree_compare_fn compare_fn,
291 splay_tree_delete_key_fn delete_key_fn,
292 splay_tree_delete_value_fn delete_value_fn,
293 splay_tree_allocate_fn allocate_fn,
294 splay_tree_deallocate_fn deallocate_fn,
295 void *allocate_data)
296 {
297 return
298 splay_tree_new_typed_alloc (compare_fn, delete_key_fn, delete_value_fn,
299 allocate_fn, allocate_fn, deallocate_fn,
300 allocate_data);
301 }
302
303 /*
304
305 @deftypefn Supplemental splay_tree splay_tree_new_with_typed_alloc @
306 (splay_tree_compare_fn @var{compare_fn}, @
307 splay_tree_delete_key_fn @var{delete_key_fn}, @
308 splay_tree_delete_value_fn @var{delete_value_fn}, @
309 splay_tree_allocate_fn @var{tree_allocate_fn}, @
310 splay_tree_allocate_fn @var{node_allocate_fn}, @
311 splay_tree_deallocate_fn @var{deallocate_fn}, @
312 void * @var{allocate_data})
313
314 This function creates a splay tree that uses two different allocators
315 @var{tree_allocate_fn} and @var{node_allocate_fn} to use for allocating the
316 tree itself and its nodes respectively. This is useful when variables of
317 different types need to be allocated with different allocators.
318
319 The splay tree will use @var{compare_fn} to compare nodes,
320 @var{delete_key_fn} to deallocate keys, and @var{delete_value_fn} to
321 deallocate values. Keys and values will be deallocated when the
322 tree is deleted using splay_tree_delete or when a node is removed
323 using splay_tree_remove. splay_tree_insert will release the previously
324 inserted key and value using @var{delete_key_fn} and @var{delete_value_fn}
325 if the inserted key is already found in the tree.
326
327 @end deftypefn
328
329 */
330
331 splay_tree
332 splay_tree_new_typed_alloc (splay_tree_compare_fn compare_fn,
333 splay_tree_delete_key_fn delete_key_fn,
334 splay_tree_delete_value_fn delete_value_fn,
335 splay_tree_allocate_fn tree_allocate_fn,
336 splay_tree_allocate_fn node_allocate_fn,
337 splay_tree_deallocate_fn deallocate_fn,
338 void * allocate_data)
339 {
340 splay_tree sp = (splay_tree) (*tree_allocate_fn)
341 (sizeof (struct splay_tree_s), allocate_data);
342
343 sp->root = 0;
344 sp->comp = compare_fn;
345 sp->delete_key = delete_key_fn;
346 sp->delete_value = delete_value_fn;
347 sp->allocate = node_allocate_fn;
348 sp->deallocate = deallocate_fn;
349 sp->allocate_data = allocate_data;
350
351 return sp;
352 }
353
354 /* Deallocate SP. */
355
356 void
357 splay_tree_delete (splay_tree sp)
358 {
359 splay_tree_delete_helper (sp, sp->root);
360 (*sp->deallocate) ((char*) sp, sp->allocate_data);
361 }
362
363 /* Insert a new node (associating KEY with DATA) into SP. If a
364 previous node with the indicated KEY exists, its data is replaced
365 with the new value. Returns the new node. */
366
367 splay_tree_node
368 splay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value)
369 {
370 int comparison = 0;
371
372 splay_tree_splay (sp, key);
373
374 if (sp->root)
375 comparison = (*sp->comp)(sp->root->key, key);
376
377 if (sp->root && comparison == 0)
378 {
379 /* If the root of the tree already has the indicated KEY, delete
380 the old key and old value, and replace them with KEY and VALUE. */
381 if (sp->delete_key)
382 (*sp->delete_key) (sp->root->key);
383 if (sp->delete_value)
384 (*sp->delete_value)(sp->root->value);
385 sp->root->key = key;
386 sp->root->value = value;
387 }
388 else
389 {
390 /* Create a new node, and insert it at the root. */
391 splay_tree_node node;
392
393 node = ((splay_tree_node)
394 (*sp->allocate) (sizeof (struct splay_tree_node_s),
395 sp->allocate_data));
396 node->key = key;
397 node->value = value;
398
399 if (!sp->root)
400 node->left = node->right = 0;
401 else if (comparison < 0)
402 {
403 node->left = sp->root;
404 node->right = node->left->right;
405 node->left->right = 0;
406 }
407 else
408 {
409 node->right = sp->root;
410 node->left = node->right->left;
411 node->right->left = 0;
412 }
413
414 sp->root = node;
415 }
416
417 return sp->root;
418 }
419
420 /* Remove KEY from SP. It is not an error if it did not exist. */
421
422 void
423 splay_tree_remove (splay_tree sp, splay_tree_key key)
424 {
425 splay_tree_splay (sp, key);
426
427 if (sp->root && (*sp->comp) (sp->root->key, key) == 0)
428 {
429 splay_tree_node left, right;
430
431 left = sp->root->left;
432 right = sp->root->right;
433
434 /* Delete the root node itself. */
435 if (sp->delete_key)
436 (*sp->delete_key) (sp->root->key);
437 if (sp->delete_value)
438 (*sp->delete_value) (sp->root->value);
439 (*sp->deallocate) (sp->root, sp->allocate_data);
440
441 /* One of the children is now the root. Doesn't matter much
442 which, so long as we preserve the properties of the tree. */
443 if (left)
444 {
445 sp->root = left;
446
447 /* If there was a right child as well, hang it off the
448 right-most leaf of the left child. */
449 if (right)
450 {
451 while (left->right)
452 left = left->right;
453 left->right = right;
454 }
455 }
456 else
457 sp->root = right;
458 }
459 }
460
461 /* Lookup KEY in SP, returning VALUE if present, and NULL
462 otherwise. */
463
464 splay_tree_node
465 splay_tree_lookup (splay_tree sp, splay_tree_key key)
466 {
467 splay_tree_splay (sp, key);
468
469 if (sp->root && (*sp->comp)(sp->root->key, key) == 0)
470 return sp->root;
471 else
472 return 0;
473 }
474
475 /* Return the node in SP with the greatest key. */
476
477 splay_tree_node
478 splay_tree_max (splay_tree sp)
479 {
480 splay_tree_node n = sp->root;
481
482 if (!n)
483 return NULL;
484
485 while (n->right)
486 n = n->right;
487
488 return n;
489 }
490
491 /* Return the node in SP with the smallest key. */
492
493 splay_tree_node
494 splay_tree_min (splay_tree sp)
495 {
496 splay_tree_node n = sp->root;
497
498 if (!n)
499 return NULL;
500
501 while (n->left)
502 n = n->left;
503
504 return n;
505 }
506
507 /* Return the immediate predecessor KEY, or NULL if there is no
508 predecessor. KEY need not be present in the tree. */
509
510 splay_tree_node
511 splay_tree_predecessor (splay_tree sp, splay_tree_key key)
512 {
513 int comparison;
514 splay_tree_node node;
515
516 /* If the tree is empty, there is certainly no predecessor. */
517 if (!sp->root)
518 return NULL;
519
520 /* Splay the tree around KEY. That will leave either the KEY
521 itself, its predecessor, or its successor at the root. */
522 splay_tree_splay (sp, key);
523 comparison = (*sp->comp)(sp->root->key, key);
524
525 /* If the predecessor is at the root, just return it. */
526 if (comparison < 0)
527 return sp->root;
528
529 /* Otherwise, find the rightmost element of the left subtree. */
530 node = sp->root->left;
531 if (node)
532 while (node->right)
533 node = node->right;
534
535 return node;
536 }
537
538 /* Return the immediate successor KEY, or NULL if there is no
539 successor. KEY need not be present in the tree. */
540
541 splay_tree_node
542 splay_tree_successor (splay_tree sp, splay_tree_key key)
543 {
544 int comparison;
545 splay_tree_node node;
546
547 /* If the tree is empty, there is certainly no successor. */
548 if (!sp->root)
549 return NULL;
550
551 /* Splay the tree around KEY. That will leave either the KEY
552 itself, its predecessor, or its successor at the root. */
553 splay_tree_splay (sp, key);
554 comparison = (*sp->comp)(sp->root->key, key);
555
556 /* If the successor is at the root, just return it. */
557 if (comparison > 0)
558 return sp->root;
559
560 /* Otherwise, find the leftmost element of the right subtree. */
561 node = sp->root->right;
562 if (node)
563 while (node->left)
564 node = node->left;
565
566 return node;
567 }
568
569 /* Call FN, passing it the DATA, for every node in SP, following an
570 in-order traversal. If FN every returns a non-zero value, the
571 iteration ceases immediately, and the value is returned.
572 Otherwise, this function returns 0. */
573
574 int
575 splay_tree_foreach (splay_tree sp, splay_tree_foreach_fn fn, void *data)
576 {
577 return splay_tree_foreach_helper (sp->root, fn, data);
578 }
579
580 /* Splay-tree comparison function, treating the keys as ints. */
581
582 int
583 splay_tree_compare_ints (splay_tree_key k1, splay_tree_key k2)
584 {
585 if ((int) k1 < (int) k2)
586 return -1;
587 else if ((int) k1 > (int) k2)
588 return 1;
589 else
590 return 0;
591 }
592
593 /* Splay-tree comparison function, treating the keys as pointers. */
594
595 int
596 splay_tree_compare_pointers (splay_tree_key k1, splay_tree_key k2)
597 {
598 if ((char*) k1 < (char*) k2)
599 return -1;
600 else if ((char*) k1 > (char*) k2)
601 return 1;
602 else
603 return 0;
604 }
605
606 /* Splay-tree comparison function, treating the keys as strings. */
607
608 int
609 splay_tree_compare_strings (splay_tree_key k1, splay_tree_key k2)
610 {
611 return strcmp ((char *) k1, (char *) k2);
612 }
613
614 /* Splay-tree delete function, simply using free. */
615
616 void
617 splay_tree_delete_pointers (splay_tree_value value)
618 {
619 free ((void *) value);
620 }