1 /* A Fibonacci heap datatype.
2 Copyright (C) 1998-2023 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 /* Short-circuit if the key is the same, as we then don't have to
218 do anything. Except if we're trying to force the new node to
219 be the new minimum for delete. */
220 if (okey == key && okey != FIBHEAPKEY_MIN)
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);
262 if (node != heap->min)
263 {
264 fprintf (stderr, "Can't force minimum on fibheap.\n");
265 abort ();
266 }
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 }