1 /* A splay-tree datatype. 2 Copyright (C) 1998-2018 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 41 /* Rotate the edge joining the left child N with its parent P. PP is the 42 grandparents' pointer to P. */ 43 44 static inline void 45 rotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n) 46 { 47 splay_tree_node tmp; 48 tmp = n->right; 49 n->right = p; 50 p->left = tmp; 51 *pp = n; 52 } 53 54 /* Rotate the edge joining the right child N with its parent P. PP is the 55 grandparents' pointer to P. */ 56 57 static inline void 58 rotate_right (splay_tree_node *pp, splay_tree_node p, splay_tree_node n) 59 { 60 splay_tree_node tmp; 61 tmp = n->left; 62 n->left = p; 63 p->right = tmp; 64 *pp = n; 65 } 66 67 /* Bottom up splay of KEY. */ 68 69 static void 70 splay_tree_splay (splay_tree sp, splay_tree_key key) 71 { 72 if (sp->root == NULL) 73 return; 74 75 do { 76 int cmp1, cmp2; 77 splay_tree_node n, c; 78 79 n = sp->root; 80 cmp1 = splay_compare (key, &n->key); 81 82 /* Found. */ 83 if (cmp1 == 0) 84 return; 85 86 /* Left or right? If no child, then we're done. */ 87 if (cmp1 < 0) 88 c = n->left; 89 else 90 c = n->right; 91 if (!c) 92 return; 93 94 /* Next one left or right? If found or no child, we're done 95 after one rotation. */ 96 cmp2 = splay_compare (key, &c->key); 97 if (cmp2 == 0 98 || (cmp2 < 0 && !c->left) 99 || (cmp2 > 0 && !c->right)) 100 { 101 if (cmp1 < 0) 102 rotate_left (&sp->root, n, c); 103 else 104 rotate_right (&sp->root, n, c); 105 return; 106 } 107 108 /* Now we have the four cases of double-rotation. */ 109 if (cmp1 < 0 && cmp2 < 0) 110 { 111 rotate_left (&n->left, c, c->left); 112 rotate_left (&sp->root, n, n->left); 113 } 114 else if (cmp1 > 0 && cmp2 > 0) 115 { 116 rotate_right (&n->right, c, c->right); 117 rotate_right (&sp->root, n, n->right); 118 } 119 else if (cmp1 < 0 && cmp2 > 0) 120 { 121 rotate_right (&n->left, c, c->right); 122 rotate_left (&sp->root, n, n->left); 123 } 124 else if (cmp1 > 0 && cmp2 < 0) 125 { 126 rotate_left (&n->right, c, c->left); 127 rotate_right (&sp->root, n, n->right); 128 } 129 } while (1); 130 } 131 132 /* Insert a new NODE into SP. The NODE shouldn't exist in the tree. */ 133 134 attribute_hidden void 135 splay_tree_insert (splay_tree sp, splay_tree_node node) 136 { 137 int comparison = 0; 138 139 splay_tree_splay (sp, &node->key); 140 141 if (sp->root) 142 comparison = splay_compare (&sp->root->key, &node->key); 143 144 if (sp->root && comparison == 0) 145 gomp_fatal ("Duplicate node"); 146 else 147 { 148 /* Insert it at the root. */ 149 if (sp->root == NULL) 150 node->left = node->right = NULL; 151 else if (comparison < 0) 152 { 153 node->left = sp->root; 154 node->right = node->left->right; 155 node->left->right = NULL; 156 } 157 else 158 { 159 node->right = sp->root; 160 node->left = node->right->left; 161 node->right->left = NULL; 162 } 163 164 sp->root = node; 165 } 166 } 167 168 /* Remove node with KEY from SP. It is not an error if it did not exist. */ 169 170 attribute_hidden void 171 splay_tree_remove (splay_tree sp, splay_tree_key key) 172 { 173 splay_tree_splay (sp, key); 174 175 if (sp->root && splay_compare (&sp->root->key, key) == 0) 176 { 177 splay_tree_node left, right; 178 179 left = sp->root->left; 180 right = sp->root->right; 181 182 /* One of the children is now the root. Doesn't matter much 183 which, so long as we preserve the properties of the tree. */ 184 if (left) 185 { 186 sp->root = left; 187 188 /* If there was a right child as well, hang it off the 189 right-most leaf of the left child. */ 190 if (right) 191 { 192 while (left->right) 193 left = left->right; 194 left->right = right; 195 } 196 } 197 else 198 sp->root = right; 199 } 200 } 201 202 /* Lookup KEY in SP, returning NODE if present, and NULL 203 otherwise. */ 204 205 attribute_hidden splay_tree_key 206 splay_tree_lookup (splay_tree sp, splay_tree_key key) 207 { 208 splay_tree_splay (sp, key); 209 210 if (sp->root && splay_compare (&sp->root->key, key) == 0) 211 return &sp->root->key; 212 else 213 return NULL; 214 } 215 216 /* Helper function for splay_tree_foreach. 217 218 Run FUNC on every node in KEY. */ 219 220 static void 221 splay_tree_foreach_internal (splay_tree_node node, splay_tree_callback func, 222 void *data) 223 { 224 if (!node) 225 return; 226 func (&node->key, data); 227 splay_tree_foreach_internal (node->left, func, data); 228 /* Yeah, whatever. GCC can fix my tail recursion. */ 229 splay_tree_foreach_internal (node->right, func, data); 230 } 231 232 /* Run FUNC on each of the nodes in SP. */ 233 234 attribute_hidden void 235 splay_tree_foreach (splay_tree sp, splay_tree_callback func, void *data) 236 { 237 splay_tree_foreach_internal (sp->root, func, data); 238 } 239