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