1 /* A splay-tree datatype. 2 Copyright (C) 1998-2015 Free Software Foundation, Inc. 3 Contributed by Mark Mitchell (mark@markmitchell.com). 4 5 This file is part of the GNU Offloading and Multi Processing Library 6 (libgomp). 7 8 Libgomp is free software; you can redistribute it and/or modify it 9 under the terms of the GNU General Public License as published by 10 the Free Software Foundation; either version 3, or (at your option) 11 any later version. 12 13 Libgomp is distributed in the hope that it will be useful, but WITHOUT ANY 14 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 15 FOR A PARTICULAR PURPOSE. See the GNU General Public License for 16 more details. 17 18 Under Section 7 of GPL version 3, you are granted additional 19 permissions described in the GCC Runtime Library Exception, version 20 3.1, as published by the Free Software Foundation. 21 22 You should have received a copy of the GNU General Public License and 23 a copy of the GCC Runtime Library Exception along with this program; 24 see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 25 <http://www.gnu.org/licenses/>. */ 26 27 /* The splay tree code copied from include/splay-tree.h and adjusted, 28 so that all the data lives directly in splay_tree_node_s structure 29 and no extra allocations are needed. */ 30 31 /* For an easily readable description of splay-trees, see: 32 33 Lewis, Harry R. and Denenberg, Larry. Data Structures and Their 34 Algorithms. Harper-Collins, Inc. 1991. 35 36 The major feature of splay trees is that all basic tree operations 37 are amortized O(log n) time for a tree with n nodes. */ 38 39 #include "libgomp.h" 40 #include "splay-tree.h" 41 42 extern int splay_compare (splay_tree_key, splay_tree_key); 43 44 /* Rotate the edge joining the left child N with its parent P. PP is the 45 grandparents' pointer to P. */ 46 47 static inline void 48 rotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n) 49 { 50 splay_tree_node tmp; 51 tmp = n->right; 52 n->right = p; 53 p->left = tmp; 54 *pp = n; 55 } 56 57 /* Rotate the edge joining the right child N with its parent P. PP is the 58 grandparents' pointer to P. */ 59 60 static inline void 61 rotate_right (splay_tree_node *pp, splay_tree_node p, splay_tree_node n) 62 { 63 splay_tree_node tmp; 64 tmp = n->left; 65 n->left = p; 66 p->right = tmp; 67 *pp = n; 68 } 69 70 /* Bottom up splay of KEY. */ 71 72 static void 73 splay_tree_splay (splay_tree sp, splay_tree_key key) 74 { 75 if (sp->root == NULL) 76 return; 77 78 do { 79 int cmp1, cmp2; 80 splay_tree_node n, c; 81 82 n = sp->root; 83 cmp1 = splay_compare (key, &n->key); 84 85 /* Found. */ 86 if (cmp1 == 0) 87 return; 88 89 /* Left or right? If no child, then we're done. */ 90 if (cmp1 < 0) 91 c = n->left; 92 else 93 c = n->right; 94 if (!c) 95 return; 96 97 /* Next one left or right? If found or no child, we're done 98 after one rotation. */ 99 cmp2 = splay_compare (key, &c->key); 100 if (cmp2 == 0 101 || (cmp2 < 0 && !c->left) 102 || (cmp2 > 0 && !c->right)) 103 { 104 if (cmp1 < 0) 105 rotate_left (&sp->root, n, c); 106 else 107 rotate_right (&sp->root, n, c); 108 return; 109 } 110 111 /* Now we have the four cases of double-rotation. */ 112 if (cmp1 < 0 && cmp2 < 0) 113 { 114 rotate_left (&n->left, c, c->left); 115 rotate_left (&sp->root, n, n->left); 116 } 117 else if (cmp1 > 0 && cmp2 > 0) 118 { 119 rotate_right (&n->right, c, c->right); 120 rotate_right (&sp->root, n, n->right); 121 } 122 else if (cmp1 < 0 && cmp2 > 0) 123 { 124 rotate_right (&n->left, c, c->right); 125 rotate_left (&sp->root, n, n->left); 126 } 127 else if (cmp1 > 0 && cmp2 < 0) 128 { 129 rotate_left (&n->right, c, c->left); 130 rotate_right (&sp->root, n, n->right); 131 } 132 } while (1); 133 } 134 135 /* Insert a new NODE into SP. The NODE shouldn't exist in the tree. */ 136 137 attribute_hidden void 138 splay_tree_insert (splay_tree sp, splay_tree_node node) 139 { 140 int comparison = 0; 141 142 splay_tree_splay (sp, &node->key); 143 144 if (sp->root) 145 comparison = splay_compare (&sp->root->key, &node->key); 146 147 if (sp->root && comparison == 0) 148 gomp_fatal ("Duplicate node"); 149 else 150 { 151 /* Insert it at the root. */ 152 if (sp->root == NULL) 153 node->left = node->right = NULL; 154 else if (comparison < 0) 155 { 156 node->left = sp->root; 157 node->right = node->left->right; 158 node->left->right = NULL; 159 } 160 else 161 { 162 node->right = sp->root; 163 node->left = node->right->left; 164 node->right->left = NULL; 165 } 166 167 sp->root = node; 168 } 169 } 170 171 /* Remove node with KEY from SP. It is not an error if it did not exist. */ 172 173 attribute_hidden void 174 splay_tree_remove (splay_tree sp, splay_tree_key key) 175 { 176 splay_tree_splay (sp, key); 177 178 if (sp->root && splay_compare (&sp->root->key, key) == 0) 179 { 180 splay_tree_node left, right; 181 182 left = sp->root->left; 183 right = sp->root->right; 184 185 /* One of the children is now the root. Doesn't matter much 186 which, so long as we preserve the properties of the tree. */ 187 if (left) 188 { 189 sp->root = left; 190 191 /* If there was a right child as well, hang it off the 192 right-most leaf of the left child. */ 193 if (right) 194 { 195 while (left->right) 196 left = left->right; 197 left->right = right; 198 } 199 } 200 else 201 sp->root = right; 202 } 203 } 204 205 /* Lookup KEY in SP, returning NODE if present, and NULL 206 otherwise. */ 207 208 attribute_hidden splay_tree_key 209 splay_tree_lookup (splay_tree sp, splay_tree_key key) 210 { 211 splay_tree_splay (sp, key); 212 213 if (sp->root && splay_compare (&sp->root->key, key) == 0) 214 return &sp->root->key; 215 else 216 return NULL; 217 } 218