gcc/fortran/bbt.c

   1 /* Balanced binary trees using treaps.
   2    Copyright (C) 2000, 2002, 2003, 2007, 2008
   3    Free Software Foundation, Inc.
   4    Contributed by Andy Vaught
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 /* The idea is to balance the tree using pseudorandom numbers.  The
  23    main constraint on this implementation is that we have several
  24    distinct structures that have to be arranged in a binary tree.
  25    These structures all contain a BBT_HEADER() in front that gives the
  26    treap-related information.  The key and value are assumed to reside
  27    in the rest of the structure.
  28
  29    When calling, we are also passed a comparison function that
  30    compares two nodes.  We don't implement a separate 'find' function
  31    here, but rather use separate functions for each variety of tree.
  32    We are also restricted to not copy treap structures, which most
  33    implementations find convenient, because we otherwise would need to
  34    know how long the structure is.
  35
  36    This implementation is based on Stefan Nilsson's article in the
  37    July 1997 Doctor Dobb's Journal, "Treaps in Java".  */
  38
  39 #include "config.h"
  40 #include "gfortran.h"
  41
  42 typedef struct gfc_treap
  43 {
  44   BBT_HEADER (gfc_treap);
  45 }
  46 gfc_bbt;
  47
  48 /* Simple linear congruential pseudorandom number generator.  The
  49    period of this generator is 44071, which is plenty for our
  50    purposes.  */
  51
  52 static int
  53 pseudo_random (void)
  54 {
  55   static int x0 = 5341;
  56
  57   x0 = (22611 * x0 + 10) % 44071;
  58   return x0;
  59 }
  60
  61
  62 /* Rotate the treap left.  */
  63
  64 static gfc_bbt *
  65 rotate_left (gfc_bbt *t)
  66 {
  67   gfc_bbt *temp;
  68
  69   temp = t->right;
  70   t->right = t->right->left;
  71   temp->left = t;
  72
  73   return temp;
  74 }
  75
  76
  77 /* Rotate the treap right.  */
  78
  79 static gfc_bbt *
  80 rotate_right (gfc_bbt *t)
  81 {
  82   gfc_bbt *temp;
  83
  84   temp = t->left;
  85   t->left = t->left->right;
  86   temp->right = t;
  87
  88   return temp;
  89 }
  90
  91
  92 /* Recursive insertion function.  Returns the updated treap, or
  93    aborts if we find a duplicate key.  */
  94
  95 static gfc_bbt *
  96 insert (gfc_bbt *new_bbt, gfc_bbt *t, compare_fn compare)
  97 {
  98   int c;
  99
 100   if (t == NULL)
 101     return new_bbt;
 102
 103   c = (*compare) (new_bbt, t);
 104
 105   if (c < 0)
 106     {
 107       t->left = insert (new_bbt, t->left, compare);
 108       if (t->priority < t->left->priority)
 109         t = rotate_right (t);
 110     }
 111   else if (c > 0)
 112     {
 113       t->right = insert (new_bbt, t->right, compare);
 114       if (t->priority < t->right->priority)
 115         t = rotate_left (t);
 116     }
 117   else /* if (c == 0)  */
 118     gfc_internal_error("insert_bbt(): Duplicate key found!");
 119
 120   return t;
 121 }
 122
 123
 124 /* Given root pointer, a new node and a comparison function, insert
 125    the new node into the treap.  It is an error to insert a key that
 126    already exists.  */
 127
 128 void
 129 gfc_insert_bbt (void *root, void *new_node, compare_fn compare)
 130 {
 131   gfc_bbt **r, *n;
 132
 133   r = (gfc_bbt **) root;
 134   n = (gfc_bbt *) new_node;
 135   n->priority = pseudo_random ();
 136   *r = insert (n, *r, compare);
 137 }
 138
 139 static gfc_bbt *
 140 delete_root (gfc_bbt *t)
 141 {
 142   gfc_bbt *temp;
 143
 144   if (t->left == NULL)
 145     return t->right;
 146   if (t->right == NULL)
 147     return t->left;
 148
 149   if (t->left->priority > t->right->priority)
 150     {
 151       temp = rotate_right (t);
 152       temp->right = delete_root (t);
 153     }
 154   else
 155     {
 156       temp = rotate_left (t);
 157       temp->left = delete_root (t);
 158     }
 159
 160   return temp;
 161 }
 162
 163
 164 /* Delete an element from a tree.  The 'old' value does not
 165    necessarily have to point to the element to be deleted, it must
 166    just point to a treap structure with the key to be deleted.
 167    Returns the new root node of the tree.  */
 168
 169 static gfc_bbt *
 170 delete_treap (gfc_bbt *old, gfc_bbt *t, compare_fn compare)
 171 {
 172   int c;
 173
 174   if (t == NULL)
 175     return NULL;
 176
 177   c = (*compare) (old, t);
 178
 179   if (c < 0)
 180     t->left = delete_treap (old, t->left, compare);
 181   if (c > 0)
 182     t->right = delete_treap (old, t->right, compare);
 183   if (c == 0)
 184     t = delete_root (t);
 185
 186   return t;
 187 }
 188
 189
 190 void
 191 gfc_delete_bbt (void *root, void *old, compare_fn compare)
 192 {
 193   gfc_bbt **t;
 194
 195   t = (gfc_bbt **) root;
 196   *t = delete_treap ((gfc_bbt *) old, *t, compare);
 197 }