1 /* A splay-tree datatype.
2 Copyright (C) 1998, 1999, 2000, 2001, 2004 Free Software Foundation, Inc.
3 Contributed by Mark Mitchell (mark@markmitchell.com).
4 Adapted for libmudflap from libiberty.
6 This file is part of GNU CC.
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)
13 In addition to the permissions in the GNU General Public License, the
14 Free Software Foundation gives you unlimited permission to link the
15 compiled version of this file into combinations with other programs,
16 and to distribute those combinations without any restriction coming
17 from the use of this file. (The General Public License restrictions
18 do apply in other respects; for example, they cover modification of
19 the file, and distribution when not linked into a combine
22 GNU CC is distributed in the hope that it will be useful, but
23 WITHOUT ANY WARRANTY; without even the implied warranty of
24 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
25 General Public License for more details.
27 You should have received a copy of the GNU General Public License
28 along with GNU CC; see the file COPYING. If not, write to
29 the Free Software Foundation, 59 Temple Place - Suite 330,
30 Boston, MA 02111-1307, USA. */
32 /* For an easily readable description of splay-trees, see:
34 Lewis, Harry R. and Denenberg, Larry. Data Structures and Their
35 Algorithms. Harper-Collins, Inc. 1991. */
39 #include "splay-tree.h"
42 static void splay_tree_splay (splay_tree, splay_tree_key);
43 static splay_tree_node splay_tree_splay_helper (splay_tree,
48 static void *splay_tree_xmalloc (size_t size);
49 static void splay_tree_free (void *object);
53 /* Inline comparison function specialized for libmudflap's key type. */
55 compare_uintptr_t (splay_tree_key k1, splay_tree_key k2)
57 if ((uintptr_t) k1 < (uintptr_t) k2)
59 else if ((uintptr_t) k1 > (uintptr_t) k2)
66 /* Help splay SP around KEY. PARENT and GRANDPARENT are the parent
67 and grandparent, respectively, of NODE. */
69 static splay_tree_node
70 splay_tree_splay_helper (splay_tree sp,
72 splay_tree_node * node,
73 splay_tree_node * parent,
74 splay_tree_node * grandparent)
76 splay_tree_node *next;
85 comparison = compare_uintptr_t (key, n->key);
88 /* We've found the target. */
90 else if (comparison < 0)
91 /* The target is to the left. */
94 /* The target is to the right. */
99 /* Check whether our recursion depth is too high. Abort this search,
100 and signal that a rebalance is required to continue. */
101 if (sp->depth > sp->max_depth)
107 /* Continue down the tree. */
109 n = splay_tree_splay_helper (sp, key, next, node, parent);
112 /* The recursive call will change the place to which NODE
114 if (*node != n || sp->rebalance_p)
119 /* NODE is the root. We are done. */
122 /* First, handle the case where there is no grandparent (i.e.,
123 *PARENT is the root of the tree.) */
126 if (n == (*parent)->left)
140 /* Next handle the cases where both N and *PARENT are left children,
141 or where both are right children. */
142 if (n == (*parent)->left && *parent == (*grandparent)->left)
144 splay_tree_node p = *parent;
146 (*grandparent)->left = p->right;
147 p->right = *grandparent;
153 else if (n == (*parent)->right && *parent == (*grandparent)->right)
155 splay_tree_node p = *parent;
157 (*grandparent)->right = p->left;
158 p->left = *grandparent;
165 /* Finally, deal with the case where N is a left child, but *PARENT
166 is a right child, or vice versa. */
167 if (n == (*parent)->left)
169 (*parent)->left = n->right;
171 (*grandparent)->right = n->left;
172 n->left = *grandparent;
178 (*parent)->right = n->left;
180 (*grandparent)->left = n->right;
181 n->right = *grandparent;
190 splay_tree_rebalance_helper1 (splay_tree_node n, void *array_ptr)
192 splay_tree_node **p = array_ptr;
199 static splay_tree_node
200 splay_tree_rebalance_helper2 (splay_tree_node * array, unsigned low,
203 unsigned middle = low + (high - low) / 2;
204 splay_tree_node n = array[middle];
206 /* Note that since we're producing a balanced binary tree, it is not a problem
207 that this function is recursive. */
208 if (low + 1 <= middle)
209 n->left = splay_tree_rebalance_helper2 (array, low, middle - 1);
213 if (middle + 1 <= high)
214 n->right = splay_tree_rebalance_helper2 (array, middle + 1, high);
222 /* Rebalance the entire tree. Do this by copying all the node
223 pointers into an array, then cleverly re-linking them. */
225 splay_tree_rebalance (splay_tree sp)
227 splay_tree_node *all_nodes, *all_nodes_1;
229 if (sp->num_keys <= 2)
232 all_nodes = splay_tree_xmalloc (sizeof (splay_tree_node) * sp->num_keys);
234 /* Traverse all nodes to copy their addresses into this array. */
235 all_nodes_1 = all_nodes;
236 splay_tree_foreach (sp, splay_tree_rebalance_helper1,
237 (void *) &all_nodes_1);
239 /* Relink all the nodes. */
240 sp->root = splay_tree_rebalance_helper2 (all_nodes, 0, sp->num_keys - 1);
242 splay_tree_free (all_nodes);
246 /* Splay SP around KEY. */
248 splay_tree_splay (splay_tree sp, splay_tree_key key)
253 /* If we just splayed the tree with the same key, do nothing. */
254 if (sp->last_splayed_key_p &&
255 compare_uintptr_t (sp->last_splayed_key, key) == 0)
258 /* Compute a maximum recursion depth for a splay tree with NUM nodes.
259 The idea is to limit excessive stack usage if we're facing
260 degenerate access patterns. Unfortunately such patterns can occur
261 e.g. during static initialization, where many static objects might
262 be registered in increasing address sequence, or during a case where
263 large tree-like heap data structures are allocated quickly.
265 On x86, this corresponds to roughly 200K of stack usage.
266 XXX: For libmudflapth, this could be a function of __mf_opts.thread_stack. */
267 sp->max_depth = 2500;
268 sp->rebalance_p = sp->depth = 0;
270 splay_tree_splay_helper (sp, key, &sp->root, NULL, NULL);
273 splay_tree_rebalance (sp);
275 sp->rebalance_p = sp->depth = 0;
276 splay_tree_splay_helper (sp, key, &sp->root, NULL, NULL);
283 /* Cache this splay key. */
284 sp->last_splayed_key = key;
285 sp->last_splayed_key_p = 1;
290 /* Allocate a new splay tree. */
294 splay_tree sp = splay_tree_xmalloc (sizeof (struct splay_tree_s));
296 sp->last_splayed_key_p = 0;
304 /* Insert a new node (associating KEY with DATA) into SP. If a
305 previous node with the indicated KEY exists, its data is replaced
306 with the new value. Returns the new node. */
308 splay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value)
312 splay_tree_splay (sp, key);
315 comparison = compare_uintptr_t (sp->root->key, key);
317 if (sp->root && comparison == 0)
319 /* If the root of the tree already has the indicated KEY, just
320 replace the value with VALUE. */
321 sp->root->value = value;
325 /* Create a new node, and insert it at the root. */
326 splay_tree_node node;
328 node = splay_tree_xmalloc (sizeof (struct splay_tree_node_s));
333 node->left = node->right = 0;
334 else if (comparison < 0)
336 node->left = sp->root;
337 node->right = node->left->right;
338 node->left->right = 0;
342 node->right = sp->root;
343 node->left = node->right->left;
344 node->right->left = 0;
348 sp->last_splayed_key_p = 0;
354 /* Remove KEY from SP. It is not an error if it did not exist. */
357 splay_tree_remove (splay_tree sp, splay_tree_key key)
359 splay_tree_splay (sp, key);
360 sp->last_splayed_key_p = 0;
361 if (sp->root && compare_uintptr_t (sp->root->key, key) == 0)
363 splay_tree_node left, right;
364 left = sp->root->left;
365 right = sp->root->right;
366 /* Delete the root node itself. */
367 splay_tree_free (sp->root);
369 /* One of the children is now the root. Doesn't matter much
370 which, so long as we preserve the properties of the tree. */
374 /* If there was a right child as well, hang it off the
375 right-most leaf of the left child. */
388 /* Lookup KEY in SP, returning VALUE if present, and NULL
392 splay_tree_lookup (splay_tree sp, splay_tree_key key)
394 splay_tree_splay (sp, key);
395 if (sp->root && compare_uintptr_t (sp->root->key, key) == 0)
401 /* Return the node in SP with the greatest key. */
404 splay_tree_max (splay_tree sp)
406 splay_tree_node n = sp->root;
414 /* Return the node in SP with the smallest key. */
417 splay_tree_min (splay_tree sp)
419 splay_tree_node n = sp->root;
427 /* Return the immediate predecessor KEY, or NULL if there is no
428 predecessor. KEY need not be present in the tree. */
431 splay_tree_predecessor (splay_tree sp, splay_tree_key key)
434 splay_tree_node node;
435 /* If the tree is empty, there is certainly no predecessor. */
438 /* Splay the tree around KEY. That will leave either the KEY
439 itself, its predecessor, or its successor at the root. */
440 splay_tree_splay (sp, key);
441 comparison = compare_uintptr_t (sp->root->key, key);
442 /* If the predecessor is at the root, just return it. */
445 /* Otherwise, find the rightmost element of the left subtree. */
446 node = sp->root->left;
453 /* Return the immediate successor KEY, or NULL if there is no
454 successor. KEY need not be present in the tree. */
457 splay_tree_successor (splay_tree sp, splay_tree_key key)
460 splay_tree_node node;
461 /* If the tree is empty, there is certainly no successor. */
464 /* Splay the tree around KEY. That will leave either the KEY
465 itself, its predecessor, or its successor at the root. */
466 splay_tree_splay (sp, key);
467 comparison = compare_uintptr_t (sp->root->key, key);
468 /* If the successor is at the root, just return it. */
471 /* Otherwise, find the leftmost element of the right subtree. */
472 node = sp->root->right;
479 /* Call FN, passing it the DATA, for every node in SP, following an
480 in-order traversal. If FN every returns a non-zero value, the
481 iteration ceases immediately, and the value is returned.
482 Otherwise, this function returns 0.
484 This function simulates recursion using dynamically allocated
485 arrays, since it may be called from splay_tree_rebalance(), which
486 in turn means that the tree is already uncomfortably deep for stack
489 splay_tree_foreach (splay_tree st, splay_tree_foreach_fn fn, void *data)
491 splay_tree_node *stack1;
495 enum s { s_left, s_here, s_right, s_up };
497 if (st->root == NULL) /* => num_keys == 0 */
500 stack1 = splay_tree_xmalloc (sizeof (splay_tree_node) * st->num_keys);
501 stack2 = splay_tree_xmalloc (sizeof (char) * st->num_keys);
504 stack1 [sp] = st->root;
505 stack2 [sp] = s_left;
515 /* Handle each of the four possible states separately. */
517 /* 1: We're here to traverse the left subtree (if any). */
520 stack2 [sp] = s_here;
524 stack1 [sp] = n->left;
525 stack2 [sp] = s_left;
529 /* 2: We're here to traverse this node. */
530 else if (s == s_here)
532 stack2 [sp] = s_right;
533 val = (*fn) (n, data);
537 /* 3: We're here to traverse the right subtree (if any). */
538 else if (s == s_right)
541 if (n->right != NULL)
544 stack1 [sp] = n->right;
545 stack2 [sp] = s_left;
549 /* 4: We're here after both subtrees (if any) have been traversed. */
553 if (sp == 0) break; /* Popping off the root note: we're finished! */
561 splay_tree_free (stack1);
562 splay_tree_free (stack2);