gcc/fortran/bbt.c

   1 /* Balanced binary trees using treaps.
   2    Copyright (C) 2000, 2002, 2003, 2007, 2008, 2010
   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 "system.h"
  41 #include "coretypes.h"
  42 #include "gfortran.h"
  43
  44 typedef struct gfc_treap
  45 {
  46   BBT_HEADER (gfc_treap);
  47 }
  48 gfc_bbt;
  49
  50 /* Simple linear congruential pseudorandom number generator.  The
  51    period of this generator is 44071, which is plenty for our
  52    purposes.  */
  53
  54 static int
  55 pseudo_random (void)
  56 {
  57   static int x0 = 5341;
  58
  59   x0 = (22611 * x0 + 10) % 44071;
  60   return x0;
  61 }
  62
  63
  64 /* Rotate the treap left.  */
  65
  66 static gfc_bbt *
  67 rotate_left (gfc_bbt *t)
  68 {
  69   gfc_bbt *temp;
  70
  71   temp = t->right;
  72   t->right = t->right->left;
  73   temp->left = t;
  74
  75   return temp;
  76 }
  77
  78
  79 /* Rotate the treap right.  */
  80
  81 static gfc_bbt *
  82 rotate_right (gfc_bbt *t)
  83 {
  84   gfc_bbt *temp;
  85
  86   temp = t->left;
  87   t->left = t->left->right;
  88   temp->right = t;
  89
  90   return temp;
  91 }
  92
  93
  94 /* Recursive insertion function.  Returns the updated treap, or
  95    aborts if we find a duplicate key.  */
  96
  97 static gfc_bbt *
  98 insert (gfc_bbt *new_bbt, gfc_bbt *t, compare_fn compare)
  99 {
 100   int c;
 101
 102   if (t == NULL)
 103     return new_bbt;
 104
 105   c = (*compare) (new_bbt, t);
 106
 107   if (c < 0)
 108     {
 109       t->left = insert (new_bbt, t->left, compare);
 110       if (t->priority < t->left->priority)
 111         t = rotate_right (t);
 112     }
 113   else if (c > 0)
 114     {
 115       t->right = insert (new_bbt, t->right, compare);
 116       if (t->priority < t->right->priority)
 117         t = rotate_left (t);
 118     }
 119   else /* if (c == 0)  */
 120     gfc_internal_error("insert_bbt(): Duplicate key found!");
 121
 122   return t;
 123 }
 124
 125
 126 /* Given root pointer, a new node and a comparison function, insert
 127    the new node into the treap.  It is an error to insert a key that
 128    already exists.  */
 129
 130 void
 131 gfc_insert_bbt (void *root, void *new_node, compare_fn compare)
 132 {
 133   gfc_bbt **r, *n;
 134
 135   r = (gfc_bbt **) root;
 136   n = (gfc_bbt *) new_node;
 137   n->priority = pseudo_random ();
 138   *r = insert (n, *r, compare);
 139 }
 140
 141 static gfc_bbt *
 142 delete_root (gfc_bbt *t)
 143 {
 144   gfc_bbt *temp;
 145
 146   if (t->left == NULL)
 147     return t->right;
 148   if (t->right == NULL)
 149     return t->left;
 150
 151   if (t->left->priority > t->right->priority)
 152     {
 153       temp = rotate_right (t);
 154       temp->right = delete_root (t);
 155     }
 156   else
 157     {
 158       temp = rotate_left (t);
 159       temp->left = delete_root (t);
 160     }
 161
 162   return temp;
 163 }
 164
 165
 166 /* Delete an element from a tree.  The 'old' value does not
 167    necessarily have to point to the element to be deleted, it must
 168    just point to a treap structure with the key to be deleted.
 169    Returns the new root node of the tree.  */
 170
 171 static gfc_bbt *
 172 delete_treap (gfc_bbt *old, gfc_bbt *t, compare_fn compare)
 173 {
 174   int c;
 175
 176   if (t == NULL)
 177     return NULL;
 178
 179   c = (*compare) (old, t);
 180
 181   if (c < 0)
 182     t->left = delete_treap (old, t->left, compare);
 183   if (c > 0)
 184     t->right = delete_treap (old, t->right, compare);
 185   if (c == 0)
 186     t = delete_root (t);
 187
 188   return t;
 189 }
 190
 191
 192 void
 193 gfc_delete_bbt (void *root, void *old, compare_fn compare)
 194 {
 195   gfc_bbt **t;
 196
 197   t = (gfc_bbt **) root;
 198   *t = delete_treap ((gfc_bbt *) old, *t, compare);
 199 }