1 /* A splay-tree datatype. 2 Copyright (C) 1998, 1999, 2000, 2001, 2009, 3 2010, 2011 Free Software Foundation, Inc. 4 Contributed by Mark Mitchell (mark (at) markmitchell.com). 5 6 This file is part of GNU CC. 7 8 GNU CC 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 2, or (at your option) 11 any later version. 12 13 GNU CC is distributed in the hope that it will be useful, but 14 WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 16 General Public License for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with GNU CC; see the file COPYING. If not, write to 20 the Free Software Foundation, 51 Franklin Street - Fifth Floor, 21 Boston, MA 02110-1301, USA. */ 22 23 /* For an easily readable description of splay-trees, see: 24 25 Lewis, Harry R. and Denenberg, Larry. Data Structures and Their 26 Algorithms. Harper-Collins, Inc. 1991. */ 27 28 #ifdef HAVE_CONFIG_H 29 #include "config.h" 30 #endif 31 32 #ifdef HAVE_STDLIB_H 33 #include <stdlib.h> 34 #endif 35 36 #include <stdio.h> 37 38 #include "libiberty.h" 39 #include "splay-tree.h" 40 41 static void splay_tree_delete_helper (splay_tree, splay_tree_node); 42 static inline void rotate_left (splay_tree_node *, 43 splay_tree_node, splay_tree_node); 44 static inline void rotate_right (splay_tree_node *, 45 splay_tree_node, splay_tree_node); 46 static void splay_tree_splay (splay_tree, splay_tree_key); 47 static int splay_tree_foreach_helper (splay_tree_node, 48 splay_tree_foreach_fn, void*); 49 50 /* Deallocate NODE (a member of SP), and all its sub-trees. */ 51 52 static void 53 splay_tree_delete_helper (splay_tree sp, splay_tree_node node) 54 { 55 splay_tree_node pending = 0; 56 splay_tree_node active = 0; 57 58 if (!node) 59 return; 60 61 #define KDEL(x) if (sp->delete_key) (*sp->delete_key)(x); 62 #define VDEL(x) if (sp->delete_value) (*sp->delete_value)(x); 63 64 KDEL (node->key); 65 VDEL (node->value); 66 67 /* We use the "key" field to hold the "next" pointer. */ 68 node->key = (splay_tree_key)pending; 69 pending = (splay_tree_node)node; 70 71 /* Now, keep processing the pending list until there aren't any 72 more. This is a little more complicated than just recursing, but 73 it doesn't toast the stack for large trees. */ 74 75 while (pending) 76 { 77 active = pending; 78 pending = 0; 79 while (active) 80 { 81 splay_tree_node temp; 82 83 /* active points to a node which has its key and value 84 deallocated, we just need to process left and right. */ 85 86 if (active->left) 87 { 88 KDEL (active->left->key); 89 VDEL (active->left->value); 90 active->left->key = (splay_tree_key)pending; 91 pending = (splay_tree_node)(active->left); 92 } 93 if (active->right) 94 { 95 KDEL (active->right->key); 96 VDEL (active->right->value); 97 active->right->key = (splay_tree_key)pending; 98 pending = (splay_tree_node)(active->right); 99 } 100 101 temp = active; 102 active = (splay_tree_node)(temp->key); 103 (*sp->deallocate) ((char*) temp, sp->allocate_data); 104 } 105 } 106 #undef KDEL 107 #undef VDEL 108 } 109 110 /* Rotate the edge joining the left child N with its parent P. PP is the 111 grandparents' pointer to P. */ 112 113 static inline void 114 rotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n) 115 { 116 splay_tree_node tmp; 117 tmp = n->right; 118 n->right = p; 119 p->left = tmp; 120 *pp = n; 121 } 122 123 /* Rotate the edge joining the right child N with its parent P. PP is the 124 grandparents' pointer to P. */ 125 126 static inline void 127 rotate_right (splay_tree_node *pp, splay_tree_node p, splay_tree_node n) 128 { 129 splay_tree_node tmp; 130 tmp = n->left; 131 n->left = p; 132 p->right = tmp; 133 *pp = n; 134 } 135 136 /* Bottom up splay of key. */ 137 138 static void 139 splay_tree_splay (splay_tree sp, splay_tree_key key) 140 { 141 if (sp->root == 0) 142 return; 143 144 do { 145 int cmp1, cmp2; 146 splay_tree_node n, c; 147 148 n = sp->root; 149 cmp1 = (*sp->comp) (key, n->key); 150 151 /* Found. */ 152 if (cmp1 == 0) 153 return; 154 155 /* Left or right? If no child, then we're done. */ 156 if (cmp1 < 0) 157 c = n->left; 158 else 159 c = n->right; 160 if (!c) 161 return; 162 163 /* Next one left or right? If found or no child, we're done 164 after one rotation. */ 165 cmp2 = (*sp->comp) (key, c->key); 166 if (cmp2 == 0 167 || (cmp2 < 0 && !c->left) 168 || (cmp2 > 0 && !c->right)) 169 { 170 if (cmp1 < 0) 171 rotate_left (&sp->root, n, c); 172 else 173 rotate_right (&sp->root, n, c); 174 return; 175 } 176 177 /* Now we have the four cases of double-rotation. */ 178 if (cmp1 < 0 && cmp2 < 0) 179 { 180 rotate_left (&n->left, c, c->left); 181 rotate_left (&sp->root, n, n->left); 182 } 183 else if (cmp1 > 0 && cmp2 > 0) 184 { 185 rotate_right (&n->right, c, c->right); 186 rotate_right (&sp->root, n, n->right); 187 } 188 else if (cmp1 < 0 && cmp2 > 0) 189 { 190 rotate_right (&n->left, c, c->right); 191 rotate_left (&sp->root, n, n->left); 192 } 193 else if (cmp1 > 0 && cmp2 < 0) 194 { 195 rotate_left (&n->right, c, c->left); 196 rotate_right (&sp->root, n, n->right); 197 } 198 } while (1); 199 } 200 201 /* Call FN, passing it the DATA, for every node below NODE, all of 202 which are from SP, following an in-order traversal. If FN every 203 returns a non-zero value, the iteration ceases immediately, and the 204 value is returned. Otherwise, this function returns 0. */ 205 206 static int 207 splay_tree_foreach_helper (splay_tree_node node, 208 splay_tree_foreach_fn fn, void *data) 209 { 210 int val; 211 splay_tree_node *stack; 212 int stack_ptr, stack_size; 213 214 /* A non-recursive implementation is used to avoid filling the stack 215 for large trees. Splay trees are worst case O(n) in the depth of 216 the tree. */ 217 218 #define INITIAL_STACK_SIZE 100 219 stack_size = INITIAL_STACK_SIZE; 220 stack_ptr = 0; 221 stack = XNEWVEC (splay_tree_node, stack_size); 222 val = 0; 223 224 for (;;) 225 { 226 while (node != NULL) 227 { 228 if (stack_ptr == stack_size) 229 { 230 stack_size *= 2; 231 stack = XRESIZEVEC (splay_tree_node, stack, stack_size); 232 } 233 stack[stack_ptr++] = node; 234 node = node->left; 235 } 236 237 if (stack_ptr == 0) 238 break; 239 240 node = stack[--stack_ptr]; 241 242 val = (*fn) (node, data); 243 if (val) 244 break; 245 246 node = node->right; 247 } 248 249 XDELETEVEC (stack); 250 return val; 251 } 252 253 /* An allocator and deallocator based on xmalloc. */ 254 static void * 255 splay_tree_xmalloc_allocate (int size, void *data ATTRIBUTE_UNUSED) 256 { 257 return (void *) xmalloc (size); 258 } 259 260 static void 261 splay_tree_xmalloc_deallocate (void *object, void *data ATTRIBUTE_UNUSED) 262 { 263 free (object); 264 } 265 266 267 /* Allocate a new splay tree, using COMPARE_FN to compare nodes, 268 DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate 269 values. Use xmalloc to allocate the splay tree structure, and any 270 nodes added. */ 271 272 splay_tree 273 splay_tree_new (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 { 277 return (splay_tree_new_with_allocator 278 (compare_fn, delete_key_fn, delete_value_fn, 279 splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate, 0)); 280 } 281 282 283 /* Allocate a new splay tree, using COMPARE_FN to compare nodes, 284 DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate 285 values. */ 286 287 splay_tree 288 splay_tree_new_with_allocator (splay_tree_compare_fn compare_fn, 289 splay_tree_delete_key_fn delete_key_fn, 290 splay_tree_delete_value_fn delete_value_fn, 291 splay_tree_allocate_fn allocate_fn, 292 splay_tree_deallocate_fn deallocate_fn, 293 void *allocate_data) 294 { 295 return 296 splay_tree_new_typed_alloc (compare_fn, delete_key_fn, delete_value_fn, 297 allocate_fn, allocate_fn, deallocate_fn, 298 allocate_data); 299 } 300 301 /* 302 303 @deftypefn Supplemental splay_tree splay_tree_new_with_typed_alloc @ 304 (splay_tree_compare_fn @var{compare_fn}, @ 305 splay_tree_delete_key_fn @var{delete_key_fn}, @ 306 splay_tree_delete_value_fn @var{delete_value_fn}, @ 307 splay_tree_allocate_fn @var{tree_allocate_fn}, @ 308 splay_tree_allocate_fn @var{node_allocate_fn}, @ 309 splay_tree_deallocate_fn @var{deallocate_fn}, @ 310 void * @var{allocate_data}) 311 312 This function creates a splay tree that uses two different allocators 313 @var{tree_allocate_fn} and @var{node_allocate_fn} to use for allocating the 314 tree itself and its nodes respectively. This is useful when variables of 315 different types need to be allocated with different allocators. 316 317 The splay tree will use @var{compare_fn} to compare nodes, 318 @var{delete_key_fn} to deallocate keys, and @var{delete_value_fn} to 319 deallocate values. 320 321 @end deftypefn 322 323 */ 324 325 splay_tree 326 splay_tree_new_typed_alloc (splay_tree_compare_fn compare_fn, 327 splay_tree_delete_key_fn delete_key_fn, 328 splay_tree_delete_value_fn delete_value_fn, 329 splay_tree_allocate_fn tree_allocate_fn, 330 splay_tree_allocate_fn node_allocate_fn, 331 splay_tree_deallocate_fn deallocate_fn, 332 void * allocate_data) 333 { 334 splay_tree sp = (splay_tree) (*tree_allocate_fn) 335 (sizeof (struct splay_tree_s), allocate_data); 336 337 sp->root = 0; 338 sp->comp = compare_fn; 339 sp->delete_key = delete_key_fn; 340 sp->delete_value = delete_value_fn; 341 sp->allocate = node_allocate_fn; 342 sp->deallocate = deallocate_fn; 343 sp->allocate_data = allocate_data; 344 345 return sp; 346 } 347 348 /* Deallocate SP. */ 349 350 void 351 splay_tree_delete (splay_tree sp) 352 { 353 splay_tree_delete_helper (sp, sp->root); 354 (*sp->deallocate) ((char*) sp, sp->allocate_data); 355 } 356 357 /* Insert a new node (associating KEY with DATA) into SP. If a 358 previous node with the indicated KEY exists, its data is replaced 359 with the new value. Returns the new node. */ 360 361 splay_tree_node 362 splay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value) 363 { 364 int comparison = 0; 365 366 splay_tree_splay (sp, key); 367 368 if (sp->root) 369 comparison = (*sp->comp)(sp->root->key, key); 370 371 if (sp->root && comparison == 0) 372 { 373 /* If the root of the tree already has the indicated KEY, just 374 replace the value with VALUE. */ 375 if (sp->delete_value) 376 (*sp->delete_value)(sp->root->value); 377 sp->root->value = value; 378 } 379 else 380 { 381 /* Create a new node, and insert it at the root. */ 382 splay_tree_node node; 383 384 node = ((splay_tree_node) 385 (*sp->allocate) (sizeof (struct splay_tree_node_s), 386 sp->allocate_data)); 387 node->key = key; 388 node->value = value; 389 390 if (!sp->root) 391 node->left = node->right = 0; 392 else if (comparison < 0) 393 { 394 node->left = sp->root; 395 node->right = node->left->right; 396 node->left->right = 0; 397 } 398 else 399 { 400 node->right = sp->root; 401 node->left = node->right->left; 402 node->right->left = 0; 403 } 404 405 sp->root = node; 406 } 407 408 return sp->root; 409 } 410 411 /* Remove KEY from SP. It is not an error if it did not exist. */ 412 413 void 414 splay_tree_remove (splay_tree sp, splay_tree_key key) 415 { 416 splay_tree_splay (sp, key); 417 418 if (sp->root && (*sp->comp) (sp->root->key, key) == 0) 419 { 420 splay_tree_node left, right; 421 422 left = sp->root->left; 423 right = sp->root->right; 424 425 /* Delete the root node itself. */ 426 if (sp->delete_value) 427 (*sp->delete_value) (sp->root->value); 428 (*sp->deallocate) (sp->root, sp->allocate_data); 429 430 /* One of the children is now the root. Doesn't matter much 431 which, so long as we preserve the properties of the tree. */ 432 if (left) 433 { 434 sp->root = left; 435 436 /* If there was a right child as well, hang it off the 437 right-most leaf of the left child. */ 438 if (right) 439 { 440 while (left->right) 441 left = left->right; 442 left->right = right; 443 } 444 } 445 else 446 sp->root = right; 447 } 448 } 449 450 /* Lookup KEY in SP, returning VALUE if present, and NULL 451 otherwise. */ 452 453 splay_tree_node 454 splay_tree_lookup (splay_tree sp, splay_tree_key key) 455 { 456 splay_tree_splay (sp, key); 457 458 if (sp->root && (*sp->comp)(sp->root->key, key) == 0) 459 return sp->root; 460 else 461 return 0; 462 } 463 464 /* Return the node in SP with the greatest key. */ 465 466 splay_tree_node 467 splay_tree_max (splay_tree sp) 468 { 469 splay_tree_node n = sp->root; 470 471 if (!n) 472 return NULL; 473 474 while (n->right) 475 n = n->right; 476 477 return n; 478 } 479 480 /* Return the node in SP with the smallest key. */ 481 482 splay_tree_node 483 splay_tree_min (splay_tree sp) 484 { 485 splay_tree_node n = sp->root; 486 487 if (!n) 488 return NULL; 489 490 while (n->left) 491 n = n->left; 492 493 return n; 494 } 495 496 /* Return the immediate predecessor KEY, or NULL if there is no 497 predecessor. KEY need not be present in the tree. */ 498 499 splay_tree_node 500 splay_tree_predecessor (splay_tree sp, splay_tree_key key) 501 { 502 int comparison; 503 splay_tree_node node; 504 505 /* If the tree is empty, there is certainly no predecessor. */ 506 if (!sp->root) 507 return NULL; 508 509 /* Splay the tree around KEY. That will leave either the KEY 510 itself, its predecessor, or its successor at the root. */ 511 splay_tree_splay (sp, key); 512 comparison = (*sp->comp)(sp->root->key, key); 513 514 /* If the predecessor is at the root, just return it. */ 515 if (comparison < 0) 516 return sp->root; 517 518 /* Otherwise, find the rightmost element of the left subtree. */ 519 node = sp->root->left; 520 if (node) 521 while (node->right) 522 node = node->right; 523 524 return node; 525 } 526 527 /* Return the immediate successor KEY, or NULL if there is no 528 successor. KEY need not be present in the tree. */ 529 530 splay_tree_node 531 splay_tree_successor (splay_tree sp, splay_tree_key key) 532 { 533 int comparison; 534 splay_tree_node node; 535 536 /* If the tree is empty, there is certainly no successor. */ 537 if (!sp->root) 538 return NULL; 539 540 /* Splay the tree around KEY. That will leave either the KEY 541 itself, its predecessor, or its successor at the root. */ 542 splay_tree_splay (sp, key); 543 comparison = (*sp->comp)(sp->root->key, key); 544 545 /* If the successor is at the root, just return it. */ 546 if (comparison > 0) 547 return sp->root; 548 549 /* Otherwise, find the leftmost element of the right subtree. */ 550 node = sp->root->right; 551 if (node) 552 while (node->left) 553 node = node->left; 554 555 return node; 556 } 557 558 /* Call FN, passing it the DATA, for every node in SP, following an 559 in-order traversal. If FN every returns a non-zero value, the 560 iteration ceases immediately, and the value is returned. 561 Otherwise, this function returns 0. */ 562 563 int 564 splay_tree_foreach (splay_tree sp, splay_tree_foreach_fn fn, void *data) 565 { 566 return splay_tree_foreach_helper (sp->root, fn, data); 567 } 568 569 /* Splay-tree comparison function, treating the keys as ints. */ 570 571 int 572 splay_tree_compare_ints (splay_tree_key k1, splay_tree_key k2) 573 { 574 if ((int) k1 < (int) k2) 575 return -1; 576 else if ((int) k1 > (int) k2) 577 return 1; 578 else 579 return 0; 580 } 581 582 /* Splay-tree comparison function, treating the keys as pointers. */ 583 584 int 585 splay_tree_compare_pointers (splay_tree_key k1, splay_tree_key k2) 586 { 587 if ((char*) k1 < (char*) k2) 588 return -1; 589 else if ((char*) k1 > (char*) k2) 590 return 1; 591 else 592 return 0; 593 } 594
