libiberty/splay-tree.c

   1 /* A splay-tree datatype.
   2    Copyright (C) 1998-2017 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, 51 Franklin Street - Fifth Floor,
  20 Boston, MA 02110-1301, 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 (splay_tree, splay_tree_node);
  41 static inline void rotate_left (splay_tree_node *,
  42                                 splay_tree_node, splay_tree_node);
  43 static inline void rotate_right (splay_tree_node *,
  44                                 splay_tree_node, splay_tree_node);
  45 static void splay_tree_splay (splay_tree, splay_tree_key);
  46 static int splay_tree_foreach_helper (splay_tree_node,
  47                                       splay_tree_foreach_fn, void*);
  48
  49 /* Deallocate NODE (a member of SP), and all its sub-trees.  */
  50
  51 static void
  52 splay_tree_delete_helper (splay_tree sp, splay_tree_node node)
  53 {
  54   splay_tree_node pending = 0;
  55   splay_tree_node active = 0;
  56
  57   if (!node)
  58     return;
  59
  60 #define KDEL(x)  if (sp->delete_key) (*sp->delete_key)(x);
  61 #define VDEL(x)  if (sp->delete_value) (*sp->delete_value)(x);
  62
  63   KDEL (node->key);
  64   VDEL (node->value);
  65
  66   /* We use the "key" field to hold the "next" pointer.  */
  67   node->key = (splay_tree_key)pending;
  68   pending = (splay_tree_node)node;
  69
  70   /* Now, keep processing the pending list until there aren't any
  71      more.  This is a little more complicated than just recursing, but
  72      it doesn't toast the stack for large trees.  */
  73
  74   while (pending)
  75     {
  76       active = pending;
  77       pending = 0;
  78       while (active)
  79         {
  80           splay_tree_node temp;
  81
  82           /* active points to a node which has its key and value
  83              deallocated, we just need to process left and right.  */
  84
  85           if (active->left)
  86             {
  87               KDEL (active->left->key);
  88               VDEL (active->left->value);
  89               active->left->key = (splay_tree_key)pending;
  90               pending = (splay_tree_node)(active->left);
  91             }
  92           if (active->right)
  93             {
  94               KDEL (active->right->key);
  95               VDEL (active->right->value);
  96               active->right->key = (splay_tree_key)pending;
  97               pending = (splay_tree_node)(active->right);
  98             }
  99
 100           temp = active;
 101           active = (splay_tree_node)(temp->key);
 102           (*sp->deallocate) ((char*) temp, sp->allocate_data);
 103         }
 104     }
 105 #undef KDEL
 106 #undef VDEL
 107 }
 108
 109 /* Rotate the edge joining the left child N with its parent P.  PP is the
 110    grandparents' pointer to P.  */
 111
 112 static inline void
 113 rotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
 114 {
 115   splay_tree_node tmp;
 116   tmp = n->right;
 117   n->right = p;
 118   p->left = tmp;
 119   *pp = n;
 120 }
 121
 122 /* Rotate the edge joining the right child N with its parent P.  PP is the
 123    grandparents' pointer to P.  */
 124
 125 static inline void
 126 rotate_right (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
 127 {
 128   splay_tree_node tmp;
 129   tmp = n->left;
 130   n->left = p;
 131   p->right = tmp;
 132   *pp = n;
 133 }
 134
 135 /* Bottom up splay of key.  */
 136
 137 static void
 138 splay_tree_splay (splay_tree sp, splay_tree_key key)
 139 {
 140   if (sp->root == 0)
 141     return;
 142
 143   do {
 144     int cmp1, cmp2;
 145     splay_tree_node n, c;
 146
 147     n = sp->root;
 148     cmp1 = (*sp->comp) (key, n->key);
 149
 150     /* Found.  */
 151     if (cmp1 == 0)
 152       return;
 153
 154     /* Left or right?  If no child, then we're done.  */
 155     if (cmp1 < 0)
 156       c = n->left;
 157     else
 158       c = n->right;
 159     if (!c)
 160       return;
 161
 162     /* Next one left or right?  If found or no child, we're done
 163        after one rotation.  */
 164     cmp2 = (*sp->comp) (key, c->key);
 165     if (cmp2 == 0
 166         || (cmp2 < 0 && !c->left)
 167         || (cmp2 > 0 && !c->right))
 168       {
 169         if (cmp1 < 0)
 170           rotate_left (&sp->root, n, c);
 171         else
 172           rotate_right (&sp->root, n, c);
 173         return;
 174       }
 175
 176     /* Now we have the four cases of double-rotation.  */
 177     if (cmp1 < 0 && cmp2 < 0)
 178       {
 179         rotate_left (&n->left, c, c->left);
 180         rotate_left (&sp->root, n, n->left);
 181       }
 182     else if (cmp1 > 0 && cmp2 > 0)
 183       {
 184         rotate_right (&n->right, c, c->right);
 185         rotate_right (&sp->root, n, n->right);
 186       }
 187     else if (cmp1 < 0 && cmp2 > 0)
 188       {
 189         rotate_right (&n->left, c, c->right);
 190         rotate_left (&sp->root, n, n->left);
 191       }
 192     else if (cmp1 > 0 && cmp2 < 0)
 193       {
 194         rotate_left (&n->right, c, c->left);
 195         rotate_right (&sp->root, n, n->right);
 196       }
 197   } while (1);
 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 (splay_tree_node node,
 207                            splay_tree_foreach_fn fn, void *data)
 208 {
 209   int val;
 210   splay_tree_node *stack;
 211   int stack_ptr, stack_size;
 212
 213   /* A non-recursive implementation is used to avoid filling the stack
 214      for large trees.  Splay trees are worst case O(n) in the depth of
 215      the tree.  */
 216
 217 #define INITIAL_STACK_SIZE 100
 218   stack_size = INITIAL_STACK_SIZE;
 219   stack_ptr = 0;
 220   stack = XNEWVEC (splay_tree_node, stack_size);
 221   val = 0;
 222
 223   for (;;)
 224     {
 225       while (node != NULL)
 226         {
 227           if (stack_ptr == stack_size)
 228             {
 229               stack_size *= 2;
 230               stack = XRESIZEVEC (splay_tree_node, stack, stack_size);
 231             }
 232           stack[stack_ptr++] = node;
 233           node = node->left;
 234         }
 235
 236       if (stack_ptr == 0)
 237         break;
 238
 239       node = stack[--stack_ptr];
 240
 241       val = (*fn) (node, data);
 242       if (val)
 243         break;
 244
 245       node = node->right;
 246     }
 247
 248   XDELETEVEC (stack);
 249   return val;
 250 }
 251
 252 /* An allocator and deallocator based on xmalloc.  */
 253 static void *
 254 splay_tree_xmalloc_allocate (int size, void *data ATTRIBUTE_UNUSED)
 255 {
 256   return (void *) xmalloc (size);
 257 }
 258
 259 static void
 260 splay_tree_xmalloc_deallocate (void *object, void *data ATTRIBUTE_UNUSED)
 261 {
 262   free (object);
 263 }
 264
 265
 266 /* Allocate a new splay tree, using COMPARE_FN to compare nodes,
 267    DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
 268    values.  Use xmalloc to allocate the splay tree structure, and any
 269    nodes added.  */
 270
 271 splay_tree
 272 splay_tree_new (splay_tree_compare_fn compare_fn,
 273                 splay_tree_delete_key_fn delete_key_fn,
 274                 splay_tree_delete_value_fn delete_value_fn)
 275 {
 276   return (splay_tree_new_with_allocator
 277           (compare_fn, delete_key_fn, delete_value_fn,
 278            splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate, 0));
 279 }
 280
 281
 282 /* Allocate a new splay tree, using COMPARE_FN to compare nodes,
 283    DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
 284    values.  */
 285
 286 splay_tree
 287 splay_tree_new_with_allocator (splay_tree_compare_fn compare_fn,
 288                                splay_tree_delete_key_fn delete_key_fn,
 289                                splay_tree_delete_value_fn delete_value_fn,
 290                                splay_tree_allocate_fn allocate_fn,
 291                                splay_tree_deallocate_fn deallocate_fn,
 292                                void *allocate_data)
 293 {
 294   return
 295     splay_tree_new_typed_alloc (compare_fn, delete_key_fn, delete_value_fn,
 296                                 allocate_fn, allocate_fn, deallocate_fn,
 297                                 allocate_data);
 298 }
 299
 300 /*
 301
 302 @deftypefn Supplemental splay_tree splay_tree_new_with_typed_alloc @
 303 (splay_tree_compare_fn @var{compare_fn}, @
 304 splay_tree_delete_key_fn @var{delete_key_fn}, @
 305 splay_tree_delete_value_fn @var{delete_value_fn}, @
 306 splay_tree_allocate_fn @var{tree_allocate_fn}, @
 307 splay_tree_allocate_fn @var{node_allocate_fn}, @
 308 splay_tree_deallocate_fn @var{deallocate_fn}, @
 309 void * @var{allocate_data})
 310
 311 This function creates a splay tree that uses two different allocators
 312 @var{tree_allocate_fn} and @var{node_allocate_fn} to use for allocating the
 313 tree itself and its nodes respectively.  This is useful when variables of
 314 different types need to be allocated with different allocators.
 315
 316 The splay tree will use @var{compare_fn} to compare nodes,
 317 @var{delete_key_fn} to deallocate keys, and @var{delete_value_fn} to
 318 deallocate values.
 319
 320 @end deftypefn
 321
 322 */
 323
 324 splay_tree
 325 splay_tree_new_typed_alloc (splay_tree_compare_fn compare_fn,
 326                             splay_tree_delete_key_fn delete_key_fn,
 327                             splay_tree_delete_value_fn delete_value_fn,
 328                             splay_tree_allocate_fn tree_allocate_fn,
 329                             splay_tree_allocate_fn node_allocate_fn,
 330                             splay_tree_deallocate_fn deallocate_fn,
 331                             void * allocate_data)
 332 {
 333   splay_tree sp = (splay_tree) (*tree_allocate_fn)
 334     (sizeof (struct splay_tree_s), allocate_data);
 335
 336   sp->root = 0;
 337   sp->comp = compare_fn;
 338   sp->delete_key = delete_key_fn;
 339   sp->delete_value = delete_value_fn;
 340   sp->allocate = node_allocate_fn;
 341   sp->deallocate = deallocate_fn;
 342   sp->allocate_data = allocate_data;
 343
 344   return sp;
 345 }
 346
 347 /* Deallocate SP.  */
 348
 349 void
 350 splay_tree_delete (splay_tree sp)
 351 {
 352   splay_tree_delete_helper (sp, sp->root);
 353   (*sp->deallocate) ((char*) sp, sp->allocate_data);
 354 }
 355
 356 /* Insert a new node (associating KEY with DATA) into SP.  If a
 357    previous node with the indicated KEY exists, its data is replaced
 358    with the new value.  Returns the new node.  */
 359
 360 splay_tree_node
 361 splay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value)
 362 {
 363   int comparison = 0;
 364
 365   splay_tree_splay (sp, key);
 366
 367   if (sp->root)
 368     comparison = (*sp->comp)(sp->root->key, key);
 369
 370   if (sp->root && comparison == 0)
 371     {
 372       /* If the root of the tree already has the indicated KEY, just
 373          replace the value with VALUE.  */
 374       if (sp->delete_value)
 375         (*sp->delete_value)(sp->root->value);
 376       sp->root->value = value;
 377     }
 378   else
 379     {
 380       /* Create a new node, and insert it at the root.  */
 381       splay_tree_node node;
 382
 383       node = ((splay_tree_node)
 384               (*sp->allocate) (sizeof (struct splay_tree_node_s),
 385                                sp->allocate_data));
 386       node->key = key;
 387       node->value = value;
 388
 389       if (!sp->root)
 390         node->left = node->right = 0;
 391       else if (comparison < 0)
 392         {
 393           node->left = sp->root;
 394           node->right = node->left->right;
 395           node->left->right = 0;
 396         }
 397       else
 398         {
 399           node->right = sp->root;
 400           node->left = node->right->left;
 401           node->right->left = 0;
 402         }
 403
 404       sp->root = node;
 405     }
 406
 407   return sp->root;
 408 }
 409
 410 /* Remove KEY from SP.  It is not an error if it did not exist.  */
 411
 412 void
 413 splay_tree_remove (splay_tree sp, splay_tree_key key)
 414 {
 415   splay_tree_splay (sp, key);
 416
 417   if (sp->root && (*sp->comp) (sp->root->key, key) == 0)
 418     {
 419       splay_tree_node left, right;
 420
 421       left = sp->root->left;
 422       right = sp->root->right;
 423
 424       /* Delete the root node itself.  */
 425       if (sp->delete_value)
 426         (*sp->delete_value) (sp->root->value);
 427       (*sp->deallocate) (sp->root, sp->allocate_data);
 428
 429       /* One of the children is now the root.  Doesn't matter much
 430          which, so long as we preserve the properties of the tree.  */
 431       if (left)
 432         {
 433           sp->root = left;
 434
 435           /* If there was a right child as well, hang it off the
 436              right-most leaf of the left child.  */
 437           if (right)
 438             {
 439               while (left->right)
 440                 left = left->right;
 441               left->right = right;
 442             }
 443         }
 444       else
 445         sp->root = right;
 446     }
 447 }
 448
 449 /* Lookup KEY in SP, returning VALUE if present, and NULL
 450    otherwise.  */
 451
 452 splay_tree_node
 453 splay_tree_lookup (splay_tree sp, splay_tree_key key)
 454 {
 455   splay_tree_splay (sp, key);
 456
 457   if (sp->root && (*sp->comp)(sp->root->key, key) == 0)
 458     return sp->root;
 459   else
 460     return 0;
 461 }
 462
 463 /* Return the node in SP with the greatest key.  */
 464
 465 splay_tree_node
 466 splay_tree_max (splay_tree sp)
 467 {
 468   splay_tree_node n = sp->root;
 469
 470   if (!n)
 471     return NULL;
 472
 473   while (n->right)
 474     n = n->right;
 475
 476   return n;
 477 }
 478
 479 /* Return the node in SP with the smallest key.  */
 480
 481 splay_tree_node
 482 splay_tree_min (splay_tree sp)
 483 {
 484   splay_tree_node n = sp->root;
 485
 486   if (!n)
 487     return NULL;
 488
 489   while (n->left)
 490     n = n->left;
 491
 492   return n;
 493 }
 494
 495 /* Return the immediate predecessor KEY, or NULL if there is no
 496    predecessor.  KEY need not be present in the tree.  */
 497
 498 splay_tree_node
 499 splay_tree_predecessor (splay_tree sp, splay_tree_key key)
 500 {
 501   int comparison;
 502   splay_tree_node node;
 503
 504   /* If the tree is empty, there is certainly no predecessor.  */
 505   if (!sp->root)
 506     return NULL;
 507
 508   /* Splay the tree around KEY.  That will leave either the KEY
 509      itself, its predecessor, or its successor at the root.  */
 510   splay_tree_splay (sp, key);
 511   comparison = (*sp->comp)(sp->root->key, key);
 512
 513   /* If the predecessor is at the root, just return it.  */
 514   if (comparison < 0)
 515     return sp->root;
 516
 517   /* Otherwise, find the rightmost element of the left subtree.  */
 518   node = sp->root->left;
 519   if (node)
 520     while (node->right)
 521       node = node->right;
 522
 523   return node;
 524 }
 525
 526 /* Return the immediate successor KEY, or NULL if there is no
 527    successor.  KEY need not be present in the tree.  */
 528
 529 splay_tree_node
 530 splay_tree_successor (splay_tree sp, splay_tree_key key)
 531 {
 532   int comparison;
 533   splay_tree_node node;
 534
 535   /* If the tree is empty, there is certainly no successor.  */
 536   if (!sp->root)
 537     return NULL;
 538
 539   /* Splay the tree around KEY.  That will leave either the KEY
 540      itself, its predecessor, or its successor at the root.  */
 541   splay_tree_splay (sp, key);
 542   comparison = (*sp->comp)(sp->root->key, key);
 543
 544   /* If the successor is at the root, just return it.  */
 545   if (comparison > 0)
 546     return sp->root;
 547
 548   /* Otherwise, find the leftmost element of the right subtree.  */
 549   node = sp->root->right;
 550   if (node)
 551     while (node->left)
 552       node = node->left;
 553
 554   return node;
 555 }
 556
 557 /* Call FN, passing it the DATA, for every node in SP, following an
 558    in-order traversal.  If FN every returns a non-zero value, the
 559    iteration ceases immediately, and the value is returned.
 560    Otherwise, this function returns 0.  */
 561
 562 int
 563 splay_tree_foreach (splay_tree sp, splay_tree_foreach_fn fn, void *data)
 564 {
 565   return splay_tree_foreach_helper (sp->root, fn, data);
 566 }
 567
 568 /* Splay-tree comparison function, treating the keys as ints.  */
 569
 570 int
 571 splay_tree_compare_ints (splay_tree_key k1, splay_tree_key k2)
 572 {
 573   if ((int) k1 < (int) k2)
 574     return -1;
 575   else if ((int) k1 > (int) k2)
 576     return 1;
 577   else
 578     return 0;
 579 }
 580
 581 /* Splay-tree comparison function, treating the keys as pointers.  */
 582
 583 int
 584 splay_tree_compare_pointers (splay_tree_key k1, splay_tree_key k2)
 585 {
 586   if ((char*) k1 < (char*) k2)
 587     return -1;
 588   else if ((char*) k1 > (char*) k2)
 589     return 1;
 590   else
 591     return 0;
 592 }