1169695Skan/* A splay-tree datatype. 2169695Skan Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc. 3169695Skan Contributed by Mark Mitchell (mark@markmitchell.com). 4169695Skan 5169695SkanThis file is part of GNU CC. 6169695Skan 7169695SkanGNU CC is free software; you can redistribute it and/or modify it 8169695Skanunder the terms of the GNU General Public License as published by 9169695Skanthe Free Software Foundation; either version 2, or (at your option) 10169695Skanany later version. 11169695Skan 12169695SkanGNU CC is distributed in the hope that it will be useful, but 13169695SkanWITHOUT ANY WARRANTY; without even the implied warranty of 14169695SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15169695SkanGeneral Public License for more details. 16169695Skan 17169695SkanYou should have received a copy of the GNU General Public License 18169695Skanalong with GNU CC; see the file COPYING. If not, write to 19169695Skanthe Free Software Foundation, 51 Franklin Street - Fifth Floor, 20169695SkanBoston, MA 02110-1301, USA. */ 21169695Skan 22169695Skan/* For an easily readable description of splay-trees, see: 23169695Skan 24169695Skan Lewis, Harry R. and Denenberg, Larry. Data Structures and Their 25169695Skan Algorithms. Harper-Collins, Inc. 1991. */ 26169695Skan 27169695Skan#ifdef HAVE_CONFIG_H 28169695Skan#include "config.h" 29169695Skan#endif 30169695Skan 31169695Skan#ifdef HAVE_STDLIB_H 32169695Skan#include <stdlib.h> 33169695Skan#endif 34169695Skan 35169695Skan#include <stdio.h> 36169695Skan 37169695Skan#include "libiberty.h" 38169695Skan#include "splay-tree.h" 39169695Skan 40169695Skanstatic void splay_tree_delete_helper (splay_tree, splay_tree_node); 41169695Skanstatic inline void rotate_left (splay_tree_node *, 42169695Skan splay_tree_node, splay_tree_node); 43169695Skanstatic inline void rotate_right (splay_tree_node *, 44169695Skan splay_tree_node, splay_tree_node); 45169695Skanstatic void splay_tree_splay (splay_tree, splay_tree_key); 46169695Skanstatic int splay_tree_foreach_helper (splay_tree, splay_tree_node, 47169695Skan splay_tree_foreach_fn, void*); 48169695Skan 49169695Skan/* Deallocate NODE (a member of SP), and all its sub-trees. */ 50169695Skan 51169695Skanstatic void 52169695Skansplay_tree_delete_helper (splay_tree sp, splay_tree_node node) 53169695Skan{ 54169695Skan splay_tree_node pending = 0; 55169695Skan splay_tree_node active = 0; 56169695Skan 57169695Skan if (!node) 58169695Skan return; 59169695Skan 60169695Skan#define KDEL(x) if (sp->delete_key) (*sp->delete_key)(x); 61169695Skan#define VDEL(x) if (sp->delete_value) (*sp->delete_value)(x); 62169695Skan 63169695Skan KDEL (node->key); 64169695Skan VDEL (node->value); 65169695Skan 66169695Skan /* We use the "key" field to hold the "next" pointer. */ 67169695Skan node->key = (splay_tree_key)pending; 68169695Skan pending = (splay_tree_node)node; 69169695Skan 70169695Skan /* Now, keep processing the pending list until there aren't any 71169695Skan more. This is a little more complicated than just recursing, but 72169695Skan it doesn't toast the stack for large trees. */ 73169695Skan 74169695Skan while (pending) 75169695Skan { 76169695Skan active = pending; 77169695Skan pending = 0; 78169695Skan while (active) 79169695Skan { 80169695Skan splay_tree_node temp; 81169695Skan 82169695Skan /* active points to a node which has its key and value 83169695Skan deallocated, we just need to process left and right. */ 84169695Skan 85169695Skan if (active->left) 86169695Skan { 87169695Skan KDEL (active->left->key); 88169695Skan VDEL (active->left->value); 89169695Skan active->left->key = (splay_tree_key)pending; 90169695Skan pending = (splay_tree_node)(active->left); 91169695Skan } 92169695Skan if (active->right) 93169695Skan { 94169695Skan KDEL (active->right->key); 95169695Skan VDEL (active->right->value); 96169695Skan active->right->key = (splay_tree_key)pending; 97169695Skan pending = (splay_tree_node)(active->right); 98169695Skan } 99169695Skan 100169695Skan temp = active; 101169695Skan active = (splay_tree_node)(temp->key); 102169695Skan (*sp->deallocate) ((char*) temp, sp->allocate_data); 103169695Skan } 104169695Skan } 105169695Skan#undef KDEL 106169695Skan#undef VDEL 107169695Skan} 108169695Skan 109169695Skan/* Rotate the edge joining the left child N with its parent P. PP is the 110169695Skan grandparents pointer to P. */ 111169695Skan 112169695Skanstatic inline void 113169695Skanrotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n) 114169695Skan{ 115169695Skan splay_tree_node tmp; 116169695Skan tmp = n->right; 117169695Skan n->right = p; 118169695Skan p->left = tmp; 119169695Skan *pp = n; 120169695Skan} 121169695Skan 122169695Skan/* Rotate the edge joining the right child N with its parent P. PP is the 123169695Skan grandparents pointer to P. */ 124169695Skan 125169695Skanstatic inline void 126169695Skanrotate_right (splay_tree_node *pp, splay_tree_node p, splay_tree_node n) 127169695Skan{ 128169695Skan splay_tree_node tmp; 129169695Skan tmp = n->left; 130169695Skan n->left = p; 131169695Skan p->right = tmp; 132169695Skan *pp = n; 133169695Skan} 134169695Skan 135169695Skan/* Bottom up splay of key. */ 136169695Skan 137169695Skanstatic void 138169695Skansplay_tree_splay (splay_tree sp, splay_tree_key key) 139169695Skan{ 140169695Skan if (sp->root == 0) 141169695Skan return; 142169695Skan 143169695Skan do { 144169695Skan int cmp1, cmp2; 145169695Skan splay_tree_node n, c; 146169695Skan 147169695Skan n = sp->root; 148169695Skan cmp1 = (*sp->comp) (key, n->key); 149169695Skan 150169695Skan /* Found. */ 151169695Skan if (cmp1 == 0) 152169695Skan return; 153169695Skan 154169695Skan /* Left or right? If no child, then we're done. */ 155169695Skan if (cmp1 < 0) 156169695Skan c = n->left; 157169695Skan else 158169695Skan c = n->right; 159169695Skan if (!c) 160169695Skan return; 161169695Skan 162169695Skan /* Next one left or right? If found or no child, we're done 163169695Skan after one rotation. */ 164169695Skan cmp2 = (*sp->comp) (key, c->key); 165169695Skan if (cmp2 == 0 166169695Skan || (cmp2 < 0 && !c->left) 167169695Skan || (cmp2 > 0 && !c->right)) 168169695Skan { 169169695Skan if (cmp1 < 0) 170169695Skan rotate_left (&sp->root, n, c); 171169695Skan else 172169695Skan rotate_right (&sp->root, n, c); 173169695Skan return; 174169695Skan } 175169695Skan 176169695Skan /* Now we have the four cases of double-rotation. */ 177169695Skan if (cmp1 < 0 && cmp2 < 0) 178169695Skan { 179169695Skan rotate_left (&n->left, c, c->left); 180169695Skan rotate_left (&sp->root, n, n->left); 181169695Skan } 182169695Skan else if (cmp1 > 0 && cmp2 > 0) 183169695Skan { 184169695Skan rotate_right (&n->right, c, c->right); 185169695Skan rotate_right (&sp->root, n, n->right); 186169695Skan } 187169695Skan else if (cmp1 < 0 && cmp2 > 0) 188169695Skan { 189169695Skan rotate_right (&n->left, c, c->right); 190169695Skan rotate_left (&sp->root, n, n->left); 191169695Skan } 192169695Skan else if (cmp1 > 0 && cmp2 < 0) 193169695Skan { 194169695Skan rotate_left (&n->right, c, c->left); 195169695Skan rotate_right (&sp->root, n, n->right); 196169695Skan } 197169695Skan } while (1); 198169695Skan} 199169695Skan 200169695Skan/* Call FN, passing it the DATA, for every node below NODE, all of 201169695Skan which are from SP, following an in-order traversal. If FN every 202169695Skan returns a non-zero value, the iteration ceases immediately, and the 203169695Skan value is returned. Otherwise, this function returns 0. */ 204169695Skan 205169695Skanstatic int 206169695Skansplay_tree_foreach_helper (splay_tree sp, splay_tree_node node, 207169695Skan splay_tree_foreach_fn fn, void *data) 208169695Skan{ 209169695Skan int val; 210169695Skan 211169695Skan if (!node) 212169695Skan return 0; 213169695Skan 214169695Skan val = splay_tree_foreach_helper (sp, node->left, fn, data); 215169695Skan if (val) 216169695Skan return val; 217169695Skan 218169695Skan val = (*fn)(node, data); 219169695Skan if (val) 220169695Skan return val; 221169695Skan 222169695Skan return splay_tree_foreach_helper (sp, node->right, fn, data); 223169695Skan} 224169695Skan 225169695Skan 226169695Skan/* An allocator and deallocator based on xmalloc. */ 227169695Skanstatic void * 228169695Skansplay_tree_xmalloc_allocate (int size, void *data ATTRIBUTE_UNUSED) 229169695Skan{ 230169695Skan return (void *) xmalloc (size); 231169695Skan} 232169695Skan 233169695Skanstatic void 234169695Skansplay_tree_xmalloc_deallocate (void *object, void *data ATTRIBUTE_UNUSED) 235169695Skan{ 236169695Skan free (object); 237169695Skan} 238169695Skan 239169695Skan 240169695Skan/* Allocate a new splay tree, using COMPARE_FN to compare nodes, 241169695Skan DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate 242169695Skan values. Use xmalloc to allocate the splay tree structure, and any 243169695Skan nodes added. */ 244169695Skan 245169695Skansplay_tree 246169695Skansplay_tree_new (splay_tree_compare_fn compare_fn, 247169695Skan splay_tree_delete_key_fn delete_key_fn, 248169695Skan splay_tree_delete_value_fn delete_value_fn) 249169695Skan{ 250169695Skan return (splay_tree_new_with_allocator 251169695Skan (compare_fn, delete_key_fn, delete_value_fn, 252169695Skan splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate, 0)); 253169695Skan} 254169695Skan 255169695Skan 256169695Skan/* Allocate a new splay tree, using COMPARE_FN to compare nodes, 257169695Skan DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate 258169695Skan values. */ 259169695Skan 260169695Skansplay_tree 261169695Skansplay_tree_new_with_allocator (splay_tree_compare_fn compare_fn, 262169695Skan splay_tree_delete_key_fn delete_key_fn, 263169695Skan splay_tree_delete_value_fn delete_value_fn, 264169695Skan splay_tree_allocate_fn allocate_fn, 265169695Skan splay_tree_deallocate_fn deallocate_fn, 266169695Skan void *allocate_data) 267169695Skan{ 268169695Skan splay_tree sp = (splay_tree) (*allocate_fn) (sizeof (struct splay_tree_s), 269169695Skan allocate_data); 270169695Skan sp->root = 0; 271169695Skan sp->comp = compare_fn; 272169695Skan sp->delete_key = delete_key_fn; 273169695Skan sp->delete_value = delete_value_fn; 274169695Skan sp->allocate = allocate_fn; 275169695Skan sp->deallocate = deallocate_fn; 276169695Skan sp->allocate_data = allocate_data; 277169695Skan 278169695Skan return sp; 279169695Skan} 280169695Skan 281169695Skan/* Deallocate SP. */ 282169695Skan 283169695Skanvoid 284169695Skansplay_tree_delete (splay_tree sp) 285169695Skan{ 286169695Skan splay_tree_delete_helper (sp, sp->root); 287169695Skan (*sp->deallocate) ((char*) sp, sp->allocate_data); 288169695Skan} 289169695Skan 290169695Skan/* Insert a new node (associating KEY with DATA) into SP. If a 291169695Skan previous node with the indicated KEY exists, its data is replaced 292169695Skan with the new value. Returns the new node. */ 293169695Skan 294169695Skansplay_tree_node 295169695Skansplay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value) 296169695Skan{ 297169695Skan int comparison = 0; 298169695Skan 299169695Skan splay_tree_splay (sp, key); 300169695Skan 301169695Skan if (sp->root) 302169695Skan comparison = (*sp->comp)(sp->root->key, key); 303169695Skan 304169695Skan if (sp->root && comparison == 0) 305169695Skan { 306169695Skan /* If the root of the tree already has the indicated KEY, just 307169695Skan replace the value with VALUE. */ 308169695Skan if (sp->delete_value) 309169695Skan (*sp->delete_value)(sp->root->value); 310169695Skan sp->root->value = value; 311169695Skan } 312169695Skan else 313169695Skan { 314169695Skan /* Create a new node, and insert it at the root. */ 315169695Skan splay_tree_node node; 316169695Skan 317169695Skan node = ((splay_tree_node) 318169695Skan (*sp->allocate) (sizeof (struct splay_tree_node_s), 319169695Skan sp->allocate_data)); 320169695Skan node->key = key; 321169695Skan node->value = value; 322169695Skan 323169695Skan if (!sp->root) 324169695Skan node->left = node->right = 0; 325169695Skan else if (comparison < 0) 326169695Skan { 327169695Skan node->left = sp->root; 328169695Skan node->right = node->left->right; 329169695Skan node->left->right = 0; 330169695Skan } 331169695Skan else 332169695Skan { 333169695Skan node->right = sp->root; 334169695Skan node->left = node->right->left; 335169695Skan node->right->left = 0; 336169695Skan } 337169695Skan 338169695Skan sp->root = node; 339169695Skan } 340169695Skan 341169695Skan return sp->root; 342169695Skan} 343169695Skan 344169695Skan/* Remove KEY from SP. It is not an error if it did not exist. */ 345169695Skan 346169695Skanvoid 347169695Skansplay_tree_remove (splay_tree sp, splay_tree_key key) 348169695Skan{ 349169695Skan splay_tree_splay (sp, key); 350169695Skan 351169695Skan if (sp->root && (*sp->comp) (sp->root->key, key) == 0) 352169695Skan { 353169695Skan splay_tree_node left, right; 354169695Skan 355169695Skan left = sp->root->left; 356169695Skan right = sp->root->right; 357169695Skan 358169695Skan /* Delete the root node itself. */ 359169695Skan if (sp->delete_value) 360169695Skan (*sp->delete_value) (sp->root->value); 361169695Skan (*sp->deallocate) (sp->root, sp->allocate_data); 362169695Skan 363169695Skan /* One of the children is now the root. Doesn't matter much 364169695Skan which, so long as we preserve the properties of the tree. */ 365169695Skan if (left) 366169695Skan { 367169695Skan sp->root = left; 368169695Skan 369169695Skan /* If there was a right child as well, hang it off the 370169695Skan right-most leaf of the left child. */ 371169695Skan if (right) 372169695Skan { 373169695Skan while (left->right) 374169695Skan left = left->right; 375169695Skan left->right = right; 376169695Skan } 377169695Skan } 378169695Skan else 379169695Skan sp->root = right; 380169695Skan } 381169695Skan} 382169695Skan 383169695Skan/* Lookup KEY in SP, returning VALUE if present, and NULL 384169695Skan otherwise. */ 385169695Skan 386169695Skansplay_tree_node 387169695Skansplay_tree_lookup (splay_tree sp, splay_tree_key key) 388169695Skan{ 389169695Skan splay_tree_splay (sp, key); 390169695Skan 391169695Skan if (sp->root && (*sp->comp)(sp->root->key, key) == 0) 392169695Skan return sp->root; 393169695Skan else 394169695Skan return 0; 395169695Skan} 396169695Skan 397169695Skan/* Return the node in SP with the greatest key. */ 398169695Skan 399169695Skansplay_tree_node 400169695Skansplay_tree_max (splay_tree sp) 401169695Skan{ 402169695Skan splay_tree_node n = sp->root; 403169695Skan 404169695Skan if (!n) 405169695Skan return NULL; 406169695Skan 407169695Skan while (n->right) 408169695Skan n = n->right; 409169695Skan 410169695Skan return n; 411169695Skan} 412169695Skan 413169695Skan/* Return the node in SP with the smallest key. */ 414169695Skan 415169695Skansplay_tree_node 416169695Skansplay_tree_min (splay_tree sp) 417169695Skan{ 418169695Skan splay_tree_node n = sp->root; 419169695Skan 420169695Skan if (!n) 421169695Skan return NULL; 422169695Skan 423169695Skan while (n->left) 424169695Skan n = n->left; 425169695Skan 426169695Skan return n; 427169695Skan} 428169695Skan 429169695Skan/* Return the immediate predecessor KEY, or NULL if there is no 430169695Skan predecessor. KEY need not be present in the tree. */ 431169695Skan 432169695Skansplay_tree_node 433169695Skansplay_tree_predecessor (splay_tree sp, splay_tree_key key) 434169695Skan{ 435169695Skan int comparison; 436169695Skan splay_tree_node node; 437169695Skan 438169695Skan /* If the tree is empty, there is certainly no predecessor. */ 439169695Skan if (!sp->root) 440169695Skan return NULL; 441169695Skan 442169695Skan /* Splay the tree around KEY. That will leave either the KEY 443169695Skan itself, its predecessor, or its successor at the root. */ 444169695Skan splay_tree_splay (sp, key); 445169695Skan comparison = (*sp->comp)(sp->root->key, key); 446169695Skan 447169695Skan /* If the predecessor is at the root, just return it. */ 448169695Skan if (comparison < 0) 449169695Skan return sp->root; 450169695Skan 451169695Skan /* Otherwise, find the rightmost element of the left subtree. */ 452169695Skan node = sp->root->left; 453169695Skan if (node) 454169695Skan while (node->right) 455169695Skan node = node->right; 456169695Skan 457169695Skan return node; 458169695Skan} 459169695Skan 460169695Skan/* Return the immediate successor KEY, or NULL if there is no 461169695Skan successor. KEY need not be present in the tree. */ 462169695Skan 463169695Skansplay_tree_node 464169695Skansplay_tree_successor (splay_tree sp, splay_tree_key key) 465169695Skan{ 466169695Skan int comparison; 467169695Skan splay_tree_node node; 468169695Skan 469169695Skan /* If the tree is empty, there is certainly no successor. */ 470169695Skan if (!sp->root) 471169695Skan return NULL; 472169695Skan 473169695Skan /* Splay the tree around KEY. That will leave either the KEY 474169695Skan itself, its predecessor, or its successor at the root. */ 475169695Skan splay_tree_splay (sp, key); 476169695Skan comparison = (*sp->comp)(sp->root->key, key); 477169695Skan 478169695Skan /* If the successor is at the root, just return it. */ 479169695Skan if (comparison > 0) 480169695Skan return sp->root; 481169695Skan 482169695Skan /* Otherwise, find the leftmost element of the right subtree. */ 483169695Skan node = sp->root->right; 484169695Skan if (node) 485169695Skan while (node->left) 486169695Skan node = node->left; 487169695Skan 488169695Skan return node; 489169695Skan} 490169695Skan 491169695Skan/* Call FN, passing it the DATA, for every node in SP, following an 492169695Skan in-order traversal. If FN every returns a non-zero value, the 493169695Skan iteration ceases immediately, and the value is returned. 494169695Skan Otherwise, this function returns 0. */ 495169695Skan 496169695Skanint 497169695Skansplay_tree_foreach (splay_tree sp, splay_tree_foreach_fn fn, void *data) 498169695Skan{ 499169695Skan return splay_tree_foreach_helper (sp, sp->root, fn, data); 500169695Skan} 501169695Skan 502169695Skan/* Splay-tree comparison function, treating the keys as ints. */ 503169695Skan 504169695Skanint 505169695Skansplay_tree_compare_ints (splay_tree_key k1, splay_tree_key k2) 506169695Skan{ 507169695Skan if ((int) k1 < (int) k2) 508169695Skan return -1; 509169695Skan else if ((int) k1 > (int) k2) 510169695Skan return 1; 511169695Skan else 512169695Skan return 0; 513169695Skan} 514169695Skan 515169695Skan/* Splay-tree comparison function, treating the keys as pointers. */ 516169695Skan 517169695Skanint 518169695Skansplay_tree_compare_pointers (splay_tree_key k1, splay_tree_key k2) 519169695Skan{ 520169695Skan if ((char*) k1 < (char*) k2) 521169695Skan return -1; 522169695Skan else if ((char*) k1 > (char*) k2) 523169695Skan return 1; 524169695Skan else 525169695Skan return 0; 526169695Skan} 527