libiberty/splay-tree.c

   1 /* A splay-tree datatype.
   2    Copyright (C) 1998 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 the Free
  19    Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  20
  21    For an easily readable description of splay-trees, see:
  22
  23      Lewis, Harry R. and Denenberg, Larry.  Data Structures and Their
  24      Algorithms.  Harper-Collins, Inc.  1991.  */
  25
  26 #ifndef IN_GCC
  27 #include "libiberty.h"
  28 #endif /* IN_GCC */
  29 #include "splay-tree.h"
  30
  31 static void splay_tree_delete_helper    PARAMS((splay_tree,
  32                                                 splay_tree_node));
  33 static void splay_tree_splay            PARAMS((splay_tree,
  34                                                 splay_tree_key));
  35 static splay_tree_node splay_tree_splay_helper
  36                                         PARAMS((splay_tree,
  37                                                 splay_tree_key,
  38                                                 splay_tree_node*,
  39                                                 splay_tree_node*,
  40                                                 splay_tree_node*));
  41 static int splay_tree_foreach_helper    PARAMS((splay_tree,
  42                                                 splay_tree_node,
  43                                                 splay_tree_foreach_fn,
  44                                                 void*));
  45
  46 /* Deallocate NODE (a member of SP), and all its sub-trees.  */
  47
  48 static void
  49 splay_tree_delete_helper (sp, node)
  50      splay_tree sp;
  51      splay_tree_node node;
  52 {
  53   if (!node)
  54     return;
  55
  56   splay_tree_delete_helper (sp, node->left);
  57   splay_tree_delete_helper (sp, node->right);
  58
  59   if (sp->delete_key)
  60     (*sp->delete_key)(node->key);
  61   if (sp->delete_value)
  62     (*sp->delete_value)(node->value);
  63
  64   free ((char*) node);
  65 }
  66
  67 /* Help splay SP around KEY.  PARENT and GRANDPARENT are the parent
  68    and grandparent, respectively, of NODE.  */
  69
  70 static splay_tree_node
  71 splay_tree_splay_helper (sp, key, node, parent, grandparent)
  72      splay_tree sp;
  73      splay_tree_key key;
  74      splay_tree_node *node;
  75      splay_tree_node *parent;
  76      splay_tree_node *grandparent;
  77 {
  78   splay_tree_node *next;
  79   splay_tree_node n;
  80   int comparison;
  81
  82   n = *node;
  83
  84   if (!n)
  85     return *parent;
  86
  87   comparison = (*sp->comp) (key, n->key);
  88
  89   if (comparison == 0)
  90     /* We've found the target.  */
  91     next = 0;
  92   else if (comparison < 0)
  93     /* The target is to the left.  */
  94     next = &n->left;
  95   else
  96     /* The target is to the right.  */
  97     next = &n->right;
  98
  99   if (next)
 100     {
 101       /* Continue down the tree.  */
 102       n = splay_tree_splay_helper (sp, key, next, node, parent);
 103
 104       /* The recursive call will change the place to which NODE
 105          points.  */
 106       if (*node != n)
 107         return n;
 108     }
 109
 110   if (!parent)
 111     /* NODE is the root.  We are done.  */
 112     return n;
 113
 114   /* First, handle the case where there is no grandparent (i.e.,
 115      *PARENT is the root of the tree.)  */
 116   if (!grandparent)
 117     {
 118       if (n == (*parent)->left)
 119         {
 120           *node = n->right;
 121           n->right = *parent;
 122         }
 123       else
 124         {
 125           *node = n->left;
 126           n->left = *parent;
 127         }
 128       *parent = n;
 129       return n;
 130     }
 131
 132   /* Next handle the cases where both N and *PARENT are left children,
 133      or where both are right children.  */
 134   if (n == (*parent)->left && *parent == (*grandparent)->left)
 135     {
 136       splay_tree_node p = *parent;
 137
 138       (*grandparent)->left = p->right;
 139       p->right = *grandparent;
 140       p->left = n->right;
 141       n->right = p;
 142       *grandparent = n;
 143       return n;
 144     }
 145   else if  (n == (*parent)->right && *parent == (*grandparent)->right)
 146     {
 147       splay_tree_node p = *parent;
 148
 149       (*grandparent)->right = p->left;
 150       p->left = *grandparent;
 151       p->right = n->left;
 152       n->left = p;
 153       *grandparent = n;
 154       return n;
 155     }
 156
 157   /* Finally, deal with the case where N is a left child, but *PARENT
 158      is a right child, or vice versa.  */
 159   if (n == (*parent)->left)
 160     {
 161       (*parent)->left = n->right;
 162       n->right = *parent;
 163       (*grandparent)->right = n->left;
 164       n->left = *grandparent;
 165       *grandparent = n;
 166       return n;
 167     }
 168   else
 169     {
 170       (*parent)->right = n->left;
 171       n->left = *parent;
 172       (*grandparent)->left = n->right;
 173       n->right = *grandparent;
 174       *grandparent = n;
 175       return n;
 176     }
 177 }
 178
 179 /* Splay SP around KEY.  */
 180
 181 static void
 182 splay_tree_splay (sp, key)
 183      splay_tree sp;
 184      splay_tree_key key;
 185 {
 186   if (sp->root == 0)
 187     return;
 188
 189   splay_tree_splay_helper (sp, key, &sp->root,
 190                            /*grandparent=*/0, /*parent=*/0);
 191 }
 192
 193 /* Call FN, passing it the DATA, for every node below NODE, all of
 194    which are from SP, following an in-order traversal.  If FN every
 195    returns a non-zero value, the iteration ceases immediately, and the
 196    value is returned.  Otherwise, this function returns 0.  */
 197
 198 static int
 199 splay_tree_foreach_helper (sp, node, fn, data)
 200      splay_tree sp;
 201      splay_tree_node node;
 202      splay_tree_foreach_fn fn;
 203      void* data;
 204 {
 205   int val;
 206
 207   if (!node)
 208     return 0;
 209
 210   val = splay_tree_foreach_helper (sp, node->left, fn, data);
 211   if (val)
 212     return val;
 213
 214   val = (*fn)(node, data);
 215   if (val)
 216     return val;
 217
 218   return splay_tree_foreach_helper (sp, node->right, fn, data);
 219 }
 220
 221 /* Allocate a new splay tree, using COMPARE_FN to compare nodes,
 222    DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
 223    values.  */
 224
 225 splay_tree
 226 splay_tree_new (compare_fn, delete_key_fn, delete_value_fn)
 227      splay_tree_compare_fn compare_fn;
 228      splay_tree_delete_key_fn delete_key_fn;
 229      splay_tree_delete_value_fn delete_value_fn;
 230 {
 231   splay_tree sp = (splay_tree) xmalloc (sizeof (struct splay_tree));
 232   sp->root = 0;
 233   sp->comp = compare_fn;
 234   sp->delete_key = delete_key_fn;
 235   sp->delete_value = delete_value_fn;
 236
 237   return sp;
 238 }
 239
 240 /* Deallocate SP.  */
 241
 242 void
 243 splay_tree_delete (sp)
 244      splay_tree sp;
 245 {
 246   splay_tree_delete_helper (sp, sp->root);
 247   free ((char*) sp);
 248 }
 249
 250 /* Insert a new node (associating KEY with DATA) into SP.  If a
 251    previous node with the indicated KEY exists, its data is replaced
 252    with the new value.  */
 253
 254 void
 255 splay_tree_insert (sp, key, value)
 256      splay_tree sp;
 257      splay_tree_key key;
 258      splay_tree_value value;
 259 {
 260   int comparison;
 261
 262   splay_tree_splay (sp, key);
 263
 264   if (sp->root)
 265     comparison = (*sp->comp)(sp->root->key, key);
 266
 267   if (sp->root && comparison == 0)
 268     {
 269       /* If the root of the tree already has the indicated KEY, just
 270          replace the value with VALUE.  */
 271       if (sp->delete_value)
 272         (*sp->delete_value)(sp->root->value);
 273       sp->root->value = value;
 274     }
 275   else
 276     {
 277       /* Create a new node, and insert it at the root.  */
 278       splay_tree_node node;
 279
 280       node = (splay_tree_node) xmalloc (sizeof (struct splay_tree_node));
 281       node->key = key;
 282       node->value = value;
 283
 284       if (!sp->root)
 285         node->left = node->right = 0;
 286       else if (comparison < 0)
 287         {
 288           node->left = sp->root;
 289           node->right = node->left->right;
 290           node->left->right = 0;
 291         }
 292       else
 293         {
 294           node->right = sp->root;
 295           node->left = node->right->left;
 296           node->right->left = 0;
 297         }
 298
 299     sp->root = node;
 300   }
 301 }
 302
 303 /* Lookup KEY in SP, returning VALUE if present, and NULL
 304    otherwise.  */
 305
 306 splay_tree_node
 307 splay_tree_lookup (sp, key)
 308      splay_tree sp;
 309      splay_tree_key key;
 310 {
 311   splay_tree_splay (sp, key);
 312
 313   if (sp->root && (*sp->comp)(sp->root->key, key) == 0)
 314     return sp->root;
 315   else
 316     return 0;
 317 }
 318
 319 /* Call FN, passing it the DATA, for every node in SP, following an
 320    in-order traversal.  If FN every returns a non-zero value, the
 321    iteration ceases immediately, and the value is returned.
 322    Otherwise, this function returns 0.  */
 323
 324 int
 325 splay_tree_foreach (sp, fn, data)
 326      splay_tree sp;
 327      splay_tree_foreach_fn fn;
 328      void *data;
 329 {
 330   return splay_tree_foreach_helper (sp, sp->root, fn, data);
 331 }