splay-tree.c revision 60484
1/* A splay-tree datatype. 2 Copyright (C) 1998, 1999 Free Software Foundation, Inc. 3 Contributed by Mark Mitchell (mark@markmitchell.com). 4 5This file is part of GNU CC. 6 7GNU CC is free software; you can redistribute it and/or modify it 8under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 2, or (at your option) 10any later version. 11 12GNU CC is distributed in the hope that it will be useful, but 13WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along with GNU CC; see the file COPYING. If not, write to 19the Free Software Foundation, 59 Temple Place - Suite 330, 20Boston, MA 02111-1307, USA. */ 21 22/* For an easily readable description of splay-trees, see: 23 24 Lewis, Harry R. and Denenberg, Larry. Data Structures and Their 25 Algorithms. Harper-Collins, Inc. 1991. */ 26 27#ifdef HAVE_CONFIG_H 28#include "config.h" 29#endif 30 31#ifdef HAVE_STDLIB_H 32#include <stdlib.h> 33#endif 34 35#include "libiberty.h" 36#include "splay-tree.h" 37 38static void splay_tree_delete_helper PARAMS((splay_tree, 39 splay_tree_node)); 40static void splay_tree_splay PARAMS((splay_tree, 41 splay_tree_key)); 42static splay_tree_node splay_tree_splay_helper 43 PARAMS((splay_tree, 44 splay_tree_key, 45 splay_tree_node*, 46 splay_tree_node*, 47 splay_tree_node*)); 48static int splay_tree_foreach_helper PARAMS((splay_tree, 49 splay_tree_node, 50 splay_tree_foreach_fn, 51 void*)); 52 53/* Deallocate NODE (a member of SP), and all its sub-trees. */ 54 55static void 56splay_tree_delete_helper (sp, node) 57 splay_tree sp; 58 splay_tree_node node; 59{ 60 if (!node) 61 return; 62 63 splay_tree_delete_helper (sp, node->left); 64 splay_tree_delete_helper (sp, node->right); 65 66 if (sp->delete_key) 67 (*sp->delete_key)(node->key); 68 if (sp->delete_value) 69 (*sp->delete_value)(node->value); 70 71 free ((char*) node); 72} 73 74/* Help splay SP around KEY. PARENT and GRANDPARENT are the parent 75 and grandparent, respectively, of NODE. */ 76 77static splay_tree_node 78splay_tree_splay_helper (sp, key, node, parent, grandparent) 79 splay_tree sp; 80 splay_tree_key key; 81 splay_tree_node *node; 82 splay_tree_node *parent; 83 splay_tree_node *grandparent; 84{ 85 splay_tree_node *next; 86 splay_tree_node n; 87 int comparison; 88 89 n = *node; 90 91 if (!n) 92 return *parent; 93 94 comparison = (*sp->comp) (key, n->key); 95 96 if (comparison == 0) 97 /* We've found the target. */ 98 next = 0; 99 else if (comparison < 0) 100 /* The target is to the left. */ 101 next = &n->left; 102 else 103 /* The target is to the right. */ 104 next = &n->right; 105 106 if (next) 107 { 108 /* Continue down the tree. */ 109 n = splay_tree_splay_helper (sp, key, next, node, parent); 110 111 /* The recursive call will change the place to which NODE 112 points. */ 113 if (*node != n) 114 return n; 115 } 116 117 if (!parent) 118 /* NODE is the root. We are done. */ 119 return n; 120 121 /* First, handle the case where there is no grandparent (i.e., 122 *PARENT is the root of the tree.) */ 123 if (!grandparent) 124 { 125 if (n == (*parent)->left) 126 { 127 *node = n->right; 128 n->right = *parent; 129 } 130 else 131 { 132 *node = n->left; 133 n->left = *parent; 134 } 135 *parent = n; 136 return n; 137 } 138 139 /* Next handle the cases where both N and *PARENT are left children, 140 or where both are right children. */ 141 if (n == (*parent)->left && *parent == (*grandparent)->left) 142 { 143 splay_tree_node p = *parent; 144 145 (*grandparent)->left = p->right; 146 p->right = *grandparent; 147 p->left = n->right; 148 n->right = p; 149 *grandparent = n; 150 return n; 151 } 152 else if (n == (*parent)->right && *parent == (*grandparent)->right) 153 { 154 splay_tree_node p = *parent; 155 156 (*grandparent)->right = p->left; 157 p->left = *grandparent; 158 p->right = n->left; 159 n->left = p; 160 *grandparent = n; 161 return n; 162 } 163 164 /* Finally, deal with the case where N is a left child, but *PARENT 165 is a right child, or vice versa. */ 166 if (n == (*parent)->left) 167 { 168 (*parent)->left = n->right; 169 n->right = *parent; 170 (*grandparent)->right = n->left; 171 n->left = *grandparent; 172 *grandparent = n; 173 return n; 174 } 175 else 176 { 177 (*parent)->right = n->left; 178 n->left = *parent; 179 (*grandparent)->left = n->right; 180 n->right = *grandparent; 181 *grandparent = n; 182 return n; 183 } 184} 185 186/* Splay SP around KEY. */ 187 188static void 189splay_tree_splay (sp, key) 190 splay_tree sp; 191 splay_tree_key key; 192{ 193 if (sp->root == 0) 194 return; 195 196 splay_tree_splay_helper (sp, key, &sp->root, 197 /*grandparent=*/0, /*parent=*/0); 198} 199 200/* Call FN, passing it the DATA, for every node below NODE, all of 201 which are from SP, following an in-order traversal. If FN every 202 returns a non-zero value, the iteration ceases immediately, and the 203 value is returned. Otherwise, this function returns 0. */ 204 205static int 206splay_tree_foreach_helper (sp, node, fn, data) 207 splay_tree sp; 208 splay_tree_node node; 209 splay_tree_foreach_fn fn; 210 void* data; 211{ 212 int val; 213 214 if (!node) 215 return 0; 216 217 val = splay_tree_foreach_helper (sp, node->left, fn, data); 218 if (val) 219 return val; 220 221 val = (*fn)(node, data); 222 if (val) 223 return val; 224 225 return splay_tree_foreach_helper (sp, node->right, fn, data); 226} 227 228/* Allocate a new splay tree, using COMPARE_FN to compare nodes, 229 DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate 230 values. */ 231 232splay_tree 233splay_tree_new (compare_fn, delete_key_fn, delete_value_fn) 234 splay_tree_compare_fn compare_fn; 235 splay_tree_delete_key_fn delete_key_fn; 236 splay_tree_delete_value_fn delete_value_fn; 237{ 238 splay_tree sp = (splay_tree) xmalloc (sizeof (struct splay_tree_s)); 239 sp->root = 0; 240 sp->comp = compare_fn; 241 sp->delete_key = delete_key_fn; 242 sp->delete_value = delete_value_fn; 243 244 return sp; 245} 246 247/* Deallocate SP. */ 248 249void 250splay_tree_delete (sp) 251 splay_tree sp; 252{ 253 splay_tree_delete_helper (sp, sp->root); 254 free ((char*) sp); 255} 256 257/* Insert a new node (associating KEY with DATA) into SP. If a 258 previous node with the indicated KEY exists, its data is replaced 259 with the new value. Returns the new node. */ 260 261splay_tree_node 262splay_tree_insert (sp, key, value) 263 splay_tree sp; 264 splay_tree_key key; 265 splay_tree_value value; 266{ 267 int comparison = 0; 268 269 splay_tree_splay (sp, key); 270 271 if (sp->root) 272 comparison = (*sp->comp)(sp->root->key, key); 273 274 if (sp->root && comparison == 0) 275 { 276 /* If the root of the tree already has the indicated KEY, just 277 replace the value with VALUE. */ 278 if (sp->delete_value) 279 (*sp->delete_value)(sp->root->value); 280 sp->root->value = value; 281 } 282 else 283 { 284 /* Create a new node, and insert it at the root. */ 285 splay_tree_node node; 286 287 node = (splay_tree_node) xmalloc (sizeof (struct splay_tree_node_s)); 288 node->key = key; 289 node->value = value; 290 291 if (!sp->root) 292 node->left = node->right = 0; 293 else if (comparison < 0) 294 { 295 node->left = sp->root; 296 node->right = node->left->right; 297 node->left->right = 0; 298 } 299 else 300 { 301 node->right = sp->root; 302 node->left = node->right->left; 303 node->right->left = 0; 304 } 305 306 sp->root = node; 307 } 308 309 return sp->root; 310} 311 312/* Lookup KEY in SP, returning VALUE if present, and NULL 313 otherwise. */ 314 315splay_tree_node 316splay_tree_lookup (sp, key) 317 splay_tree sp; 318 splay_tree_key key; 319{ 320 splay_tree_splay (sp, key); 321 322 if (sp->root && (*sp->comp)(sp->root->key, key) == 0) 323 return sp->root; 324 else 325 return 0; 326} 327 328/* Call FN, passing it the DATA, for every node in SP, following an 329 in-order traversal. If FN every returns a non-zero value, the 330 iteration ceases immediately, and the value is returned. 331 Otherwise, this function returns 0. */ 332 333int 334splay_tree_foreach (sp, fn, data) 335 splay_tree sp; 336 splay_tree_foreach_fn fn; 337 void *data; 338{ 339 return splay_tree_foreach_helper (sp, sp->root, fn, data); 340} 341 342/* Splay-tree comparison function, treating the keys as ints. */ 343 344int 345splay_tree_compare_ints (k1, k2) 346 splay_tree_key k1; 347 splay_tree_key k2; 348{ 349 if ((int) k1 < (int) k2) 350 return -1; 351 else if ((int) k1 > (int) k2) 352 return 1; 353 else 354 return 0; 355} 356 357/* Splay-tree comparison function, treating the keys as pointers. */ 358 359int 360splay_tree_compare_pointers (k1, k2) 361 splay_tree_key k1; 362 splay_tree_key k2; 363{ 364 if ((char*) k1 < (char*) k2) 365 return -1; 366 else if ((char*) k1 > (char*) k2) 367 return 1; 368 else 369 return 0; 370} 371