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