OSDN Git Service

* Fix for g++/15861
[pf3gnuchains/gcc-fork.git] / libmudflap / splay-tree.c
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.
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 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
20 executable.)
21
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.
26
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.  */
31
32 /* For an easily readable description of splay-trees, see:
33
34      Lewis, Harry R. and Denenberg, Larry.  Data Structures and Their
35      Algorithms.  Harper-Collins, Inc.  1991.  */
36
37 #include <stdlib.h>
38 #include <stdio.h>
39 #include "splay-tree.h"
40
41
42 static void splay_tree_delete_helper (splay_tree, splay_tree_node);
43 static void splay_tree_splay (splay_tree, splay_tree_key);
44 static splay_tree_node splay_tree_splay_helper (splay_tree,
45                                                 splay_tree_key,
46                                                 splay_tree_node *,
47                                                 splay_tree_node *,
48                                                 splay_tree_node *);
49 static void *splay_tree_xmalloc (size_t size);
50 static void splay_tree_free (void *object);
51
52
53
54 /* Inline comparison function specialized for libmudflap's key type.  */
55 static inline int
56 compare_uintptr_t (splay_tree_key k1, splay_tree_key k2)
57 {
58   if ((uintptr_t) k1 < (uintptr_t) k2)
59     return -1;
60   else if ((uintptr_t) k1 > (uintptr_t) k2)
61     return 1;
62   else
63     return 0;
64 }
65
66
67 /* Help splay SP around KEY.  PARENT and GRANDPARENT are the parent
68    and grandparent, respectively, of NODE.  */
69
70 static splay_tree_node
71 splay_tree_splay_helper (splay_tree sp,
72                          splay_tree_key key,
73                          splay_tree_node * node,
74                          splay_tree_node * parent,
75                          splay_tree_node * grandparent)
76 {
77   splay_tree_node *next;
78   splay_tree_node n;
79   int comparison;
80
81   n = *node;
82
83   if (!n)
84     return *parent;
85
86   comparison = compare_uintptr_t (key, n->key);
87
88   if (comparison == 0)
89     /* We've found the target.  */
90     next = 0;
91   else if (comparison < 0)
92     /* The target is to the left.  */
93     next = &n->left;
94   else
95     /* The target is to the right.  */
96     next = &n->right;
97
98   if (next)
99     {
100       /* Check whether our recursion depth is too high.  Abort this search,
101          and signal that a rebalance is required to continue.  */
102       if (sp->depth > sp->max_depth)
103         {
104           sp->rebalance_p = 1;
105           return n;
106          }
107
108       /* Continue down the tree.  */
109       sp->depth ++;
110       n = splay_tree_splay_helper (sp, key, next, node, parent);
111       sp->depth --;
112
113       /* The recursive call will change the place to which NODE
114          points.  */
115       if (*node != n || sp->rebalance_p)
116         return n;
117     }
118
119   if (!parent)
120     /* NODE is the root.  We are done.  */
121     return n;
122
123   /* First, handle the case where there is no grandparent (i.e.,
124    *PARENT is the root of the tree.)  */
125   if (!grandparent)
126     {
127       if (n == (*parent)->left)
128         {
129           *node = n->right;
130           n->right = *parent;
131         }
132       else
133         {
134           *node = n->left;
135           n->left = *parent;
136         }
137       *parent = n;
138       return n;
139     }
140
141   /* Next handle the cases where both N and *PARENT are left children,
142      or where both are right children.  */
143   if (n == (*parent)->left && *parent == (*grandparent)->left)
144     {
145       splay_tree_node p = *parent;
146
147       (*grandparent)->left = p->right;
148       p->right = *grandparent;
149       p->left = n->right;
150       n->right = p;
151       *grandparent = n;
152       return n;
153     }
154   else if (n == (*parent)->right && *parent == (*grandparent)->right)
155     {
156       splay_tree_node p = *parent;
157
158       (*grandparent)->right = p->left;
159       p->left = *grandparent;
160       p->right = n->left;
161       n->left = p;
162       *grandparent = n;
163       return n;
164     }
165
166   /* Finally, deal with the case where N is a left child, but *PARENT
167      is a right child, or vice versa.  */
168   if (n == (*parent)->left)
169     {
170       (*parent)->left = n->right;
171       n->right = *parent;
172       (*grandparent)->right = n->left;
173       n->left = *grandparent;
174       *grandparent = n;
175       return n;
176     }
177   else
178     {
179       (*parent)->right = n->left;
180       n->left = *parent;
181       (*grandparent)->left = n->right;
182       n->right = *grandparent;
183       *grandparent = n;
184       return n;
185     }
186 }
187
188
189
190 static int
191 splay_tree_rebalance_helper1 (splay_tree_node n, void *array_ptr)
192 {
193   splay_tree_node **p = array_ptr;
194   *(*p) = n;
195   (*p)++;
196   return 0;
197 }
198
199
200 static splay_tree_node
201 splay_tree_rebalance_helper2 (splay_tree_node * array, unsigned low,
202                               unsigned high)
203 {
204   unsigned middle = low + (high - low) / 2;
205   splay_tree_node n = array[middle];
206
207   /* Note that since we're producing a balanced binary tree, it is not a problem
208      that this function is recursive.  */
209   if (low + 1 <= middle)
210     n->left = splay_tree_rebalance_helper2 (array, low, middle - 1);
211   else
212     n->left = NULL;
213
214   if (middle + 1 <= high)
215     n->right = splay_tree_rebalance_helper2 (array, middle + 1, high);
216   else
217     n->right = NULL;
218
219   return n;
220 }
221
222
223 /* Rebalance the entire tree.  Do this by copying all the node
224    pointers into an array, then cleverly re-linking them.  */
225 void
226 splay_tree_rebalance (splay_tree sp)
227 {
228   splay_tree_node *all_nodes, *all_nodes_1;
229
230   if (sp->num_keys <= 2)
231     return;
232
233   all_nodes = splay_tree_xmalloc (sizeof (splay_tree_node) * sp->num_keys);
234
235   /* Traverse all nodes to copy their addresses into this array.  */
236   all_nodes_1 = all_nodes;
237   splay_tree_foreach (sp, splay_tree_rebalance_helper1,
238                       (void *) &all_nodes_1);
239
240   /* Relink all the nodes.  */
241   sp->root = splay_tree_rebalance_helper2 (all_nodes, 0, sp->num_keys - 1);
242
243   splay_tree_free (all_nodes);
244 }
245
246
247 /* Splay SP around KEY.  */
248 static void
249 splay_tree_splay (splay_tree sp, splay_tree_key key)
250 {
251   if (sp->root == 0)
252     return;
253
254   /* If we just splayed the tree with the same key, do nothing.  */
255   if (sp->last_splayed_key_p &&
256       compare_uintptr_t (sp->last_splayed_key, key) == 0)
257     return;
258
259   /* Compute a maximum recursion depth for a splay tree with NUM nodes.
260      The idea is to limit excessive stack usage if we're facing
261      degenerate access patterns.  Unfortunately such patterns can occur
262      e.g. during static initialization, where many static objects might
263      be registered in increasing address sequence, or during a case where
264      large tree-like heap data structures are allocated quickly. 
265
266      On x86, this corresponds to roughly 200K of stack usage. 
267      XXX: For libmudflapth, this could be a function of __mf_opts.thread_stack.  */
268   sp->max_depth = 2500;
269   sp->rebalance_p = sp->depth = 0;
270
271   splay_tree_splay_helper (sp, key, &sp->root, NULL, NULL);
272   if (sp->rebalance_p)
273     {
274       splay_tree_rebalance (sp);
275
276       sp->rebalance_p = sp->depth = 0;
277       splay_tree_splay_helper (sp, key, &sp->root, NULL, NULL);
278
279       if (sp->rebalance_p)
280         abort ();
281     }
282
283
284   /* Cache this splay key. */
285   sp->last_splayed_key = key;
286   sp->last_splayed_key_p = 1;
287 }
288
289
290
291 /* Allocate a new splay tree.  */
292 splay_tree
293 splay_tree_new ()
294 {
295   splay_tree sp = splay_tree_xmalloc (sizeof (struct splay_tree_s));
296   sp->root = NULL;
297   sp->last_splayed_key_p = 0;
298   sp->num_keys = 0;
299
300   return sp;
301 }
302
303
304
305 /* Insert a new node (associating KEY with DATA) into SP.  If a
306    previous node with the indicated KEY exists, its data is replaced
307    with the new value.  Returns the new node.  */
308 splay_tree_node
309 splay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value)
310 {
311   int comparison = 0;
312
313   splay_tree_splay (sp, key);
314
315   if (sp->root)
316     comparison = compare_uintptr_t (sp->root->key, key);
317
318   if (sp->root && comparison == 0)
319     {
320       /* If the root of the tree already has the indicated KEY, just
321          replace the value with VALUE.  */
322       sp->root->value = value;
323     }
324   else
325     {
326       /* Create a new node, and insert it at the root.  */
327       splay_tree_node node;
328
329       node = splay_tree_xmalloc (sizeof (struct splay_tree_node_s));
330       node->key = key;
331       node->value = value;
332       sp->num_keys++;
333       if (!sp->root)
334         node->left = node->right = 0;
335       else if (comparison < 0)
336         {
337           node->left = sp->root;
338           node->right = node->left->right;
339           node->left->right = 0;
340         }
341       else
342         {
343           node->right = sp->root;
344           node->left = node->right->left;
345           node->right->left = 0;
346         }
347
348       sp->root = node;
349       sp->last_splayed_key_p = 0;
350     }
351
352   return sp->root;
353 }
354
355 /* Remove KEY from SP.  It is not an error if it did not exist.  */
356
357 void
358 splay_tree_remove (splay_tree sp, splay_tree_key key)
359 {
360   splay_tree_splay (sp, key);
361   sp->last_splayed_key_p = 0;
362   if (sp->root && compare_uintptr_t (sp->root->key, key) == 0)
363     {
364       splay_tree_node left, right;
365       left = sp->root->left;
366       right = sp->root->right;
367       /* Delete the root node itself.  */
368       splay_tree_free (sp->root);
369       sp->num_keys--;
370       /* One of the children is now the root.  Doesn't matter much
371          which, so long as we preserve the properties of the tree.  */
372       if (left)
373         {
374           sp->root = left;
375           /* If there was a right child as well, hang it off the 
376              right-most leaf of the left child.  */
377           if (right)
378             {
379               while (left->right)
380                 left = left->right;
381               left->right = right;
382             }
383         }
384       else
385         sp->root = right;
386     }
387 }
388
389 /* Lookup KEY in SP, returning VALUE if present, and NULL 
390    otherwise.  */
391
392 splay_tree_node
393 splay_tree_lookup (splay_tree sp, splay_tree_key key)
394 {
395   splay_tree_splay (sp, key);
396   if (sp->root && compare_uintptr_t (sp->root->key, key) == 0)
397     return sp->root;
398   else
399     return 0;
400 }
401
402 /* Return the node in SP with the greatest key.  */
403
404 splay_tree_node
405 splay_tree_max (splay_tree sp)
406 {
407   splay_tree_node n = sp->root;
408   if (!n)
409     return NULL;
410   while (n->right)
411     n = n->right;
412   return n;
413 }
414
415 /* Return the node in SP with the smallest key.  */
416
417 splay_tree_node
418 splay_tree_min (splay_tree sp)
419 {
420   splay_tree_node n = sp->root;
421   if (!n)
422     return NULL;
423   while (n->left)
424     n = n->left;
425   return n;
426 }
427
428 /* Return the immediate predecessor KEY, or NULL if there is no
429    predecessor.  KEY need not be present in the tree.  */
430
431 splay_tree_node
432 splay_tree_predecessor (splay_tree sp, splay_tree_key key)
433 {
434   int comparison;
435   splay_tree_node node;
436   /* If the tree is empty, there is certainly no predecessor.  */
437   if (!sp->root)
438     return NULL;
439   /* Splay the tree around KEY.  That will leave either the KEY
440      itself, its predecessor, or its successor at the root.  */
441   splay_tree_splay (sp, key);
442   comparison = compare_uintptr_t (sp->root->key, key);
443   /* If the predecessor is at the root, just return it.  */
444   if (comparison < 0)
445     return sp->root;
446   /* Otherwise, find the rightmost element of the left subtree.  */
447   node = sp->root->left;
448   if (node)
449     while (node->right)
450       node = node->right;
451   return node;
452 }
453
454 /* Return the immediate successor KEY, or NULL if there is no
455    successor.  KEY need not be present in the tree.  */
456
457 splay_tree_node
458 splay_tree_successor (splay_tree sp, splay_tree_key key)
459 {
460   int comparison;
461   splay_tree_node node;
462   /* If the tree is empty, there is certainly no successor.  */
463   if (!sp->root)
464     return NULL;
465   /* Splay the tree around KEY.  That will leave either the KEY
466      itself, its predecessor, or its successor at the root.  */
467   splay_tree_splay (sp, key);
468   comparison = compare_uintptr_t (sp->root->key, key);
469   /* If the successor is at the root, just return it.  */
470   if (comparison > 0)
471     return sp->root;
472   /* Otherwise, find the leftmost element of the right subtree.  */
473   node = sp->root->right;
474   if (node)
475     while (node->left)
476       node = node->left;
477   return node;
478 }
479
480 /* Call FN, passing it the DATA, for every node in SP, following an
481    in-order traversal.  If FN every returns a non-zero value, the
482    iteration ceases immediately, and the value is returned.
483    Otherwise, this function returns 0.
484    
485    This function simulates recursion using dynamically allocated
486    arrays, since it may be called from splay_tree_rebalance(), which
487    in turn means that the tree is already uncomfortably deep for stack
488    space limits.  */
489 int
490 splay_tree_foreach (splay_tree st, splay_tree_foreach_fn fn, void *data)
491 {
492   splay_tree_node *stack1;
493   char *stack2;
494   unsigned sp;
495   int val = 0;
496   enum s { s_left, s_here, s_right, s_up };
497
498   if (st->root == NULL) /* => num_keys == 0 */
499     return 0;
500
501   stack1 = splay_tree_xmalloc (sizeof (splay_tree_node) * st->num_keys);
502   stack2 = splay_tree_xmalloc (sizeof (char) * st->num_keys);
503
504   sp = 0;
505   stack1 [sp] = st->root;
506   stack2 [sp] = s_left;
507
508   while (1)
509     {
510       splay_tree_node n;
511       enum s s;
512
513       n = stack1 [sp];
514       s = stack2 [sp];
515
516       /* Handle each of the four possible states separately.  */
517
518       /* 1: We're here to traverse the left subtree (if any).  */
519       if (s == s_left)
520         {
521           stack2 [sp] = s_here;
522           if (n->left != NULL)
523             {
524               sp ++;
525               stack1 [sp] = n->left;
526               stack2 [sp] = s_left;
527             }
528         }
529
530       /* 2: We're here to traverse this node.  */
531       else if (s == s_here)
532         {
533           stack2 [sp] = s_right;
534           val = (*fn) (n, data);
535           if (val) break;
536         }
537
538       /* 3: We're here to traverse the right subtree (if any).  */
539       else if (s == s_right)
540         {
541           stack2 [sp] = s_up;
542           if (n->right != NULL)
543             {
544               sp ++;
545               stack1 [sp] = n->right;
546               stack2 [sp] = s_left;
547             }
548         }
549
550       /* 4: We're here after both subtrees (if any) have been traversed.  */
551       else if (s == s_up)
552         {
553           /* Pop the stack.  */
554           if (sp == 0) break; /* Popping off the root note: we're finished!  */
555           sp --;
556         }
557
558       else
559         abort ();
560     }
561
562   splay_tree_free (stack1);
563   splay_tree_free (stack2);
564   return val;
565 }