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