libiberty/splay-tree.c

   1 /* A splay-tree datatype.
   2    Copyright (C) 1998, 1999, 2000 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 immediate predecessor KEY, or NULL if there is no
 372    predecessor.  KEY need not be present in the tree.  */
 373
 374 splay_tree_node
 375 splay_tree_predecessor (sp, key)
 376      splay_tree sp;
 377      splay_tree_key key;
 378 {
 379   int comparison;
 380   splay_tree_node node;
 381
 382   /* If the tree is empty, there is certainly no predecessor.  */
 383   if (!sp->root)
 384     return NULL;
 385
 386   /* Splay the tree around KEY.  That will leave either the KEY
 387      itself, its predecessor, or its successor at the root.  */
 388   splay_tree_splay (sp, key);
 389   comparison = (*sp->comp)(sp->root->key, key);
 390
 391   /* If the predecessor is at the root, just return it.  */
 392   if (comparison < 0)
 393     return sp->root;
 394
 395   /* Otherwise, find the leftmost element of the right subtree.  */
 396   node = sp->root->left;
 397   if (node)
 398     while (node->right)
 399       node = node->right;
 400
 401   return node;
 402 }
 403
 404 /* Return the immediate successor KEY, or NULL if there is no
 405    predecessor.  KEY need not be present in the tree.  */
 406
 407 splay_tree_node
 408 splay_tree_successor (sp, key)
 409      splay_tree sp;
 410      splay_tree_key key;
 411 {
 412   int comparison;
 413   splay_tree_node node;
 414
 415   /* If the tree is empty, there is certainly no predecessor.  */
 416   if (!sp->root)
 417     return NULL;
 418
 419   /* Splay the tree around KEY.  That will leave either the KEY
 420      itself, its predecessor, or its successor at the root.  */
 421   splay_tree_splay (sp, key);
 422   comparison = (*sp->comp)(sp->root->key, key);
 423
 424   /* If the successor is at the root, just return it.  */
 425   if (comparison > 0)
 426     return sp->root;
 427
 428   /* Otherwise, find the rightmost element of the left subtree.  */
 429   node = sp->root->right;
 430   if (node)
 431     while (node->left)
 432       node = node->left;
 433
 434   return node;
 435 }
 436
 437 /* Call FN, passing it the DATA, for every node in SP, following an
 438    in-order traversal.  If FN every returns a non-zero value, the
 439    iteration ceases immediately, and the value is returned.
 440    Otherwise, this function returns 0.  */
 441
 442 int
 443 splay_tree_foreach (sp, fn, data)
 444      splay_tree sp;
 445      splay_tree_foreach_fn fn;
 446      void *data;
 447 {
 448   return splay_tree_foreach_helper (sp, sp->root, fn, data);
 449 }
 450
 451 /* Splay-tree comparison function, treating the keys as ints.  */
 452
 453 int
 454 splay_tree_compare_ints (k1, k2)
 455      splay_tree_key k1;
 456      splay_tree_key k2;
 457 {
 458   if ((int) k1 < (int) k2)
 459     return -1;
 460   else if ((int) k1 > (int) k2)
 461     return 1;
 462   else
 463     return 0;
 464 }
 465
 466 /* Splay-tree comparison function, treating the keys as pointers.  */
 467
 468 int
 469 splay_tree_compare_pointers (k1, k2)
 470      splay_tree_key k1;
 471      splay_tree_key k2;
 472 {
 473   if ((char*) k1 < (char*) k2)
 474     return -1;
 475   else if ((char*) k1 > (char*) k2)
 476     return 1;
 477   else
 478     return 0;
 479 }