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