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