Commit | Line | Data |
---|---|---|
252b5132 | 1 | /* A splay-tree datatype. |
e00bc6a7 | 2 | Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc. |
252b5132 RH |
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 | |
979c05d3 NC |
19 | the Free Software Foundation, 51 Franklin Street - Fifth Floor, |
20 | Boston, MA 02110-1301, USA. */ | |
252b5132 RH |
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 | ||
60c64519 DD |
35 | #include <stdio.h> |
36 | ||
252b5132 RH |
37 | #include "libiberty.h" |
38 | #include "splay-tree.h" | |
39 | ||
1e45deed DD |
40 | static void splay_tree_delete_helper (splay_tree, splay_tree_node); |
41 | static void splay_tree_splay (splay_tree, splay_tree_key); | |
42 | static splay_tree_node splay_tree_splay_helper (splay_tree, | |
252b5132 RH |
43 | splay_tree_key, |
44 | splay_tree_node*, | |
45 | splay_tree_node*, | |
1e45deed DD |
46 | splay_tree_node*); |
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 | ||
110 | /* Help splay SP around KEY. PARENT and GRANDPARENT are the parent | |
111 | and grandparent, respectively, of NODE. */ | |
112 | ||
113 | static splay_tree_node | |
1e45deed DD |
114 | splay_tree_splay_helper (splay_tree sp, splay_tree_key key, |
115 | splay_tree_node *node, splay_tree_node *parent, | |
116 | splay_tree_node *grandparent) | |
252b5132 RH |
117 | { |
118 | splay_tree_node *next; | |
119 | splay_tree_node n; | |
120 | int comparison; | |
121 | ||
122 | n = *node; | |
123 | ||
124 | if (!n) | |
125 | return *parent; | |
126 | ||
127 | comparison = (*sp->comp) (key, n->key); | |
128 | ||
129 | if (comparison == 0) | |
130 | /* We've found the target. */ | |
131 | next = 0; | |
132 | else if (comparison < 0) | |
133 | /* The target is to the left. */ | |
134 | next = &n->left; | |
135 | else | |
136 | /* The target is to the right. */ | |
137 | next = &n->right; | |
138 | ||
139 | if (next) | |
140 | { | |
141 | /* Continue down the tree. */ | |
142 | n = splay_tree_splay_helper (sp, key, next, node, parent); | |
143 | ||
144 | /* The recursive call will change the place to which NODE | |
145 | points. */ | |
146 | if (*node != n) | |
147 | return n; | |
148 | } | |
149 | ||
150 | if (!parent) | |
151 | /* NODE is the root. We are done. */ | |
152 | return n; | |
153 | ||
154 | /* First, handle the case where there is no grandparent (i.e., | |
155 | *PARENT is the root of the tree.) */ | |
156 | if (!grandparent) | |
157 | { | |
158 | if (n == (*parent)->left) | |
159 | { | |
160 | *node = n->right; | |
161 | n->right = *parent; | |
162 | } | |
163 | else | |
164 | { | |
165 | *node = n->left; | |
166 | n->left = *parent; | |
167 | } | |
168 | *parent = n; | |
169 | return n; | |
170 | } | |
171 | ||
172 | /* Next handle the cases where both N and *PARENT are left children, | |
173 | or where both are right children. */ | |
174 | if (n == (*parent)->left && *parent == (*grandparent)->left) | |
175 | { | |
176 | splay_tree_node p = *parent; | |
177 | ||
178 | (*grandparent)->left = p->right; | |
179 | p->right = *grandparent; | |
180 | p->left = n->right; | |
181 | n->right = p; | |
182 | *grandparent = n; | |
183 | return n; | |
184 | } | |
185 | else if (n == (*parent)->right && *parent == (*grandparent)->right) | |
186 | { | |
187 | splay_tree_node p = *parent; | |
188 | ||
189 | (*grandparent)->right = p->left; | |
190 | p->left = *grandparent; | |
191 | p->right = n->left; | |
192 | n->left = p; | |
193 | *grandparent = n; | |
194 | return n; | |
195 | } | |
196 | ||
197 | /* Finally, deal with the case where N is a left child, but *PARENT | |
198 | is a right child, or vice versa. */ | |
199 | if (n == (*parent)->left) | |
200 | { | |
201 | (*parent)->left = n->right; | |
202 | n->right = *parent; | |
203 | (*grandparent)->right = n->left; | |
204 | n->left = *grandparent; | |
205 | *grandparent = n; | |
206 | return n; | |
207 | } | |
208 | else | |
209 | { | |
210 | (*parent)->right = n->left; | |
211 | n->left = *parent; | |
212 | (*grandparent)->left = n->right; | |
213 | n->right = *grandparent; | |
214 | *grandparent = n; | |
215 | return n; | |
216 | } | |
217 | } | |
218 | ||
219 | /* Splay SP around KEY. */ | |
220 | ||
221 | static void | |
1e45deed | 222 | splay_tree_splay (splay_tree sp, splay_tree_key key) |
252b5132 RH |
223 | { |
224 | if (sp->root == 0) | |
225 | return; | |
226 | ||
227 | splay_tree_splay_helper (sp, key, &sp->root, | |
228 | /*grandparent=*/0, /*parent=*/0); | |
229 | } | |
230 | ||
231 | /* Call FN, passing it the DATA, for every node below NODE, all of | |
232 | which are from SP, following an in-order traversal. If FN every | |
233 | returns a non-zero value, the iteration ceases immediately, and the | |
234 | value is returned. Otherwise, this function returns 0. */ | |
235 | ||
236 | static int | |
1e45deed DD |
237 | splay_tree_foreach_helper (splay_tree sp, splay_tree_node node, |
238 | splay_tree_foreach_fn fn, void *data) | |
252b5132 RH |
239 | { |
240 | int val; | |
241 | ||
242 | if (!node) | |
243 | return 0; | |
244 | ||
245 | val = splay_tree_foreach_helper (sp, node->left, fn, data); | |
246 | if (val) | |
247 | return val; | |
248 | ||
249 | val = (*fn)(node, data); | |
250 | if (val) | |
251 | return val; | |
252 | ||
253 | return splay_tree_foreach_helper (sp, node->right, fn, data); | |
254 | } | |
255 | ||
2bbcdae9 JB |
256 | |
257 | /* An allocator and deallocator based on xmalloc. */ | |
258 | static void * | |
1e45deed | 259 | splay_tree_xmalloc_allocate (int size, void *data ATTRIBUTE_UNUSED) |
2bbcdae9 | 260 | { |
585cc78f | 261 | return (void *) xmalloc (size); |
2bbcdae9 JB |
262 | } |
263 | ||
264 | static void | |
1e45deed | 265 | splay_tree_xmalloc_deallocate (void *object, void *data ATTRIBUTE_UNUSED) |
2bbcdae9 JB |
266 | { |
267 | free (object); | |
268 | } | |
269 | ||
270 | ||
252b5132 RH |
271 | /* Allocate a new splay tree, using COMPARE_FN to compare nodes, |
272 | DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate | |
2bbcdae9 JB |
273 | values. Use xmalloc to allocate the splay tree structure, and any |
274 | nodes added. */ | |
252b5132 RH |
275 | |
276 | splay_tree | |
1e45deed DD |
277 | splay_tree_new (splay_tree_compare_fn compare_fn, |
278 | splay_tree_delete_key_fn delete_key_fn, | |
279 | splay_tree_delete_value_fn delete_value_fn) | |
252b5132 | 280 | { |
2bbcdae9 JB |
281 | return (splay_tree_new_with_allocator |
282 | (compare_fn, delete_key_fn, delete_value_fn, | |
283 | splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate, 0)); | |
284 | } | |
285 | ||
286 | ||
287 | /* Allocate a new splay tree, using COMPARE_FN to compare nodes, | |
288 | DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate | |
289 | values. */ | |
290 | ||
291 | splay_tree | |
1e45deed DD |
292 | splay_tree_new_with_allocator (splay_tree_compare_fn compare_fn, |
293 | splay_tree_delete_key_fn delete_key_fn, | |
294 | splay_tree_delete_value_fn delete_value_fn, | |
295 | splay_tree_allocate_fn allocate_fn, | |
296 | splay_tree_deallocate_fn deallocate_fn, | |
297 | void *allocate_data) | |
2bbcdae9 JB |
298 | { |
299 | splay_tree sp = (splay_tree) (*allocate_fn) (sizeof (struct splay_tree_s), | |
300 | allocate_data); | |
252b5132 RH |
301 | sp->root = 0; |
302 | sp->comp = compare_fn; | |
303 | sp->delete_key = delete_key_fn; | |
304 | sp->delete_value = delete_value_fn; | |
2bbcdae9 JB |
305 | sp->allocate = allocate_fn; |
306 | sp->deallocate = deallocate_fn; | |
307 | sp->allocate_data = allocate_data; | |
252b5132 RH |
308 | |
309 | return sp; | |
310 | } | |
311 | ||
312 | /* Deallocate SP. */ | |
313 | ||
314 | void | |
1e45deed | 315 | splay_tree_delete (splay_tree sp) |
252b5132 RH |
316 | { |
317 | splay_tree_delete_helper (sp, sp->root); | |
2bbcdae9 | 318 | (*sp->deallocate) ((char*) sp, sp->allocate_data); |
252b5132 RH |
319 | } |
320 | ||
321 | /* Insert a new node (associating KEY with DATA) into SP. If a | |
322 | previous node with the indicated KEY exists, its data is replaced | |
0c0a36a4 | 323 | with the new value. Returns the new node. */ |
252b5132 | 324 | |
0c0a36a4 | 325 | splay_tree_node |
1e45deed | 326 | splay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value) |
252b5132 | 327 | { |
af32ff69 | 328 | int comparison = 0; |
252b5132 RH |
329 | |
330 | splay_tree_splay (sp, key); | |
331 | ||
332 | if (sp->root) | |
333 | comparison = (*sp->comp)(sp->root->key, key); | |
334 | ||
335 | if (sp->root && comparison == 0) | |
336 | { | |
337 | /* If the root of the tree already has the indicated KEY, just | |
338 | replace the value with VALUE. */ | |
339 | if (sp->delete_value) | |
340 | (*sp->delete_value)(sp->root->value); | |
341 | sp->root->value = value; | |
342 | } | |
343 | else | |
344 | { | |
345 | /* Create a new node, and insert it at the root. */ | |
346 | splay_tree_node node; | |
347 | ||
2bbcdae9 JB |
348 | node = ((splay_tree_node) |
349 | (*sp->allocate) (sizeof (struct splay_tree_node_s), | |
350 | sp->allocate_data)); | |
252b5132 RH |
351 | node->key = key; |
352 | node->value = value; | |
353 | ||
354 | if (!sp->root) | |
355 | node->left = node->right = 0; | |
356 | else if (comparison < 0) | |
357 | { | |
358 | node->left = sp->root; | |
359 | node->right = node->left->right; | |
360 | node->left->right = 0; | |
361 | } | |
362 | else | |
363 | { | |
364 | node->right = sp->root; | |
365 | node->left = node->right->left; | |
366 | node->right->left = 0; | |
367 | } | |
368 | ||
74bcd529 DD |
369 | sp->root = node; |
370 | } | |
0c0a36a4 ILT |
371 | |
372 | return sp->root; | |
252b5132 RH |
373 | } |
374 | ||
afe36a78 RH |
375 | /* Remove KEY from SP. It is not an error if it did not exist. */ |
376 | ||
377 | void | |
1e45deed | 378 | splay_tree_remove (splay_tree sp, splay_tree_key key) |
afe36a78 RH |
379 | { |
380 | splay_tree_splay (sp, key); | |
381 | ||
382 | if (sp->root && (*sp->comp) (sp->root->key, key) == 0) | |
383 | { | |
384 | splay_tree_node left, right; | |
385 | ||
386 | left = sp->root->left; | |
387 | right = sp->root->right; | |
388 | ||
389 | /* Delete the root node itself. */ | |
390 | if (sp->delete_value) | |
391 | (*sp->delete_value) (sp->root->value); | |
2bbcdae9 | 392 | (*sp->deallocate) (sp->root, sp->allocate_data); |
afe36a78 RH |
393 | |
394 | /* One of the children is now the root. Doesn't matter much | |
395 | which, so long as we preserve the properties of the tree. */ | |
396 | if (left) | |
397 | { | |
398 | sp->root = left; | |
399 | ||
400 | /* If there was a right child as well, hang it off the | |
401 | right-most leaf of the left child. */ | |
402 | if (right) | |
403 | { | |
404 | while (left->right) | |
405 | left = left->right; | |
406 | left->right = right; | |
407 | } | |
408 | } | |
409 | else | |
410 | sp->root = right; | |
411 | } | |
412 | } | |
413 | ||
252b5132 RH |
414 | /* Lookup KEY in SP, returning VALUE if present, and NULL |
415 | otherwise. */ | |
416 | ||
417 | splay_tree_node | |
1e45deed | 418 | splay_tree_lookup (splay_tree sp, splay_tree_key key) |
252b5132 RH |
419 | { |
420 | splay_tree_splay (sp, key); | |
421 | ||
422 | if (sp->root && (*sp->comp)(sp->root->key, key) == 0) | |
423 | return sp->root; | |
424 | else | |
425 | return 0; | |
426 | } | |
427 | ||
e00bc6a7 DD |
428 | /* Return the node in SP with the greatest key. */ |
429 | ||
430 | splay_tree_node | |
1e45deed | 431 | splay_tree_max (splay_tree sp) |
e00bc6a7 DD |
432 | { |
433 | splay_tree_node n = sp->root; | |
434 | ||
435 | if (!n) | |
436 | return NULL; | |
437 | ||
438 | while (n->right) | |
439 | n = n->right; | |
440 | ||
441 | return n; | |
442 | } | |
443 | ||
444 | /* Return the node in SP with the smallest key. */ | |
445 | ||
446 | splay_tree_node | |
1e45deed | 447 | splay_tree_min (splay_tree sp) |
e00bc6a7 DD |
448 | { |
449 | splay_tree_node n = sp->root; | |
450 | ||
451 | if (!n) | |
452 | return NULL; | |
453 | ||
454 | while (n->left) | |
455 | n = n->left; | |
456 | ||
457 | return n; | |
458 | } | |
459 | ||
74bcd529 DD |
460 | /* Return the immediate predecessor KEY, or NULL if there is no |
461 | predecessor. KEY need not be present in the tree. */ | |
462 | ||
463 | splay_tree_node | |
1e45deed | 464 | splay_tree_predecessor (splay_tree sp, splay_tree_key key) |
74bcd529 DD |
465 | { |
466 | int comparison; | |
467 | splay_tree_node node; | |
468 | ||
469 | /* If the tree is empty, there is certainly no predecessor. */ | |
470 | if (!sp->root) | |
471 | return NULL; | |
472 | ||
473 | /* Splay the tree around KEY. That will leave either the KEY | |
474 | itself, its predecessor, or its successor at the root. */ | |
475 | splay_tree_splay (sp, key); | |
476 | comparison = (*sp->comp)(sp->root->key, key); | |
477 | ||
478 | /* If the predecessor is at the root, just return it. */ | |
479 | if (comparison < 0) | |
480 | return sp->root; | |
481 | ||
0f3538e7 | 482 | /* Otherwise, find the rightmost element of the left subtree. */ |
74bcd529 DD |
483 | node = sp->root->left; |
484 | if (node) | |
485 | while (node->right) | |
486 | node = node->right; | |
487 | ||
488 | return node; | |
489 | } | |
490 | ||
491 | /* Return the immediate successor KEY, or NULL if there is no | |
a54ba43f | 492 | successor. KEY need not be present in the tree. */ |
74bcd529 DD |
493 | |
494 | splay_tree_node | |
1e45deed | 495 | splay_tree_successor (splay_tree sp, splay_tree_key key) |
74bcd529 DD |
496 | { |
497 | int comparison; | |
498 | splay_tree_node node; | |
499 | ||
a54ba43f | 500 | /* If the tree is empty, there is certainly no successor. */ |
74bcd529 DD |
501 | if (!sp->root) |
502 | return NULL; | |
503 | ||
504 | /* Splay the tree around KEY. That will leave either the KEY | |
505 | itself, its predecessor, or its successor at the root. */ | |
506 | splay_tree_splay (sp, key); | |
507 | comparison = (*sp->comp)(sp->root->key, key); | |
508 | ||
509 | /* If the successor is at the root, just return it. */ | |
510 | if (comparison > 0) | |
511 | return sp->root; | |
512 | ||
0f3538e7 | 513 | /* Otherwise, find the leftmost element of the right subtree. */ |
74bcd529 DD |
514 | node = sp->root->right; |
515 | if (node) | |
516 | while (node->left) | |
517 | node = node->left; | |
518 | ||
519 | return node; | |
520 | } | |
521 | ||
252b5132 RH |
522 | /* Call FN, passing it the DATA, for every node in SP, following an |
523 | in-order traversal. If FN every returns a non-zero value, the | |
524 | iteration ceases immediately, and the value is returned. | |
525 | Otherwise, this function returns 0. */ | |
526 | ||
527 | int | |
1e45deed | 528 | splay_tree_foreach (splay_tree sp, splay_tree_foreach_fn fn, void *data) |
252b5132 RH |
529 | { |
530 | return splay_tree_foreach_helper (sp, sp->root, fn, data); | |
531 | } | |
532 | ||
533 | /* Splay-tree comparison function, treating the keys as ints. */ | |
534 | ||
535 | int | |
1e45deed | 536 | splay_tree_compare_ints (splay_tree_key k1, splay_tree_key k2) |
252b5132 RH |
537 | { |
538 | if ((int) k1 < (int) k2) | |
539 | return -1; | |
540 | else if ((int) k1 > (int) k2) | |
541 | return 1; | |
542 | else | |
543 | return 0; | |
544 | } | |
545 | ||
546 | /* Splay-tree comparison function, treating the keys as pointers. */ | |
547 | ||
548 | int | |
1e45deed | 549 | splay_tree_compare_pointers (splay_tree_key k1, splay_tree_key k2) |
252b5132 RH |
550 | { |
551 | if ((char*) k1 < (char*) k2) | |
552 | return -1; | |
553 | else if ((char*) k1 > (char*) k2) | |
554 | return 1; | |
555 | else | |
556 | return 0; | |
557 | } |