1/* Balanced binary trees using treaps. 2 Copyright (C) 2000-2015 Free Software Foundation, Inc. 3 Contributed by Andy Vaught 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 3, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along 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 43typedef struct gfc_treap 44{ 45 BBT_HEADER (gfc_treap); 46} 47gfc_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 53static int 54pseudo_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 65static gfc_bbt * 66rotate_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 80static gfc_bbt * 81rotate_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 96static gfc_bbt * 97insert (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 129void 130gfc_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 140static gfc_bbt * 141delete_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 170static gfc_bbt * 171delete_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 191void 192gfc_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