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