• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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
splay_tree_delete_helper(splay_tree sp,splay_tree_node node)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
rotate_left(splay_tree_node * pp,splay_tree_node p,splay_tree_node n)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
rotate_right(splay_tree_node * pp,splay_tree_node p,splay_tree_node n)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
splay_tree_splay(splay_tree sp,splay_tree_key key)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
splay_tree_foreach_helper(splay_tree_node node,splay_tree_foreach_fn fn,void * data)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 *
splay_tree_xmalloc_allocate(int size,void * data ATTRIBUTE_UNUSED)255 splay_tree_xmalloc_allocate (int size, void *data ATTRIBUTE_UNUSED)
256 {
257   return (void *) xmalloc (size);
258 }
259 
260 static void
splay_tree_xmalloc_deallocate(void * object,void * data ATTRIBUTE_UNUSED)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
splay_tree_new(splay_tree_compare_fn compare_fn,splay_tree_delete_key_fn delete_key_fn,splay_tree_delete_value_fn delete_value_fn)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
splay_tree_new_with_allocator(splay_tree_compare_fn compare_fn,splay_tree_delete_key_fn delete_key_fn,splay_tree_delete_value_fn delete_value_fn,splay_tree_allocate_fn allocate_fn,splay_tree_deallocate_fn deallocate_fn,void * allocate_data)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
splay_tree_new_typed_alloc(splay_tree_compare_fn compare_fn,splay_tree_delete_key_fn delete_key_fn,splay_tree_delete_value_fn delete_value_fn,splay_tree_allocate_fn tree_allocate_fn,splay_tree_allocate_fn node_allocate_fn,splay_tree_deallocate_fn deallocate_fn,void * allocate_data)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
splay_tree_delete(splay_tree sp)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
splay_tree_insert(splay_tree sp,splay_tree_key key,splay_tree_value value)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
splay_tree_remove(splay_tree sp,splay_tree_key key)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
splay_tree_lookup(splay_tree sp,splay_tree_key key)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
splay_tree_max(splay_tree sp)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
splay_tree_min(splay_tree sp)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
splay_tree_predecessor(splay_tree sp,splay_tree_key key)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
splay_tree_successor(splay_tree sp,splay_tree_key key)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
splay_tree_foreach(splay_tree sp,splay_tree_foreach_fn fn,void * data)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
splay_tree_compare_ints(splay_tree_key k1,splay_tree_key k2)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
splay_tree_compare_pointers(splay_tree_key k1,splay_tree_key k2)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 }
594