fibheap.c revision 130562
1/* A Fibonacci heap datatype. 2 Copyright 1998, 1999, 2000, 2001 Free Software Foundation, Inc. 3 Contributed by Daniel Berlin (dan@cgsoftware.com). 4 5This file is part of GNU CC. 6 7GNU CC is free software; you can redistribute it and/or modify it 8under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 2, or (at your option) 10any later version. 11 12GNU CC is distributed in the hope that it will be useful, but 13WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along with GNU CC; see the file COPYING. If not, write to 19the Free Software Foundation, 59 Temple Place - Suite 330, 20Boston, MA 02111-1307, USA. */ 21 22#ifdef HAVE_CONFIG_H 23#include "config.h" 24#endif 25#ifdef HAVE_LIMITS_H 26#include <limits.h> 27#endif 28#ifdef HAVE_STDLIB_H 29#include <stdlib.h> 30#endif 31#ifdef HAVE_STRING_H 32#include <string.h> 33#endif 34#include "libiberty.h" 35#include "fibheap.h" 36 37 38#define FIBHEAPKEY_MIN LONG_MIN 39 40static void fibheap_ins_root PARAMS ((fibheap_t, fibnode_t)); 41static void fibheap_rem_root PARAMS ((fibheap_t, fibnode_t)); 42static void fibheap_consolidate PARAMS ((fibheap_t)); 43static void fibheap_link PARAMS ((fibheap_t, fibnode_t, fibnode_t)); 44static void fibheap_cut PARAMS ((fibheap_t, fibnode_t, fibnode_t)); 45static void fibheap_cascading_cut PARAMS ((fibheap_t, fibnode_t)); 46static fibnode_t fibheap_extr_min_node PARAMS ((fibheap_t)); 47static int fibheap_compare PARAMS ((fibheap_t, fibnode_t, fibnode_t)); 48static int fibheap_comp_data PARAMS ((fibheap_t, fibheapkey_t, void *, 49 fibnode_t)); 50static fibnode_t fibnode_new PARAMS ((void)); 51static void fibnode_insert_after PARAMS ((fibnode_t, fibnode_t)); 52#define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b) 53static fibnode_t fibnode_remove PARAMS ((fibnode_t)); 54 55 56/* Create a new fibonacci heap. */ 57fibheap_t 58fibheap_new () 59{ 60 return (fibheap_t) xcalloc (1, sizeof (struct fibheap)); 61} 62 63/* Create a new fibonacci heap node. */ 64static fibnode_t 65fibnode_new () 66{ 67 fibnode_t node; 68 69 node = (fibnode_t) xcalloc (1, sizeof *node); 70 node->left = node; 71 node->right = node; 72 73 return node; 74} 75 76static inline int 77fibheap_compare (heap, a, b) 78 fibheap_t heap ATTRIBUTE_UNUSED; 79 fibnode_t a; 80 fibnode_t b; 81{ 82 if (a->key < b->key) 83 return -1; 84 if (a->key > b->key) 85 return 1; 86 return 0; 87} 88 89static inline int 90fibheap_comp_data (heap, key, data, b) 91 fibheap_t heap; 92 fibheapkey_t key; 93 void *data; 94 fibnode_t b; 95{ 96 struct fibnode a; 97 98 a.key = key; 99 a.data = data; 100 101 return fibheap_compare (heap, &a, b); 102} 103 104/* Insert DATA, with priority KEY, into HEAP. */ 105fibnode_t 106fibheap_insert (heap, key, data) 107 fibheap_t heap; 108 fibheapkey_t key; 109 void *data; 110{ 111 fibnode_t node; 112 113 /* Create the new node. */ 114 node = fibnode_new (); 115 116 /* Set the node's data. */ 117 node->data = data; 118 node->key = key; 119 120 /* Insert it into the root list. */ 121 fibheap_ins_root (heap, node); 122 123 /* If their was no minimum, or this key is less than the min, 124 it's the new min. */ 125 if (heap->min == NULL || node->key < heap->min->key) 126 heap->min = node; 127 128 heap->nodes++; 129 130 return node; 131} 132 133/* Return the data of the minimum node (if we know it). */ 134void * 135fibheap_min (heap) 136 fibheap_t heap; 137{ 138 /* If there is no min, we can't easily return it. */ 139 if (heap->min == NULL) 140 return NULL; 141 return heap->min->data; 142} 143 144/* Return the key of the minimum node (if we know it). */ 145fibheapkey_t 146fibheap_min_key (heap) 147 fibheap_t heap; 148{ 149 /* If there is no min, we can't easily return it. */ 150 if (heap->min == NULL) 151 return 0; 152 return heap->min->key; 153} 154 155/* Union HEAPA and HEAPB into a new heap. */ 156fibheap_t 157fibheap_union (heapa, heapb) 158 fibheap_t heapa; 159 fibheap_t heapb; 160{ 161 fibnode_t a_root, b_root, temp; 162 163 /* If one of the heaps is empty, the union is just the other heap. */ 164 if ((a_root = heapa->root) == NULL) 165 { 166 free (heapa); 167 return heapb; 168 } 169 if ((b_root = heapb->root) == NULL) 170 { 171 free (heapb); 172 return heapa; 173 } 174 175 /* Merge them to the next nodes on the opposite chain. */ 176 a_root->left->right = b_root; 177 b_root->left->right = a_root; 178 temp = a_root->left; 179 a_root->left = b_root->left; 180 b_root->left = temp; 181 heapa->nodes += heapb->nodes; 182 183 /* And set the new minimum, if it's changed. */ 184 if (fibheap_compare (heapa, heapb->min, heapa->min) < 0) 185 heapa->min = heapb->min; 186 187 free (heapb); 188 return heapa; 189} 190 191/* Extract the data of the minimum node from HEAP. */ 192void * 193fibheap_extract_min (heap) 194 fibheap_t heap; 195{ 196 fibnode_t z; 197 void *ret = NULL; 198 199 /* If we don't have a min set, it means we have no nodes. */ 200 if (heap->min != NULL) 201 { 202 /* Otherwise, extract the min node, free the node, and return the 203 node's data. */ 204 z = fibheap_extr_min_node (heap); 205 ret = z->data; 206 free (z); 207 } 208 209 return ret; 210} 211 212/* Replace both the KEY and the DATA associated with NODE. */ 213void * 214fibheap_replace_key_data (heap, node, key, data) 215 fibheap_t heap; 216 fibnode_t node; 217 fibheapkey_t key; 218 void *data; 219{ 220 void *odata; 221 fibheapkey_t okey; 222 fibnode_t y; 223 224 /* If we wanted to, we could actually do a real increase by redeleting and 225 inserting. However, this would require O (log n) time. So just bail out 226 for now. */ 227 if (fibheap_comp_data (heap, key, data, node) > 0) 228 return NULL; 229 230 odata = node->data; 231 okey = node->key; 232 node->data = data; 233 node->key = key; 234 y = node->parent; 235 236 if (okey == key) 237 return odata; 238 239 /* These two compares are specifically <= 0 to make sure that in the case 240 of equality, a node we replaced the data on, becomes the new min. This 241 is needed so that delete's call to extractmin gets the right node. */ 242 if (y != NULL && fibheap_compare (heap, node, y) <= 0) 243 { 244 fibheap_cut (heap, node, y); 245 fibheap_cascading_cut (heap, y); 246 } 247 248 if (fibheap_compare (heap, node, heap->min) <= 0) 249 heap->min = node; 250 251 return odata; 252} 253 254/* Replace the DATA associated with NODE. */ 255void * 256fibheap_replace_data (heap, node, data) 257 fibheap_t heap; 258 fibnode_t node; 259 void *data; 260{ 261 return fibheap_replace_key_data (heap, node, node->key, data); 262} 263 264/* Replace the KEY associated with NODE. */ 265fibheapkey_t 266fibheap_replace_key (heap, node, key) 267 fibheap_t heap; 268 fibnode_t node; 269 fibheapkey_t key; 270{ 271 int okey = node->key; 272 fibheap_replace_key_data (heap, node, key, node->data); 273 return okey; 274} 275 276/* Delete NODE from HEAP. */ 277void * 278fibheap_delete_node (heap, node) 279 fibheap_t heap; 280 fibnode_t node; 281{ 282 void *ret = node->data; 283 284 /* To perform delete, we just make it the min key, and extract. */ 285 fibheap_replace_key (heap, node, FIBHEAPKEY_MIN); 286 fibheap_extract_min (heap); 287 288 return ret; 289} 290 291/* Delete HEAP. */ 292void 293fibheap_delete (heap) 294 fibheap_t heap; 295{ 296 while (heap->min != NULL) 297 free (fibheap_extr_min_node (heap)); 298 299 free (heap); 300} 301 302/* Determine if HEAP is empty. */ 303int 304fibheap_empty (heap) 305 fibheap_t heap; 306{ 307 return heap->nodes == 0; 308} 309 310/* Extract the minimum node of the heap. */ 311static fibnode_t 312fibheap_extr_min_node (heap) 313 fibheap_t heap; 314{ 315 fibnode_t ret = heap->min; 316 fibnode_t x, y, orig; 317 318 /* Attach the child list of the minimum node to the root list of the heap. 319 If there is no child list, we don't do squat. */ 320 for (x = ret->child, orig = NULL; x != orig && x != NULL; x = y) 321 { 322 if (orig == NULL) 323 orig = x; 324 y = x->right; 325 x->parent = NULL; 326 fibheap_ins_root (heap, x); 327 } 328 329 /* Remove the old root. */ 330 fibheap_rem_root (heap, ret); 331 heap->nodes--; 332 333 /* If we are left with no nodes, then the min is NULL. */ 334 if (heap->nodes == 0) 335 heap->min = NULL; 336 else 337 { 338 /* Otherwise, consolidate to find new minimum, as well as do the reorg 339 work that needs to be done. */ 340 heap->min = ret->right; 341 fibheap_consolidate (heap); 342 } 343 344 return ret; 345} 346 347/* Insert NODE into the root list of HEAP. */ 348static void 349fibheap_ins_root (heap, node) 350 fibheap_t heap; 351 fibnode_t node; 352{ 353 /* If the heap is currently empty, the new node becomes the singleton 354 circular root list. */ 355 if (heap->root == NULL) 356 { 357 heap->root = node; 358 node->left = node; 359 node->right = node; 360 return; 361 } 362 363 /* Otherwise, insert it in the circular root list between the root 364 and it's right node. */ 365 fibnode_insert_after (heap->root, node); 366} 367 368/* Remove NODE from the rootlist of HEAP. */ 369static void 370fibheap_rem_root (heap, node) 371 fibheap_t heap; 372 fibnode_t node; 373{ 374 if (node->left == node) 375 heap->root = NULL; 376 else 377 heap->root = fibnode_remove (node); 378} 379 380/* Consolidate the heap. */ 381static void 382fibheap_consolidate (heap) 383 fibheap_t heap; 384{ 385 fibnode_t a[1 + 8 * sizeof (long)]; 386 fibnode_t w; 387 fibnode_t y; 388 fibnode_t x; 389 int i; 390 int d; 391 int D; 392 393 D = 1 + 8 * sizeof (long); 394 395 memset (a, 0, sizeof (fibnode_t) * D); 396 397 while ((w = heap->root) != NULL) 398 { 399 x = w; 400 fibheap_rem_root (heap, w); 401 d = x->degree; 402 while (a[d] != NULL) 403 { 404 y = a[d]; 405 if (fibheap_compare (heap, x, y) > 0) 406 { 407 fibnode_t temp; 408 temp = x; 409 x = y; 410 y = temp; 411 } 412 fibheap_link (heap, y, x); 413 a[d] = NULL; 414 d++; 415 } 416 a[d] = x; 417 } 418 heap->min = NULL; 419 for (i = 0; i < D; i++) 420 if (a[i] != NULL) 421 { 422 fibheap_ins_root (heap, a[i]); 423 if (heap->min == NULL || fibheap_compare (heap, a[i], heap->min) < 0) 424 heap->min = a[i]; 425 } 426} 427 428/* Make NODE a child of PARENT. */ 429static void 430fibheap_link (heap, node, parent) 431 fibheap_t heap ATTRIBUTE_UNUSED; 432 fibnode_t node; 433 fibnode_t parent; 434{ 435 if (parent->child == NULL) 436 parent->child = node; 437 else 438 fibnode_insert_before (parent->child, node); 439 node->parent = parent; 440 parent->degree++; 441 node->mark = 0; 442} 443 444/* Remove NODE from PARENT's child list. */ 445static void 446fibheap_cut (heap, node, parent) 447 fibheap_t heap; 448 fibnode_t node; 449 fibnode_t parent; 450{ 451 fibnode_remove (node); 452 parent->degree--; 453 fibheap_ins_root (heap, node); 454 node->parent = NULL; 455 node->mark = 0; 456} 457 458static void 459fibheap_cascading_cut (heap, y) 460 fibheap_t heap; 461 fibnode_t y; 462{ 463 fibnode_t z; 464 465 while ((z = y->parent) != NULL) 466 { 467 if (y->mark == 0) 468 { 469 y->mark = 1; 470 return; 471 } 472 else 473 { 474 fibheap_cut (heap, y, z); 475 y = z; 476 } 477 } 478} 479 480static void 481fibnode_insert_after (a, b) 482 fibnode_t a; 483 fibnode_t b; 484{ 485 if (a == a->right) 486 { 487 a->right = b; 488 a->left = b; 489 b->right = a; 490 b->left = a; 491 } 492 else 493 { 494 b->right = a->right; 495 a->right->left = b; 496 a->right = b; 497 b->left = a; 498 } 499} 500 501static fibnode_t 502fibnode_remove (node) 503 fibnode_t node; 504{ 505 fibnode_t ret; 506 507 if (node == node->left) 508 ret = NULL; 509 else 510 ret = node->left; 511 512 if (node->parent != NULL && node->parent->child == node) 513 node->parent->child = ret; 514 515 node->right->left = node->left; 516 node->left->right = node->right; 517 518 node->parent = NULL; 519 node->left = node; 520 node->right = node; 521 522 return ret; 523} 524