OSDN Git Service

b1410aa3005356ff02e56f2e38f27b099043e1f4
[pf3gnuchains/gcc-fork.git] / libiberty / splay-tree.c
1 /* A splay-tree datatype.  
2    Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
3    Contributed by Mark Mitchell (mark@markmitchell.com).
4
5 This file is part of GNU CC.
6    
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.
11
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.
16
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, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA.  */
21
22 /* For an easily readable description of splay-trees, see:
23
24      Lewis, Harry R. and Denenberg, Larry.  Data Structures and Their
25      Algorithms.  Harper-Collins, Inc.  1991.  */
26
27 #ifdef HAVE_CONFIG_H
28 #include "config.h"
29 #endif
30
31 #ifdef HAVE_STDLIB_H
32 #include <stdlib.h>
33 #endif
34
35 #include <stdio.h>
36
37 #include "libiberty.h"
38 #include "splay-tree.h"
39
40 static void splay_tree_delete_helper    PARAMS((splay_tree, 
41                                                 splay_tree_node));
42 static void splay_tree_splay            PARAMS((splay_tree,
43                                                 splay_tree_key));
44 static splay_tree_node splay_tree_splay_helper     
45                                         PARAMS((splay_tree,
46                                                 splay_tree_key,
47                                                 splay_tree_node*,
48                                                 splay_tree_node*,
49                                                 splay_tree_node*));
50 static int splay_tree_foreach_helper    PARAMS((splay_tree,
51                                                 splay_tree_node,
52                                                 splay_tree_foreach_fn,
53                                                 void*));
54
55 /* Deallocate NODE (a member of SP), and all its sub-trees.  */
56
57 static void 
58 splay_tree_delete_helper (sp, node)
59      splay_tree sp;
60      splay_tree_node node;
61 {
62   splay_tree_node pending = 0;
63   splay_tree_node active = 0;
64
65   if (!node)
66     return;
67
68 #define KDEL(x)  if (sp->delete_key) (*sp->delete_key)(x);
69 #define VDEL(x)  if (sp->delete_value) (*sp->delete_value)(x);
70
71   KDEL (node->key);
72   VDEL (node->value);
73
74   /* We use the "key" field to hold the "next" pointer.  */
75   node->key = (splay_tree_key)pending;
76   pending = (splay_tree_node)node;
77
78   /* Now, keep processing the pending list until there aren't any
79      more.  This is a little more complicated than just recursing, but
80      it doesn't toast the stack for large trees.  */
81
82   while (pending)
83     {
84       active = pending;
85       pending = 0;
86       while (active)
87         {
88           splay_tree_node temp;
89
90           /* active points to a node which has its key and value
91              deallocated, we just need to process left and right.  */
92
93           if (active->left)
94             {
95               KDEL (active->left->key);
96               VDEL (active->left->value);
97               active->left->key = (splay_tree_key)pending;
98               pending = (splay_tree_node)(active->left);
99             }
100           if (active->right)
101             {
102               KDEL (active->right->key);
103               VDEL (active->right->value);
104               active->right->key = (splay_tree_key)pending;
105               pending = (splay_tree_node)(active->right);
106             }
107
108           temp = active;
109           active = (splay_tree_node)(temp->key);
110           (*sp->deallocate) ((char*) temp, sp->allocate_data);
111         }
112     }
113 #undef KDEL
114 #undef VDEL
115 }
116
117 /* Help splay SP around KEY.  PARENT and GRANDPARENT are the parent
118    and grandparent, respectively, of NODE.  */
119
120 static splay_tree_node
121 splay_tree_splay_helper (sp, key, node, parent, grandparent)
122      splay_tree sp;
123      splay_tree_key key;
124      splay_tree_node *node;
125      splay_tree_node *parent;
126      splay_tree_node *grandparent;
127 {
128   splay_tree_node *next;
129   splay_tree_node n;
130   int comparison;
131   
132   n = *node;
133
134   if (!n)
135     return *parent;
136
137   comparison = (*sp->comp) (key, n->key);
138
139   if (comparison == 0)
140     /* We've found the target.  */
141     next = 0;
142   else if (comparison < 0)
143     /* The target is to the left.  */
144     next = &n->left;
145   else 
146     /* The target is to the right.  */
147     next = &n->right;
148
149   if (next)
150     {
151       /* Continue down the tree.  */
152       n = splay_tree_splay_helper (sp, key, next, node, parent);
153
154       /* The recursive call will change the place to which NODE
155          points.  */
156       if (*node != n)
157         return n;
158     }
159
160   if (!parent)
161     /* NODE is the root.  We are done.  */
162     return n;
163
164   /* First, handle the case where there is no grandparent (i.e.,
165      *PARENT is the root of the tree.)  */
166   if (!grandparent) 
167     {
168       if (n == (*parent)->left)
169         {
170           *node = n->right;
171           n->right = *parent;
172         }
173       else
174         {
175           *node = n->left;
176           n->left = *parent;
177         }
178       *parent = n;
179       return n;
180     }
181
182   /* Next handle the cases where both N and *PARENT are left children,
183      or where both are right children.  */
184   if (n == (*parent)->left && *parent == (*grandparent)->left)
185     {
186       splay_tree_node p = *parent;
187
188       (*grandparent)->left = p->right;
189       p->right = *grandparent;
190       p->left = n->right;
191       n->right = p;
192       *grandparent = n;
193       return n; 
194     }
195   else if  (n == (*parent)->right && *parent == (*grandparent)->right)
196     {
197       splay_tree_node p = *parent;
198
199       (*grandparent)->right = p->left;
200       p->left = *grandparent;
201       p->right = n->left;
202       n->left = p;
203       *grandparent = n;
204       return n;
205     }
206
207   /* Finally, deal with the case where N is a left child, but *PARENT
208      is a right child, or vice versa.  */
209   if (n == (*parent)->left) 
210     {
211       (*parent)->left = n->right;
212       n->right = *parent;
213       (*grandparent)->right = n->left;
214       n->left = *grandparent;
215       *grandparent = n;
216       return n;
217     } 
218   else
219     {
220       (*parent)->right = n->left;
221       n->left = *parent;
222       (*grandparent)->left = n->right;
223       n->right = *grandparent;
224       *grandparent = n;
225       return n;
226     }
227 }
228
229 /* Splay SP around KEY.  */
230
231 static void
232 splay_tree_splay (sp, key)
233      splay_tree sp;
234      splay_tree_key key;
235 {
236   if (sp->root == 0)
237     return;
238
239   splay_tree_splay_helper (sp, key, &sp->root, 
240                            /*grandparent=*/0, /*parent=*/0); 
241 }
242
243 /* Call FN, passing it the DATA, for every node below NODE, all of
244    which are from SP, following an in-order traversal.  If FN every
245    returns a non-zero value, the iteration ceases immediately, and the
246    value is returned.  Otherwise, this function returns 0.  */
247
248 static int
249 splay_tree_foreach_helper (sp, node, fn, data)
250      splay_tree sp;
251      splay_tree_node node;
252      splay_tree_foreach_fn fn;
253      void* data;
254 {
255   int val;
256
257   if (!node)
258     return 0;
259
260   val = splay_tree_foreach_helper (sp, node->left, fn, data);
261   if (val)
262     return val;
263
264   val = (*fn)(node, data);
265   if (val)
266     return val;
267
268   return splay_tree_foreach_helper (sp, node->right, fn, data);
269 }
270
271
272 /* An allocator and deallocator based on xmalloc.  */
273 static void *
274 splay_tree_xmalloc_allocate (size, data)
275      int size;
276      void *data ATTRIBUTE_UNUSED;
277 {
278   return (void *) xmalloc (size);
279 }
280
281 static void
282 splay_tree_xmalloc_deallocate (object, data)
283      void *object;
284      void *data ATTRIBUTE_UNUSED;
285 {
286   free (object);
287 }
288
289
290 /* Allocate a new splay tree, using COMPARE_FN to compare nodes,
291    DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
292    values.  Use xmalloc to allocate the splay tree structure, and any
293    nodes added.  */
294
295 splay_tree 
296 splay_tree_new (compare_fn, delete_key_fn, delete_value_fn)
297      splay_tree_compare_fn compare_fn;
298      splay_tree_delete_key_fn delete_key_fn;
299      splay_tree_delete_value_fn delete_value_fn;
300 {
301   return (splay_tree_new_with_allocator
302           (compare_fn, delete_key_fn, delete_value_fn,
303            splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate, 0));
304 }
305
306
307 /* Allocate a new splay tree, using COMPARE_FN to compare nodes,
308    DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
309    values.  */
310
311 splay_tree 
312 splay_tree_new_with_allocator (compare_fn, delete_key_fn, delete_value_fn,
313                                allocate_fn, deallocate_fn, allocate_data)
314      splay_tree_compare_fn compare_fn;
315      splay_tree_delete_key_fn delete_key_fn;
316      splay_tree_delete_value_fn delete_value_fn;
317      splay_tree_allocate_fn allocate_fn;
318      splay_tree_deallocate_fn deallocate_fn;
319      void *allocate_data;
320 {
321   splay_tree sp = (splay_tree) (*allocate_fn) (sizeof (struct splay_tree_s),
322                                                allocate_data);
323   sp->root = 0;
324   sp->comp = compare_fn;
325   sp->delete_key = delete_key_fn;
326   sp->delete_value = delete_value_fn;
327   sp->allocate = allocate_fn;
328   sp->deallocate = deallocate_fn;
329   sp->allocate_data = allocate_data;
330
331   return sp;
332 }
333
334 /* Deallocate SP.  */
335
336 void 
337 splay_tree_delete (sp)
338      splay_tree sp;
339 {
340   splay_tree_delete_helper (sp, sp->root);
341   (*sp->deallocate) ((char*) sp, sp->allocate_data);
342 }
343
344 /* Insert a new node (associating KEY with DATA) into SP.  If a
345    previous node with the indicated KEY exists, its data is replaced
346    with the new value.  Returns the new node.  */
347
348 splay_tree_node
349 splay_tree_insert (sp, key, value)
350      splay_tree sp;
351      splay_tree_key key;
352      splay_tree_value value;
353 {
354   int comparison = 0;
355
356   splay_tree_splay (sp, key);
357
358   if (sp->root)
359     comparison = (*sp->comp)(sp->root->key, key);
360
361   if (sp->root && comparison == 0)
362     {
363       /* If the root of the tree already has the indicated KEY, just
364          replace the value with VALUE.  */
365       if (sp->delete_value)
366         (*sp->delete_value)(sp->root->value);
367       sp->root->value = value;
368     } 
369   else 
370     {
371       /* Create a new node, and insert it at the root.  */
372       splay_tree_node node;
373       
374       node = ((splay_tree_node)
375               (*sp->allocate) (sizeof (struct splay_tree_node_s),
376                                sp->allocate_data));
377       node->key = key;
378       node->value = value;
379       
380       if (!sp->root)
381         node->left = node->right = 0;
382       else if (comparison < 0)
383         {
384           node->left = sp->root;
385           node->right = node->left->right;
386           node->left->right = 0;
387         }
388       else
389         {
390           node->right = sp->root;
391           node->left = node->right->left;
392           node->right->left = 0;
393         }
394
395       sp->root = node;
396     }
397
398   return sp->root;
399 }
400
401 /* Remove KEY from SP.  It is not an error if it did not exist.  */
402
403 void
404 splay_tree_remove (sp, key)
405      splay_tree sp;
406      splay_tree_key key;
407 {
408   splay_tree_splay (sp, key);
409
410   if (sp->root && (*sp->comp) (sp->root->key, key) == 0)
411     {
412       splay_tree_node left, right;
413
414       left = sp->root->left;
415       right = sp->root->right;
416
417       /* Delete the root node itself.  */
418       if (sp->delete_value)
419         (*sp->delete_value) (sp->root->value);
420       (*sp->deallocate) (sp->root, sp->allocate_data);
421
422       /* One of the children is now the root.  Doesn't matter much
423          which, so long as we preserve the properties of the tree.  */
424       if (left)
425         {
426           sp->root = left;
427
428           /* If there was a right child as well, hang it off the 
429              right-most leaf of the left child.  */
430           if (right)
431             {
432               while (left->right)
433                 left = left->right;
434               left->right = right;
435             }
436         }
437       else
438         sp->root = right;
439     }
440 }
441
442 /* Lookup KEY in SP, returning VALUE if present, and NULL 
443    otherwise.  */
444
445 splay_tree_node
446 splay_tree_lookup (sp, key)
447      splay_tree sp;
448      splay_tree_key key;
449 {
450   splay_tree_splay (sp, key);
451
452   if (sp->root && (*sp->comp)(sp->root->key, key) == 0)
453     return sp->root;
454   else
455     return 0;
456 }
457
458 /* Return the node in SP with the greatest key.  */
459
460 splay_tree_node
461 splay_tree_max (sp)
462      splay_tree sp;
463 {
464   splay_tree_node n = sp->root;
465
466   if (!n)
467     return NULL;
468
469   while (n->right)
470     n = n->right;
471
472   return n;
473 }
474
475 /* Return the node in SP with the smallest key.  */
476
477 splay_tree_node
478 splay_tree_min (sp)
479      splay_tree sp;
480 {
481   splay_tree_node n = sp->root;
482
483   if (!n)
484     return NULL;
485
486   while (n->left)
487     n = n->left;
488
489   return n;
490 }
491
492 /* Return the immediate predecessor KEY, or NULL if there is no
493    predecessor.  KEY need not be present in the tree.  */
494
495 splay_tree_node
496 splay_tree_predecessor (sp, key)
497      splay_tree sp;
498      splay_tree_key key;
499 {
500   int comparison;
501   splay_tree_node node;
502
503   /* If the tree is empty, there is certainly no predecessor.  */
504   if (!sp->root)
505     return NULL;
506
507   /* Splay the tree around KEY.  That will leave either the KEY
508      itself, its predecessor, or its successor at the root.  */
509   splay_tree_splay (sp, key);
510   comparison = (*sp->comp)(sp->root->key, key);
511
512   /* If the predecessor is at the root, just return it.  */
513   if (comparison < 0)
514     return sp->root;
515
516   /* Otherwise, find the rightmost element of the left subtree.  */
517   node = sp->root->left;
518   if (node)
519     while (node->right)
520       node = node->right;
521
522   return node;
523 }
524
525 /* Return the immediate successor KEY, or NULL if there is no
526    successor.  KEY need not be present in the tree.  */
527
528 splay_tree_node
529 splay_tree_successor (sp, key)
530      splay_tree sp;
531      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 (sp, fn, data)
565      splay_tree sp;
566      splay_tree_foreach_fn fn;
567      void *data;
568 {
569   return splay_tree_foreach_helper (sp, sp->root, fn, data);
570 }
571
572 /* Splay-tree comparison function, treating the keys as ints.  */
573
574 int
575 splay_tree_compare_ints (k1, k2)
576      splay_tree_key k1;
577      splay_tree_key k2;
578 {
579   if ((int) k1 < (int) k2)
580     return -1;
581   else if ((int) k1 > (int) k2)
582     return 1;
583   else 
584     return 0;
585 }
586
587 /* Splay-tree comparison function, treating the keys as pointers.  */
588
589 int
590 splay_tree_compare_pointers (k1, k2)
591      splay_tree_key k1;
592      splay_tree_key k2;
593 {
594   if ((char*) k1 < (char*) k2)
595     return -1;
596   else if ((char*) k1 > (char*) k2)
597     return 1;
598   else 
599     return 0;
600 }