libiberty/splay-tree.c

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