1 /* A splay-tree datatype. 2 Copyright (C) 1998, 1999, 2000, 2001, 2009, 3 2010 Free Software Foundation, Inc. 4 Contributed by Mark Mitchell (mark@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, 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 sp, splay_tree_node node, 208 splay_tree_foreach_fn fn, void *data) 209 { 210 int val; 211 212 if (!node) 213 return 0; 214 215 val = splay_tree_foreach_helper (sp, node->left, fn, data); 216 if (val) 217 return val; 218 219 val = (*fn)(node, data); 220 if (val) 221 return val; 222 223 return splay_tree_foreach_helper (sp, node->right, fn, data); 224 } 225 226 227 /* An allocator and deallocator based on xmalloc. */ 228 static void * 229 splay_tree_xmalloc_allocate (int size, void *data ATTRIBUTE_UNUSED) 230 { 231 return (void *) xmalloc (size); 232 } 233 234 static void 235 splay_tree_xmalloc_deallocate (void *object, void *data ATTRIBUTE_UNUSED) 236 { 237 free (object); 238 } 239 240 241 /* Allocate a new splay tree, using COMPARE_FN to compare nodes, 242 DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate 243 values. Use xmalloc to allocate the splay tree structure, and any 244 nodes added. */ 245 246 splay_tree 247 splay_tree_new (splay_tree_compare_fn compare_fn, 248 splay_tree_delete_key_fn delete_key_fn, 249 splay_tree_delete_value_fn delete_value_fn) 250 { 251 return (splay_tree_new_with_allocator 252 (compare_fn, delete_key_fn, delete_value_fn, 253 splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate, 0)); 254 } 255 256 257 /* Allocate a new splay tree, using COMPARE_FN to compare nodes, 258 DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate 259 values. */ 260 261 splay_tree 262 splay_tree_new_with_allocator (splay_tree_compare_fn compare_fn, 263 splay_tree_delete_key_fn delete_key_fn, 264 splay_tree_delete_value_fn delete_value_fn, 265 splay_tree_allocate_fn allocate_fn, 266 splay_tree_deallocate_fn deallocate_fn, 267 void *allocate_data) 268 { 269 return 270 splay_tree_new_typed_alloc (compare_fn, delete_key_fn, delete_value_fn, 271 allocate_fn, allocate_fn, deallocate_fn, 272 allocate_data); 273 } 274 275 /* 276 277 @deftypefn Supplemental splay_tree splay_tree_new_with_typed_alloc 278 (splay_tree_compare_fn @var{compare_fn}, 279 splay_tree_delete_key_fn @var{delete_key_fn}, 280 splay_tree_delete_value_fn @var{delete_value_fn}, 281 splay_tree_allocate_fn @var{tree_allocate_fn}, 282 splay_tree_allocate_fn @var{node_allocate_fn}, 283 splay_tree_deallocate_fn @var{deallocate_fn}, 284 void * @var{allocate_data}) 285 286 This function creates a splay tree that uses two different allocators 287 @var{tree_allocate_fn} and @var{node_allocate_fn} to use for allocating the 288 tree itself and its nodes respectively. This is useful when variables of 289 different types need to be allocated with different allocators. 290 291 The splay tree will use @var{compare_fn} to compare nodes, 292 @var{delete_key_fn} to deallocate keys, and @var{delete_value_fn} to 293 deallocate values. 294 295 @end deftypefn 296 297 */ 298 299 splay_tree 300 splay_tree_new_typed_alloc (splay_tree_compare_fn compare_fn, 301 splay_tree_delete_key_fn delete_key_fn, 302 splay_tree_delete_value_fn delete_value_fn, 303 splay_tree_allocate_fn tree_allocate_fn, 304 splay_tree_allocate_fn node_allocate_fn, 305 splay_tree_deallocate_fn deallocate_fn, 306 void * allocate_data) 307 { 308 splay_tree sp = (splay_tree) (*tree_allocate_fn) 309 (sizeof (struct splay_tree_s), allocate_data); 310 311 sp->root = 0; 312 sp->comp = compare_fn; 313 sp->delete_key = delete_key_fn; 314 sp->delete_value = delete_value_fn; 315 sp->allocate = node_allocate_fn; 316 sp->deallocate = deallocate_fn; 317 sp->allocate_data = allocate_data; 318 319 return sp; 320 } 321 322 /* Deallocate SP. */ 323 324 void 325 splay_tree_delete (splay_tree sp) 326 { 327 splay_tree_delete_helper (sp, sp->root); 328 (*sp->deallocate) ((char*) sp, sp->allocate_data); 329 } 330 331 /* Insert a new node (associating KEY with DATA) into SP. If a 332 previous node with the indicated KEY exists, its data is replaced 333 with the new value. Returns the new node. */ 334 335 splay_tree_node 336 splay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value) 337 { 338 int comparison = 0; 339 340 splay_tree_splay (sp, key); 341 342 if (sp->root) 343 comparison = (*sp->comp)(sp->root->key, key); 344 345 if (sp->root && comparison == 0) 346 { 347 /* If the root of the tree already has the indicated KEY, just 348 replace the value with VALUE. */ 349 if (sp->delete_value) 350 (*sp->delete_value)(sp->root->value); 351 sp->root->value = value; 352 } 353 else 354 { 355 /* Create a new node, and insert it at the root. */ 356 splay_tree_node node; 357 358 node = ((splay_tree_node) 359 (*sp->allocate) (sizeof (struct splay_tree_node_s), 360 sp->allocate_data)); 361 node->key = key; 362 node->value = value; 363 364 if (!sp->root) 365 node->left = node->right = 0; 366 else if (comparison < 0) 367 { 368 node->left = sp->root; 369 node->right = node->left->right; 370 node->left->right = 0; 371 } 372 else 373 { 374 node->right = sp->root; 375 node->left = node->right->left; 376 node->right->left = 0; 377 } 378 379 sp->root = node; 380 } 381 382 return sp->root; 383 } 384 385 /* Remove KEY from SP. It is not an error if it did not exist. */ 386 387 void 388 splay_tree_remove (splay_tree sp, splay_tree_key key) 389 { 390 splay_tree_splay (sp, key); 391 392 if (sp->root && (*sp->comp) (sp->root->key, key) == 0) 393 { 394 splay_tree_node left, right; 395 396 left = sp->root->left; 397 right = sp->root->right; 398 399 /* Delete the root node itself. */ 400 if (sp->delete_value) 401 (*sp->delete_value) (sp->root->value); 402 (*sp->deallocate) (sp->root, sp->allocate_data); 403 404 /* One of the children is now the root. Doesn't matter much 405 which, so long as we preserve the properties of the tree. */ 406 if (left) 407 { 408 sp->root = left; 409 410 /* If there was a right child as well, hang it off the 411 right-most leaf of the left child. */ 412 if (right) 413 { 414 while (left->right) 415 left = left->right; 416 left->right = right; 417 } 418 } 419 else 420 sp->root = right; 421 } 422 } 423 424 /* Lookup KEY in SP, returning VALUE if present, and NULL 425 otherwise. */ 426 427 splay_tree_node 428 splay_tree_lookup (splay_tree sp, splay_tree_key key) 429 { 430 splay_tree_splay (sp, key); 431 432 if (sp->root && (*sp->comp)(sp->root->key, key) == 0) 433 return sp->root; 434 else 435 return 0; 436 } 437 438 /* Return the node in SP with the greatest key. */ 439 440 splay_tree_node 441 splay_tree_max (splay_tree sp) 442 { 443 splay_tree_node n = sp->root; 444 445 if (!n) 446 return NULL; 447 448 while (n->right) 449 n = n->right; 450 451 return n; 452 } 453 454 /* Return the node in SP with the smallest key. */ 455 456 splay_tree_node 457 splay_tree_min (splay_tree sp) 458 { 459 splay_tree_node n = sp->root; 460 461 if (!n) 462 return NULL; 463 464 while (n->left) 465 n = n->left; 466 467 return n; 468 } 469 470 /* Return the immediate predecessor KEY, or NULL if there is no 471 predecessor. KEY need not be present in the tree. */ 472 473 splay_tree_node 474 splay_tree_predecessor (splay_tree sp, splay_tree_key key) 475 { 476 int comparison; 477 splay_tree_node node; 478 479 /* If the tree is empty, there is certainly no predecessor. */ 480 if (!sp->root) 481 return NULL; 482 483 /* Splay the tree around KEY. That will leave either the KEY 484 itself, its predecessor, or its successor at the root. */ 485 splay_tree_splay (sp, key); 486 comparison = (*sp->comp)(sp->root->key, key); 487 488 /* If the predecessor is at the root, just return it. */ 489 if (comparison < 0) 490 return sp->root; 491 492 /* Otherwise, find the rightmost element of the left subtree. */ 493 node = sp->root->left; 494 if (node) 495 while (node->right) 496 node = node->right; 497 498 return node; 499 } 500 501 /* Return the immediate successor KEY, or NULL if there is no 502 successor. KEY need not be present in the tree. */ 503 504 splay_tree_node 505 splay_tree_successor (splay_tree sp, splay_tree_key key) 506 { 507 int comparison; 508 splay_tree_node node; 509 510 /* If the tree is empty, there is certainly no successor. */ 511 if (!sp->root) 512 return NULL; 513 514 /* Splay the tree around KEY. That will leave either the KEY 515 itself, its predecessor, or its successor at the root. */ 516 splay_tree_splay (sp, key); 517 comparison = (*sp->comp)(sp->root->key, key); 518 519 /* If the successor is at the root, just return it. */ 520 if (comparison > 0) 521 return sp->root; 522 523 /* Otherwise, find the leftmost element of the right subtree. */ 524 node = sp->root->right; 525 if (node) 526 while (node->left) 527 node = node->left; 528 529 return node; 530 } 531 532 /* Call FN, passing it the DATA, for every node in SP, following an 533 in-order traversal. If FN every returns a non-zero value, the 534 iteration ceases immediately, and the value is returned. 535 Otherwise, this function returns 0. */ 536 537 int 538 splay_tree_foreach (splay_tree sp, splay_tree_foreach_fn fn, void *data) 539 { 540 return splay_tree_foreach_helper (sp, sp->root, fn, data); 541 } 542 543 /* Splay-tree comparison function, treating the keys as ints. */ 544 545 int 546 splay_tree_compare_ints (splay_tree_key k1, splay_tree_key k2) 547 { 548 if ((int) k1 < (int) k2) 549 return -1; 550 else if ((int) k1 > (int) k2) 551 return 1; 552 else 553 return 0; 554 } 555 556 /* Splay-tree comparison function, treating the keys as pointers. */ 557 558 int 559 splay_tree_compare_pointers (splay_tree_key k1, splay_tree_key k2) 560 { 561 if ((char*) k1 < (char*) k2) 562 return -1; 563 else if ((char*) k1 > (char*) k2) 564 return 1; 565 else 566 return 0; 567 } 568