Mercurial > hg > CbC > CbC_gcc
annotate libiberty/fibheap.c @ 111:04ced10e8804
gcc 7
| author | kono |
|---|---|
| date | Fri, 27 Oct 2017 22:46:09 +0900 |
| parents | 77e2b8dfacca |
| children | 84e7813d76e9 |
| rev | line source |
|---|---|
| 0 | 1 /* A Fibonacci heap datatype. |
| 111 | 2 Copyright (C) 1998-2017 Free Software Foundation, Inc. |
| 0 | 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 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
217 /* Short-circuit if the key is the same, as we then don't have to |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
218 do anything. Except if we're trying to force the new node to |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
219 be the new minimum for delete. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
220 if (okey == key && okey != FIBHEAPKEY_MIN) |
| 0 | 221 return odata; |
| 222 | |
| 223 /* These two compares are specifically <= 0 to make sure that in the case | |
| 224 of equality, a node we replaced the data on, becomes the new min. This | |
| 225 is needed so that delete's call to extractmin gets the right node. */ | |
| 226 if (y != NULL && fibheap_compare (heap, node, y) <= 0) | |
| 227 { | |
| 228 fibheap_cut (heap, node, y); | |
| 229 fibheap_cascading_cut (heap, y); | |
| 230 } | |
| 231 | |
| 232 if (fibheap_compare (heap, node, heap->min) <= 0) | |
| 233 heap->min = node; | |
| 234 | |
| 235 return odata; | |
| 236 } | |
| 237 | |
| 238 /* Replace the DATA associated with NODE. */ | |
| 239 void * | |
| 240 fibheap_replace_data (fibheap_t heap, fibnode_t node, void *data) | |
| 241 { | |
| 242 return fibheap_replace_key_data (heap, node, node->key, data); | |
| 243 } | |
| 244 | |
| 245 /* Replace the KEY associated with NODE. */ | |
| 246 fibheapkey_t | |
| 247 fibheap_replace_key (fibheap_t heap, fibnode_t node, fibheapkey_t key) | |
| 248 { | |
| 249 int okey = node->key; | |
| 250 fibheap_replace_key_data (heap, node, key, node->data); | |
| 251 return okey; | |
| 252 } | |
| 253 | |
| 254 /* Delete NODE from HEAP. */ | |
| 255 void * | |
| 256 fibheap_delete_node (fibheap_t heap, fibnode_t node) | |
| 257 { | |
| 258 void *ret = node->data; | |
| 259 | |
| 260 /* To perform delete, we just make it the min key, and extract. */ | |
| 261 fibheap_replace_key (heap, node, FIBHEAPKEY_MIN); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
262 if (node != heap->min) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
263 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
264 fprintf (stderr, "Can't force minimum on fibheap.\n"); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
265 abort (); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
266 } |
| 0 | 267 fibheap_extract_min (heap); |
| 268 | |
| 269 return ret; | |
| 270 } | |
| 271 | |
| 272 /* Delete HEAP. */ | |
| 273 void | |
| 274 fibheap_delete (fibheap_t heap) | |
| 275 { | |
| 276 while (heap->min != NULL) | |
| 277 free (fibheap_extr_min_node (heap)); | |
| 278 | |
| 279 free (heap); | |
| 280 } | |
| 281 | |
| 282 /* Determine if HEAP is empty. */ | |
| 283 int | |
| 284 fibheap_empty (fibheap_t heap) | |
| 285 { | |
| 286 return heap->nodes == 0; | |
| 287 } | |
| 288 | |
| 289 /* Extract the minimum node of the heap. */ | |
| 290 static fibnode_t | |
| 291 fibheap_extr_min_node (fibheap_t heap) | |
| 292 { | |
| 293 fibnode_t ret = heap->min; | |
| 294 fibnode_t x, y, orig; | |
| 295 | |
| 296 /* Attach the child list of the minimum node to the root list of the heap. | |
| 297 If there is no child list, we don't do squat. */ | |
| 298 for (x = ret->child, orig = NULL; x != orig && x != NULL; x = y) | |
| 299 { | |
| 300 if (orig == NULL) | |
| 301 orig = x; | |
| 302 y = x->right; | |
| 303 x->parent = NULL; | |
| 304 fibheap_ins_root (heap, x); | |
| 305 } | |
| 306 | |
| 307 /* Remove the old root. */ | |
| 308 fibheap_rem_root (heap, ret); | |
| 309 heap->nodes--; | |
| 310 | |
| 311 /* If we are left with no nodes, then the min is NULL. */ | |
| 312 if (heap->nodes == 0) | |
| 313 heap->min = NULL; | |
| 314 else | |
| 315 { | |
| 316 /* Otherwise, consolidate to find new minimum, as well as do the reorg | |
| 317 work that needs to be done. */ | |
| 318 heap->min = ret->right; | |
| 319 fibheap_consolidate (heap); | |
| 320 } | |
| 321 | |
| 322 return ret; | |
| 323 } | |
| 324 | |
| 325 /* Insert NODE into the root list of HEAP. */ | |
| 326 static void | |
| 327 fibheap_ins_root (fibheap_t heap, fibnode_t node) | |
| 328 { | |
| 329 /* If the heap is currently empty, the new node becomes the singleton | |
| 330 circular root list. */ | |
| 331 if (heap->root == NULL) | |
| 332 { | |
| 333 heap->root = node; | |
| 334 node->left = node; | |
| 335 node->right = node; | |
| 336 return; | |
| 337 } | |
| 338 | |
| 339 /* Otherwise, insert it in the circular root list between the root | |
| 340 and it's right node. */ | |
| 341 fibnode_insert_after (heap->root, node); | |
| 342 } | |
| 343 | |
| 344 /* Remove NODE from the rootlist of HEAP. */ | |
| 345 static void | |
| 346 fibheap_rem_root (fibheap_t heap, fibnode_t node) | |
| 347 { | |
| 348 if (node->left == node) | |
| 349 heap->root = NULL; | |
| 350 else | |
| 351 heap->root = fibnode_remove (node); | |
| 352 } | |
| 353 | |
| 354 /* Consolidate the heap. */ | |
| 355 static void | |
| 356 fibheap_consolidate (fibheap_t heap) | |
| 357 { | |
| 358 fibnode_t a[1 + 8 * sizeof (long)]; | |
| 359 fibnode_t w; | |
| 360 fibnode_t y; | |
| 361 fibnode_t x; | |
| 362 int i; | |
| 363 int d; | |
| 364 int D; | |
| 365 | |
| 366 D = 1 + 8 * sizeof (long); | |
| 367 | |
| 368 memset (a, 0, sizeof (fibnode_t) * D); | |
| 369 | |
| 370 while ((w = heap->root) != NULL) | |
| 371 { | |
| 372 x = w; | |
| 373 fibheap_rem_root (heap, w); | |
| 374 d = x->degree; | |
| 375 while (a[d] != NULL) | |
| 376 { | |
| 377 y = a[d]; | |
| 378 if (fibheap_compare (heap, x, y) > 0) | |
| 379 { | |
| 380 fibnode_t temp; | |
| 381 temp = x; | |
| 382 x = y; | |
| 383 y = temp; | |
| 384 } | |
| 385 fibheap_link (heap, y, x); | |
| 386 a[d] = NULL; | |
| 387 d++; | |
| 388 } | |
| 389 a[d] = x; | |
| 390 } | |
| 391 heap->min = NULL; | |
| 392 for (i = 0; i < D; i++) | |
| 393 if (a[i] != NULL) | |
| 394 { | |
| 395 fibheap_ins_root (heap, a[i]); | |
| 396 if (heap->min == NULL || fibheap_compare (heap, a[i], heap->min) < 0) | |
| 397 heap->min = a[i]; | |
| 398 } | |
| 399 } | |
| 400 | |
| 401 /* Make NODE a child of PARENT. */ | |
| 402 static void | |
| 403 fibheap_link (fibheap_t heap ATTRIBUTE_UNUSED, | |
| 404 fibnode_t node, fibnode_t parent) | |
| 405 { | |
| 406 if (parent->child == NULL) | |
| 407 parent->child = node; | |
| 408 else | |
| 409 fibnode_insert_before (parent->child, node); | |
| 410 node->parent = parent; | |
| 411 parent->degree++; | |
| 412 node->mark = 0; | |
| 413 } | |
| 414 | |
| 415 /* Remove NODE from PARENT's child list. */ | |
| 416 static void | |
| 417 fibheap_cut (fibheap_t heap, fibnode_t node, fibnode_t parent) | |
| 418 { | |
| 419 fibnode_remove (node); | |
| 420 parent->degree--; | |
| 421 fibheap_ins_root (heap, node); | |
| 422 node->parent = NULL; | |
| 423 node->mark = 0; | |
| 424 } | |
| 425 | |
| 426 static void | |
| 427 fibheap_cascading_cut (fibheap_t heap, fibnode_t y) | |
| 428 { | |
| 429 fibnode_t z; | |
| 430 | |
| 431 while ((z = y->parent) != NULL) | |
| 432 { | |
| 433 if (y->mark == 0) | |
| 434 { | |
| 435 y->mark = 1; | |
| 436 return; | |
| 437 } | |
| 438 else | |
| 439 { | |
| 440 fibheap_cut (heap, y, z); | |
| 441 y = z; | |
| 442 } | |
| 443 } | |
| 444 } | |
| 445 | |
| 446 static void | |
| 447 fibnode_insert_after (fibnode_t a, fibnode_t b) | |
| 448 { | |
| 449 if (a == a->right) | |
| 450 { | |
| 451 a->right = b; | |
| 452 a->left = b; | |
| 453 b->right = a; | |
| 454 b->left = a; | |
| 455 } | |
| 456 else | |
| 457 { | |
| 458 b->right = a->right; | |
| 459 a->right->left = b; | |
| 460 a->right = b; | |
| 461 b->left = a; | |
| 462 } | |
| 463 } | |
| 464 | |
| 465 static fibnode_t | |
| 466 fibnode_remove (fibnode_t node) | |
| 467 { | |
| 468 fibnode_t ret; | |
| 469 | |
| 470 if (node == node->left) | |
| 471 ret = NULL; | |
| 472 else | |
| 473 ret = node->left; | |
| 474 | |
| 475 if (node->parent != NULL && node->parent->child == node) | |
| 476 node->parent->child = ret; | |
| 477 | |
| 478 node->right->left = node->left; | |
| 479 node->left->right = node->right; | |
| 480 | |
| 481 node->parent = NULL; | |
| 482 node->left = node; | |
| 483 node->right = node; | |
| 484 | |
| 485 return ret; | |
| 486 } |