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