libiberty/splay-tree.c

   1 /* A splay-tree datatype.
   2    Copyright (C) 1998-2019 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.  Keys and values will be deallocated when the
 322 tree is deleted using splay_tree_delete or when a node is removed
 323 using splay_tree_remove.  splay_tree_insert will release the previously
 324 inserted key and value using @var{delete_key_fn} and @var{delete_value_fn}
 325 if the inserted key is already found in the tree.
 326
 327 @end deftypefn
 328
 329 */
 330
 331 splay_tree
 332 splay_tree_new_typed_alloc (splay_tree_compare_fn compare_fn,
 333                             splay_tree_delete_key_fn delete_key_fn,
 334                             splay_tree_delete_value_fn delete_value_fn,
 335                             splay_tree_allocate_fn tree_allocate_fn,
 336                             splay_tree_allocate_fn node_allocate_fn,
 337                             splay_tree_deallocate_fn deallocate_fn,
 338                             void * allocate_data)
 339 {
 340   splay_tree sp = (splay_tree) (*tree_allocate_fn)
 341     (sizeof (struct splay_tree_s), allocate_data);
 342
 343   sp->root = 0;
 344   sp->comp = compare_fn;
 345   sp->delete_key = delete_key_fn;
 346   sp->delete_value = delete_value_fn;
 347   sp->allocate = node_allocate_fn;
 348   sp->deallocate = deallocate_fn;
 349   sp->allocate_data = allocate_data;
 350
 351   return sp;
 352 }
 353
 354 /* Deallocate SP.  */
 355
 356 void
 357 splay_tree_delete (splay_tree sp)
 358 {
 359   splay_tree_delete_helper (sp, sp->root);
 360   (*sp->deallocate) ((char*) sp, sp->allocate_data);
 361 }
 362
 363 /* Insert a new node (associating KEY with DATA) into SP.  If a
 364    previous node with the indicated KEY exists, its data is replaced
 365    with the new value.  Returns the new node.  */
 366
 367 splay_tree_node
 368 splay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value)
 369 {
 370   int comparison = 0;
 371
 372   splay_tree_splay (sp, key);
 373
 374   if (sp->root)
 375     comparison = (*sp->comp)(sp->root->key, key);
 376
 377   if (sp->root && comparison == 0)
 378     {
 379       /* If the root of the tree already has the indicated KEY, delete
 380          the old key and old value, and replace them with KEY and  VALUE.  */
 381       if (sp->delete_key)
 382         (*sp->delete_key) (sp->root->key);
 383       if (sp->delete_value)
 384         (*sp->delete_value)(sp->root->value);
 385       sp->root->key = key;
 386       sp->root->value = value;
 387     }
 388   else
 389     {
 390       /* Create a new node, and insert it at the root.  */
 391       splay_tree_node node;
 392
 393       node = ((splay_tree_node)
 394               (*sp->allocate) (sizeof (struct splay_tree_node_s),
 395                                sp->allocate_data));
 396       node->key = key;
 397       node->value = value;
 398
 399       if (!sp->root)
 400         node->left = node->right = 0;
 401       else if (comparison < 0)
 402         {
 403           node->left = sp->root;
 404           node->right = node->left->right;
 405           node->left->right = 0;
 406         }
 407       else
 408         {
 409           node->right = sp->root;
 410           node->left = node->right->left;
 411           node->right->left = 0;
 412         }
 413
 414       sp->root = node;
 415     }
 416
 417   return sp->root;
 418 }
 419
 420 /* Remove KEY from SP.  It is not an error if it did not exist.  */
 421
 422 void
 423 splay_tree_remove (splay_tree sp, splay_tree_key key)
 424 {
 425   splay_tree_splay (sp, key);
 426
 427   if (sp->root && (*sp->comp) (sp->root->key, key) == 0)
 428     {
 429       splay_tree_node left, right;
 430
 431       left = sp->root->left;
 432       right = sp->root->right;
 433
 434       /* Delete the root node itself.  */
 435       if (sp->delete_key)
 436         (*sp->delete_key) (sp->root->key);
 437       if (sp->delete_value)
 438         (*sp->delete_value) (sp->root->value);
 439       (*sp->deallocate) (sp->root, sp->allocate_data);
 440
 441       /* One of the children is now the root.  Doesn't matter much
 442          which, so long as we preserve the properties of the tree.  */
 443       if (left)
 444         {
 445           sp->root = left;
 446
 447           /* If there was a right child as well, hang it off the
 448              right-most leaf of the left child.  */
 449           if (right)
 450             {
 451               while (left->right)
 452                 left = left->right;
 453               left->right = right;
 454             }
 455         }
 456       else
 457         sp->root = right;
 458     }
 459 }
 460
 461 /* Lookup KEY in SP, returning VALUE if present, and NULL
 462    otherwise.  */
 463
 464 splay_tree_node
 465 splay_tree_lookup (splay_tree sp, splay_tree_key key)
 466 {
 467   splay_tree_splay (sp, key);
 468
 469   if (sp->root && (*sp->comp)(sp->root->key, key) == 0)
 470     return sp->root;
 471   else
 472     return 0;
 473 }
 474
 475 /* Return the node in SP with the greatest key.  */
 476
 477 splay_tree_node
 478 splay_tree_max (splay_tree sp)
 479 {
 480   splay_tree_node n = sp->root;
 481
 482   if (!n)
 483     return NULL;
 484
 485   while (n->right)
 486     n = n->right;
 487
 488   return n;
 489 }
 490
 491 /* Return the node in SP with the smallest key.  */
 492
 493 splay_tree_node
 494 splay_tree_min (splay_tree sp)
 495 {
 496   splay_tree_node n = sp->root;
 497
 498   if (!n)
 499     return NULL;
 500
 501   while (n->left)
 502     n = n->left;
 503
 504   return n;
 505 }
 506
 507 /* Return the immediate predecessor KEY, or NULL if there is no
 508    predecessor.  KEY need not be present in the tree.  */
 509
 510 splay_tree_node
 511 splay_tree_predecessor (splay_tree sp, splay_tree_key key)
 512 {
 513   int comparison;
 514   splay_tree_node node;
 515
 516   /* If the tree is empty, there is certainly no predecessor.  */
 517   if (!sp->root)
 518     return NULL;
 519
 520   /* Splay the tree around KEY.  That will leave either the KEY
 521      itself, its predecessor, or its successor at the root.  */
 522   splay_tree_splay (sp, key);
 523   comparison = (*sp->comp)(sp->root->key, key);
 524
 525   /* If the predecessor is at the root, just return it.  */
 526   if (comparison < 0)
 527     return sp->root;
 528
 529   /* Otherwise, find the rightmost element of the left subtree.  */
 530   node = sp->root->left;
 531   if (node)
 532     while (node->right)
 533       node = node->right;
 534
 535   return node;
 536 }
 537
 538 /* Return the immediate successor KEY, or NULL if there is no
 539    successor.  KEY need not be present in the tree.  */
 540
 541 splay_tree_node
 542 splay_tree_successor (splay_tree sp, splay_tree_key key)
 543 {
 544   int comparison;
 545   splay_tree_node node;
 546
 547   /* If the tree is empty, there is certainly no successor.  */
 548   if (!sp->root)
 549     return NULL;
 550
 551   /* Splay the tree around KEY.  That will leave either the KEY
 552      itself, its predecessor, or its successor at the root.  */
 553   splay_tree_splay (sp, key);
 554   comparison = (*sp->comp)(sp->root->key, key);
 555
 556   /* If the successor is at the root, just return it.  */
 557   if (comparison > 0)
 558     return sp->root;
 559
 560   /* Otherwise, find the leftmost element of the right subtree.  */
 561   node = sp->root->right;
 562   if (node)
 563     while (node->left)
 564       node = node->left;
 565
 566   return node;
 567 }
 568
 569 /* Call FN, passing it the DATA, for every node in SP, following an
 570    in-order traversal.  If FN every returns a non-zero value, the
 571    iteration ceases immediately, and the value is returned.
 572    Otherwise, this function returns 0.  */
 573
 574 int
 575 splay_tree_foreach (splay_tree sp, splay_tree_foreach_fn fn, void *data)
 576 {
 577   return splay_tree_foreach_helper (sp->root, fn, data);
 578 }
 579
 580 /* Splay-tree comparison function, treating the keys as ints.  */
 581
 582 int
 583 splay_tree_compare_ints (splay_tree_key k1, splay_tree_key k2)
 584 {
 585   if ((int) k1 < (int) k2)
 586     return -1;
 587   else if ((int) k1 > (int) k2)
 588     return 1;
 589   else
 590     return 0;
 591 }
 592
 593 /* Splay-tree comparison function, treating the keys as pointers.  */
 594
 595 int
 596 splay_tree_compare_pointers (splay_tree_key k1, splay_tree_key k2)
 597 {
 598   if ((char*) k1 < (char*) k2)
 599     return -1;
 600   else if ((char*) k1 > (char*) k2)
 601     return 1;
 602   else
 603     return 0;
 604 }
 605
 606 /* Splay-tree comparison function, treating the keys as strings.  */
 607
 608 int
 609 splay_tree_compare_strings (splay_tree_key k1, splay_tree_key k2)
 610 {
 611   return strcmp ((char *) k1, (char *) k2);
 612 }
 613
 614 /* Splay-tree delete function, simply using free.  */
 615
 616 void
 617 splay_tree_delete_pointers (splay_tree_value value)
 618 {
 619   free ((void *) value);
 620 }