Handle SLP of call pattern statements
[official-gcc.git] / libiberty / splay-tree.c
blobd3be4aa90b54dc5f4bda4fdb44835e4b44dcd253
1 /* A splay-tree datatype.
2 Copyright (C) 1998-2018 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.
323 @end deftypefn
327 splay_tree
328 splay_tree_new_typed_alloc (splay_tree_compare_fn compare_fn,
329 splay_tree_delete_key_fn delete_key_fn,
330 splay_tree_delete_value_fn delete_value_fn,
331 splay_tree_allocate_fn tree_allocate_fn,
332 splay_tree_allocate_fn node_allocate_fn,
333 splay_tree_deallocate_fn deallocate_fn,
334 void * allocate_data)
336 splay_tree sp = (splay_tree) (*tree_allocate_fn)
337 (sizeof (struct splay_tree_s), allocate_data);
339 sp->root = 0;
340 sp->comp = compare_fn;
341 sp->delete_key = delete_key_fn;
342 sp->delete_value = delete_value_fn;
343 sp->allocate = node_allocate_fn;
344 sp->deallocate = deallocate_fn;
345 sp->allocate_data = allocate_data;
347 return sp;
350 /* Deallocate SP. */
352 void
353 splay_tree_delete (splay_tree sp)
355 splay_tree_delete_helper (sp, sp->root);
356 (*sp->deallocate) ((char*) sp, sp->allocate_data);
359 /* Insert a new node (associating KEY with DATA) into SP. If a
360 previous node with the indicated KEY exists, its data is replaced
361 with the new value. Returns the new node. */
363 splay_tree_node
364 splay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value)
366 int comparison = 0;
368 splay_tree_splay (sp, key);
370 if (sp->root)
371 comparison = (*sp->comp)(sp->root->key, key);
373 if (sp->root && comparison == 0)
375 /* If the root of the tree already has the indicated KEY, just
376 replace the value with VALUE. */
377 if (sp->delete_value)
378 (*sp->delete_value)(sp->root->value);
379 sp->root->value = value;
381 else
383 /* Create a new node, and insert it at the root. */
384 splay_tree_node node;
386 node = ((splay_tree_node)
387 (*sp->allocate) (sizeof (struct splay_tree_node_s),
388 sp->allocate_data));
389 node->key = key;
390 node->value = value;
392 if (!sp->root)
393 node->left = node->right = 0;
394 else if (comparison < 0)
396 node->left = sp->root;
397 node->right = node->left->right;
398 node->left->right = 0;
400 else
402 node->right = sp->root;
403 node->left = node->right->left;
404 node->right->left = 0;
407 sp->root = node;
410 return sp->root;
413 /* Remove KEY from SP. It is not an error if it did not exist. */
415 void
416 splay_tree_remove (splay_tree sp, splay_tree_key key)
418 splay_tree_splay (sp, key);
420 if (sp->root && (*sp->comp) (sp->root->key, key) == 0)
422 splay_tree_node left, right;
424 left = sp->root->left;
425 right = sp->root->right;
427 /* Delete the root node itself. */
428 if (sp->delete_value)
429 (*sp->delete_value) (sp->root->value);
430 (*sp->deallocate) (sp->root, sp->allocate_data);
432 /* One of the children is now the root. Doesn't matter much
433 which, so long as we preserve the properties of the tree. */
434 if (left)
436 sp->root = left;
438 /* If there was a right child as well, hang it off the
439 right-most leaf of the left child. */
440 if (right)
442 while (left->right)
443 left = left->right;
444 left->right = right;
447 else
448 sp->root = right;
452 /* Lookup KEY in SP, returning VALUE if present, and NULL
453 otherwise. */
455 splay_tree_node
456 splay_tree_lookup (splay_tree sp, splay_tree_key key)
458 splay_tree_splay (sp, key);
460 if (sp->root && (*sp->comp)(sp->root->key, key) == 0)
461 return sp->root;
462 else
463 return 0;
466 /* Return the node in SP with the greatest key. */
468 splay_tree_node
469 splay_tree_max (splay_tree sp)
471 splay_tree_node n = sp->root;
473 if (!n)
474 return NULL;
476 while (n->right)
477 n = n->right;
479 return n;
482 /* Return the node in SP with the smallest key. */
484 splay_tree_node
485 splay_tree_min (splay_tree sp)
487 splay_tree_node n = sp->root;
489 if (!n)
490 return NULL;
492 while (n->left)
493 n = n->left;
495 return n;
498 /* Return the immediate predecessor KEY, or NULL if there is no
499 predecessor. KEY need not be present in the tree. */
501 splay_tree_node
502 splay_tree_predecessor (splay_tree sp, splay_tree_key key)
504 int comparison;
505 splay_tree_node node;
507 /* If the tree is empty, there is certainly no predecessor. */
508 if (!sp->root)
509 return NULL;
511 /* Splay the tree around KEY. That will leave either the KEY
512 itself, its predecessor, or its successor at the root. */
513 splay_tree_splay (sp, key);
514 comparison = (*sp->comp)(sp->root->key, key);
516 /* If the predecessor is at the root, just return it. */
517 if (comparison < 0)
518 return sp->root;
520 /* Otherwise, find the rightmost element of the left subtree. */
521 node = sp->root->left;
522 if (node)
523 while (node->right)
524 node = node->right;
526 return node;
529 /* Return the immediate successor KEY, or NULL if there is no
530 successor. KEY need not be present in the tree. */
532 splay_tree_node
533 splay_tree_successor (splay_tree sp, splay_tree_key key)
535 int comparison;
536 splay_tree_node node;
538 /* If the tree is empty, there is certainly no successor. */
539 if (!sp->root)
540 return NULL;
542 /* Splay the tree around KEY. That will leave either the KEY
543 itself, its predecessor, or its successor at the root. */
544 splay_tree_splay (sp, key);
545 comparison = (*sp->comp)(sp->root->key, key);
547 /* If the successor is at the root, just return it. */
548 if (comparison > 0)
549 return sp->root;
551 /* Otherwise, find the leftmost element of the right subtree. */
552 node = sp->root->right;
553 if (node)
554 while (node->left)
555 node = node->left;
557 return node;
560 /* Call FN, passing it the DATA, for every node in SP, following an
561 in-order traversal. If FN every returns a non-zero value, the
562 iteration ceases immediately, and the value is returned.
563 Otherwise, this function returns 0. */
566 splay_tree_foreach (splay_tree sp, splay_tree_foreach_fn fn, void *data)
568 return splay_tree_foreach_helper (sp->root, fn, data);
571 /* Splay-tree comparison function, treating the keys as ints. */
574 splay_tree_compare_ints (splay_tree_key k1, splay_tree_key k2)
576 if ((int) k1 < (int) k2)
577 return -1;
578 else if ((int) k1 > (int) k2)
579 return 1;
580 else
581 return 0;
584 /* Splay-tree comparison function, treating the keys as pointers. */
587 splay_tree_compare_pointers (splay_tree_key k1, splay_tree_key k2)
589 if ((char*) k1 < (char*) k2)
590 return -1;
591 else if ((char*) k1 > (char*) k2)
592 return 1;
593 else
594 return 0;
597 /* Splay-tree comparison function, treating the keys as strings. */
600 splay_tree_compare_strings (splay_tree_key k1, splay_tree_key k2)
602 return strcmp ((char *) k1, (char *) k2);
605 /* Splay-tree delete function, simply using free. */
607 void
608 splay_tree_delete_pointers (splay_tree_value value)
610 free ((void *) value);