1260067Skargl/* A splay-tree datatype. 2260067Skargl Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc. 3260067Skargl Contributed by Mark Mitchell (mark@markmitchell.com). 4260067Skargl 5260067SkarglThis file is part of GNU CC. 6260067Skargl 7260067SkarglGNU CC is free software; you can redistribute it and/or modify it 8260067Skarglunder the terms of the GNU General Public License as published by 9260067Skarglthe Free Software Foundation; either version 2, or (at your option) 10260067Skarglany later version. 11260067Skargl 12260067SkarglGNU CC is distributed in the hope that it will be useful, but 13260067SkarglWITHOUT ANY WARRANTY; without even the implied warranty of 14260067SkarglMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15260067SkarglGeneral Public License for more details. 16260067Skargl 17260067SkarglYou should have received a copy of the GNU General Public License 18260067Skarglalong with GNU CC; see the file COPYING. If not, write to 19260067Skarglthe Free Software Foundation, 51 Franklin Street - Fifth Floor, 20260067SkarglBoston, MA 02110-1301, USA. */ 21260067Skargl 22260067Skargl/* For an easily readable description of splay-trees, see: 23260067Skargl 24260067Skargl Lewis, Harry R. and Denenberg, Larry. Data Structures and Their 25260067Skargl Algorithms. Harper-Collins, Inc. 1991. */ 26260067Skargl 27260067Skargl#ifdef HAVE_CONFIG_H 28260067Skargl#include "config.h" 29260067Skargl#endif 30260067Skargl 31260067Skargl#ifdef HAVE_STDLIB_H 32260067Skargl#include <stdlib.h> 33260067Skargl#endif 34260067Skargl 35260067Skargl#include <stdio.h> 36260067Skargl 37260067Skargl#include "libiberty.h" 38260067Skargl#include "splay-tree.h" 39260067Skargl 40260067Skarglstatic void splay_tree_delete_helper (splay_tree, splay_tree_node); 41260067Skarglstatic inline void rotate_left (splay_tree_node *, 42260067Skargl splay_tree_node, splay_tree_node); 43260067Skarglstatic inline void rotate_right (splay_tree_node *, 44260067Skargl splay_tree_node, splay_tree_node); 45260067Skarglstatic void splay_tree_splay (splay_tree, splay_tree_key); 46260067Skarglstatic int splay_tree_foreach_helper (splay_tree, splay_tree_node, 47260067Skargl splay_tree_foreach_fn, void*); 48260067Skargl 49260067Skargl/* Deallocate NODE (a member of SP), and all its sub-trees. */ 50260067Skargl 51260067Skarglstatic void 52260067Skarglsplay_tree_delete_helper (splay_tree sp, splay_tree_node node) 53260067Skargl{ 54260067Skargl splay_tree_node pending = 0; 55260067Skargl splay_tree_node active = 0; 56260067Skargl 57260067Skargl if (!node) 58260067Skargl return; 59260067Skargl 60260067Skargl#define KDEL(x) if (sp->delete_key) (*sp->delete_key)(x); 61260067Skargl#define VDEL(x) if (sp->delete_value) (*sp->delete_value)(x); 62260067Skargl 63260067Skargl KDEL (node->key); 64260067Skargl VDEL (node->value); 65260067Skargl 66260067Skargl /* We use the "key" field to hold the "next" pointer. */ 67260067Skargl node->key = (splay_tree_key)pending; 68260067Skargl pending = (splay_tree_node)node; 69260067Skargl 70260067Skargl /* Now, keep processing the pending list until there aren't any 71260067Skargl more. This is a little more complicated than just recursing, but 72260067Skargl it doesn't toast the stack for large trees. */ 73260067Skargl 74260067Skargl while (pending) 75260067Skargl { 76260067Skargl active = pending; 77260067Skargl pending = 0; 78260067Skargl while (active) 79260067Skargl { 80271779Stijl splay_tree_node temp; 81260067Skargl 82260067Skargl /* active points to a node which has its key and value 83260067Skargl deallocated, we just need to process left and right. */ 84260067Skargl 85260067Skargl if (active->left) 86260067Skargl { 87260067Skargl KDEL (active->left->key); 88260067Skargl VDEL (active->left->value); 89260067Skargl active->left->key = (splay_tree_key)pending; 90260067Skargl pending = (splay_tree_node)(active->left); 91260067Skargl } 92260067Skargl if (active->right) 93260067Skargl { 94260067Skargl KDEL (active->right->key); 95260067Skargl VDEL (active->right->value); 96260067Skargl active->right->key = (splay_tree_key)pending; 97260067Skargl pending = (splay_tree_node)(active->right); 98260067Skargl } 99260067Skargl 100260067Skargl temp = active; 101260067Skargl active = (splay_tree_node)(temp->key); 102260067Skargl (*sp->deallocate) ((char*) temp, sp->allocate_data); 103260067Skargl } 104260067Skargl } 105260067Skargl#undef KDEL 106260067Skargl#undef VDEL 107260067Skargl} 108260067Skargl 109260067Skargl/* Rotate the edge joining the left child N with its parent P. PP is the 110260067Skargl grandparents' pointer to P. */ 111260067Skargl 112260067Skarglstatic inline void 113260067Skarglrotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n) 114260067Skargl{ 115260067Skargl splay_tree_node tmp; 116260067Skargl tmp = n->right; 117260067Skargl n->right = p; 118260067Skargl p->left = tmp; 119260067Skargl *pp = n; 120260067Skargl} 121260067Skargl 122260067Skargl/* Rotate the edge joining the right child N with its parent P. PP is the 123260067Skargl grandparents' pointer to P. */ 124260067Skargl 125260067Skarglstatic inline void 126260067Skarglrotate_right (splay_tree_node *pp, splay_tree_node p, splay_tree_node n) 127260067Skargl{ 128260067Skargl splay_tree_node tmp; 129260067Skargl tmp = n->left; 130260067Skargl n->left = p; 131260067Skargl p->right = tmp; 132 *pp = n; 133} 134 135/* Bottom up splay of key. */ 136 137static void 138splay_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 205static int 206splay_tree_foreach_helper (splay_tree sp, splay_tree_node node, 207 splay_tree_foreach_fn fn, void *data) 208{ 209 int val; 210 211 if (!node) 212 return 0; 213 214 val = splay_tree_foreach_helper (sp, node->left, fn, data); 215 if (val) 216 return val; 217 218 val = (*fn)(node, data); 219 if (val) 220 return val; 221 222 return splay_tree_foreach_helper (sp, node->right, fn, data); 223} 224 225 226/* An allocator and deallocator based on xmalloc. */ 227static void * 228splay_tree_xmalloc_allocate (int size, void *data ATTRIBUTE_UNUSED) 229{ 230 return (void *) xmalloc (size); 231} 232 233static void 234splay_tree_xmalloc_deallocate (void *object, void *data ATTRIBUTE_UNUSED) 235{ 236 free (object); 237} 238 239 240/* Allocate a new splay tree, using COMPARE_FN to compare nodes, 241 DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate 242 values. Use xmalloc to allocate the splay tree structure, and any 243 nodes added. */ 244 245splay_tree 246splay_tree_new (splay_tree_compare_fn compare_fn, 247 splay_tree_delete_key_fn delete_key_fn, 248 splay_tree_delete_value_fn delete_value_fn) 249{ 250 return (splay_tree_new_with_allocator 251 (compare_fn, delete_key_fn, delete_value_fn, 252 splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate, 0)); 253} 254 255 256/* Allocate a new splay tree, using COMPARE_FN to compare nodes, 257 DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate 258 values. */ 259 260splay_tree 261splay_tree_new_with_allocator (splay_tree_compare_fn compare_fn, 262 splay_tree_delete_key_fn delete_key_fn, 263 splay_tree_delete_value_fn delete_value_fn, 264 splay_tree_allocate_fn allocate_fn, 265 splay_tree_deallocate_fn deallocate_fn, 266 void *allocate_data) 267{ 268 splay_tree sp = (splay_tree) (*allocate_fn) (sizeof (struct splay_tree_s), 269 allocate_data); 270 sp->root = 0; 271 sp->comp = compare_fn; 272 sp->delete_key = delete_key_fn; 273 sp->delete_value = delete_value_fn; 274 sp->allocate = allocate_fn; 275 sp->deallocate = deallocate_fn; 276 sp->allocate_data = allocate_data; 277 278 return sp; 279} 280 281/* Deallocate SP. */ 282 283void 284splay_tree_delete (splay_tree sp) 285{ 286 splay_tree_delete_helper (sp, sp->root); 287 (*sp->deallocate) ((char*) sp, sp->allocate_data); 288} 289 290/* Insert a new node (associating KEY with DATA) into SP. If a 291 previous node with the indicated KEY exists, its data is replaced 292 with the new value. Returns the new node. */ 293 294splay_tree_node 295splay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value) 296{ 297 int comparison = 0; 298 299 splay_tree_splay (sp, key); 300 301 if (sp->root) 302 comparison = (*sp->comp)(sp->root->key, key); 303 304 if (sp->root && comparison == 0) 305 { 306 /* If the root of the tree already has the indicated KEY, just 307 replace the value with VALUE. */ 308 if (sp->delete_value) 309 (*sp->delete_value)(sp->root->value); 310 sp->root->value = value; 311 } 312 else 313 { 314 /* Create a new node, and insert it at the root. */ 315 splay_tree_node node; 316 317 node = ((splay_tree_node) 318 (*sp->allocate) (sizeof (struct splay_tree_node_s), 319 sp->allocate_data)); 320 node->key = key; 321 node->value = value; 322 323 if (!sp->root) 324 node->left = node->right = 0; 325 else if (comparison < 0) 326 { 327 node->left = sp->root; 328 node->right = node->left->right; 329 node->left->right = 0; 330 } 331 else 332 { 333 node->right = sp->root; 334 node->left = node->right->left; 335 node->right->left = 0; 336 } 337 338 sp->root = node; 339 } 340 341 return sp->root; 342} 343 344/* Remove KEY from SP. It is not an error if it did not exist. */ 345 346void 347splay_tree_remove (splay_tree sp, splay_tree_key key) 348{ 349 splay_tree_splay (sp, key); 350 351 if (sp->root && (*sp->comp) (sp->root->key, key) == 0) 352 { 353 splay_tree_node left, right; 354 355 left = sp->root->left; 356 right = sp->root->right; 357 358 /* Delete the root node itself. */ 359 if (sp->delete_value) 360 (*sp->delete_value) (sp->root->value); 361 (*sp->deallocate) (sp->root, sp->allocate_data); 362 363 /* One of the children is now the root. Doesn't matter much 364 which, so long as we preserve the properties of the tree. */ 365 if (left) 366 { 367 sp->root = left; 368 369 /* If there was a right child as well, hang it off the 370 right-most leaf of the left child. */ 371 if (right) 372 { 373 while (left->right) 374 left = left->right; 375 left->right = right; 376 } 377 } 378 else 379 sp->root = right; 380 } 381} 382 383/* Lookup KEY in SP, returning VALUE if present, and NULL 384 otherwise. */ 385 386splay_tree_node 387splay_tree_lookup (splay_tree sp, splay_tree_key key) 388{ 389 splay_tree_splay (sp, key); 390 391 if (sp->root && (*sp->comp)(sp->root->key, key) == 0) 392 return sp->root; 393 else 394 return 0; 395} 396 397/* Return the node in SP with the greatest key. */ 398 399splay_tree_node 400splay_tree_max (splay_tree sp) 401{ 402 splay_tree_node n = sp->root; 403 404 if (!n) 405 return NULL; 406 407 while (n->right) 408 n = n->right; 409 410 return n; 411} 412 413/* Return the node in SP with the smallest key. */ 414 415splay_tree_node 416splay_tree_min (splay_tree sp) 417{ 418 splay_tree_node n = sp->root; 419 420 if (!n) 421 return NULL; 422 423 while (n->left) 424 n = n->left; 425 426 return n; 427} 428 429/* Return the immediate predecessor KEY, or NULL if there is no 430 predecessor. KEY need not be present in the tree. */ 431 432splay_tree_node 433splay_tree_predecessor (splay_tree sp, splay_tree_key key) 434{ 435 int comparison; 436 splay_tree_node node; 437 438 /* If the tree is empty, there is certainly no predecessor. */ 439 if (!sp->root) 440 return NULL; 441 442 /* Splay the tree around KEY. That will leave either the KEY 443 itself, its predecessor, or its successor at the root. */ 444 splay_tree_splay (sp, key); 445 comparison = (*sp->comp)(sp->root->key, key); 446 447 /* If the predecessor is at the root, just return it. */ 448 if (comparison < 0) 449 return sp->root; 450 451 /* Otherwise, find the rightmost element of the left subtree. */ 452 node = sp->root->left; 453 if (node) 454 while (node->right) 455 node = node->right; 456 457 return node; 458} 459 460/* Return the immediate successor KEY, or NULL if there is no 461 successor. KEY need not be present in the tree. */ 462 463splay_tree_node 464splay_tree_successor (splay_tree sp, splay_tree_key key) 465{ 466 int comparison; 467 splay_tree_node node; 468 469 /* If the tree is empty, there is certainly no successor. */ 470 if (!sp->root) 471 return NULL; 472 473 /* Splay the tree around KEY. That will leave either the KEY 474 itself, its predecessor, or its successor at the root. */ 475 splay_tree_splay (sp, key); 476 comparison = (*sp->comp)(sp->root->key, key); 477 478 /* If the successor is at the root, just return it. */ 479 if (comparison > 0) 480 return sp->root; 481 482 /* Otherwise, find the leftmost element of the right subtree. */ 483 node = sp->root->right; 484 if (node) 485 while (node->left) 486 node = node->left; 487 488 return node; 489} 490 491/* Call FN, passing it the DATA, for every node in SP, following an 492 in-order traversal. If FN every returns a non-zero value, the 493 iteration ceases immediately, and the value is returned. 494 Otherwise, this function returns 0. */ 495 496int 497splay_tree_foreach (splay_tree sp, splay_tree_foreach_fn fn, void *data) 498{ 499 return splay_tree_foreach_helper (sp, sp->root, fn, data); 500} 501 502/* Splay-tree comparison function, treating the keys as ints. */ 503 504int 505splay_tree_compare_ints (splay_tree_key k1, splay_tree_key k2) 506{ 507 if ((int) k1 < (int) k2) 508 return -1; 509 else if ((int) k1 > (int) k2) 510 return 1; 511 else 512 return 0; 513} 514 515/* Splay-tree comparison function, treating the keys as pointers. */ 516 517int 518splay_tree_compare_pointers (splay_tree_key k1, splay_tree_key k2) 519{ 520 if ((char*) k1 < (char*) k2) 521 return -1; 522 else if ((char*) k1 > (char*) k2) 523 return 1; 524 else 525 return 0; 526} 527