splay-tree.c revision 104834
1/* A splay-tree datatype. 2 Copyright (C) 1998, 1999, 2000, 2001 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 <stdio.h> 36 37#include "libiberty.h" 38#include "splay-tree.h" 39 40static void splay_tree_delete_helper PARAMS((splay_tree, 41 splay_tree_node)); 42static void splay_tree_splay PARAMS((splay_tree, 43 splay_tree_key)); 44static splay_tree_node splay_tree_splay_helper 45 PARAMS((splay_tree, 46 splay_tree_key, 47 splay_tree_node*, 48 splay_tree_node*, 49 splay_tree_node*)); 50static int splay_tree_foreach_helper PARAMS((splay_tree, 51 splay_tree_node, 52 splay_tree_foreach_fn, 53 void*)); 54 55/* Deallocate NODE (a member of SP), and all its sub-trees. */ 56 57static void 58splay_tree_delete_helper (sp, node) 59 splay_tree sp; 60 splay_tree_node node; 61{ 62 if (!node) 63 return; 64 65 splay_tree_delete_helper (sp, node->left); 66 splay_tree_delete_helper (sp, node->right); 67 68 if (sp->delete_key) 69 (*sp->delete_key)(node->key); 70 if (sp->delete_value) 71 (*sp->delete_value)(node->value); 72 73 (*sp->deallocate) ((char*) node, sp->allocate_data); 74} 75 76/* Help splay SP around KEY. PARENT and GRANDPARENT are the parent 77 and grandparent, respectively, of NODE. */ 78 79static splay_tree_node 80splay_tree_splay_helper (sp, key, node, parent, grandparent) 81 splay_tree sp; 82 splay_tree_key key; 83 splay_tree_node *node; 84 splay_tree_node *parent; 85 splay_tree_node *grandparent; 86{ 87 splay_tree_node *next; 88 splay_tree_node n; 89 int comparison; 90 91 n = *node; 92 93 if (!n) 94 return *parent; 95 96 comparison = (*sp->comp) (key, n->key); 97 98 if (comparison == 0) 99 /* We've found the target. */ 100 next = 0; 101 else if (comparison < 0) 102 /* The target is to the left. */ 103 next = &n->left; 104 else 105 /* The target is to the right. */ 106 next = &n->right; 107 108 if (next) 109 { 110 /* Continue down the tree. */ 111 n = splay_tree_splay_helper (sp, key, next, node, parent); 112 113 /* The recursive call will change the place to which NODE 114 points. */ 115 if (*node != n) 116 return n; 117 } 118 119 if (!parent) 120 /* NODE is the root. We are done. */ 121 return n; 122 123 /* First, handle the case where there is no grandparent (i.e., 124 *PARENT is the root of the tree.) */ 125 if (!grandparent) 126 { 127 if (n == (*parent)->left) 128 { 129 *node = n->right; 130 n->right = *parent; 131 } 132 else 133 { 134 *node = n->left; 135 n->left = *parent; 136 } 137 *parent = n; 138 return n; 139 } 140 141 /* Next handle the cases where both N and *PARENT are left children, 142 or where both are right children. */ 143 if (n == (*parent)->left && *parent == (*grandparent)->left) 144 { 145 splay_tree_node p = *parent; 146 147 (*grandparent)->left = p->right; 148 p->right = *grandparent; 149 p->left = n->right; 150 n->right = p; 151 *grandparent = n; 152 return n; 153 } 154 else if (n == (*parent)->right && *parent == (*grandparent)->right) 155 { 156 splay_tree_node p = *parent; 157 158 (*grandparent)->right = p->left; 159 p->left = *grandparent; 160 p->right = n->left; 161 n->left = p; 162 *grandparent = n; 163 return n; 164 } 165 166 /* Finally, deal with the case where N is a left child, but *PARENT 167 is a right child, or vice versa. */ 168 if (n == (*parent)->left) 169 { 170 (*parent)->left = n->right; 171 n->right = *parent; 172 (*grandparent)->right = n->left; 173 n->left = *grandparent; 174 *grandparent = n; 175 return n; 176 } 177 else 178 { 179 (*parent)->right = n->left; 180 n->left = *parent; 181 (*grandparent)->left = n->right; 182 n->right = *grandparent; 183 *grandparent = n; 184 return n; 185 } 186} 187 188/* Splay SP around KEY. */ 189 190static void 191splay_tree_splay (sp, key) 192 splay_tree sp; 193 splay_tree_key key; 194{ 195 if (sp->root == 0) 196 return; 197 198 splay_tree_splay_helper (sp, key, &sp->root, 199 /*grandparent=*/0, /*parent=*/0); 200} 201 202/* Call FN, passing it the DATA, for every node below NODE, all of 203 which are from SP, following an in-order traversal. If FN every 204 returns a non-zero value, the iteration ceases immediately, and the 205 value is returned. Otherwise, this function returns 0. */ 206 207static int 208splay_tree_foreach_helper (sp, node, fn, data) 209 splay_tree sp; 210 splay_tree_node node; 211 splay_tree_foreach_fn fn; 212 void* data; 213{ 214 int val; 215 216 if (!node) 217 return 0; 218 219 val = splay_tree_foreach_helper (sp, node->left, fn, data); 220 if (val) 221 return val; 222 223 val = (*fn)(node, data); 224 if (val) 225 return val; 226 227 return splay_tree_foreach_helper (sp, node->right, fn, data); 228} 229 230 231/* An allocator and deallocator based on xmalloc. */ 232static void * 233splay_tree_xmalloc_allocate (size, data) 234 int size; 235 void *data ATTRIBUTE_UNUSED; 236{ 237 return xmalloc (size); 238} 239 240static void 241splay_tree_xmalloc_deallocate (object, data) 242 void *object; 243 void *data ATTRIBUTE_UNUSED; 244{ 245 free (object); 246} 247 248 249/* Allocate a new splay tree, using COMPARE_FN to compare nodes, 250 DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate 251 values. Use xmalloc to allocate the splay tree structure, and any 252 nodes added. */ 253 254splay_tree 255splay_tree_new (compare_fn, delete_key_fn, delete_value_fn) 256 splay_tree_compare_fn compare_fn; 257 splay_tree_delete_key_fn delete_key_fn; 258 splay_tree_delete_value_fn delete_value_fn; 259{ 260 return (splay_tree_new_with_allocator 261 (compare_fn, delete_key_fn, delete_value_fn, 262 splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate, 0)); 263} 264 265 266/* Allocate a new splay tree, using COMPARE_FN to compare nodes, 267 DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate 268 values. */ 269 270splay_tree 271splay_tree_new_with_allocator (compare_fn, delete_key_fn, delete_value_fn, 272 allocate_fn, deallocate_fn, allocate_data) 273 splay_tree_compare_fn compare_fn; 274 splay_tree_delete_key_fn delete_key_fn; 275 splay_tree_delete_value_fn delete_value_fn; 276 splay_tree_allocate_fn allocate_fn; 277 splay_tree_deallocate_fn deallocate_fn; 278 void *allocate_data; 279{ 280 splay_tree sp = (splay_tree) (*allocate_fn) (sizeof (struct splay_tree_s), 281 allocate_data); 282 sp->root = 0; 283 sp->comp = compare_fn; 284 sp->delete_key = delete_key_fn; 285 sp->delete_value = delete_value_fn; 286 sp->allocate = allocate_fn; 287 sp->deallocate = deallocate_fn; 288 sp->allocate_data = allocate_data; 289 290 return sp; 291} 292 293/* Deallocate SP. */ 294 295void 296splay_tree_delete (sp) 297 splay_tree sp; 298{ 299 splay_tree_delete_helper (sp, sp->root); 300 (*sp->deallocate) ((char*) sp, sp->allocate_data); 301} 302 303/* Insert a new node (associating KEY with DATA) into SP. If a 304 previous node with the indicated KEY exists, its data is replaced 305 with the new value. Returns the new node. */ 306 307splay_tree_node 308splay_tree_insert (sp, key, value) 309 splay_tree sp; 310 splay_tree_key key; 311 splay_tree_value value; 312{ 313 int comparison = 0; 314 315 splay_tree_splay (sp, key); 316 317 if (sp->root) 318 comparison = (*sp->comp)(sp->root->key, key); 319 320 if (sp->root && comparison == 0) 321 { 322 /* If the root of the tree already has the indicated KEY, just 323 replace the value with VALUE. */ 324 if (sp->delete_value) 325 (*sp->delete_value)(sp->root->value); 326 sp->root->value = value; 327 } 328 else 329 { 330 /* Create a new node, and insert it at the root. */ 331 splay_tree_node node; 332 333 node = ((splay_tree_node) 334 (*sp->allocate) (sizeof (struct splay_tree_node_s), 335 sp->allocate_data)); 336 node->key = key; 337 node->value = value; 338 339 if (!sp->root) 340 node->left = node->right = 0; 341 else if (comparison < 0) 342 { 343 node->left = sp->root; 344 node->right = node->left->right; 345 node->left->right = 0; 346 } 347 else 348 { 349 node->right = sp->root; 350 node->left = node->right->left; 351 node->right->left = 0; 352 } 353 354 sp->root = node; 355 } 356 357 return sp->root; 358} 359 360/* Remove KEY from SP. It is not an error if it did not exist. */ 361 362void 363splay_tree_remove (sp, key) 364 splay_tree sp; 365 splay_tree_key key; 366{ 367 splay_tree_splay (sp, key); 368 369 if (sp->root && (*sp->comp) (sp->root->key, key) == 0) 370 { 371 splay_tree_node left, right; 372 373 left = sp->root->left; 374 right = sp->root->right; 375 376 /* Delete the root node itself. */ 377 if (sp->delete_value) 378 (*sp->delete_value) (sp->root->value); 379 (*sp->deallocate) (sp->root, sp->allocate_data); 380 381 /* One of the children is now the root. Doesn't matter much 382 which, so long as we preserve the properties of the tree. */ 383 if (left) 384 { 385 sp->root = left; 386 387 /* If there was a right child as well, hang it off the 388 right-most leaf of the left child. */ 389 if (right) 390 { 391 while (left->right) 392 left = left->right; 393 left->right = right; 394 } 395 } 396 else 397 sp->root = right; 398 } 399} 400 401/* Lookup KEY in SP, returning VALUE if present, and NULL 402 otherwise. */ 403 404splay_tree_node 405splay_tree_lookup (sp, key) 406 splay_tree sp; 407 splay_tree_key key; 408{ 409 splay_tree_splay (sp, key); 410 411 if (sp->root && (*sp->comp)(sp->root->key, key) == 0) 412 return sp->root; 413 else 414 return 0; 415} 416 417/* Return the node in SP with the greatest key. */ 418 419splay_tree_node 420splay_tree_max (sp) 421 splay_tree sp; 422{ 423 splay_tree_node n = sp->root; 424 425 if (!n) 426 return NULL; 427 428 while (n->right) 429 n = n->right; 430 431 return n; 432} 433 434/* Return the node in SP with the smallest key. */ 435 436splay_tree_node 437splay_tree_min (sp) 438 splay_tree sp; 439{ 440 splay_tree_node n = sp->root; 441 442 if (!n) 443 return NULL; 444 445 while (n->left) 446 n = n->left; 447 448 return n; 449} 450 451/* Return the immediate predecessor KEY, or NULL if there is no 452 predecessor. KEY need not be present in the tree. */ 453 454splay_tree_node 455splay_tree_predecessor (sp, key) 456 splay_tree sp; 457 splay_tree_key key; 458{ 459 int comparison; 460 splay_tree_node node; 461 462 /* If the tree is empty, there is certainly no predecessor. */ 463 if (!sp->root) 464 return NULL; 465 466 /* Splay the tree around KEY. That will leave either the KEY 467 itself, its predecessor, or its successor at the root. */ 468 splay_tree_splay (sp, key); 469 comparison = (*sp->comp)(sp->root->key, key); 470 471 /* If the predecessor is at the root, just return it. */ 472 if (comparison < 0) 473 return sp->root; 474 475 /* Otherwise, find the leftmost element of the right subtree. */ 476 node = sp->root->left; 477 if (node) 478 while (node->right) 479 node = node->right; 480 481 return node; 482} 483 484/* Return the immediate successor KEY, or NULL if there is no 485 predecessor. KEY need not be present in the tree. */ 486 487splay_tree_node 488splay_tree_successor (sp, key) 489 splay_tree sp; 490 splay_tree_key key; 491{ 492 int comparison; 493 splay_tree_node node; 494 495 /* If the tree is empty, there is certainly no predecessor. */ 496 if (!sp->root) 497 return NULL; 498 499 /* Splay the tree around KEY. That will leave either the KEY 500 itself, its predecessor, or its successor at the root. */ 501 splay_tree_splay (sp, key); 502 comparison = (*sp->comp)(sp->root->key, key); 503 504 /* If the successor is at the root, just return it. */ 505 if (comparison > 0) 506 return sp->root; 507 508 /* Otherwise, find the rightmost element of the left subtree. */ 509 node = sp->root->right; 510 if (node) 511 while (node->left) 512 node = node->left; 513 514 return node; 515} 516 517/* Call FN, passing it the DATA, for every node in SP, following an 518 in-order traversal. If FN every returns a non-zero value, the 519 iteration ceases immediately, and the value is returned. 520 Otherwise, this function returns 0. */ 521 522int 523splay_tree_foreach (sp, fn, data) 524 splay_tree sp; 525 splay_tree_foreach_fn fn; 526 void *data; 527{ 528 return splay_tree_foreach_helper (sp, sp->root, fn, data); 529} 530 531/* Splay-tree comparison function, treating the keys as ints. */ 532 533int 534splay_tree_compare_ints (k1, k2) 535 splay_tree_key k1; 536 splay_tree_key k2; 537{ 538 if ((int) k1 < (int) k2) 539 return -1; 540 else if ((int) k1 > (int) k2) 541 return 1; 542 else 543 return 0; 544} 545 546/* Splay-tree comparison function, treating the keys as pointers. */ 547 548int 549splay_tree_compare_pointers (k1, k2) 550 splay_tree_key k1; 551 splay_tree_key k2; 552{ 553 if ((char*) k1 < (char*) k2) 554 return -1; 555 else if ((char*) k1 > (char*) k2) 556 return 1; 557 else 558 return 0; 559} 560