libmudflap/splay-tree.c

   1 /* A splay-tree datatype.
   2    Copyright (C) 1998, 1999, 2000, 2001, 2004 Free Software Foundation, Inc.
   3    Contributed by Mark Mitchell (mark@markmitchell.com).
   4    Adapted for libmudflap from libiberty.
   5
   6 This file is part of GNU CC.
   7
   8 GNU CC is free software; you can redistribute it and/or modify it
   9 under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 2, or (at your option)
  11 any later version.
  12
  13 In addition to the permissions in the GNU General Public License, the
  14 Free Software Foundation gives you unlimited permission to link the
  15 compiled version of this file into combinations with other programs,
  16 and to distribute those combinations without any restriction coming
  17 from the use of this file.  (The General Public License restrictions
  18 do apply in other respects; for example, they cover modification of
  19 the file, and distribution when not linked into a combine
  20 executable.)
  21
  22 GNU CC is distributed in the hope that it will be useful, but
  23 WITHOUT ANY WARRANTY; without even the implied warranty of
  24 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  25 General Public License for more details.
  26
  27 You should have received a copy of the GNU General Public License
  28 along with GNU CC; see the file COPYING.  If not, write to
  29 the Free Software Foundation, 59 Temple Place - Suite 330,
  30 Boston, MA 02111-1307, USA.  */
  31
  32 /* For an easily readable description of splay-trees, see:
  33
  34      Lewis, Harry R. and Denenberg, Larry.  Data Structures and Their
  35      Algorithms.  Harper-Collins, Inc.  1991.  */
  36
  37 #include <stdlib.h>
  38 #include <stdio.h>
  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
  57
  58 /* Inline comparison function specialized for libmudflap's key type.  */
  59 static inline int
  60 compare_uintptr_t (splay_tree_key k1, splay_tree_key k2)
  61 {
  62   if ((uintptr_t) k1 < (uintptr_t) k2)
  63     return -1;
  64   else if ((uintptr_t) k1 > (uintptr_t) k2)
  65     return 1;
  66   else
  67     return 0;
  68 }
  69
  70
  71
  72 /* Deallocate NODE (a member of SP), and all its sub-trees.  */
  73
  74 static void
  75 splay_tree_delete_helper (sp, node)
  76      splay_tree sp;
  77      splay_tree_node node;
  78 {
  79   if (!node)
  80     return;
  81
  82   splay_tree_delete_helper (sp, node->left);
  83   splay_tree_delete_helper (sp, node->right);
  84   (*sp->deallocate) ((char*) node, sp->allocate_data);
  85 }
  86
  87 /* Help splay SP around KEY.  PARENT and GRANDPARENT are the parent
  88    and grandparent, respectively, of NODE.  */
  89
  90 static splay_tree_node
  91 splay_tree_splay_helper (sp, key, node, parent, grandparent)
  92      splay_tree sp;
  93      splay_tree_key key;
  94      splay_tree_node *node;
  95      splay_tree_node *parent;
  96      splay_tree_node *grandparent;
  97 {
  98   splay_tree_node *next;
  99   splay_tree_node n;
 100   int comparison;
 101
 102   n = *node;
 103
 104   if (!n)
 105     return *parent;
 106
 107   comparison = compare_uintptr_t (key, n->key);
 108
 109   if (comparison == 0)
 110     /* We've found the target.  */
 111     next = 0;
 112   else if (comparison < 0)
 113     /* The target is to the left.  */
 114     next = &n->left;
 115   else
 116     /* The target is to the right.  */
 117     next = &n->right;
 118
 119   if (next)
 120     {
 121       /* Continue down the tree.  */
 122       n = splay_tree_splay_helper (sp, key, next, node, parent);
 123
 124       /* The recursive call will change the place to which NODE
 125          points.  */
 126       if (*node != n)
 127         return n;
 128     }
 129
 130   if (!parent)
 131     /* NODE is the root.  We are done.  */
 132     return n;
 133
 134   /* First, handle the case where there is no grandparent (i.e.,
 135      *PARENT is the root of the tree.)  */
 136   if (!grandparent)
 137     {
 138       if (n == (*parent)->left)
 139         {
 140           *node = n->right;
 141           n->right = *parent;
 142         }
 143       else
 144         {
 145           *node = n->left;
 146           n->left = *parent;
 147         }
 148       *parent = n;
 149       return n;
 150     }
 151
 152   /* Next handle the cases where both N and *PARENT are left children,
 153      or where both are right children.  */
 154   if (n == (*parent)->left && *parent == (*grandparent)->left)
 155     {
 156       splay_tree_node p = *parent;
 157
 158       (*grandparent)->left = p->right;
 159       p->right = *grandparent;
 160       p->left = n->right;
 161       n->right = p;
 162       *grandparent = n;
 163       return n;
 164     }
 165   else if  (n == (*parent)->right && *parent == (*grandparent)->right)
 166     {
 167       splay_tree_node p = *parent;
 168
 169       (*grandparent)->right = p->left;
 170       p->left = *grandparent;
 171       p->right = n->left;
 172       n->left = p;
 173       *grandparent = n;
 174       return n;
 175     }
 176
 177   /* Finally, deal with the case where N is a left child, but *PARENT
 178      is a right child, or vice versa.  */
 179   if (n == (*parent)->left)
 180     {
 181       (*parent)->left = n->right;
 182       n->right = *parent;
 183       (*grandparent)->right = n->left;
 184       n->left = *grandparent;
 185       *grandparent = n;
 186       return n;
 187     }
 188   else
 189     {
 190       (*parent)->right = n->left;
 191       n->left = *parent;
 192       (*grandparent)->left = n->right;
 193       n->right = *grandparent;
 194       *grandparent = n;
 195       return n;
 196     }
 197 }
 198
 199 /* Splay SP around KEY.  */
 200
 201 static void
 202 splay_tree_splay (sp, key)
 203      splay_tree sp;
 204      splay_tree_key key;
 205 {
 206   if (sp->root == 0)
 207     return;
 208
 209   /* If we just splayed the tree with the same key, do nothing.  */
 210   if (sp->last_splayed_key_p &&
 211       compare_uintptr_t (sp->last_splayed_key, key) == 0)
 212     return;
 213
 214   splay_tree_splay_helper (sp, key, &sp->root,
 215                            /*grandparent=*/0, /*parent=*/0);
 216
 217   /* Cache this splay key. */
 218   sp->last_splayed_key = key;
 219   sp->last_splayed_key_p = 1;
 220 }
 221
 222 /* Call FN, passing it the DATA, for every node below NODE, all of
 223    which are from SP, following an in-order traversal.  If FN every
 224    returns a non-zero value, the iteration ceases immediately, and the
 225    value is returned.  Otherwise, this function returns 0.  */
 226
 227 static int
 228 splay_tree_foreach_helper (sp, node, fn, data)
 229      splay_tree sp;
 230      splay_tree_node node;
 231      splay_tree_foreach_fn fn;
 232      void* data;
 233 {
 234   int val;
 235
 236   if (!node)
 237     return 0;
 238
 239   val = splay_tree_foreach_helper (sp, node->left, fn, data);
 240   if (val)
 241     return val;
 242
 243   val = (*fn)(node, data);
 244   if (val)
 245     return val;
 246
 247   return splay_tree_foreach_helper (sp, node->right, fn, data);
 248 }
 249
 250
 251 /* An allocator and deallocator based on xmalloc.  */
 252 static void *
 253 splay_tree_xmalloc_allocate (size, data)
 254      int size;
 255      void *data ATTRIBUTE_UNUSED;
 256 {
 257   return (void *) xmalloc (size);
 258 }
 259
 260 static void
 261 splay_tree_xmalloc_deallocate (object, data)
 262      void *object;
 263      void *data ATTRIBUTE_UNUSED;
 264 {
 265   free (object);
 266 }
 267
 268
 269 /* Allocate a new splay tree, using COMPARE_FN to compare nodes,
 270    DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
 271    values.  Use xmalloc to allocate the splay tree structure, and any
 272    nodes added.  */
 273
 274 splay_tree
 275 splay_tree_new ()
 276 {
 277   splay_tree_allocate_fn allocate_fn = splay_tree_xmalloc_allocate;
 278   splay_tree_deallocate_fn deallocate_fn = splay_tree_xmalloc_deallocate;
 279   void *allocate_data = NULL;
 280   splay_tree sp = (splay_tree) (*allocate_fn) (sizeof (struct splay_tree_s),
 281                                                allocate_data);
 282   sp->root = 0;
 283   sp->allocate = allocate_fn;
 284   sp->deallocate = deallocate_fn;
 285   sp->allocate_data = allocate_data;
 286   sp->last_splayed_key_p = 0;
 287
 288   return sp;
 289 }
 290
 291 /* Deallocate SP.  */
 292
 293 void
 294 splay_tree_delete (sp)
 295      splay_tree sp;
 296 {
 297   splay_tree_delete_helper (sp, sp->root);
 298   (*sp->deallocate) ((char*) sp, sp->allocate_data);
 299 }
 300
 301 /* Insert a new node (associating KEY with DATA) into SP.  If a
 302    previous node with the indicated KEY exists, its data is replaced
 303    with the new value.  Returns the new node.  */
 304
 305 splay_tree_node
 306 splay_tree_insert (sp, key, value)
 307      splay_tree sp;
 308      splay_tree_key key;
 309      splay_tree_value value;
 310 {
 311   int comparison = 0;
 312
 313   splay_tree_splay (sp, key);
 314
 315   if (sp->root)
 316     comparison = compare_uintptr_t (sp->root->key, key);
 317
 318   if (sp->root && comparison == 0)
 319     {
 320       /* If the root of the tree already has the indicated KEY, just
 321          replace the value with VALUE.  */
 322       sp->root->value = value;
 323     }
 324   else
 325     {
 326       /* Create a new node, and insert it at the root.  */
 327       splay_tree_node node;
 328
 329       node = ((splay_tree_node)
 330               (*sp->allocate) (sizeof (struct splay_tree_node_s),
 331                                sp->allocate_data));
 332       node->key = key;
 333       node->value = value;
 334
 335       if (!sp->root)
 336         node->left = node->right = 0;
 337       else if (comparison < 0)
 338         {
 339           node->left = sp->root;
 340           node->right = node->left->right;
 341           node->left->right = 0;
 342         }
 343       else
 344         {
 345           node->right = sp->root;
 346           node->left = node->right->left;
 347           node->right->left = 0;
 348         }
 349
 350       sp->root = node;
 351       sp->last_splayed_key_p = 0;
 352     }
 353
 354   return sp->root;
 355 }
 356
 357 /* Remove KEY from SP.  It is not an error if it did not exist.  */
 358
 359 void
 360 splay_tree_remove (sp, key)
 361      splay_tree sp;
 362      splay_tree_key key;
 363 {
 364   splay_tree_splay (sp, key);
 365   sp->last_splayed_key_p = 0;
 366
 367   if (sp->root && compare_uintptr_t (sp->root->key, key) == 0)
 368     {
 369       splay_tree_node left, right;
 370
 371       left = sp->root->left;
 372       right = sp->root->right;
 373
 374       /* Delete the root node itself.  */
 375       (*sp->deallocate) (sp->root, sp->allocate_data);
 376
 377       /* One of the children is now the root.  Doesn't matter much
 378          which, so long as we preserve the properties of the tree.  */
 379       if (left)
 380         {
 381           sp->root = left;
 382
 383           /* If there was a right child as well, hang it off the
 384              right-most leaf of the left child.  */
 385           if (right)
 386             {
 387               while (left->right)
 388                 left = left->right;
 389               left->right = right;
 390             }
 391         }
 392       else
 393         sp->root = right;
 394     }
 395 }
 396
 397 /* Lookup KEY in SP, returning VALUE if present, and NULL
 398    otherwise.  */
 399
 400 splay_tree_node
 401 splay_tree_lookup (sp, key)
 402      splay_tree sp;
 403      splay_tree_key key;
 404 {
 405   splay_tree_splay (sp, key);
 406
 407   if (sp->root && compare_uintptr_t (sp->root->key, key) == 0)
 408     return sp->root;
 409   else
 410     return 0;
 411 }
 412
 413 /* Return the node in SP with the greatest key.  */
 414
 415 splay_tree_node
 416 splay_tree_max (sp)
 417      splay_tree sp;
 418 {
 419   splay_tree_node n = sp->root;
 420
 421   if (!n)
 422     return NULL;
 423
 424   while (n->right)
 425     n = n->right;
 426
 427   return n;
 428 }
 429
 430 /* Return the node in SP with the smallest key.  */
 431
 432 splay_tree_node
 433 splay_tree_min (sp)
 434      splay_tree sp;
 435 {
 436   splay_tree_node n = sp->root;
 437
 438   if (!n)
 439     return NULL;
 440
 441   while (n->left)
 442     n = n->left;
 443
 444   return n;
 445 }
 446
 447 /* Return the immediate predecessor KEY, or NULL if there is no
 448    predecessor.  KEY need not be present in the tree.  */
 449
 450 splay_tree_node
 451 splay_tree_predecessor (sp, key)
 452      splay_tree sp;
 453      splay_tree_key key;
 454 {
 455   int comparison;
 456   splay_tree_node node;
 457
 458   /* If the tree is empty, there is certainly no predecessor.  */
 459   if (!sp->root)
 460     return NULL;
 461
 462   /* Splay the tree around KEY.  That will leave either the KEY
 463      itself, its predecessor, or its successor at the root.  */
 464   splay_tree_splay (sp, key);
 465   comparison = compare_uintptr_t (sp->root->key, key);
 466
 467   /* If the predecessor is at the root, just return it.  */
 468   if (comparison < 0)
 469     return sp->root;
 470
 471   /* Otherwise, find the rightmost element of the left subtree.  */
 472   node = sp->root->left;
 473   if (node)
 474     while (node->right)
 475       node = node->right;
 476
 477   return node;
 478 }
 479
 480 /* Return the immediate successor KEY, or NULL if there is no
 481    successor.  KEY need not be present in the tree.  */
 482
 483 splay_tree_node
 484 splay_tree_successor (sp, key)
 485      splay_tree sp;
 486      splay_tree_key key;
 487 {
 488   int comparison;
 489   splay_tree_node node;
 490
 491   /* If the tree is empty, there is certainly no successor.  */
 492   if (!sp->root)
 493     return NULL;
 494
 495   /* Splay the tree around KEY.  That will leave either the KEY
 496      itself, its predecessor, or its successor at the root.  */
 497   splay_tree_splay (sp, key);
 498   comparison = compare_uintptr_t (sp->root->key, key);
 499
 500   /* If the successor is at the root, just return it.  */
 501   if (comparison > 0)
 502     return sp->root;
 503
 504   /* Otherwise, find the leftmost element of the right subtree.  */
 505   node = sp->root->right;
 506   if (node)
 507     while (node->left)
 508       node = node->left;
 509
 510   return node;
 511 }
 512
 513 /* Call FN, passing it the DATA, for every node in SP, following an
 514    in-order traversal.  If FN every returns a non-zero value, the
 515    iteration ceases immediately, and the value is returned.
 516    Otherwise, this function returns 0.  */
 517
 518 int
 519 splay_tree_foreach (sp, fn, data)
 520      splay_tree sp;
 521      splay_tree_foreach_fn fn;
 522      void *data;
 523 {
 524   return splay_tree_foreach_helper (sp, sp->root, fn, data);
 525 }