128021Sjoerg/* A splay-tree datatype. 289736Sphantom Copyright (C) 1998-2020 Free Software Foundation, Inc. 328021Sjoerg Contributed by Mark Mitchell (mark@markmitchell.com). 428021Sjoerg 528021Sjoerg This file is part of the GNU Offloading and Multi Processing Library 628021Sjoerg (libgomp). 728021Sjoerg 828021Sjoerg Libgomp is free software; you can redistribute it and/or modify it 928021Sjoerg under the terms of the GNU General Public License as published by 1028021Sjoerg the Free Software Foundation; either version 3, or (at your option) 1128021Sjoerg any later version. 1228021Sjoerg 1328021Sjoerg Libgomp is distributed in the hope that it will be useful, but WITHOUT ANY 1428021Sjoerg WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 1528021Sjoerg FOR A PARTICULAR PURPOSE. See the GNU General Public License for 1628021Sjoerg more details. 1728021Sjoerg 1828021Sjoerg Under Section 7 of GPL version 3, you are granted additional 1928021Sjoerg permissions described in the GCC Runtime Library Exception, version 2028021Sjoerg 3.1, as published by the Free Software Foundation. 2128021Sjoerg 2228021Sjoerg You should have received a copy of the GNU General Public License and 2328021Sjoerg a copy of the GCC Runtime Library Exception along with this program; 2428021Sjoerg see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 2528021Sjoerg <http://www.gnu.org/licenses/>. */ 2650476Speter 2728021Sjoerg/* The splay tree code copied from include/splay-tree.h and adjusted, 2828021Sjoerg so that all the data lives directly in splay_tree_node_s structure 2989736Sphantom and no extra allocations are needed. */ 3089736Sphantom 3172167Sphantom/* For an easily readable description of splay-trees, see: 3228021Sjoerg 3328021Sjoerg Lewis, Harry R. and Denenberg, Larry. Data Structures and Their 3428021Sjoerg Algorithms. Harper-Collins, Inc. 1991. 3528021Sjoerg 3628021Sjoerg The major feature of splay trees is that all basic tree operations 3789736Sphantom are amortized O(log n) time for a tree with n nodes. */ 3889736Sphantom 3989736Sphantom#include "libgomp.h" 4089736Sphantom 4189736Sphantom/* Rotate the edge joining the left child N with its parent P. PP is the 4289736Sphantom grandparents' pointer to P. */ 4389736Sphantom 4489736Sphantomstatic inline void 4589736Sphantomrotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n) 4689736Sphantom{ 4789736Sphantom splay_tree_node tmp; 4889736Sphantom tmp = n->right; 4989736Sphantom n->right = p; 5028021Sjoerg p->left = tmp; 5128021Sjoerg *pp = n; 5289736Sphantom} 5389736Sphantom 5428021Sjoerg/* Rotate the edge joining the right child N with its parent P. PP is the 5589736Sphantom grandparents' pointer to P. */ 56 57static inline void 58rotate_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 69static void 70splay_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 134attribute_hidden void 135splay_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 170attribute_hidden void 171splay_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 205attribute_hidden splay_tree_key 206splay_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 220static void 221splay_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 234attribute_hidden void 235splay_tree_foreach (splay_tree sp, splay_tree_callback func, void *data) 236{ 237 splay_tree_foreach_internal (sp->root, func, data); 238} 239