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   free ((char*) node);
  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 /* Allocate a new splay tree, using COMPARE_FN to compare nodes,
 231    DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
 232    values.  */
 233
 234 splay_tree
 235 splay_tree_new (compare_fn, delete_key_fn, delete_value_fn)
 236      splay_tree_compare_fn compare_fn;
 237      splay_tree_delete_key_fn delete_key_fn;
 238      splay_tree_delete_value_fn delete_value_fn;
 239 {
 240   splay_tree sp = (splay_tree) xmalloc (sizeof (struct splay_tree_s));
 241   sp->root = 0;
 242   sp->comp = compare_fn;
 243   sp->delete_key = delete_key_fn;
 244   sp->delete_value = delete_value_fn;
 245
 246   return sp;
 247 }
 248
 249 /* Deallocate SP.  */
 250
 251 void
 252 splay_tree_delete (sp)
 253      splay_tree sp;
 254 {
 255   splay_tree_delete_helper (sp, sp->root);
 256   free ((char*) sp);
 257 }
 258
 259 /* Insert a new node (associating KEY with DATA) into SP.  If a
 260    previous node with the indicated KEY exists, its data is replaced
 261    with the new value.  Returns the new node.  */
 262
 263 splay_tree_node
 264 splay_tree_insert (sp, key, value)
 265      splay_tree sp;
 266      splay_tree_key key;
 267      splay_tree_value value;
 268 {
 269   int comparison = 0;
 270
 271   splay_tree_splay (sp, key);
 272
 273   if (sp->root)
 274     comparison = (*sp->comp)(sp->root->key, key);
 275
 276   if (sp->root && comparison == 0)
 277     {
 278       /* If the root of the tree already has the indicated KEY, just
 279          replace the value with VALUE.  */
 280       if (sp->delete_value)
 281         (*sp->delete_value)(sp->root->value);
 282       sp->root->value = value;
 283     }
 284   else
 285     {
 286       /* Create a new node, and insert it at the root.  */
 287       splay_tree_node node;
 288
 289       node = (splay_tree_node) xmalloc (sizeof (struct splay_tree_node_s));
 290       node->key = key;
 291       node->value = value;
 292
 293       if (!sp->root)
 294         node->left = node->right = 0;
 295       else if (comparison < 0)
 296         {
 297           node->left = sp->root;
 298           node->right = node->left->right;
 299           node->left->right = 0;
 300         }
 301       else
 302         {
 303           node->right = sp->root;
 304           node->left = node->right->left;
 305           node->right->left = 0;
 306         }
 307
 308       sp->root = node;
 309     }
 310
 311   return sp->root;
 312 }
 313
 314 /* Remove KEY from SP.  It is not an error if it did not exist.  */
 315
 316 void
 317 splay_tree_remove (sp, key)
 318      splay_tree sp;
 319      splay_tree_key key;
 320 {
 321   splay_tree_splay (sp, key);
 322
 323   if (sp->root && (*sp->comp) (sp->root->key, key) == 0)
 324     {
 325       splay_tree_node left, right;
 326
 327       left = sp->root->left;
 328       right = sp->root->right;
 329
 330       /* Delete the root node itself.  */
 331       if (sp->delete_value)
 332         (*sp->delete_value) (sp->root->value);
 333       free (sp->root);
 334
 335       /* One of the children is now the root.  Doesn't matter much
 336          which, so long as we preserve the properties of the tree.  */
 337       if (left)
 338         {
 339           sp->root = left;
 340
 341           /* If there was a right child as well, hang it off the
 342              right-most leaf of the left child.  */
 343           if (right)
 344             {
 345               while (left->right)
 346                 left = left->right;
 347               left->right = right;
 348             }
 349         }
 350       else
 351         sp->root = right;
 352     }
 353 }
 354
 355 /* Lookup KEY in SP, returning VALUE if present, and NULL
 356    otherwise.  */
 357
 358 splay_tree_node
 359 splay_tree_lookup (sp, key)
 360      splay_tree sp;
 361      splay_tree_key key;
 362 {
 363   splay_tree_splay (sp, key);
 364
 365   if (sp->root && (*sp->comp)(sp->root->key, key) == 0)
 366     return sp->root;
 367   else
 368     return 0;
 369 }
 370
 371 /* Return the node in SP with the greatest key.  */
 372
 373 splay_tree_node
 374 splay_tree_max (sp)
 375      splay_tree sp;
 376 {
 377   splay_tree_node n = sp->root;
 378
 379   if (!n)
 380     return NULL;
 381
 382   while (n->right)
 383     n = n->right;
 384
 385   return n;
 386 }
 387
 388 /* Return the node in SP with the smallest key.  */
 389
 390 splay_tree_node
 391 splay_tree_min (sp)
 392      splay_tree sp;
 393 {
 394   splay_tree_node n = sp->root;
 395
 396   if (!n)
 397     return NULL;
 398
 399   while (n->left)
 400     n = n->left;
 401
 402   return n;
 403 }
 404
 405 /* Return the immediate predecessor KEY, or NULL if there is no
 406    predecessor.  KEY need not be present in the tree.  */
 407
 408 splay_tree_node
 409 splay_tree_predecessor (sp, key)
 410      splay_tree sp;
 411      splay_tree_key key;
 412 {
 413   int comparison;
 414   splay_tree_node node;
 415
 416   /* If the tree is empty, there is certainly no predecessor.  */
 417   if (!sp->root)
 418     return NULL;
 419
 420   /* Splay the tree around KEY.  That will leave either the KEY
 421      itself, its predecessor, or its successor at the root.  */
 422   splay_tree_splay (sp, key);
 423   comparison = (*sp->comp)(sp->root->key, key);
 424
 425   /* If the predecessor is at the root, just return it.  */
 426   if (comparison < 0)
 427     return sp->root;
 428
 429   /* Otherwise, find the leftmost element of the right subtree.  */
 430   node = sp->root->left;
 431   if (node)
 432     while (node->right)
 433       node = node->right;
 434
 435   return node;
 436 }
 437
 438 /* Return the immediate successor KEY, or NULL if there is no
 439    predecessor.  KEY need not be present in the tree.  */
 440
 441 splay_tree_node
 442 splay_tree_successor (sp, key)
 443      splay_tree sp;
 444      splay_tree_key key;
 445 {
 446   int comparison;
 447   splay_tree_node node;
 448
 449   /* If the tree is empty, there is certainly no predecessor.  */
 450   if (!sp->root)
 451     return NULL;
 452
 453   /* Splay the tree around KEY.  That will leave either the KEY
 454      itself, its predecessor, or its successor at the root.  */
 455   splay_tree_splay (sp, key);
 456   comparison = (*sp->comp)(sp->root->key, key);
 457
 458   /* If the successor is at the root, just return it.  */
 459   if (comparison > 0)
 460     return sp->root;
 461
 462   /* Otherwise, find the rightmost element of the left subtree.  */
 463   node = sp->root->right;
 464   if (node)
 465     while (node->left)
 466       node = node->left;
 467
 468   return node;
 469 }
 470
 471 /* Call FN, passing it the DATA, for every node in SP, following an
 472    in-order traversal.  If FN every returns a non-zero value, the
 473    iteration ceases immediately, and the value is returned.
 474    Otherwise, this function returns 0.  */
 475
 476 int
 477 splay_tree_foreach (sp, fn, data)
 478      splay_tree sp;
 479      splay_tree_foreach_fn fn;
 480      void *data;
 481 {
 482   return splay_tree_foreach_helper (sp, sp->root, fn, data);
 483 }
 484
 485 /* Splay-tree comparison function, treating the keys as ints.  */
 486
 487 int
 488 splay_tree_compare_ints (k1, k2)
 489      splay_tree_key k1;
 490      splay_tree_key k2;
 491 {
 492   if ((int) k1 < (int) k2)
 493     return -1;
 494   else if ((int) k1 > (int) k2)
 495     return 1;
 496   else
 497     return 0;
 498 }
 499
 500 /* Splay-tree comparison function, treating the keys as pointers.  */
 501
 502 int
 503 splay_tree_compare_pointers (k1, k2)
 504      splay_tree_key k1;
 505      splay_tree_key k2;
 506 {
 507   if ((char*) k1 < (char*) k2)
 508     return -1;
 509   else if ((char*) k1 > (char*) k2)
 510     return 1;
 511   else
 512     return 0;
 513 }