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