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 }