libiberty/splay-tree.c

   1 /* A splay-tree datatype.
   2    Copyright (C) 1998, 1999, 2000, 2001, 2009,
   3    2010 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, 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 sp, splay_tree_node node,
 208                            splay_tree_foreach_fn fn, void *data)
 209 {
 210   int val;
 211
 212   if (!node)
 213     return 0;
 214
 215   val = splay_tree_foreach_helper (sp, node->left, fn, data);
 216   if (val)
 217     return val;
 218
 219   val = (*fn)(node, data);
 220   if (val)
 221     return val;
 222
 223   return splay_tree_foreach_helper (sp, node->right, fn, data);
 224 }
 225
 226
 227 /* An allocator and deallocator based on xmalloc.  */
 228 static void *
 229 splay_tree_xmalloc_allocate (int size, void *data ATTRIBUTE_UNUSED)
 230 {
 231   return (void *) xmalloc (size);
 232 }
 233
 234 static void
 235 splay_tree_xmalloc_deallocate (void *object, void *data ATTRIBUTE_UNUSED)
 236 {
 237   free (object);
 238 }
 239
 240
 241 /* Allocate a new splay tree, using COMPARE_FN to compare nodes,
 242    DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
 243    values.  Use xmalloc to allocate the splay tree structure, and any
 244    nodes added.  */
 245
 246 splay_tree
 247 splay_tree_new (splay_tree_compare_fn compare_fn,
 248                 splay_tree_delete_key_fn delete_key_fn,
 249                 splay_tree_delete_value_fn delete_value_fn)
 250 {
 251   return (splay_tree_new_with_allocator
 252           (compare_fn, delete_key_fn, delete_value_fn,
 253            splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate, 0));
 254 }
 255
 256
 257 /* Allocate a new splay tree, using COMPARE_FN to compare nodes,
 258    DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
 259    values.  */
 260
 261 splay_tree
 262 splay_tree_new_with_allocator (splay_tree_compare_fn compare_fn,
 263                                splay_tree_delete_key_fn delete_key_fn,
 264                                splay_tree_delete_value_fn delete_value_fn,
 265                                splay_tree_allocate_fn allocate_fn,
 266                                splay_tree_deallocate_fn deallocate_fn,
 267                                void *allocate_data)
 268 {
 269   return
 270     splay_tree_new_typed_alloc (compare_fn, delete_key_fn, delete_value_fn,
 271                                 allocate_fn, allocate_fn, deallocate_fn,
 272                                 allocate_data);
 273 }
 274
 275 /*
 276
 277 @deftypefn Supplemental splay_tree splay_tree_new_with_typed_alloc
 278 (splay_tree_compare_fn @var{compare_fn},
 279 splay_tree_delete_key_fn @var{delete_key_fn},
 280 splay_tree_delete_value_fn @var{delete_value_fn},
 281 splay_tree_allocate_fn @var{tree_allocate_fn},
 282 splay_tree_allocate_fn @var{node_allocate_fn},
 283 splay_tree_deallocate_fn @var{deallocate_fn},
 284 void * @var{allocate_data})
 285
 286 This function creates a splay tree that uses two different allocators
 287 @var{tree_allocate_fn} and @var{node_allocate_fn} to use for allocating the
 288 tree itself and its nodes respectively.  This is useful when variables of
 289 different types need to be allocated with different allocators.
 290
 291 The splay tree will use @var{compare_fn} to compare nodes,
 292 @var{delete_key_fn} to deallocate keys, and @var{delete_value_fn} to
 293 deallocate values.
 294
 295 @end deftypefn
 296
 297 */
 298
 299 splay_tree
 300 splay_tree_new_typed_alloc (splay_tree_compare_fn compare_fn,
 301                             splay_tree_delete_key_fn delete_key_fn,
 302                             splay_tree_delete_value_fn delete_value_fn,
 303                             splay_tree_allocate_fn tree_allocate_fn,
 304                             splay_tree_allocate_fn node_allocate_fn,
 305                             splay_tree_deallocate_fn deallocate_fn,
 306                             void * allocate_data)
 307 {
 308   splay_tree sp = (splay_tree) (*tree_allocate_fn)
 309     (sizeof (struct splay_tree_s), allocate_data);
 310
 311   sp->root = 0;
 312   sp->comp = compare_fn;
 313   sp->delete_key = delete_key_fn;
 314   sp->delete_value = delete_value_fn;
 315   sp->allocate = node_allocate_fn;
 316   sp->deallocate = deallocate_fn;
 317   sp->allocate_data = allocate_data;
 318
 319   return sp;
 320 }
 321
 322 /* Deallocate SP.  */
 323
 324 void
 325 splay_tree_delete (splay_tree sp)
 326 {
 327   splay_tree_delete_helper (sp, sp->root);
 328   (*sp->deallocate) ((char*) sp, sp->allocate_data);
 329 }
 330
 331 /* Insert a new node (associating KEY with DATA) into SP.  If a
 332    previous node with the indicated KEY exists, its data is replaced
 333    with the new value.  Returns the new node.  */
 334
 335 splay_tree_node
 336 splay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value)
 337 {
 338   int comparison = 0;
 339
 340   splay_tree_splay (sp, key);
 341
 342   if (sp->root)
 343     comparison = (*sp->comp)(sp->root->key, key);
 344
 345   if (sp->root && comparison == 0)
 346     {
 347       /* If the root of the tree already has the indicated KEY, just
 348          replace the value with VALUE.  */
 349       if (sp->delete_value)
 350         (*sp->delete_value)(sp->root->value);
 351       sp->root->value = value;
 352     }
 353   else
 354     {
 355       /* Create a new node, and insert it at the root.  */
 356       splay_tree_node node;
 357
 358       node = ((splay_tree_node)
 359               (*sp->allocate) (sizeof (struct splay_tree_node_s),
 360                                sp->allocate_data));
 361       node->key = key;
 362       node->value = value;
 363
 364       if (!sp->root)
 365         node->left = node->right = 0;
 366       else if (comparison < 0)
 367         {
 368           node->left = sp->root;
 369           node->right = node->left->right;
 370           node->left->right = 0;
 371         }
 372       else
 373         {
 374           node->right = sp->root;
 375           node->left = node->right->left;
 376           node->right->left = 0;
 377         }
 378
 379       sp->root = node;
 380     }
 381
 382   return sp->root;
 383 }
 384
 385 /* Remove KEY from SP.  It is not an error if it did not exist.  */
 386
 387 void
 388 splay_tree_remove (splay_tree sp, splay_tree_key key)
 389 {
 390   splay_tree_splay (sp, key);
 391
 392   if (sp->root && (*sp->comp) (sp->root->key, key) == 0)
 393     {
 394       splay_tree_node left, right;
 395
 396       left = sp->root->left;
 397       right = sp->root->right;
 398
 399       /* Delete the root node itself.  */
 400       if (sp->delete_value)
 401         (*sp->delete_value) (sp->root->value);
 402       (*sp->deallocate) (sp->root, sp->allocate_data);
 403
 404       /* One of the children is now the root.  Doesn't matter much
 405          which, so long as we preserve the properties of the tree.  */
 406       if (left)
 407         {
 408           sp->root = left;
 409
 410           /* If there was a right child as well, hang it off the
 411              right-most leaf of the left child.  */
 412           if (right)
 413             {
 414               while (left->right)
 415                 left = left->right;
 416               left->right = right;
 417             }
 418         }
 419       else
 420         sp->root = right;
 421     }
 422 }
 423
 424 /* Lookup KEY in SP, returning VALUE if present, and NULL
 425    otherwise.  */
 426
 427 splay_tree_node
 428 splay_tree_lookup (splay_tree sp, splay_tree_key key)
 429 {
 430   splay_tree_splay (sp, key);
 431
 432   if (sp->root && (*sp->comp)(sp->root->key, key) == 0)
 433     return sp->root;
 434   else
 435     return 0;
 436 }
 437
 438 /* Return the node in SP with the greatest key.  */
 439
 440 splay_tree_node
 441 splay_tree_max (splay_tree sp)
 442 {
 443   splay_tree_node n = sp->root;
 444
 445   if (!n)
 446     return NULL;
 447
 448   while (n->right)
 449     n = n->right;
 450
 451   return n;
 452 }
 453
 454 /* Return the node in SP with the smallest key.  */
 455
 456 splay_tree_node
 457 splay_tree_min (splay_tree sp)
 458 {
 459   splay_tree_node n = sp->root;
 460
 461   if (!n)
 462     return NULL;
 463
 464   while (n->left)
 465     n = n->left;
 466
 467   return n;
 468 }
 469
 470 /* Return the immediate predecessor KEY, or NULL if there is no
 471    predecessor.  KEY need not be present in the tree.  */
 472
 473 splay_tree_node
 474 splay_tree_predecessor (splay_tree sp, splay_tree_key key)
 475 {
 476   int comparison;
 477   splay_tree_node node;
 478
 479   /* If the tree is empty, there is certainly no predecessor.  */
 480   if (!sp->root)
 481     return NULL;
 482
 483   /* Splay the tree around KEY.  That will leave either the KEY
 484      itself, its predecessor, or its successor at the root.  */
 485   splay_tree_splay (sp, key);
 486   comparison = (*sp->comp)(sp->root->key, key);
 487
 488   /* If the predecessor is at the root, just return it.  */
 489   if (comparison < 0)
 490     return sp->root;
 491
 492   /* Otherwise, find the rightmost element of the left subtree.  */
 493   node = sp->root->left;
 494   if (node)
 495     while (node->right)
 496       node = node->right;
 497
 498   return node;
 499 }
 500
 501 /* Return the immediate successor KEY, or NULL if there is no
 502    successor.  KEY need not be present in the tree.  */
 503
 504 splay_tree_node
 505 splay_tree_successor (splay_tree sp, splay_tree_key key)
 506 {
 507   int comparison;
 508   splay_tree_node node;
 509
 510   /* If the tree is empty, there is certainly no successor.  */
 511   if (!sp->root)
 512     return NULL;
 513
 514   /* Splay the tree around KEY.  That will leave either the KEY
 515      itself, its predecessor, or its successor at the root.  */
 516   splay_tree_splay (sp, key);
 517   comparison = (*sp->comp)(sp->root->key, key);
 518
 519   /* If the successor is at the root, just return it.  */
 520   if (comparison > 0)
 521     return sp->root;
 522
 523   /* Otherwise, find the leftmost element of the right subtree.  */
 524   node = sp->root->right;
 525   if (node)
 526     while (node->left)
 527       node = node->left;
 528
 529   return node;
 530 }
 531
 532 /* Call FN, passing it the DATA, for every node in SP, following an
 533    in-order traversal.  If FN every returns a non-zero value, the
 534    iteration ceases immediately, and the value is returned.
 535    Otherwise, this function returns 0.  */
 536
 537 int
 538 splay_tree_foreach (splay_tree sp, splay_tree_foreach_fn fn, void *data)
 539 {
 540   return splay_tree_foreach_helper (sp, sp->root, fn, data);
 541 }
 542
 543 /* Splay-tree comparison function, treating the keys as ints.  */
 544
 545 int
 546 splay_tree_compare_ints (splay_tree_key k1, splay_tree_key k2)
 547 {
 548   if ((int) k1 < (int) k2)
 549     return -1;
 550   else if ((int) k1 > (int) k2)
 551     return 1;
 552   else
 553     return 0;
 554 }
 555
 556 /* Splay-tree comparison function, treating the keys as pointers.  */
 557
 558 int
 559 splay_tree_compare_pointers (splay_tree_key k1, splay_tree_key k2)
 560 {
 561   if ((char*) k1 < (char*) k2)
 562     return -1;
 563   else if ((char*) k1 > (char*) k2)
 564     return 1;
 565   else
 566     return 0;
 567 }