pa.c (hppa_profile_hook): Remove offset adjustment.
[official-gcc.git] / libiberty / splay-tree.c
blob4bbb39a62ca476de7dd63b5ee592373e7a9a51a2
1 /* A splay-tree datatype.
2 Copyright (C) 1998-2019 Free Software Foundation, Inc.
3 Contributed by Mark Mitchell (mark@markmitchell.com).
5 This file is part of GNU CC.
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.
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.
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. */
22 /* For an easily readable description of splay-trees, see:
24 Lewis, Harry R. and Denenberg, Larry. Data Structures and Their
25 Algorithms. Harper-Collins, Inc. 1991. */
27 #ifdef HAVE_CONFIG_H
28 #include "config.h"
29 #endif
31 #ifdef HAVE_STDLIB_H
32 #include <stdlib.h>
33 #endif
34 #ifdef HAVE_STRING_H
35 #include <string.h>
36 #endif
38 #include <stdio.h>
40 #include "libiberty.h"
41 #include "splay-tree.h"
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*);
52 /* Deallocate NODE (a member of SP), and all its sub-trees. */
54 static void
55 splay_tree_delete_helper (splay_tree sp, splay_tree_node node)
57 splay_tree_node pending = 0;
58 splay_tree_node active = 0;
60 if (!node)
61 return;
63 #define KDEL(x) if (sp->delete_key) (*sp->delete_key)(x);
64 #define VDEL(x) if (sp->delete_value) (*sp->delete_value)(x);
66 KDEL (node->key);
67 VDEL (node->value);
69 /* We use the "key" field to hold the "next" pointer. */
70 node->key = (splay_tree_key)pending;
71 pending = (splay_tree_node)node;
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. */
77 while (pending)
79 active = pending;
80 pending = 0;
81 while (active)
83 splay_tree_node temp;
85 /* active points to a node which has its key and value
86 deallocated, we just need to process left and right. */
88 if (active->left)
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);
95 if (active->right)
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);
103 temp = active;
104 active = (splay_tree_node)(temp->key);
105 (*sp->deallocate) ((char*) temp, sp->allocate_data);
108 #undef KDEL
109 #undef VDEL
112 /* Rotate the edge joining the left child N with its parent P. PP is the
113 grandparents' pointer to P. */
115 static inline void
116 rotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
118 splay_tree_node tmp;
119 tmp = n->right;
120 n->right = p;
121 p->left = tmp;
122 *pp = n;
125 /* Rotate the edge joining the right child N with its parent P. PP is the
126 grandparents' pointer to P. */
128 static inline void
129 rotate_right (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
131 splay_tree_node tmp;
132 tmp = n->left;
133 n->left = p;
134 p->right = tmp;
135 *pp = n;
138 /* Bottom up splay of key. */
140 static void
141 splay_tree_splay (splay_tree sp, splay_tree_key key)
143 if (sp->root == 0)
144 return;
146 do {
147 int cmp1, cmp2;
148 splay_tree_node n, c;
150 n = sp->root;
151 cmp1 = (*sp->comp) (key, n->key);
153 /* Found. */
154 if (cmp1 == 0)
155 return;
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;
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))
172 if (cmp1 < 0)
173 rotate_left (&sp->root, n, c);
174 else
175 rotate_right (&sp->root, n, c);
176 return;
179 /* Now we have the four cases of double-rotation. */
180 if (cmp1 < 0 && cmp2 < 0)
182 rotate_left (&n->left, c, c->left);
183 rotate_left (&sp->root, n, n->left);
185 else if (cmp1 > 0 && cmp2 > 0)
187 rotate_right (&n->right, c, c->right);
188 rotate_right (&sp->root, n, n->right);
190 else if (cmp1 < 0 && cmp2 > 0)
192 rotate_right (&n->left, c, c->right);
193 rotate_left (&sp->root, n, n->left);
195 else if (cmp1 > 0 && cmp2 < 0)
197 rotate_left (&n->right, c, c->left);
198 rotate_right (&sp->root, n, n->right);
200 } while (1);
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. */
208 static int
209 splay_tree_foreach_helper (splay_tree_node node,
210 splay_tree_foreach_fn fn, void *data)
212 int val;
213 splay_tree_node *stack;
214 int stack_ptr, stack_size;
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. */
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;
226 for (;;)
228 while (node != NULL)
230 if (stack_ptr == stack_size)
232 stack_size *= 2;
233 stack = XRESIZEVEC (splay_tree_node, stack, stack_size);
235 stack[stack_ptr++] = node;
236 node = node->left;
239 if (stack_ptr == 0)
240 break;
242 node = stack[--stack_ptr];
244 val = (*fn) (node, data);
245 if (val)
246 break;
248 node = node->right;
251 XDELETEVEC (stack);
252 return val;
255 /* An allocator and deallocator based on xmalloc. */
256 static void *
257 splay_tree_xmalloc_allocate (int size, void *data ATTRIBUTE_UNUSED)
259 return (void *) xmalloc (size);
262 static void
263 splay_tree_xmalloc_deallocate (void *object, void *data ATTRIBUTE_UNUSED)
265 free (object);
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. */
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)
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));
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. */
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)
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);
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})
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.
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.
327 @end deftypefn
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)
340 splay_tree sp = (splay_tree) (*tree_allocate_fn)
341 (sizeof (struct splay_tree_s), allocate_data);
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;
351 return sp;
354 /* Deallocate SP. */
356 void
357 splay_tree_delete (splay_tree sp)
359 splay_tree_delete_helper (sp, sp->root);
360 (*sp->deallocate) ((char*) sp, sp->allocate_data);
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. */
367 splay_tree_node
368 splay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value)
370 int comparison = 0;
372 splay_tree_splay (sp, key);
374 if (sp->root)
375 comparison = (*sp->comp)(sp->root->key, key);
377 if (sp->root && comparison == 0)
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;
388 else
390 /* Create a new node, and insert it at the root. */
391 splay_tree_node node;
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;
399 if (!sp->root)
400 node->left = node->right = 0;
401 else if (comparison < 0)
403 node->left = sp->root;
404 node->right = node->left->right;
405 node->left->right = 0;
407 else
409 node->right = sp->root;
410 node->left = node->right->left;
411 node->right->left = 0;
414 sp->root = node;
417 return sp->root;
420 /* Remove KEY from SP. It is not an error if it did not exist. */
422 void
423 splay_tree_remove (splay_tree sp, splay_tree_key key)
425 splay_tree_splay (sp, key);
427 if (sp->root && (*sp->comp) (sp->root->key, key) == 0)
429 splay_tree_node left, right;
431 left = sp->root->left;
432 right = sp->root->right;
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);
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)
445 sp->root = left;
447 /* If there was a right child as well, hang it off the
448 right-most leaf of the left child. */
449 if (right)
451 while (left->right)
452 left = left->right;
453 left->right = right;
456 else
457 sp->root = right;
461 /* Lookup KEY in SP, returning VALUE if present, and NULL
462 otherwise. */
464 splay_tree_node
465 splay_tree_lookup (splay_tree sp, splay_tree_key key)
467 splay_tree_splay (sp, key);
469 if (sp->root && (*sp->comp)(sp->root->key, key) == 0)
470 return sp->root;
471 else
472 return 0;
475 /* Return the node in SP with the greatest key. */
477 splay_tree_node
478 splay_tree_max (splay_tree sp)
480 splay_tree_node n = sp->root;
482 if (!n)
483 return NULL;
485 while (n->right)
486 n = n->right;
488 return n;
491 /* Return the node in SP with the smallest key. */
493 splay_tree_node
494 splay_tree_min (splay_tree sp)
496 splay_tree_node n = sp->root;
498 if (!n)
499 return NULL;
501 while (n->left)
502 n = n->left;
504 return n;
507 /* Return the immediate predecessor KEY, or NULL if there is no
508 predecessor. KEY need not be present in the tree. */
510 splay_tree_node
511 splay_tree_predecessor (splay_tree sp, splay_tree_key key)
513 int comparison;
514 splay_tree_node node;
516 /* If the tree is empty, there is certainly no predecessor. */
517 if (!sp->root)
518 return NULL;
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);
525 /* If the predecessor is at the root, just return it. */
526 if (comparison < 0)
527 return sp->root;
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;
535 return node;
538 /* Return the immediate successor KEY, or NULL if there is no
539 successor. KEY need not be present in the tree. */
541 splay_tree_node
542 splay_tree_successor (splay_tree sp, splay_tree_key key)
544 int comparison;
545 splay_tree_node node;
547 /* If the tree is empty, there is certainly no successor. */
548 if (!sp->root)
549 return NULL;
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);
556 /* If the successor is at the root, just return it. */
557 if (comparison > 0)
558 return sp->root;
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;
566 return node;
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. */
575 splay_tree_foreach (splay_tree sp, splay_tree_foreach_fn fn, void *data)
577 return splay_tree_foreach_helper (sp->root, fn, data);
580 /* Splay-tree comparison function, treating the keys as ints. */
583 splay_tree_compare_ints (splay_tree_key k1, splay_tree_key k2)
585 if ((int) k1 < (int) k2)
586 return -1;
587 else if ((int) k1 > (int) k2)
588 return 1;
589 else
590 return 0;
593 /* Splay-tree comparison function, treating the keys as pointers. */
596 splay_tree_compare_pointers (splay_tree_key k1, splay_tree_key k2)
598 if ((char*) k1 < (char*) k2)
599 return -1;
600 else if ((char*) k1 > (char*) k2)
601 return 1;
602 else
603 return 0;
606 /* Splay-tree comparison function, treating the keys as strings. */
609 splay_tree_compare_strings (splay_tree_key k1, splay_tree_key k2)
611 return strcmp ((char *) k1, (char *) k2);
614 /* Splay-tree delete function, simply using free. */
616 void
617 splay_tree_delete_pointers (splay_tree_value value)
619 free ((void *) value);