merge from gcc
[external/binutils.git] / libiberty / splay-tree.c
1 /* A splay-tree datatype.  
2    Copyright (C) 1998, 1999, 2000, 2001, 2009,
3    2010, 2011 Free Software Foundation, Inc.
4    Contributed by Mark Mitchell (mark@markmitchell.com).
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 GNU CC is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16 General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GNU CC; see the file COPYING.  If not, write to
20 the Free Software Foundation, 51 Franklin Street - Fifth Floor,
21 Boston, MA 02110-1301, USA.  */
22
23 /* For an easily readable description of splay-trees, see:
24
25      Lewis, Harry R. and Denenberg, Larry.  Data Structures and Their
26      Algorithms.  Harper-Collins, Inc.  1991.  */
27
28 #ifdef HAVE_CONFIG_H
29 #include "config.h"
30 #endif
31
32 #ifdef HAVE_STDLIB_H
33 #include <stdlib.h>
34 #endif
35
36 #include <stdio.h>
37
38 #include "libiberty.h"
39 #include "splay-tree.h"
40
41 static void splay_tree_delete_helper (splay_tree, splay_tree_node);
42 static inline void rotate_left (splay_tree_node *,
43                                 splay_tree_node, splay_tree_node);
44 static inline void rotate_right (splay_tree_node *,
45                                 splay_tree_node, splay_tree_node);
46 static void splay_tree_splay (splay_tree, splay_tree_key);
47 static int splay_tree_foreach_helper (splay_tree_node,
48                                       splay_tree_foreach_fn, void*);
49
50 /* Deallocate NODE (a member of SP), and all its sub-trees.  */
51
52 static void 
53 splay_tree_delete_helper (splay_tree sp, splay_tree_node node)
54 {
55   splay_tree_node pending = 0;
56   splay_tree_node active = 0;
57
58   if (!node)
59     return;
60
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);
66
67   /* We use the "key" field to hold the "next" pointer.  */
68   node->key = (splay_tree_key)pending;
69   pending = (splay_tree_node)node;
70
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
108 }
109
110 /* Rotate the edge joining the left child N with its parent P.  PP is the
111    grandparents' pointer to P.  */
112
113 static inline void
114 rotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
115 {
116   splay_tree_node tmp;
117   tmp = n->right;
118   n->right = p;
119   p->left = tmp;
120   *pp = n;
121 }
122
123 /* Rotate the edge joining the right child N with its parent P.  PP is the
124    grandparents' pointer to P.  */
125
126 static inline void
127 rotate_right (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
128 {
129   splay_tree_node tmp;
130   tmp = n->left;
131   n->left = p;
132   p->right = tmp;
133   *pp = n;
134 }
135
136 /* Bottom up splay of key.  */
137
138 static void
139 splay_tree_splay (splay_tree sp, splay_tree_key key)
140 {
141   if (sp->root == 0)
142     return;
143
144   do {
145     int cmp1, cmp2;
146     splay_tree_node n, c;
147
148     n = sp->root;
149     cmp1 = (*sp->comp) (key, n->key);
150
151     /* Found.  */
152     if (cmp1 == 0)
153       return;
154
155     /* Left or right?  If no child, then we're done.  */
156     if (cmp1 < 0)
157       c = n->left;
158     else
159       c = n->right;
160     if (!c)
161       return;
162
163     /* Next one left or right?  If found or no child, we're done
164        after one rotation.  */
165     cmp2 = (*sp->comp) (key, c->key);
166     if (cmp2 == 0
167         || (cmp2 < 0 && !c->left)
168         || (cmp2 > 0 && !c->right))
169       {
170         if (cmp1 < 0)
171           rotate_left (&sp->root, n, c);
172         else
173           rotate_right (&sp->root, n, c);
174         return;
175       }
176
177     /* Now we have the four cases of double-rotation.  */
178     if (cmp1 < 0 && cmp2 < 0)
179       {
180         rotate_left (&n->left, c, c->left);
181         rotate_left (&sp->root, n, n->left);
182       }
183     else if (cmp1 > 0 && cmp2 > 0)
184       {
185         rotate_right (&n->right, c, c->right);
186         rotate_right (&sp->root, n, n->right);
187       }
188     else if (cmp1 < 0 && cmp2 > 0)
189       {
190         rotate_right (&n->left, c, c->right);
191         rotate_left (&sp->root, n, n->left);
192       }
193     else if (cmp1 > 0 && cmp2 < 0)
194       {
195         rotate_left (&n->right, c, c->left);
196         rotate_right (&sp->root, n, n->right);
197       }
198   } while (1);
199 }
200
201 /* Call FN, passing it the DATA, for every node below NODE, all of
202    which are from SP, following an in-order traversal.  If FN every
203    returns a non-zero value, the iteration ceases immediately, and the
204    value is returned.  Otherwise, this function returns 0.  */
205
206 static int
207 splay_tree_foreach_helper (splay_tree_node node,
208                            splay_tree_foreach_fn fn, void *data)
209 {
210   int val;
211   splay_tree_node *stack;
212   int stack_ptr, stack_size;
213
214   /* A non-recursive implementation is used to avoid filling the stack
215      for large trees.  Splay trees are worst case O(n) in the depth of
216      the tree.  */
217
218 #define INITIAL_STACK_SIZE 100
219   stack_size = INITIAL_STACK_SIZE;
220   stack_ptr = 0;
221   stack = XNEWVEC (splay_tree_node, stack_size);
222   val = 0;
223
224   for (;;)
225     {
226       while (node != NULL)
227         {
228           if (stack_ptr == stack_size)
229             {
230               stack_size *= 2;
231               stack = XRESIZEVEC (splay_tree_node, stack, stack_size);
232             }
233           stack[stack_ptr++] = node;
234           node = node->left;
235         }
236
237       if (stack_ptr == 0)
238         break;
239
240       node = stack[--stack_ptr];
241
242       val = (*fn) (node, data);
243       if (val)
244         break;
245
246       node = node->right;
247     }
248
249   XDELETEVEC (stack);
250   return val;
251 }
252
253 /* An allocator and deallocator based on xmalloc.  */
254 static void *
255 splay_tree_xmalloc_allocate (int size, void *data ATTRIBUTE_UNUSED)
256 {
257   return (void *) xmalloc (size);
258 }
259
260 static void
261 splay_tree_xmalloc_deallocate (void *object, void *data ATTRIBUTE_UNUSED)
262 {
263   free (object);
264 }
265
266
267 /* Allocate a new splay tree, using COMPARE_FN to compare nodes,
268    DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
269    values.  Use xmalloc to allocate the splay tree structure, and any
270    nodes added.  */
271
272 splay_tree 
273 splay_tree_new (splay_tree_compare_fn compare_fn,
274                 splay_tree_delete_key_fn delete_key_fn,
275                 splay_tree_delete_value_fn delete_value_fn)
276 {
277   return (splay_tree_new_with_allocator
278           (compare_fn, delete_key_fn, delete_value_fn,
279            splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate, 0));
280 }
281
282
283 /* Allocate a new splay tree, using COMPARE_FN to compare nodes,
284    DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
285    values.  */
286
287 splay_tree 
288 splay_tree_new_with_allocator (splay_tree_compare_fn compare_fn,
289                                splay_tree_delete_key_fn delete_key_fn,
290                                splay_tree_delete_value_fn delete_value_fn,
291                                splay_tree_allocate_fn allocate_fn,
292                                splay_tree_deallocate_fn deallocate_fn,
293                                void *allocate_data)
294 {
295   return
296     splay_tree_new_typed_alloc (compare_fn, delete_key_fn, delete_value_fn,
297                                 allocate_fn, allocate_fn, deallocate_fn,
298                                 allocate_data);
299 }
300
301 /*
302
303 @deftypefn Supplemental splay_tree splay_tree_new_with_typed_alloc @
304 (splay_tree_compare_fn @var{compare_fn}, @
305 splay_tree_delete_key_fn @var{delete_key_fn}, @
306 splay_tree_delete_value_fn @var{delete_value_fn}, @
307 splay_tree_allocate_fn @var{tree_allocate_fn}, @
308 splay_tree_allocate_fn @var{node_allocate_fn}, @
309 splay_tree_deallocate_fn @var{deallocate_fn}, @
310 void * @var{allocate_data})
311
312 This function creates a splay tree that uses two different allocators
313 @var{tree_allocate_fn} and @var{node_allocate_fn} to use for allocating the
314 tree itself and its nodes respectively.  This is useful when variables of
315 different types need to be allocated with different allocators.
316
317 The splay tree will use @var{compare_fn} to compare nodes,
318 @var{delete_key_fn} to deallocate keys, and @var{delete_value_fn} to
319 deallocate values.
320
321 @end deftypefn
322
323 */
324
325 splay_tree
326 splay_tree_new_typed_alloc (splay_tree_compare_fn compare_fn,
327                             splay_tree_delete_key_fn delete_key_fn,
328                             splay_tree_delete_value_fn delete_value_fn,
329                             splay_tree_allocate_fn tree_allocate_fn,
330                             splay_tree_allocate_fn node_allocate_fn,
331                             splay_tree_deallocate_fn deallocate_fn,
332                             void * allocate_data)
333 {
334   splay_tree sp = (splay_tree) (*tree_allocate_fn)
335     (sizeof (struct splay_tree_s), allocate_data);
336
337   sp->root = 0;
338   sp->comp = compare_fn;
339   sp->delete_key = delete_key_fn;
340   sp->delete_value = delete_value_fn;
341   sp->allocate = node_allocate_fn;
342   sp->deallocate = deallocate_fn;
343   sp->allocate_data = allocate_data;
344
345   return sp;
346 }
347
348 /* Deallocate SP.  */
349
350 void 
351 splay_tree_delete (splay_tree sp)
352 {
353   splay_tree_delete_helper (sp, sp->root);
354   (*sp->deallocate) ((char*) sp, sp->allocate_data);
355 }
356
357 /* Insert a new node (associating KEY with DATA) into SP.  If a
358    previous node with the indicated KEY exists, its data is replaced
359    with the new value.  Returns the new node.  */
360
361 splay_tree_node
362 splay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value)
363 {
364   int comparison = 0;
365
366   splay_tree_splay (sp, key);
367
368   if (sp->root)
369     comparison = (*sp->comp)(sp->root->key, key);
370
371   if (sp->root && comparison == 0)
372     {
373       /* If the root of the tree already has the indicated KEY, just
374          replace the value with VALUE.  */
375       if (sp->delete_value)
376         (*sp->delete_value)(sp->root->value);
377       sp->root->value = value;
378     } 
379   else 
380     {
381       /* Create a new node, and insert it at the root.  */
382       splay_tree_node node;
383
384       node = ((splay_tree_node)
385               (*sp->allocate) (sizeof (struct splay_tree_node_s),
386                                sp->allocate_data));
387       node->key = key;
388       node->value = value;
389       
390       if (!sp->root)
391         node->left = node->right = 0;
392       else if (comparison < 0)
393         {
394           node->left = sp->root;
395           node->right = node->left->right;
396           node->left->right = 0;
397         }
398       else
399         {
400           node->right = sp->root;
401           node->left = node->right->left;
402           node->right->left = 0;
403         }
404
405       sp->root = node;
406     }
407
408   return sp->root;
409 }
410
411 /* Remove KEY from SP.  It is not an error if it did not exist.  */
412
413 void
414 splay_tree_remove (splay_tree sp, splay_tree_key key)
415 {
416   splay_tree_splay (sp, key);
417
418   if (sp->root && (*sp->comp) (sp->root->key, key) == 0)
419     {
420       splay_tree_node left, right;
421
422       left = sp->root->left;
423       right = sp->root->right;
424
425       /* Delete the root node itself.  */
426       if (sp->delete_value)
427         (*sp->delete_value) (sp->root->value);
428       (*sp->deallocate) (sp->root, sp->allocate_data);
429
430       /* One of the children is now the root.  Doesn't matter much
431          which, so long as we preserve the properties of the tree.  */
432       if (left)
433         {
434           sp->root = left;
435
436           /* If there was a right child as well, hang it off the 
437              right-most leaf of the left child.  */
438           if (right)
439             {
440               while (left->right)
441                 left = left->right;
442               left->right = right;
443             }
444         }
445       else
446         sp->root = right;
447     }
448 }
449
450 /* Lookup KEY in SP, returning VALUE if present, and NULL 
451    otherwise.  */
452
453 splay_tree_node
454 splay_tree_lookup (splay_tree sp, splay_tree_key key)
455 {
456   splay_tree_splay (sp, key);
457
458   if (sp->root && (*sp->comp)(sp->root->key, key) == 0)
459     return sp->root;
460   else
461     return 0;
462 }
463
464 /* Return the node in SP with the greatest key.  */
465
466 splay_tree_node
467 splay_tree_max (splay_tree sp)
468 {
469   splay_tree_node n = sp->root;
470
471   if (!n)
472     return NULL;
473
474   while (n->right)
475     n = n->right;
476
477   return n;
478 }
479
480 /* Return the node in SP with the smallest key.  */
481
482 splay_tree_node
483 splay_tree_min (splay_tree sp)
484 {
485   splay_tree_node n = sp->root;
486
487   if (!n)
488     return NULL;
489
490   while (n->left)
491     n = n->left;
492
493   return n;
494 }
495
496 /* Return the immediate predecessor KEY, or NULL if there is no
497    predecessor.  KEY need not be present in the tree.  */
498
499 splay_tree_node
500 splay_tree_predecessor (splay_tree sp, splay_tree_key key)
501 {
502   int comparison;
503   splay_tree_node node;
504
505   /* If the tree is empty, there is certainly no predecessor.  */
506   if (!sp->root)
507     return NULL;
508
509   /* Splay the tree around KEY.  That will leave either the KEY
510      itself, its predecessor, or its successor at the root.  */
511   splay_tree_splay (sp, key);
512   comparison = (*sp->comp)(sp->root->key, key);
513
514   /* If the predecessor is at the root, just return it.  */
515   if (comparison < 0)
516     return sp->root;
517
518   /* Otherwise, find the rightmost element of the left subtree.  */
519   node = sp->root->left;
520   if (node)
521     while (node->right)
522       node = node->right;
523
524   return node;
525 }
526
527 /* Return the immediate successor KEY, or NULL if there is no
528    successor.  KEY need not be present in the tree.  */
529
530 splay_tree_node
531 splay_tree_successor (splay_tree sp, splay_tree_key key)
532 {
533   int comparison;
534   splay_tree_node node;
535
536   /* If the tree is empty, there is certainly no successor.  */
537   if (!sp->root)
538     return NULL;
539
540   /* Splay the tree around KEY.  That will leave either the KEY
541      itself, its predecessor, or its successor at the root.  */
542   splay_tree_splay (sp, key);
543   comparison = (*sp->comp)(sp->root->key, key);
544
545   /* If the successor is at the root, just return it.  */
546   if (comparison > 0)
547     return sp->root;
548
549   /* Otherwise, find the leftmost element of the right subtree.  */
550   node = sp->root->right;
551   if (node)
552     while (node->left)
553       node = node->left;
554
555   return node;
556 }
557
558 /* Call FN, passing it the DATA, for every node in SP, following an
559    in-order traversal.  If FN every returns a non-zero value, the
560    iteration ceases immediately, and the value is returned.
561    Otherwise, this function returns 0.  */
562
563 int
564 splay_tree_foreach (splay_tree sp, splay_tree_foreach_fn fn, void *data)
565 {
566   return splay_tree_foreach_helper (sp->root, fn, data);
567 }
568
569 /* Splay-tree comparison function, treating the keys as ints.  */
570
571 int
572 splay_tree_compare_ints (splay_tree_key k1, splay_tree_key k2)
573 {
574   if ((int) k1 < (int) k2)
575     return -1;
576   else if ((int) k1 > (int) k2)
577     return 1;
578   else 
579     return 0;
580 }
581
582 /* Splay-tree comparison function, treating the keys as pointers.  */
583
584 int
585 splay_tree_compare_pointers (splay_tree_key k1, splay_tree_key k2)
586 {
587   if ((char*) k1 < (char*) k2)
588     return -1;
589   else if ((char*) k1 > (char*) k2)
590     return 1;
591   else 
592     return 0;
593 }