libiberty/splay-tree.c

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