gcc/fortran/bbt.cc

   1 /* Balanced binary trees using treaps.
   2    Copyright (C) 2000-2024 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 #define INCLUDE_MEMORY
  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, returning the new root node of the tree.
 167    The OLD value does not necessarily have to point to the element to be
 168    deleted, it must just point to a treap structure with the key to be deleted.
 169    The REMOVED argument, if non-null, is set to the removed element from the
 170    tree upon return.  */
 171
 172 static gfc_bbt *
 173 delete_treap (gfc_bbt *old, gfc_bbt *t, compare_fn compare, gfc_bbt **removed)
 174 {
 175   int c;
 176
 177   if (t == nullptr)
 178     {
 179       if (removed)
 180         *removed = nullptr;
 181       return nullptr;
 182     }
 183
 184   c = (*compare) (old, t);
 185
 186   if (c < 0)
 187     t->left = delete_treap (old, t->left, compare, removed);
 188   if (c > 0)
 189     t->right = delete_treap (old, t->right, compare, removed);
 190   if (c == 0)
 191     {
 192       if (removed)
 193         *removed = t;
 194       t = delete_root (t);
 195     }
 196
 197   return t;
 198 }
 199
 200
 201 /* Delete the element from the tree at *ROOT that matches the OLD element
 202    according to the COMPARE_FN function.  This updates the *ROOT pointer to
 203    point to the new tree root (if different from the original) and returns the
 204    deleted element.  */
 205
 206 void *
 207 gfc_delete_bbt (void *root, void *old, compare_fn compare)
 208 {
 209   gfc_bbt **t;
 210   gfc_bbt *removed;
 211
 212   t = (gfc_bbt **) root;
 213   *t = delete_treap ((gfc_bbt *) old, *t, compare, &removed);
 214
 215   return (void *) removed;
 216 }