OSDN Git Service

* splay-tree.h (splay_tree_predecessor): Declare.
[pf3gnuchains/gcc-fork.git] / libiberty / splay-tree.c
1 /* A splay-tree datatype.  
2    Copyright (C) 1998, 1999, 2000 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 "libiberty.h"
36 #include "splay-tree.h"
37
38 static void splay_tree_delete_helper    PARAMS((splay_tree, 
39                                                 splay_tree_node));
40 static void splay_tree_splay            PARAMS((splay_tree,
41                                                 splay_tree_key));
42 static splay_tree_node splay_tree_splay_helper     
43                                         PARAMS((splay_tree,
44                                                 splay_tree_key,
45                                                 splay_tree_node*,
46                                                 splay_tree_node*,
47                                                 splay_tree_node*));
48 static int splay_tree_foreach_helper    PARAMS((splay_tree,
49                                                 splay_tree_node,
50                                                 splay_tree_foreach_fn,
51                                                 void*));
52
53 /* Deallocate NODE (a member of SP), and all its sub-trees.  */
54
55 static void 
56 splay_tree_delete_helper (sp, node)
57      splay_tree sp;
58      splay_tree_node node;
59 {
60   if (!node)
61     return;
62
63   splay_tree_delete_helper (sp, node->left);
64   splay_tree_delete_helper (sp, node->right);
65
66   if (sp->delete_key)
67     (*sp->delete_key)(node->key);
68   if (sp->delete_value)
69     (*sp->delete_value)(node->value);
70
71   free ((char*) node);
72 }
73
74 /* Help splay SP around KEY.  PARENT and GRANDPARENT are the parent
75    and grandparent, respectively, of NODE.  */
76
77 static splay_tree_node
78 splay_tree_splay_helper (sp, key, node, parent, grandparent)
79      splay_tree sp;
80      splay_tree_key key;
81      splay_tree_node *node;
82      splay_tree_node *parent;
83      splay_tree_node *grandparent;
84 {
85   splay_tree_node *next;
86   splay_tree_node n;
87   int comparison;
88   
89   n = *node;
90
91   if (!n)
92     return *parent;
93
94   comparison = (*sp->comp) (key, n->key);
95
96   if (comparison == 0)
97     /* We've found the target.  */
98     next = 0;
99   else if (comparison < 0)
100     /* The target is to the left.  */
101     next = &n->left;
102   else 
103     /* The target is to the right.  */
104     next = &n->right;
105
106   if (next)
107     {
108       /* Continue down the tree.  */
109       n = splay_tree_splay_helper (sp, key, next, node, parent);
110
111       /* The recursive call will change the place to which NODE
112          points.  */
113       if (*node != n)
114         return n;
115     }
116
117   if (!parent)
118     /* NODE is the root.  We are done.  */
119     return n;
120
121   /* First, handle the case where there is no grandparent (i.e.,
122      *PARENT is the root of the tree.)  */
123   if (!grandparent) 
124     {
125       if (n == (*parent)->left)
126         {
127           *node = n->right;
128           n->right = *parent;
129         }
130       else
131         {
132           *node = n->left;
133           n->left = *parent;
134         }
135       *parent = n;
136       return n;
137     }
138
139   /* Next handle the cases where both N and *PARENT are left children,
140      or where both are right children.  */
141   if (n == (*parent)->left && *parent == (*grandparent)->left)
142     {
143       splay_tree_node p = *parent;
144
145       (*grandparent)->left = p->right;
146       p->right = *grandparent;
147       p->left = n->right;
148       n->right = p;
149       *grandparent = n;
150       return n; 
151     }
152   else if  (n == (*parent)->right && *parent == (*grandparent)->right)
153     {
154       splay_tree_node p = *parent;
155
156       (*grandparent)->right = p->left;
157       p->left = *grandparent;
158       p->right = n->left;
159       n->left = p;
160       *grandparent = n;
161       return n;
162     }
163
164   /* Finally, deal with the case where N is a left child, but *PARENT
165      is a right child, or vice versa.  */
166   if (n == (*parent)->left) 
167     {
168       (*parent)->left = n->right;
169       n->right = *parent;
170       (*grandparent)->right = n->left;
171       n->left = *grandparent;
172       *grandparent = n;
173       return n;
174     } 
175   else
176     {
177       (*parent)->right = n->left;
178       n->left = *parent;
179       (*grandparent)->left = n->right;
180       n->right = *grandparent;
181       *grandparent = n;
182       return n;
183     }
184 }
185
186 /* Splay SP around KEY.  */
187
188 static void
189 splay_tree_splay (sp, key)
190      splay_tree sp;
191      splay_tree_key key;
192 {
193   if (sp->root == 0)
194     return;
195
196   splay_tree_splay_helper (sp, key, &sp->root, 
197                            /*grandparent=*/0, /*parent=*/0); 
198 }
199
200 /* Call FN, passing it the DATA, for every node below NODE, all of
201    which are from SP, following an in-order traversal.  If FN every
202    returns a non-zero value, the iteration ceases immediately, and the
203    value is returned.  Otherwise, this function returns 0.  */
204
205 static int
206 splay_tree_foreach_helper (sp, node, fn, data)
207      splay_tree sp;
208      splay_tree_node node;
209      splay_tree_foreach_fn fn;
210      void* data;
211 {
212   int val;
213
214   if (!node)
215     return 0;
216
217   val = splay_tree_foreach_helper (sp, node->left, fn, data);
218   if (val)
219     return val;
220
221   val = (*fn)(node, data);
222   if (val)
223     return val;
224
225   return splay_tree_foreach_helper (sp, node->right, fn, data);
226 }
227
228 /* Allocate a new splay tree, using COMPARE_FN to compare nodes,
229    DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
230    values.  */
231
232 splay_tree 
233 splay_tree_new (compare_fn, delete_key_fn, delete_value_fn)
234      splay_tree_compare_fn compare_fn;
235      splay_tree_delete_key_fn delete_key_fn;
236      splay_tree_delete_value_fn delete_value_fn;
237 {
238   splay_tree sp = (splay_tree) xmalloc (sizeof (struct splay_tree_s));
239   sp->root = 0;
240   sp->comp = compare_fn;
241   sp->delete_key = delete_key_fn;
242   sp->delete_value = delete_value_fn;
243
244   return sp;
245 }
246
247 /* Deallocate SP.  */
248
249 void 
250 splay_tree_delete (sp)
251      splay_tree sp;
252 {
253   splay_tree_delete_helper (sp, sp->root);
254   free ((char*) sp);
255 }
256
257 /* Insert a new node (associating KEY with DATA) into SP.  If a
258    previous node with the indicated KEY exists, its data is replaced
259    with the new value.  Returns the new node.  */
260
261 splay_tree_node
262 splay_tree_insert (sp, key, value)
263      splay_tree sp;
264      splay_tree_key key;
265      splay_tree_value value;
266 {
267   int comparison = 0;
268
269   splay_tree_splay (sp, key);
270
271   if (sp->root)
272     comparison = (*sp->comp)(sp->root->key, key);
273
274   if (sp->root && comparison == 0)
275     {
276       /* If the root of the tree already has the indicated KEY, just
277          replace the value with VALUE.  */
278       if (sp->delete_value)
279         (*sp->delete_value)(sp->root->value);
280       sp->root->value = value;
281     } 
282   else 
283     {
284       /* Create a new node, and insert it at the root.  */
285       splay_tree_node node;
286       
287       node = (splay_tree_node) xmalloc (sizeof (struct splay_tree_node_s));
288       node->key = key;
289       node->value = value;
290       
291       if (!sp->root)
292         node->left = node->right = 0;
293       else if (comparison < 0)
294         {
295           node->left = sp->root;
296           node->right = node->left->right;
297           node->left->right = 0;
298         }
299       else
300         {
301           node->right = sp->root;
302           node->left = node->right->left;
303           node->right->left = 0;
304         }
305
306     sp->root = node;
307   }
308
309   return sp->root;
310 }
311
312 /* Remove KEY from SP.  It is not an error if it did not exist.  */
313
314 void
315 splay_tree_remove (sp, key)
316      splay_tree sp;
317      splay_tree_key key;
318 {
319   splay_tree_splay (sp, key);
320
321   if (sp->root && (*sp->comp) (sp->root->key, key) == 0)
322     {
323       splay_tree_node left, right;
324
325       left = sp->root->left;
326       right = sp->root->right;
327
328       /* Delete the root node itself.  */
329       if (sp->delete_value)
330         (*sp->delete_value) (sp->root->value);
331       free (sp->root);
332
333       /* One of the children is now the root.  Doesn't matter much
334          which, so long as we preserve the properties of the tree.  */
335       if (left)
336         {
337           sp->root = left;
338
339           /* If there was a right child as well, hang it off the 
340              right-most leaf of the left child.  */
341           if (right)
342             {
343               while (left->right)
344                 left = left->right;
345               left->right = right;
346             }
347         }
348       else
349         sp->root = right;
350     }
351 }
352
353 /* Lookup KEY in SP, returning VALUE if present, and NULL 
354    otherwise.  */
355
356 splay_tree_node
357 splay_tree_lookup (sp, key)
358      splay_tree sp;
359      splay_tree_key key;
360 {
361   splay_tree_splay (sp, key);
362
363   if (sp->root && (*sp->comp)(sp->root->key, key) == 0)
364     return sp->root;
365   else
366     return 0;
367 }
368
369 /* Return the immediate predecessor KEY, or NULL if there is no
370    predecessor.  KEY need not be present in the tree.  */
371
372 splay_tree_node
373 splay_tree_predecessor (sp, key)
374      splay_tree sp;
375      splay_tree_key key;
376 {
377   int comparison;
378   splay_tree_node node;
379
380   /* If the tree is empty, there is certainly no predecessor.  */
381   if (!sp->root)
382     return NULL;
383
384   /* Splay the tree around KEY.  That will leave either the KEY
385      itself, its predecessor, or its successor at the root.  */
386   splay_tree_splay (sp, key);
387   comparison = (*sp->comp)(sp->root->key, key);
388
389   /* If the predecessor is at the root, just return it.  */
390   if (comparison < 0)
391     return sp->root;
392
393   /* Otherwise, find the rightmost element of the left subtree.  */
394   node = sp->root->left;
395   if (node)
396     while (node->right)
397       node = node->right;
398
399   return node;
400 }
401
402 /* Return the immediate successor KEY, or NULL if there is no
403    predecessor.  KEY need not be present in the tree.  */
404
405 splay_tree_node
406 splay_tree_successor (sp, key)
407      splay_tree sp;
408      splay_tree_key key;
409 {
410   int comparison;
411   splay_tree_node node;
412
413   /* If the tree is empty, there is certainly no predecessor.  */
414   if (!sp->root)
415     return NULL;
416
417   /* Splay the tree around KEY.  That will leave either the KEY
418      itself, its predecessor, or its successor at the root.  */
419   splay_tree_splay (sp, key);
420   comparison = (*sp->comp)(sp->root->key, key);
421
422   /* If the successor is at the root, just return it.  */
423   if (comparison > 0)
424     return sp->root;
425
426   /* Otherwise, find the rightmost element of the left subtree.  */
427   node = sp->root->right;
428   if (node)
429     while (node->left)
430       node = node->left;
431
432   return node;
433 }
434
435 /* Call FN, passing it the DATA, for every node in SP, following an
436    in-order traversal.  If FN every returns a non-zero value, the
437    iteration ceases immediately, and the value is returned.
438    Otherwise, this function returns 0.  */
439
440 int
441 splay_tree_foreach (sp, fn, data)
442      splay_tree sp;
443      splay_tree_foreach_fn fn;
444      void *data;
445 {
446   return splay_tree_foreach_helper (sp, sp->root, fn, data);
447 }
448
449 /* Splay-tree comparison function, treating the keys as ints.  */
450
451 int
452 splay_tree_compare_ints (k1, k2)
453      splay_tree_key k1;
454      splay_tree_key k2;
455 {
456   if ((int) k1 < (int) k2)
457     return -1;
458   else if ((int) k1 > (int) k2)
459     return 1;
460   else 
461     return 0;
462 }
463
464 /* Splay-tree comparison function, treating the keys as pointers.  */
465
466 int
467 splay_tree_compare_pointers (k1, k2)
468      splay_tree_key k1;
469      splay_tree_key k2;
470 {
471   if ((char*) k1 < (char*) k2)
472     return -1;
473   else if ((char*) k1 > (char*) k2)
474     return 1;
475   else 
476     return 0;
477 }