libiberty/splay-tree.c

   1 /* A splay-tree datatype.
   2    Copyright (C) 1998, 1999 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 "libiberty.h"
  36 #include "splay-tree.h"
  37
  38 static void splay_tree_delete_helper    PARAMS((splay_tree,
  39                                                 splay_tree_node));
  40 static void splay_tree_splay            PARAMS((splay_tree,
  41                                                 splay_tree_key));
  42 static splay_tree_node splay_tree_splay_helper
  43                                         PARAMS((splay_tree,
  44                                                 splay_tree_key,
  45                                                 splay_tree_node*,
  46                                                 splay_tree_node*,
  47                                                 splay_tree_node*));
  48 static int splay_tree_foreach_helper    PARAMS((splay_tree,
  49                                                 splay_tree_node,
  50                                                 splay_tree_foreach_fn,
  51                                                 void*));
  52
  53 /* Deallocate NODE (a member of SP), and all its sub-trees.  */
  54
  55 static void
  56 splay_tree_delete_helper (sp, node)
  57      splay_tree sp;
  58      splay_tree_node node;
  59 {
  60   if (!node)
  61     return;
  62
  63   splay_tree_delete_helper (sp, node->left);
  64   splay_tree_delete_helper (sp, node->right);
  65
  66   if (sp->delete_key)
  67     (*sp->delete_key)(node->key);
  68   if (sp->delete_value)
  69     (*sp->delete_value)(node->value);
  70
  71   free ((char*) node);
  72 }
  73
  74 /* Help splay SP around KEY.  PARENT and GRANDPARENT are the parent
  75    and grandparent, respectively, of NODE.  */
  76
  77 static splay_tree_node
  78 splay_tree_splay_helper (sp, key, node, parent, grandparent)
  79      splay_tree sp;
  80      splay_tree_key key;
  81      splay_tree_node *node;
  82      splay_tree_node *parent;
  83      splay_tree_node *grandparent;
  84 {
  85   splay_tree_node *next;
  86   splay_tree_node n;
  87   int comparison;
  88
  89   n = *node;
  90
  91   if (!n)
  92     return *parent;
  93
  94   comparison = (*sp->comp) (key, n->key);
  95
  96   if (comparison == 0)
  97     /* We've found the target.  */
  98     next = 0;
  99   else if (comparison < 0)
 100     /* The target is to the left.  */
 101     next = &n->left;
 102   else
 103     /* The target is to the right.  */
 104     next = &n->right;
 105
 106   if (next)
 107     {
 108       /* Continue down the tree.  */
 109       n = splay_tree_splay_helper (sp, key, next, node, parent);
 110
 111       /* The recursive call will change the place to which NODE
 112          points.  */
 113       if (*node != n)
 114         return n;
 115     }
 116
 117   if (!parent)
 118     /* NODE is the root.  We are done.  */
 119     return n;
 120
 121   /* First, handle the case where there is no grandparent (i.e.,
 122      *PARENT is the root of the tree.)  */
 123   if (!grandparent)
 124     {
 125       if (n == (*parent)->left)
 126         {
 127           *node = n->right;
 128           n->right = *parent;
 129         }
 130       else
 131         {
 132           *node = n->left;
 133           n->left = *parent;
 134         }
 135       *parent = n;
 136       return n;
 137     }
 138
 139   /* Next handle the cases where both N and *PARENT are left children,
 140      or where both are right children.  */
 141   if (n == (*parent)->left && *parent == (*grandparent)->left)
 142     {
 143       splay_tree_node p = *parent;
 144
 145       (*grandparent)->left = p->right;
 146       p->right = *grandparent;
 147       p->left = n->right;
 148       n->right = p;
 149       *grandparent = n;
 150       return n;
 151     }
 152   else if  (n == (*parent)->right && *parent == (*grandparent)->right)
 153     {
 154       splay_tree_node p = *parent;
 155
 156       (*grandparent)->right = p->left;
 157       p->left = *grandparent;
 158       p->right = n->left;
 159       n->left = p;
 160       *grandparent = n;
 161       return n;
 162     }
 163
 164   /* Finally, deal with the case where N is a left child, but *PARENT
 165      is a right child, or vice versa.  */
 166   if (n == (*parent)->left)
 167     {
 168       (*parent)->left = n->right;
 169       n->right = *parent;
 170       (*grandparent)->right = n->left;
 171       n->left = *grandparent;
 172       *grandparent = n;
 173       return n;
 174     }
 175   else
 176     {
 177       (*parent)->right = n->left;
 178       n->left = *parent;
 179       (*grandparent)->left = n->right;
 180       n->right = *grandparent;
 181       *grandparent = n;
 182       return n;
 183     }
 184 }
 185
 186 /* Splay SP around KEY.  */
 187
 188 static void
 189 splay_tree_splay (sp, key)
 190      splay_tree sp;
 191      splay_tree_key key;
 192 {
 193   if (sp->root == 0)
 194     return;
 195
 196   splay_tree_splay_helper (sp, key, &sp->root,
 197                            /*grandparent=*/0, /*parent=*/0);
 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 (sp, node, fn, data)
 207      splay_tree sp;
 208      splay_tree_node node;
 209      splay_tree_foreach_fn fn;
 210      void* data;
 211 {
 212   int val;
 213
 214   if (!node)
 215     return 0;
 216
 217   val = splay_tree_foreach_helper (sp, node->left, fn, data);
 218   if (val)
 219     return val;
 220
 221   val = (*fn)(node, data);
 222   if (val)
 223     return val;
 224
 225   return splay_tree_foreach_helper (sp, node->right, fn, data);
 226 }
 227
 228 /* Allocate a new splay tree, using COMPARE_FN to compare nodes,
 229    DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
 230    values.  */
 231
 232 splay_tree
 233 splay_tree_new (compare_fn, delete_key_fn, delete_value_fn)
 234      splay_tree_compare_fn compare_fn;
 235      splay_tree_delete_key_fn delete_key_fn;
 236      splay_tree_delete_value_fn delete_value_fn;
 237 {
 238   splay_tree sp = (splay_tree) xmalloc (sizeof (struct splay_tree_s));
 239   sp->root = 0;
 240   sp->comp = compare_fn;
 241   sp->delete_key = delete_key_fn;
 242   sp->delete_value = delete_value_fn;
 243
 244   return sp;
 245 }
 246
 247 /* Deallocate SP.  */
 248
 249 void
 250 splay_tree_delete (sp)
 251      splay_tree sp;
 252 {
 253   splay_tree_delete_helper (sp, sp->root);
 254   free ((char*) sp);
 255 }
 256
 257 /* Insert a new node (associating KEY with DATA) into SP.  If a
 258    previous node with the indicated KEY exists, its data is replaced
 259    with the new value.  Returns the new node.  */
 260
 261 splay_tree_node
 262 splay_tree_insert (sp, key, value)
 263      splay_tree sp;
 264      splay_tree_key key;
 265      splay_tree_value value;
 266 {
 267   int comparison = 0;
 268
 269   splay_tree_splay (sp, key);
 270
 271   if (sp->root)
 272     comparison = (*sp->comp)(sp->root->key, key);
 273
 274   if (sp->root && comparison == 0)
 275     {
 276       /* If the root of the tree already has the indicated KEY, just
 277          replace the value with VALUE.  */
 278       if (sp->delete_value)
 279         (*sp->delete_value)(sp->root->value);
 280       sp->root->value = value;
 281     }
 282   else
 283     {
 284       /* Create a new node, and insert it at the root.  */
 285       splay_tree_node node;
 286
 287       node = (splay_tree_node) xmalloc (sizeof (struct splay_tree_node_s));
 288       node->key = key;
 289       node->value = value;
 290
 291       if (!sp->root)
 292         node->left = node->right = 0;
 293       else if (comparison < 0)
 294         {
 295           node->left = sp->root;
 296           node->right = node->left->right;
 297           node->left->right = 0;
 298         }
 299       else
 300         {
 301           node->right = sp->root;
 302           node->left = node->right->left;
 303           node->right->left = 0;
 304         }
 305
 306     sp->root = node;
 307   }
 308
 309   return sp->root;
 310 }
 311
 312 /* Remove KEY from SP.  It is not an error if it did not exist.  */
 313
 314 void
 315 splay_tree_remove (sp, key)
 316      splay_tree sp;
 317      splay_tree_key key;
 318 {
 319   splay_tree_splay (sp, key);
 320
 321   if (sp->root && (*sp->comp) (sp->root->key, key) == 0)
 322     {
 323       splay_tree_node left, right;
 324
 325       left = sp->root->left;
 326       right = sp->root->right;
 327
 328       /* Delete the root node itself.  */
 329       if (sp->delete_value)
 330         (*sp->delete_value) (sp->root->value);
 331       free (sp->root);
 332
 333       /* One of the children is now the root.  Doesn't matter much
 334          which, so long as we preserve the properties of the tree.  */
 335       if (left)
 336         {
 337           sp->root = left;
 338
 339           /* If there was a right child as well, hang it off the
 340              right-most leaf of the left child.  */
 341           if (right)
 342             {
 343               while (left->right)
 344                 left = left->right;
 345               left->right = right;
 346             }
 347         }
 348       else
 349         sp->root = right;
 350     }
 351 }
 352
 353 /* Lookup KEY in SP, returning VALUE if present, and NULL
 354    otherwise.  */
 355
 356 splay_tree_node
 357 splay_tree_lookup (sp, key)
 358      splay_tree sp;
 359      splay_tree_key key;
 360 {
 361   splay_tree_splay (sp, key);
 362
 363   if (sp->root && (*sp->comp)(sp->root->key, key) == 0)
 364     return sp->root;
 365   else
 366     return 0;
 367 }
 368
 369 /* Call FN, passing it the DATA, for every node in SP, following an
 370    in-order traversal.  If FN every returns a non-zero value, the
 371    iteration ceases immediately, and the value is returned.
 372    Otherwise, this function returns 0.  */
 373
 374 int
 375 splay_tree_foreach (sp, fn, data)
 376      splay_tree sp;
 377      splay_tree_foreach_fn fn;
 378      void *data;
 379 {
 380   return splay_tree_foreach_helper (sp, sp->root, fn, data);
 381 }
 382
 383 /* Splay-tree comparison function, treating the keys as ints.  */
 384
 385 int
 386 splay_tree_compare_ints (k1, k2)
 387      splay_tree_key k1;
 388      splay_tree_key k2;
 389 {
 390   if ((int) k1 < (int) k2)
 391     return -1;
 392   else if ((int) k1 > (int) k2)
 393     return 1;
 394   else
 395     return 0;
 396 }
 397
 398 /* Splay-tree comparison function, treating the keys as pointers.  */
 399
 400 int
 401 splay_tree_compare_pointers (k1, k2)
 402      splay_tree_key k1;
 403      splay_tree_key k2;
 404 {
 405   if ((char*) k1 < (char*) k2)
 406     return -1;
 407   else if ((char*) k1 > (char*) k2)
 408     return 1;
 409   else
 410     return 0;
 411 }