1 /* Fibonacci heap for GNU compiler.
2 Copyright (C) 1998-2023 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin (dan@cgsoftware.com).
4 Re-implemented in C++ by Martin Liska <mliska@suse.cz>
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
21
22 /* Fibonacci heaps are somewhat complex, but, there's an article in
23 DDJ that explains them pretty well:
24
25 http://www.ddj.com/articles/1997/9701/9701o/9701o.htm?topic=algoritms
26
27 Introduction to algorithms by Corman and Rivest also goes over them.
28
29 The original paper that introduced them is "Fibonacci heaps and their
30 uses in improved network optimization algorithms" by Tarjan and
31 Fredman (JACM 34(3), July 1987).
32
33 Amortized and real worst case time for operations:
34
35 ExtractMin: O(lg n) amortized. O(n) worst case.
36 DecreaseKey: O(1) amortized. O(lg n) worst case.
37 Insert: O(1) amortized.
38 Union: O(1) amortized. */
39
40 #ifndef GCC_FIBONACCI_HEAP_H
41 #define GCC_FIBONACCI_HEAP_H
42
43 /* Forward definition. */
44
45 template<class K, class V>
46 class fibonacci_heap;
47
48 /* Fibonacci heap node class. */
49
50 template<class K, class V>
51 class fibonacci_node
52 {
53 typedef fibonacci_node<K,V> fibonacci_node_t;
54 friend class fibonacci_heap<K,V>;
55
56 public:
57 /* Default constructor. */
58 fibonacci_node (): m_parent (NULL), m_child (NULL), m_left (this),
59 m_right (this), m_data (NULL), m_degree (0), m_mark (0)
60 {
61 }
62
63 /* Constructor for a node with given KEY. */
64 fibonacci_node (K key, V *data = NULL): m_parent (NULL), m_child (NULL),
65 m_left (this), m_right (this), m_key (key), m_data (data),
66 m_degree (0), m_mark (0)
67 {
68 }
69
70 /* Compare fibonacci node with OTHER node. */
71 int compare (fibonacci_node_t *other)
72 {
73 if (m_key < other->m_key)
74 return -1;
75 if (m_key > other->m_key)
76 return 1;
77 return 0;
78 }
79
80 /* Compare the node with a given KEY. */
81 int compare_data (K key)
82 {
83 return fibonacci_node_t (key).compare (this);
84 }
85
86 /* Remove fibonacci heap node. */
87 fibonacci_node_t *remove ();
88
89 /* Link the node with PARENT. */
90 void link (fibonacci_node_t *parent);
91
92 /* Return key associated with the node. */
93 K get_key ()
94 {
95 return m_key;
96 }
97
98 /* Return data associated with the node. */
99 V *get_data ()
100 {
101 return m_data;
102 }
103
104 private:
105 /* Put node B after this node. */
106 void insert_after (fibonacci_node_t *b);
107
108 /* Insert fibonacci node B after this node. */
109 void insert_before (fibonacci_node_t *b)
110 {
111 m_left->insert_after (b);
112 }
113
114 /* Parent node. */
115 fibonacci_node *m_parent;
116 /* Child node. */
117 fibonacci_node *m_child;
118 /* Left sibling. */
119 fibonacci_node *m_left;
120 /* Right node. */
121 fibonacci_node *m_right;
122 /* Key associated with node. */
123 K m_key;
124 /* Data associated with node. */
125 V *m_data;
126
127 #if defined (__GNUC__) && (!defined (SIZEOF_INT) || SIZEOF_INT < 4)
128 /* Degree of the node. */
129 __extension__ unsigned long int m_degree : 31;
130 /* Mark of the node. */
131 __extension__ unsigned long int m_mark : 1;
132 #else
133 /* Degree of the node. */
134 unsigned int m_degree : 31;
135 /* Mark of the node. */
136 unsigned int m_mark : 1;
137 #endif
138 };
139
140 /* Fibonacci heap class. */
141 template<class K, class V>
142 class fibonacci_heap
143 {
144 typedef fibonacci_node<K,V> fibonacci_node_t;
145 friend class fibonacci_node<K,V>;
146
147 public:
148 /* Default constructor. ALLOCATOR is optional and is primarily useful
149 when heaps are going to be merged (in that case they need to be allocated
150 in same alloc pool). */
151 fibonacci_heap (K global_min_key, pool_allocator *allocator = NULL):
152 m_nodes (0), m_min (NULL), m_root (NULL),
153 m_global_min_key (global_min_key),
154 m_allocator (allocator), m_own_allocator (false)
155 {
156 if (!m_allocator)
157 {
158 m_allocator = new pool_allocator ("Fibonacci heap",
159 sizeof (fibonacci_node_t));
160 m_own_allocator = true;
161 }
162 }
163
164 /* Destructor. */
165 ~fibonacci_heap ()
166 {
167 /* Actual memory will be released by the destructor of m_allocator. */
168 if (need_finalization_p<fibonacci_node_t> () || !m_own_allocator)
169 while (m_min != NULL)
170 {
171 fibonacci_node_t *n = extract_minimum_node ();
172 n->~fibonacci_node_t ();
173 if (!m_own_allocator)
174 m_allocator->remove (n);
175 }
176 if (m_own_allocator)
177 delete m_allocator;
178 }
179
180 /* Insert new node given by KEY and DATA associated with the key. */
181 fibonacci_node_t *insert (K key, V *data);
182
183 /* Return true if no entry is present. */
184 bool empty () const
185 {
186 return m_nodes == 0;
187 }
188
189 /* Return the number of nodes. */
190 size_t nodes () const
191 {
192 return m_nodes;
193 }
194
195 /* Return minimal key presented in the heap. */
196 K min_key () const
197 {
198 if (m_min == NULL)
199 gcc_unreachable ();
200
201 return m_min->m_key;
202 }
203
204 /* For given NODE, set new KEY value. */
205 K replace_key (fibonacci_node_t *node, K key)
206 {
207 K okey = node->m_key;
208
209 replace_key_data (node, key, node->m_data);
210 return okey;
211 }
212
213 /* For given NODE, decrease value to new KEY. */
214 K decrease_key (fibonacci_node_t *node, K key)
215 {
216 gcc_assert (key <= node->m_key);
217 return replace_key (node, key);
218 }
219
220 /* For given NODE, set new KEY and DATA value. */
221 V *replace_key_data (fibonacci_node_t *node, K key, V *data);
222
223 /* Extract minimum node in the heap. If RELEASE is specified,
224 memory is released. */
225 V *extract_min (bool release = true);
226
227 /* Return value associated with minimum node in the heap. */
228 V *min () const
229 {
230 if (m_min == NULL)
231 return NULL;
232
233 return m_min->m_data;
234 }
235
236 /* Replace data associated with NODE and replace it with DATA. */
237 V *replace_data (fibonacci_node_t *node, V *data)
238 {
239 return replace_key_data (node, node->m_key, data);
240 }
241
242 /* Delete NODE in the heap. */
243 V *delete_node (fibonacci_node_t *node, bool release = true);
244
245 /* Union the heap with HEAPB. */
246 fibonacci_heap *union_with (fibonacci_heap *heapb);
247
248 private:
249 /* Insert new NODE given by KEY and DATA associated with the key. */
250 fibonacci_node_t *insert (fibonacci_node_t *node, K key, V *data);
251
252 /* Insert new NODE that has already filled key and value. */
253 fibonacci_node_t *insert_node (fibonacci_node_t *node);
254
255 /* Insert it into the root list. */
256 void insert_root (fibonacci_node_t *node);
257
258 /* Remove NODE from PARENT's child list. */
259 void cut (fibonacci_node_t *node, fibonacci_node_t *parent);
260
261 /* Process cut of node Y and do it recursivelly. */
262 void cascading_cut (fibonacci_node_t *y);
263
264 /* Extract minimum node from the heap. */
265 fibonacci_node_t * extract_minimum_node ();
266
267 /* Remove root NODE from the heap. */
268 void remove_root (fibonacci_node_t *node);
269
270 /* Consolidate heap. */
271 void consolidate ();
272
273 /* Number of nodes. */
274 size_t m_nodes;
275 /* Minimum node of the heap. */
276 fibonacci_node_t *m_min;
277 /* Root node of the heap. */
278 fibonacci_node_t *m_root;
279 /* Global minimum given in the heap construction. */
280 K m_global_min_key;
281
282 /* Allocator used to hold nodes. */
283 pool_allocator *m_allocator;
284 /* True if alocator is owned by the current heap only. */
285 bool m_own_allocator;
286 };
287
288 /* Remove fibonacci heap node. */
289
290 template<class K, class V>
291 fibonacci_node<K,V> *
292 fibonacci_node<K,V>::remove ()
293 {
294 fibonacci_node<K,V> *ret;
295
296 if (this == m_left)
297 ret = NULL;
298 else
299 ret = m_left;
300
301 if (m_parent != NULL && m_parent->m_child == this)
302 m_parent->m_child = ret;
303
304 m_right->m_left = m_left;
305 m_left->m_right = m_right;
306
307 m_parent = NULL;
308 m_left = this;
309 m_right = this;
310
311 return ret;
312 }
313
314 /* Link the node with PARENT. */
315
316 template<class K, class V>
317 void
318 fibonacci_node<K,V>::link (fibonacci_node<K,V> *parent)
319 {
320 if (parent->m_child == NULL)
321 parent->m_child = this;
322 else
323 parent->m_child->insert_before (this);
324 m_parent = parent;
325 parent->m_degree++;
326 m_mark = 0;
327 }
328
329 /* Put node B after this node. */
330
331 template<class K, class V>
332 void
333 fibonacci_node<K,V>::insert_after (fibonacci_node<K,V> *b)
334 {
335 fibonacci_node<K,V> *a = this;
336
337 if (a == a->m_right)
338 {
339 a->m_right = b;
340 a->m_left = b;
341 b->m_right = a;
342 b->m_left = a;
343 }
344 else
345 {
346 b->m_right = a->m_right;
347 a->m_right->m_left = b;
348 a->m_right = b;
349 b->m_left = a;
350 }
351 }
352
353 /* Insert new node given by KEY and DATA associated with the key. */
354
355 template<class K, class V>
356 fibonacci_node<K,V>*
357 fibonacci_heap<K,V>::insert (K key, V *data)
358 {
359 /* Create the new node. */
360 fibonacci_node<K,V> *node = new (m_allocator->allocate ())
361 fibonacci_node_t (key, data);
362
363 return insert_node (node);
364 }
365
366 /* Insert new NODE given by DATA associated with the key. */
367
368 template<class K, class V>
369 fibonacci_node<K,V>*
370 fibonacci_heap<K,V>::insert (fibonacci_node_t *node, K key, V *data)
371 {
372 /* Set the node's data. */
373 node->m_data = data;
374 node->m_key = key;
375
376 return insert_node (node);
377 }
378
379 /* Insert new NODE that has already filled key and value. */
380
381 template<class K, class V>
382 fibonacci_node<K,V>*
383 fibonacci_heap<K,V>::insert_node (fibonacci_node_t *node)
384 {
385 /* Insert it into the root list. */
386 insert_root (node);
387
388 /* If their was no minimum, or this key is less than the min,
389 it's the new min. */
390 if (m_min == NULL || node->m_key < m_min->m_key)
391 m_min = node;
392
393 m_nodes++;
394
395 return node;
396 }
397
398 /* For given NODE, set new KEY and DATA value. */
399
400 template<class K, class V>
401 V*
402 fibonacci_heap<K,V>::replace_key_data (fibonacci_node<K,V> *node, K key,
403 V *data)
404 {
405 K okey;
406 fibonacci_node<K,V> *y;
407 V *odata = node->m_data;
408
409 /* If we wanted to, we do a real increase by redeleting and
410 inserting. */
411 if (node->compare_data (key) > 0)
412 {
413 delete_node (node, false);
414
415 node = new (node) fibonacci_node_t ();
416 insert (node, key, data);
417
418 return odata;
419 }
420
421 okey = node->m_key;
422 node->m_data = data;
423 node->m_key = key;
424 y = node->m_parent;
425
426 /* Short-circuit if the key is the same, as we then don't have to
427 do anything. Except if we're trying to force the new node to
428 be the new minimum for delete. */
429 if (okey == key && okey != m_global_min_key)
430 return odata;
431
432 /* These two compares are specifically <= 0 to make sure that in the case
433 of equality, a node we replaced the data on, becomes the new min. This
434 is needed so that delete's call to extractmin gets the right node. */
435 if (y != NULL && node->compare (y) <= 0)
436 {
437 cut (node, y);
438 cascading_cut (y);
439 }
440
441 if (node->compare (m_min) <= 0)
442 m_min = node;
443
444 return odata;
445 }
446
447 /* Extract minimum node in the heap. Delete fibonacci node if RELEASE
448 is true. */
449
450 template<class K, class V>
451 V*
452 fibonacci_heap<K,V>::extract_min (bool release)
453 {
454 fibonacci_node<K,V> *z;
455 V *ret = NULL;
456
457 /* If we don't have a min set, it means we have no nodes. */
458 if (m_min != NULL)
459 {
460 /* Otherwise, extract the min node, free the node, and return the
461 node's data. */
462 z = extract_minimum_node ();
463 ret = z->m_data;
464
465 if (release)
466 {
467 z->~fibonacci_node_t ();
468 m_allocator->remove (z);
469 }
470 }
471
472 return ret;
473 }
474
475 /* Delete NODE in the heap, if RELEASE is specified memory is released. */
476
477 template<class K, class V>
478 V*
479 fibonacci_heap<K,V>::delete_node (fibonacci_node<K,V> *node, bool release)
480 {
481 V *ret = node->m_data;
482
483 /* To perform delete, we just make it the min key, and extract. */
484 replace_key (node, m_global_min_key);
485 if (node != m_min)
486 {
487 fprintf (stderr, "Can't force minimum on fibheap.\n");
488 abort ();
489 }
490 extract_min (release);
491
492 return ret;
493 }
494
495 /* Union the heap with HEAPB. One of the heaps is going to be deleted. */
496
497 template<class K, class V>
498 fibonacci_heap<K,V>*
499 fibonacci_heap<K,V>::union_with (fibonacci_heap<K,V> *heapb)
500 {
501 fibonacci_heap<K,V> *heapa = this;
502
503 fibonacci_node<K,V> *a_root, *b_root;
504
505 /* Both heaps must share allocator. */
506 gcc_checking_assert (m_allocator == heapb->m_allocator);
507
508 /* If one of the heaps is empty, the union is just the other heap. */
509 if ((a_root = heapa->m_root) == NULL)
510 {
511 delete (heapa);
512 return heapb;
513 }
514 if ((b_root = heapb->m_root) == NULL)
515 {
516 delete (heapb);
517 return heapa;
518 }
519
520 /* Merge them to the next nodes on the opposite chain. */
521 a_root->m_left->m_right = b_root;
522 b_root->m_left->m_right = a_root;
523 std::swap (a_root->m_left, b_root->m_left);
524 heapa->m_nodes += heapb->m_nodes;
525
526 /* And set the new minimum, if it's changed. */
527 if (heapb->m_min->compare (heapa->m_min) < 0)
528 heapa->m_min = heapb->m_min;
529
530 /* Set m_min to NULL to not to delete live fibonacci nodes. */
531 heapb->m_min = NULL;
532 delete (heapb);
533
534 return heapa;
535 }
536
537 /* Insert it into the root list. */
538
539 template<class K, class V>
540 void
541 fibonacci_heap<K,V>::insert_root (fibonacci_node_t *node)
542 {
543 /* If the heap is currently empty, the new node becomes the singleton
544 circular root list. */
545 if (m_root == NULL)
546 {
547 m_root = node;
548 node->m_left = node;
549 node->m_right = node;
550 return;
551 }
552
553 /* Otherwise, insert it in the circular root list between the root
554 and it's right node. */
555 m_root->insert_after (node);
556 }
557
558 /* Remove NODE from PARENT's child list. */
559
560 template<class K, class V>
561 void
562 fibonacci_heap<K,V>::cut (fibonacci_node<K,V> *node,
563 fibonacci_node<K,V> *parent)
564 {
565 node->remove ();
566 parent->m_degree--;
567 insert_root (node);
568 node->m_parent = NULL;
569 node->m_mark = 0;
570 }
571
572 /* Process cut of node Y and do it recursivelly. */
573
574 template<class K, class V>
575 void
576 fibonacci_heap<K,V>::cascading_cut (fibonacci_node<K,V> *y)
577 {
578 fibonacci_node<K,V> *z;
579
580 while ((z = y->m_parent) != NULL)
581 {
582 if (y->m_mark == 0)
583 {
584 y->m_mark = 1;
585 return;
586 }
587 else
588 {
589 cut (y, z);
590 y = z;
591 }
592 }
593 }
594
595 /* Extract minimum node from the heap. */
596
597 template<class K, class V>
598 fibonacci_node<K,V>*
599 fibonacci_heap<K,V>::extract_minimum_node ()
600 {
601 fibonacci_node<K,V> *ret = m_min;
602 fibonacci_node<K,V> *x, *y, *orig;
603
604 /* Attach the child list of the minimum node to the root list of the heap.
605 If there is no child list, we don't do squat. */
606 for (x = ret->m_child, orig = NULL; x != orig && x != NULL; x = y)
607 {
608 if (orig == NULL)
609 orig = x;
610 y = x->m_right;
611 x->m_parent = NULL;
612 insert_root (x);
613 }
614
615 /* Remove the old root. */
616 remove_root (ret);
617 m_nodes--;
618
619 /* If we are left with no nodes, then the min is NULL. */
620 if (m_nodes == 0)
621 m_min = NULL;
622 else
623 {
624 /* Otherwise, consolidate to find new minimum, as well as do the reorg
625 work that needs to be done. */
626 m_min = ret->m_right;
627 consolidate ();
628 }
629
630 return ret;
631 }
632
633 /* Remove root NODE from the heap. */
634
635 template<class K, class V>
636 void
637 fibonacci_heap<K,V>::remove_root (fibonacci_node<K,V> *node)
638 {
639 if (node->m_left == node)
640 m_root = NULL;
641 else
642 m_root = node->remove ();
643 }
644
645 /* Consolidate heap. */
646
647 template<class K, class V>
648 void fibonacci_heap<K,V>::consolidate ()
649 {
650 const int D = 1 + 8 * sizeof (long);
651 fibonacci_node<K,V> *a[D];
652 fibonacci_node<K,V> *w, *x, *y;
653 int i, d;
654
655 memset (a, 0, sizeof (a));
656
657 while ((w = m_root) != NULL)
658 {
659 x = w;
660 remove_root (w);
661 d = x->m_degree;
662 gcc_checking_assert (d < D);
663 while (a[d] != NULL)
664 {
665 y = a[d];
666 if (x->compare (y) > 0)
667 std::swap (x, y);
668 y->link (x);
669 a[d] = NULL;
670 d++;
671 }
672 a[d] = x;
673 }
674 m_min = NULL;
675 for (i = 0; i < D; i++)
676 if (a[i] != NULL)
677 {
678 insert_root (a[i]);
679 if (m_min == NULL || a[i]->compare (m_min) < 0)
680 m_min = a[i];
681 }
682 }
683
684 #endif // GCC_FIBONACCI_HEAP_H