Home | History | Annotate | Download | only in libiberty
      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 (at) 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 }
    594