gcc/fortran/bbt.cc

   1 /* Balanced binary trees using treaps.
   2    Copyright (C) 2000-2023 Free Software Foundation, Inc.
   3    Contributed by Andy Vaught
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 /* The idea is to balance the tree using pseudorandom numbers.  The
  22    main constraint on this implementation is that we have several
  23    distinct structures that have to be arranged in a binary tree.
  24    These structures all contain a BBT_HEADER() in front that gives the
  25    treap-related information.  The key and value are assumed to reside
  26    in the rest of the structure.
  27
  28    When calling, we are also passed a comparison function that
  29    compares two nodes.  We don't implement a separate 'find' function
  30    here, but rather use separate functions for each variety of tree.
  31    We are also restricted to not copy treap structures, which most
  32    implementations find convenient, because we otherwise would need to
  33    know how long the structure is.
  34
  35    This implementation is based on Stefan Nilsson's article in the
  36    July 1997 Doctor Dobb's Journal, "Treaps in Java".  */
  37
  38 #include "config.h"
  39 #include "system.h"
  40 #include "coretypes.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, returning the new root node of the tree.
 166    The OLD value does not necessarily have to point to the element to be
 167    deleted, it must just point to a treap structure with the key to be deleted.
 168    The REMOVED argument, if non-null, is set to the removed element from the
 169    tree upon return.  */
 170
 171 static gfc_bbt *
 172 delete_treap (gfc_bbt *old, gfc_bbt *t, compare_fn compare, gfc_bbt **removed)
 173 {
 174   int c;
 175
 176   if (t == nullptr)
 177     {
 178       if (removed)
 179         *removed = nullptr;
 180       return nullptr;
 181     }
 182
 183   c = (*compare) (old, t);
 184
 185   if (c < 0)
 186     t->left = delete_treap (old, t->left, compare, removed);
 187   if (c > 0)
 188     t->right = delete_treap (old, t->right, compare, removed);
 189   if (c == 0)
 190     {
 191       if (removed)
 192         *removed = t;
 193       t = delete_root (t);
 194     }
 195
 196   return t;
 197 }
 198
 199
 200 /* Delete the element from the tree at *ROOT that matches the OLD element
 201    according to the COMPARE_FN function.  This updates the *ROOT pointer to
 202    point to the new tree root (if different from the original) and returns the
 203    deleted element.  */
 204
 205 void *
 206 gfc_delete_bbt (void *root, void *old, compare_fn compare)
 207 {
 208   gfc_bbt **t;
 209   gfc_bbt *removed;
 210
 211   t = (gfc_bbt **) root;
 212   *t = delete_treap ((gfc_bbt *) old, *t, compare, &removed);
 213
 214   return (void *) removed;
 215 }