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, 51 Franklin Street - Fifth Floor, 20Boston, MA 02110-1301, 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 (fibheap_t, fibnode_t); 41static void fibheap_rem_root (fibheap_t, fibnode_t); 42static void fibheap_consolidate (fibheap_t); 43static void fibheap_link (fibheap_t, fibnode_t, fibnode_t); 44static void fibheap_cut (fibheap_t, fibnode_t, fibnode_t); 45static void fibheap_cascading_cut (fibheap_t, fibnode_t); 46static fibnode_t fibheap_extr_min_node (fibheap_t); 47static int fibheap_compare (fibheap_t, fibnode_t, fibnode_t); 48static int fibheap_comp_data (fibheap_t, fibheapkey_t, void *, fibnode_t); 49static fibnode_t fibnode_new (void); 50static void fibnode_insert_after (fibnode_t, fibnode_t); 51#define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b) 52static fibnode_t fibnode_remove (fibnode_t); 53 54 55/* Create a new fibonacci heap. */ 56fibheap_t 57fibheap_new (void) 58{ 59 return (fibheap_t) xcalloc (1, sizeof (struct fibheap)); 60} 61 62/* Create a new fibonacci heap node. */ 63static fibnode_t 64fibnode_new (void) 65{ 66 fibnode_t node; 67 68 node = (fibnode_t) xcalloc (1, sizeof *node); 69 node->left = node; 70 node->right = node; 71 72 return node; 73} 74 75static inline int 76fibheap_compare (fibheap_t heap ATTRIBUTE_UNUSED, fibnode_t a, fibnode_t b) 77{ 78 if (a->key < b->key) 79 return -1; 80 if (a->key > b->key) 81 return 1; 82 return 0; 83} 84 85static inline int 86fibheap_comp_data (fibheap_t heap, fibheapkey_t key, void *data, fibnode_t b) 87{ 88 struct fibnode a; 89 90 a.key = key; 91 a.data = data; 92 93 return fibheap_compare (heap, &a, b); 94} 95 96/* Insert DATA, with priority KEY, into HEAP. */ 97fibnode_t 98fibheap_insert (fibheap_t heap, fibheapkey_t key, void *data) 99{ 100 fibnode_t node; 101 102 /* Create the new node. */ 103 node = fibnode_new (); 104 105 /* Set the node's data. */ 106 node->data = data; 107 node->key = key; 108 109 /* Insert it into the root list. */ 110 fibheap_ins_root (heap, node); 111 112 /* If their was no minimum, or this key is less than the min, 113 it's the new min. */ 114 if (heap->min == NULL || node->key < heap->min->key) 115 heap->min = node; 116 117 heap->nodes++; 118 119 return node; 120} 121 122/* Return the data of the minimum node (if we know it). */ 123void * 124fibheap_min (fibheap_t heap) 125{ 126 /* If there is no min, we can't easily return it. */ 127 if (heap->min == NULL) 128 return NULL; 129 return heap->min->data; 130} 131 132/* Return the key of the minimum node (if we know it). */ 133fibheapkey_t 134fibheap_min_key (fibheap_t heap) 135{ 136 /* If there is no min, we can't easily return it. */ 137 if (heap->min == NULL) 138 return 0; 139 return heap->min->key; 140} 141 142/* Union HEAPA and HEAPB into a new heap. */ 143fibheap_t 144fibheap_union (fibheap_t heapa, fibheap_t heapb) 145{ 146 fibnode_t a_root, b_root, temp; 147 148 /* If one of the heaps is empty, the union is just the other heap. */ 149 if ((a_root = heapa->root) == NULL) 150 { 151 free (heapa); 152 return heapb; 153 } 154 if ((b_root = heapb->root) == NULL) 155 { 156 free (heapb); 157 return heapa; 158 } 159 160 /* Merge them to the next nodes on the opposite chain. */ 161 a_root->left->right = b_root; 162 b_root->left->right = a_root; 163 temp = a_root->left; 164 a_root->left = b_root->left; 165 b_root->left = temp; 166 heapa->nodes += heapb->nodes; 167 168 /* And set the new minimum, if it's changed. */ 169 if (fibheap_compare (heapa, heapb->min, heapa->min) < 0) 170 heapa->min = heapb->min; 171 172 free (heapb); 173 return heapa; 174} 175 176/* Extract the data of the minimum node from HEAP. */ 177void * 178fibheap_extract_min (fibheap_t heap) 179{ 180 fibnode_t z; 181 void *ret = NULL; 182 183 /* If we don't have a min set, it means we have no nodes. */ 184 if (heap->min != NULL) 185 { 186 /* Otherwise, extract the min node, free the node, and return the 187 node's data. */ 188 z = fibheap_extr_min_node (heap); 189 ret = z->data; 190 free (z); 191 } 192 193 return ret; 194} 195 196/* Replace both the KEY and the DATA associated with NODE. */ 197void * 198fibheap_replace_key_data (fibheap_t heap, fibnode_t node, 199 fibheapkey_t key, void *data) 200{ 201 void *odata; 202 fibheapkey_t okey; 203 fibnode_t y; 204 205 /* If we wanted to, we could actually do a real increase by redeleting and 206 inserting. However, this would require O (log n) time. So just bail out 207 for now. */ 208 if (fibheap_comp_data (heap, key, data, node) > 0) 209 return NULL; 210 211 odata = node->data; 212 okey = node->key; 213 node->data = data; 214 node->key = key; 215 y = node->parent; 216 217 if (okey == key) 218 return odata; 219 220 /* These two compares are specifically <= 0 to make sure that in the case 221 of equality, a node we replaced the data on, becomes the new min. This 222 is needed so that delete's call to extractmin gets the right node. */ 223 if (y != NULL && fibheap_compare (heap, node, y) <= 0) 224 { 225 fibheap_cut (heap, node, y); 226 fibheap_cascading_cut (heap, y); 227 } 228 229 if (fibheap_compare (heap, node, heap->min) <= 0) 230 heap->min = node; 231 232 return odata; 233} 234 235/* Replace the DATA associated with NODE. */ 236void * 237fibheap_replace_data (fibheap_t heap, fibnode_t node, void *data) 238{ 239 return fibheap_replace_key_data (heap, node, node->key, data); 240} 241 242/* Replace the KEY associated with NODE. */ 243fibheapkey_t 244fibheap_replace_key (fibheap_t heap, fibnode_t node, fibheapkey_t key) 245{ 246 int okey = node->key; 247 fibheap_replace_key_data (heap, node, key, node->data); 248 return okey; 249} 250 251/* Delete NODE from HEAP. */ 252void * 253fibheap_delete_node (fibheap_t heap, fibnode_t node) 254{ 255 void *ret = node->data; 256 257 /* To perform delete, we just make it the min key, and extract. */ 258 fibheap_replace_key (heap, node, FIBHEAPKEY_MIN); 259 fibheap_extract_min (heap); 260 261 return ret; 262} 263 264/* Delete HEAP. */ 265void 266fibheap_delete (fibheap_t heap) 267{ 268 while (heap->min != NULL) 269 free (fibheap_extr_min_node (heap)); 270 271 free (heap); 272} 273 274/* Determine if HEAP is empty. */ 275int 276fibheap_empty (fibheap_t heap) 277{ 278 return heap->nodes == 0; 279} 280 281/* Extract the minimum node of the heap. */ 282static fibnode_t 283fibheap_extr_min_node (fibheap_t heap) 284{ 285 fibnode_t ret = heap->min; 286 fibnode_t x, y, orig; 287 288 /* Attach the child list of the minimum node to the root list of the heap. 289 If there is no child list, we don't do squat. */ 290 for (x = ret->child, orig = NULL; x != orig && x != NULL; x = y) 291 { 292 if (orig == NULL) 293 orig = x; 294 y = x->right; 295 x->parent = NULL; 296 fibheap_ins_root (heap, x); 297 } 298 299 /* Remove the old root. */ 300 fibheap_rem_root (heap, ret); 301 heap->nodes--; 302 303 /* If we are left with no nodes, then the min is NULL. */ 304 if (heap->nodes == 0) 305 heap->min = NULL; 306 else 307 { 308 /* Otherwise, consolidate to find new minimum, as well as do the reorg 309 work that needs to be done. */ 310 heap->min = ret->right; 311 fibheap_consolidate (heap); 312 } 313 314 return ret; 315} 316 317/* Insert NODE into the root list of HEAP. */ 318static void 319fibheap_ins_root (fibheap_t heap, fibnode_t node) 320{ 321 /* If the heap is currently empty, the new node becomes the singleton 322 circular root list. */ 323 if (heap->root == NULL) 324 { 325 heap->root = node; 326 node->left = node; 327 node->right = node; 328 return; 329 } 330 331 /* Otherwise, insert it in the circular root list between the root 332 and it's right node. */ 333 fibnode_insert_after (heap->root, node); 334} 335 336/* Remove NODE from the rootlist of HEAP. */ 337static void 338fibheap_rem_root (fibheap_t heap, fibnode_t node) 339{ 340 if (node->left == node) 341 heap->root = NULL; 342 else 343 heap->root = fibnode_remove (node); 344} 345 346/* Consolidate the heap. */ 347static void 348fibheap_consolidate (fibheap_t heap) 349{ 350 fibnode_t a[1 + 8 * sizeof (long)]; 351 fibnode_t w; 352 fibnode_t y; 353 fibnode_t x; 354 int i; 355 int d; 356 int D; 357 358 D = 1 + 8 * sizeof (long); 359 360 memset (a, 0, sizeof (fibnode_t) * D); 361 362 while ((w = heap->root) != NULL) 363 { 364 x = w; 365 fibheap_rem_root (heap, w); 366 d = x->degree; 367 while (a[d] != NULL) 368 { 369 y = a[d]; 370 if (fibheap_compare (heap, x, y) > 0) 371 { 372 fibnode_t temp; 373 temp = x; 374 x = y; 375 y = temp; 376 } 377 fibheap_link (heap, y, x); 378 a[d] = NULL; 379 d++; 380 } 381 a[d] = x; 382 } 383 heap->min = NULL; 384 for (i = 0; i < D; i++) 385 if (a[i] != NULL) 386 { 387 fibheap_ins_root (heap, a[i]); 388 if (heap->min == NULL || fibheap_compare (heap, a[i], heap->min) < 0) 389 heap->min = a[i]; 390 } 391} 392 393/* Make NODE a child of PARENT. */ 394static void 395fibheap_link (fibheap_t heap ATTRIBUTE_UNUSED, 396 fibnode_t node, fibnode_t parent) 397{ 398 if (parent->child == NULL) 399 parent->child = node; 400 else 401 fibnode_insert_before (parent->child, node); 402 node->parent = parent; 403 parent->degree++; 404 node->mark = 0; 405} 406 407/* Remove NODE from PARENT's child list. */ 408static void 409fibheap_cut (fibheap_t heap, fibnode_t node, fibnode_t parent) 410{ 411 fibnode_remove (node); 412 parent->degree--; 413 fibheap_ins_root (heap, node); 414 node->parent = NULL; 415 node->mark = 0; 416} 417 418static void 419fibheap_cascading_cut (fibheap_t heap, fibnode_t y) 420{ 421 fibnode_t z; 422 423 while ((z = y->parent) != NULL) 424 { 425 if (y->mark == 0) 426 { 427 y->mark = 1; 428 return; 429 } 430 else 431 { 432 fibheap_cut (heap, y, z); 433 y = z; 434 } 435 } 436} 437 438static void 439fibnode_insert_after (fibnode_t a, fibnode_t b) 440{ 441 if (a == a->right) 442 { 443 a->right = b; 444 a->left = b; 445 b->right = a; 446 b->left = a; 447 } 448 else 449 { 450 b->right = a->right; 451 a->right->left = b; 452 a->right = b; 453 b->left = a; 454 } 455} 456 457static fibnode_t 458fibnode_remove (fibnode_t node) 459{ 460 fibnode_t ret; 461 462 if (node == node->left) 463 ret = NULL; 464 else 465 ret = node->left; 466 467 if (node->parent != NULL && node->parent->child == node) 468 node->parent->child = ret; 469 470 node->right->left = node->left; 471 node->left->right = node->right; 472 473 node->parent = NULL; 474 node->left = node; 475 node->right = node; 476 477 return ret; 478} 479