1 /* Balanced binary trees using treaps. 2 Copyright (C) 2000-2019 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. 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 } 199