1 /* A typesafe wrapper around libiberty's splay-tree.h. 2 Copyright (C) 2015-2022 Free Software Foundation, Inc. 3 4 This file is part of GCC. 5 6 GCC is free software; you can redistribute it and/or modify it under 7 the terms of the GNU General Public License as published by the Free 8 Software Foundation; either version 3, or (at your option) any later 9 version. 10 11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12 WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with GCC; see the file COPYING3. If not see 18 <http://www.gnu.org/licenses/>. */ 19 20 #ifndef GCC_TYPED_SPLAY_TREE_H 21 #define GCC_TYPED_SPLAY_TREE_H 22 23 /* Typesafe wrapper around libiberty's splay-tree.h. */ 24 template <typename KEY_TYPE, typename VALUE_TYPE> 25 class typed_splay_tree 26 { 27 public: 28 typedef KEY_TYPE key_type; 29 typedef VALUE_TYPE value_type; 30 31 typedef int (*compare_fn) (key_type, key_type); 32 typedef void (*delete_key_fn) (key_type); 33 typedef void (*delete_value_fn) (value_type); 34 typedef int (*foreach_fn) (key_type, value_type, void *); 35 36 typed_splay_tree (compare_fn, 37 delete_key_fn, 38 delete_value_fn); 39 ~typed_splay_tree (); 40 41 value_type lookup (key_type k); 42 value_type predecessor (key_type k); 43 value_type successor (key_type k); 44 void insert (key_type k, value_type v); 45 void remove (key_type k); 46 value_type max (); 47 value_type min (); 48 int foreach (foreach_fn, void *); 49 50 private: 51 /* Copy and assignment ops are not supported. */ 52 typed_splay_tree (const typed_splay_tree &); 53 typed_splay_tree & operator = (const typed_splay_tree &); 54 55 typedef key_type splay_tree_key; 56 typedef value_type splay_tree_value; 57 58 /* The nodes in the splay tree. */ 59 struct splay_tree_node_s { 60 /* The key. */ 61 splay_tree_key key; 62 63 /* The value. */ 64 splay_tree_value value; 65 66 /* The left and right children, respectively. */ 67 splay_tree_node_s *left, *right; 68 69 /* Used as temporary value for tree traversals. */ 70 splay_tree_node_s *back; 71 }; 72 typedef splay_tree_node_s *splay_tree_node; 73 74 inline void KDEL (splay_tree_key); 75 inline void VDEL (splay_tree_value); 76 void splay_tree_delete_helper (splay_tree_node); 77 static inline void rotate_left (splay_tree_node *, 78 splay_tree_node, splay_tree_node); 79 static inline void rotate_right (splay_tree_node *, 80 splay_tree_node, splay_tree_node); 81 void splay_tree_splay (splay_tree_key); 82 static int splay_tree_foreach_helper (splay_tree_node, 83 foreach_fn, void*); 84 splay_tree_node splay_tree_insert (splay_tree_key, splay_tree_value); 85 void splay_tree_remove (splay_tree_key key); 86 splay_tree_node splay_tree_lookup (splay_tree_key key); 87 splay_tree_node splay_tree_predecessor (splay_tree_key); 88 splay_tree_node splay_tree_successor (splay_tree_key); 89 splay_tree_node splay_tree_max (); 90 splay_tree_node splay_tree_min (); 91 92 static value_type node_to_value (splay_tree_node node); 93 94 /* The root of the tree. */ 95 splay_tree_node root; 96 97 /* The comparision function. */ 98 compare_fn comp; 99 100 /* The deallocate-key function. NULL if no cleanup is necessary. */ 101 delete_key_fn delete_key; 102 103 /* The deallocate-value function. NULL if no cleanup is necessary. */ 104 delete_value_fn delete_value; 105 }; 106 107 /* Constructor for typed_splay_tree <K, V>. */ 108 109 template <typename KEY_TYPE, typename VALUE_TYPE> 110 inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>:: 111 typed_splay_tree (compare_fn compare_fn, 112 delete_key_fn delete_key_fn, 113 delete_value_fn delete_value_fn) 114 { 115 root = NULL; 116 comp = compare_fn; 117 delete_key = delete_key_fn; 118 delete_value = delete_value_fn; 119 } 120 121 /* Destructor for typed_splay_tree <K, V>. */ 122 123 template <typename KEY_TYPE, typename VALUE_TYPE> 124 inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>:: 125 ~typed_splay_tree () 126 { 127 splay_tree_delete_helper (root); 128 } 129 130 /* Lookup KEY, returning a value if present, and NULL 131 otherwise. */ 132 133 template <typename KEY_TYPE, typename VALUE_TYPE> 134 inline VALUE_TYPE 135 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::lookup (key_type key) 136 { 137 splay_tree_node node = splay_tree_lookup (key); 138 return node_to_value (node); 139 } 140 141 /* Return the immediate predecessor of KEY, or NULL if there is no 142 predecessor. KEY need not be present in the tree. */ 143 144 template <typename KEY_TYPE, typename VALUE_TYPE> 145 inline VALUE_TYPE 146 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::predecessor (key_type key) 147 { 148 splay_tree_node node = splay_tree_predecessor (key); 149 return node_to_value (node); 150 } 151 152 /* Return the immediate successor of KEY, or NULL if there is no 153 successor. KEY need not be present in the tree. */ 154 155 template <typename KEY_TYPE, typename VALUE_TYPE> 156 inline VALUE_TYPE 157 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::successor (key_type key) 158 { 159 splay_tree_node node = splay_tree_successor (key); 160 return node_to_value (node); 161 } 162 163 /* Insert a new node (associating KEY with VALUE). If a 164 previous node with the indicated KEY exists, its data is replaced 165 with the new value. */ 166 167 template <typename KEY_TYPE, typename VALUE_TYPE> 168 inline void 169 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::insert (key_type key, 170 value_type value) 171 { 172 splay_tree_insert (key, value); 173 } 174 175 /* Remove a node (associating KEY with VALUE). */ 176 177 template <typename KEY_TYPE, typename VALUE_TYPE> 178 inline void 179 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::remove (key_type key) 180 { 181 splay_tree_remove (key); 182 } 183 184 /* Get the value with maximal key. */ 185 186 template <typename KEY_TYPE, typename VALUE_TYPE> 187 inline VALUE_TYPE 188 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::max () 189 { 190 return node_to_value (splay_tree_max ()); 191 } 192 193 /* Get the value with minimal key. */ 194 195 template <typename KEY_TYPE, typename VALUE_TYPE> 196 inline VALUE_TYPE 197 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::min () 198 { 199 return node_to_value (splay_tree_min ()); 200 } 201 202 /* Call OUTER_CB, passing it the OUTER_USER_DATA, for every node, 203 following an in-order traversal. If OUTER_CB ever returns a non-zero 204 value, the iteration ceases immediately, and the value is returned. 205 Otherwise, this function returns 0. */ 206 207 template <typename KEY_TYPE, typename VALUE_TYPE> 208 inline int 209 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::foreach (foreach_fn foreach_fn, 210 void *user_data) 211 { 212 return splay_tree_foreach_helper (root, foreach_fn, user_data); 213 } 214 215 /* Internal function for converting from splay_tree_node to 216 VALUE_TYPE. */ 217 template <typename KEY_TYPE, typename VALUE_TYPE> 218 inline VALUE_TYPE 219 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::node_to_value (splay_tree_node node) 220 { 221 if (node) 222 return node->value; 223 else 224 return 0; 225 } 226 227 template <typename KEY_TYPE, typename VALUE_TYPE> 228 inline void 229 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::KDEL(splay_tree_key x) 230 { 231 if (delete_key) 232 (*delete_key)(x); 233 } 234 235 template <typename KEY_TYPE, typename VALUE_TYPE> 236 inline void 237 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::VDEL(splay_tree_value x) 238 { 239 if (delete_value) 240 (*delete_value)(x); 241 } 242 243 /* Deallocate NODE (a member of SP), and all its sub-trees. */ 244 245 template <typename KEY_TYPE, typename VALUE_TYPE> 246 void 247 typed_splay_tree<KEY_TYPE, 248 VALUE_TYPE>::splay_tree_delete_helper (splay_tree_node node) 249 { 250 splay_tree_node pending = NULL; 251 splay_tree_node active = NULL; 252 253 if (!node) 254 return; 255 256 KDEL (node->key); 257 VDEL (node->value); 258 259 /* We use the "back" field to hold the "next" pointer. */ 260 node->back = pending; 261 pending = node; 262 263 /* Now, keep processing the pending list until there aren't any 264 more. This is a little more complicated than just recursing, but 265 it doesn't toast the stack for large trees. */ 266 267 while (pending) 268 { 269 active = pending; 270 pending = NULL; 271 while (active) 272 { 273 splay_tree_node temp; 274 275 /* active points to a node which has its key and value 276 deallocated, we just need to process left and right. */ 277 278 if (active->left) 279 { 280 KDEL (active->left->key); 281 VDEL (active->left->value); 282 active->left->back = pending; 283 pending = active->left; 284 } 285 if (active->right) 286 { 287 KDEL (active->right->key); 288 VDEL (active->right->value); 289 active->right->back = pending; 290 pending = active->right; 291 } 292 293 temp = active; 294 active = temp->back; 295 delete temp; 296 } 297 } 298 } 299 300 /* Rotate the edge joining the left child N with its parent P. PP is the 301 grandparents' pointer to P. */ 302 303 template <typename KEY_TYPE, typename VALUE_TYPE> 304 inline void 305 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::rotate_left (splay_tree_node *pp, 306 splay_tree_node p, 307 splay_tree_node n) 308 { 309 splay_tree_node tmp; 310 tmp = n->right; 311 n->right = p; 312 p->left = tmp; 313 *pp = n; 314 } 315 316 /* Rotate the edge joining the right child N with its parent P. PP is the 317 grandparents' pointer to P. */ 318 319 template <typename KEY_TYPE, typename VALUE_TYPE> 320 inline void 321 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::rotate_right (splay_tree_node *pp, 322 splay_tree_node p, 323 splay_tree_node n) 324 { 325 splay_tree_node tmp; 326 tmp = n->left; 327 n->left = p; 328 p->right = tmp; 329 *pp = n; 330 } 331 332 /* Bottom up splay of key. */ 333 334 template <typename KEY_TYPE, typename VALUE_TYPE> 335 void 336 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_splay (splay_tree_key key) 337 { 338 if (root == NULL) 339 return; 340 341 do { 342 int cmp1, cmp2; 343 splay_tree_node n, c; 344 345 n = root; 346 cmp1 = (*comp) (key, n->key); 347 348 /* Found. */ 349 if (cmp1 == 0) 350 return; 351 352 /* Left or right? If no child, then we're done. */ 353 if (cmp1 < 0) 354 c = n->left; 355 else 356 c = n->right; 357 if (!c) 358 return; 359 360 /* Next one left or right? If found or no child, we're done 361 after one rotation. */ 362 cmp2 = (*comp) (key, c->key); 363 if (cmp2 == 0 364 || (cmp2 < 0 && !c->left) 365 || (cmp2 > 0 && !c->right)) 366 { 367 if (cmp1 < 0) 368 rotate_left (&root, n, c); 369 else 370 rotate_right (&root, n, c); 371 return; 372 } 373 374 /* Now we have the four cases of double-rotation. */ 375 if (cmp1 < 0 && cmp2 < 0) 376 { 377 rotate_left (&n->left, c, c->left); 378 rotate_left (&root, n, n->left); 379 } 380 else if (cmp1 > 0 && cmp2 > 0) 381 { 382 rotate_right (&n->right, c, c->right); 383 rotate_right (&root, n, n->right); 384 } 385 else if (cmp1 < 0 && cmp2 > 0) 386 { 387 rotate_right (&n->left, c, c->right); 388 rotate_left (&root, n, n->left); 389 } 390 else if (cmp1 > 0 && cmp2 < 0) 391 { 392 rotate_left (&n->right, c, c->left); 393 rotate_right (&root, n, n->right); 394 } 395 } while (1); 396 } 397 398 /* Call FN, passing it the DATA, for every node below NODE, all of 399 which are from SP, following an in-order traversal. If FN every 400 returns a non-zero value, the iteration ceases immediately, and the 401 value is returned. Otherwise, this function returns 0. */ 402 403 template <typename KEY_TYPE, typename VALUE_TYPE> 404 int 405 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_foreach_helper ( 406 splay_tree_node node, 407 foreach_fn fn, void *data) 408 { 409 int val; 410 splay_tree_node stack; 411 412 /* A non-recursive implementation is used to avoid filling the stack 413 for large trees. Splay trees are worst case O(n) in the depth of 414 the tree. */ 415 416 stack = NULL; 417 val = 0; 418 419 for (;;) 420 { 421 while (node != NULL) 422 { 423 node->back = stack; 424 stack = node; 425 node = node->left; 426 } 427 428 if (stack == NULL) 429 break; 430 431 node = stack; 432 stack = stack->back; 433 434 val = (*fn) (node->key, node->value, data); 435 if (val) 436 break; 437 438 node = node->right; 439 } 440 441 return val; 442 } 443 444 /* Insert a new node (associating KEY with DATA) into SP. If a 445 previous node with the indicated KEY exists, its data is replaced 446 with the new value. Returns the new node. */ 447 448 template <typename KEY_TYPE, typename VALUE_TYPE> 449 typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node 450 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_insert ( 451 splay_tree_key key, 452 splay_tree_value value) 453 { 454 int comparison = 0; 455 456 splay_tree_splay (key); 457 458 if (root) 459 comparison = (*comp)(root->key, key); 460 461 if (root && comparison == 0) 462 { 463 /* If the root of the tree already has the indicated KEY, just 464 replace the value with VALUE. */ 465 VDEL(root->value); 466 root->value = value; 467 } 468 else 469 { 470 /* Create a new node, and insert it at the root. */ 471 splay_tree_node node; 472 473 node = new splay_tree_node_s; 474 node->key = key; 475 node->value = value; 476 477 if (!root) 478 node->left = node->right = 0; 479 else if (comparison < 0) 480 { 481 node->left = root; 482 node->right = node->left->right; 483 node->left->right = 0; 484 } 485 else 486 { 487 node->right = root; 488 node->left = node->right->left; 489 node->right->left = 0; 490 } 491 492 root = node; 493 } 494 495 return root; 496 } 497 498 /* Remove KEY from SP. It is not an error if it did not exist. */ 499 500 template <typename KEY_TYPE, typename VALUE_TYPE> 501 void 502 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_remove (splay_tree_key key) 503 { 504 splay_tree_splay (key); 505 506 if (root && (*comp) (root->key, key) == 0) 507 { 508 splay_tree_node left, right; 509 510 left = root->left; 511 right = root->right; 512 513 /* Delete the root node itself. */ 514 VDEL (root->value); 515 delete root; 516 517 /* One of the children is now the root. Doesn't matter much 518 which, so long as we preserve the properties of the tree. */ 519 if (left) 520 { 521 root = left; 522 523 /* If there was a right child as well, hang it off the 524 right-most leaf of the left child. */ 525 if (right) 526 { 527 while (left->right) 528 left = left->right; 529 left->right = right; 530 } 531 } 532 else 533 root = right; 534 } 535 } 536 537 /* Lookup KEY in SP, returning VALUE if present, and NULL 538 otherwise. */ 539 540 template <typename KEY_TYPE, typename VALUE_TYPE> 541 typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node 542 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_lookup (splay_tree_key key) 543 { 544 splay_tree_splay (key); 545 546 if (root && (*comp)(root->key, key) == 0) 547 return root; 548 else 549 return 0; 550 } 551 552 /* Return the node in SP with the greatest key. */ 553 554 template <typename KEY_TYPE, typename VALUE_TYPE> 555 typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node 556 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_max () 557 { 558 splay_tree_node n = root; 559 560 if (!n) 561 return NULL; 562 563 while (n->right) 564 n = n->right; 565 566 return n; 567 } 568 569 /* Return the node in SP with the smallest key. */ 570 571 template <typename KEY_TYPE, typename VALUE_TYPE> 572 typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node 573 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_min () 574 { 575 splay_tree_node n = root; 576 577 if (!n) 578 return NULL; 579 580 while (n->left) 581 n = n->left; 582 583 return n; 584 } 585 586 /* Return the immediate predecessor KEY, or NULL if there is no 587 predecessor. KEY need not be present in the tree. */ 588 589 template <typename KEY_TYPE, typename VALUE_TYPE> 590 typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node 591 typed_splay_tree<KEY_TYPE, 592 VALUE_TYPE>::splay_tree_predecessor (splay_tree_key key) 593 { 594 int comparison; 595 splay_tree_node node; 596 597 /* If the tree is empty, there is certainly no predecessor. */ 598 if (!root) 599 return NULL; 600 601 /* Splay the tree around KEY. That will leave either the KEY 602 itself, its predecessor, or its successor at the root. */ 603 splay_tree_splay (key); 604 comparison = (*comp)(root->key, key); 605 606 /* If the predecessor is at the root, just return it. */ 607 if (comparison < 0) 608 return root; 609 610 /* Otherwise, find the rightmost element of the left subtree. */ 611 node = root->left; 612 if (node) 613 while (node->right) 614 node = node->right; 615 616 return node; 617 } 618 619 /* Return the immediate successor KEY, or NULL if there is no 620 successor. KEY need not be present in the tree. */ 621 622 template <typename KEY_TYPE, typename VALUE_TYPE> 623 typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node 624 typed_splay_tree<KEY_TYPE, 625 VALUE_TYPE>::splay_tree_successor (splay_tree_key key) 626 { 627 int comparison; 628 splay_tree_node node; 629 630 /* If the tree is empty, there is certainly no successor. */ 631 if (!root) 632 return NULL; 633 634 /* Splay the tree around KEY. That will leave either the KEY 635 itself, its predecessor, or its successor at the root. */ 636 splay_tree_splay (key); 637 comparison = (*comp)(root->key, key); 638 639 /* If the successor is at the root, just return it. */ 640 if (comparison > 0) 641 return root; 642 643 /* Otherwise, find the leftmost element of the right subtree. */ 644 node = root->right; 645 if (node) 646 while (node->left) 647 node = node->left; 648 649 return node; 650 } 651 652 #endif /* GCC_TYPED_SPLAY_TREE_H */ 653
Indexes created Sun Mar 01 05:31:48 UTC 2026