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