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