1 /* A Fibonacci heap datatype. 2 Copyright 1998, 1999, 2000, 2001 Free Software Foundation, Inc. 3 Contributed by Daniel Berlin (dan@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. */ 56 fibheap_t 57 fibheap_new (void) 58 { 59 return (fibheap_t) xcalloc (1, sizeof (struct fibheap)); 60 } 61 62 /* Create a new fibonacci heap node. */ 63 static fibnode_t 64 fibnode_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 75 static inline int 76 fibheap_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 85 static inline int 86 fibheap_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. */ 97 fibnode_t 98 fibheap_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). */ 123 void * 124 fibheap_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). */ 133 fibheapkey_t 134 fibheap_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. */ 143 fibheap_t 144 fibheap_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. */ 177 void * 178 fibheap_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. */ 197 void * 198 fibheap_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. */ 236 void * 237 fibheap_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. */ 243 fibheapkey_t 244 fibheap_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. */ 252 void * 253 fibheap_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. */ 265 void 266 fibheap_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. */ 275 int 276 fibheap_empty (fibheap_t heap) 277 { 278 return heap->nodes == 0; 279 } 280 281 /* Extract the minimum node of the heap. */ 282 static fibnode_t 283 fibheap_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. */ 318 static void 319 fibheap_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. */ 337 static void 338 fibheap_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. */ 347 static void 348 fibheap_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. */ 394 static void 395 fibheap_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. */ 408 static void 409 fibheap_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 418 static void 419 fibheap_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 438 static void 439 fibnode_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 457 static fibnode_t 458 fibnode_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