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