Line data Source code
1 : /* Fibonacci heap for GNU compiler.
2 : Copyright (C) 1998-2026 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 40 : fibonacci_node (): m_parent (NULL), m_child (NULL), m_left (this),
59 40 : m_right (this), m_data (NULL), m_degree (0), m_mark (0)
60 : {
61 : }
62 :
63 : /* Constructor for a node with given KEY. */
64 25011733 : fibonacci_node (K key, V *data = NULL): m_parent (NULL), m_child (NULL),
65 23230701 : m_left (this), m_right (this), m_key (key), m_data (data),
66 23230701 : m_degree (0), m_mark (0)
67 : {
68 : }
69 :
70 : /* Compare fibonacci node with OTHER node. */
71 75584941 : int compare (fibonacci_node_t *other)
72 : {
73 43870196 : if (m_key < other->m_key)
74 : return -1;
75 32165251 : if (m_key > other->m_key)
76 13358992 : return 1;
77 : return 0;
78 : }
79 :
80 : /* Compare the node with a given KEY. */
81 2774626 : int compare_data (K key)
82 : {
83 4555658 : 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 7542052 : K get_key ()
94 : {
95 7542052 : return m_key;
96 : }
97 :
98 : /* Return data associated with the node. */
99 4170963 : V *get_data ()
100 : {
101 4170963 : 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 27286598 : void insert_before (fibonacci_node_t *b)
110 : {
111 54573196 : m_left->insert_after (b);
112 27286598 : }
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 4393526 : fibonacci_heap (K global_min_key, pool_allocator *allocator = NULL):
152 4393526 : m_nodes (0), m_min (NULL), m_root (NULL),
153 4393526 : m_global_min_key (global_min_key),
154 4393526 : m_allocator (allocator), m_own_allocator (false)
155 : {
156 4393502 : if (!m_allocator)
157 : {
158 4393502 : m_allocator = new pool_allocator ("Fibonacci heap",
159 : sizeof (fibonacci_node_t));
160 4393502 : m_own_allocator = true;
161 : }
162 4393502 : }
163 :
164 : /* Destructor. */
165 4384493 : ~fibonacci_heap ()
166 : {
167 : /* Actual memory will be released by the destructor of m_allocator. */
168 4384493 : if (need_finalization_p<fibonacci_node_t> () || !m_own_allocator)
169 24 : while (m_min != NULL)
170 : {
171 0 : fibonacci_node_t *n = extract_minimum_node ();
172 0 : n->~fibonacci_node_t ();
173 0 : if (!m_own_allocator)
174 0 : m_allocator->remove (n);
175 : }
176 4384493 : if (m_own_allocator)
177 8768938 : delete m_allocator;
178 4384493 : }
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 26970587 : bool empty () const
185 : {
186 25911880 : return m_nodes == 0;
187 : }
188 :
189 : /* Return the number of nodes. */
190 366364 : size_t nodes () const
191 : {
192 366364 : return m_nodes;
193 : }
194 :
195 : /* Return minimal key presented in the heap. */
196 4379328 : K min_key () const
197 : {
198 4379328 : if (m_min == NULL)
199 0 : gcc_unreachable ();
200 :
201 4379328 : return m_min->m_key;
202 : }
203 :
204 : /* For given NODE, set new KEY value. */
205 2774626 : K replace_key (fibonacci_node_t *node, K key)
206 : {
207 2774626 : K okey = node->m_key;
208 :
209 2774626 : replace_key_data (node, key, node->m_data);
210 2384003 : return okey;
211 : }
212 :
213 : /* For given NODE, decrease value to new KEY. */
214 891882 : K decrease_key (fibonacci_node_t *node, K key)
215 : {
216 891882 : gcc_assert (key <= node->m_key);
217 891882 : 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 2203828 : V *min () const
229 : {
230 2203828 : if (m_min == NULL)
231 : return NULL;
232 :
233 2136299 : 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 86857034 : fibonacci_node<K,V>::remove ()
293 : {
294 : fibonacci_node<K,V> *ret;
295 :
296 86857034 : if (this == m_left)
297 : ret = NULL;
298 : else
299 86768396 : ret = m_left;
300 :
301 86857034 : if (m_parent != NULL && m_parent->m_child == this)
302 135667 : m_parent->m_child = ret;
303 :
304 86857034 : m_right->m_left = m_left;
305 86857034 : m_left->m_right = m_right;
306 :
307 86857034 : m_parent = NULL;
308 86857034 : m_left = this;
309 86857034 : m_right = this;
310 :
311 86857034 : return ret;
312 : }
313 :
314 : /* Link the node with PARENT. */
315 :
316 : template<class K, class V>
317 : void
318 39174093 : fibonacci_node<K,V>::link (fibonacci_node<K,V> *parent)
319 : {
320 39174093 : if (parent->m_child == NULL)
321 11887495 : parent->m_child = this;
322 : else
323 27286598 : parent->m_child->insert_before (this);
324 39174093 : m_parent = parent;
325 39174093 : parent->m_degree++;
326 39174093 : m_mark = 0;
327 39174093 : }
328 :
329 : /* Put node B after this node. */
330 :
331 : template<class K, class V>
332 : void
333 113909579 : fibonacci_node<K,V>::insert_after (fibonacci_node<K,V> *b)
334 : {
335 113909579 : fibonacci_node<K,V> *a = this;
336 :
337 27286598 : if (a == a->m_right)
338 : {
339 26126069 : a->m_right = b;
340 26126069 : a->m_left = b;
341 26126069 : b->m_right = a;
342 26126069 : b->m_left = a;
343 : }
344 : else
345 : {
346 87783510 : b->m_right = a->m_right;
347 87783510 : a->m_right->m_left = b;
348 87783510 : a->m_right = b;
349 87783510 : b->m_left = a;
350 : }
351 0 : }
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 22237107 : fibonacci_heap<K,V>::insert (K key, V *data)
358 : {
359 : /* Create the new node. */
360 22237107 : fibonacci_node<K,V> *node = new (m_allocator->allocate ())
361 : fibonacci_node_t (key, data);
362 :
363 22237107 : 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 40 : fibonacci_heap<K,V>::insert (fibonacci_node_t *node, K key, V *data)
371 : {
372 : /* Set the node's data. */
373 40 : node->m_data = data;
374 40 : node->m_key = key;
375 :
376 40 : 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 22237147 : fibonacci_heap<K,V>::insert_node (fibonacci_node_t *node)
384 : {
385 : /* Insert it into the root list. */
386 22237147 : 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 22237147 : if (m_min == NULL || node->m_key < m_min->m_key)
391 6543851 : m_min = node;
392 :
393 22237147 : m_nodes++;
394 :
395 22237147 : return node;
396 : }
397 :
398 : /* For given NODE, set new KEY and DATA value. */
399 :
400 : template<class K, class V>
401 : V*
402 2774626 : fibonacci_heap<K,V>::replace_key_data (fibonacci_node<K,V> *node, K key,
403 : V *data)
404 : {
405 993594 : K okey;
406 : fibonacci_node<K,V> *y;
407 2774626 : V *odata = node->m_data;
408 :
409 : /* If we wanted to, we do a real increase by redeleting and
410 : inserting. */
411 2774626 : if (node->compare_data (key) > 0)
412 : {
413 40 : delete_node (node, false);
414 :
415 40 : node = new (node) fibonacci_node_t ();
416 40 : insert (node, key, data);
417 :
418 40 : return odata;
419 : }
420 :
421 2774586 : okey = node->m_key;
422 2774586 : node->m_data = data;
423 2774586 : node->m_key = key;
424 2774586 : 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 2774586 : 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 2774586 : if (y != NULL && node->compare (y) <= 0)
436 : {
437 225032 : cut (node, y);
438 225032 : cascading_cut (y);
439 : }
440 :
441 2774586 : if (node->compare (m_min) <= 0)
442 1615227 : 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 22128724 : fibonacci_heap<K,V>::extract_min (bool release)
453 : {
454 : fibonacci_node<K,V> *z;
455 22128724 : V *ret = NULL;
456 :
457 : /* If we don't have a min set, it means we have no nodes. */
458 22128724 : if (m_min != NULL)
459 : {
460 : /* Otherwise, extract the min node, free the node, and return the
461 : node's data. */
462 22128661 : z = extract_minimum_node ();
463 22128661 : ret = z->m_data;
464 :
465 22128661 : if (release)
466 : {
467 22128621 : z->~fibonacci_node_t ();
468 22128621 : m_allocator->remove (z);
469 : }
470 : }
471 :
472 22128724 : 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 577157 : fibonacci_heap<K,V>::delete_node (fibonacci_node<K,V> *node, bool release)
480 : {
481 577157 : V *ret = node->m_data;
482 :
483 : /* To perform delete, we just make it the min key, and extract. */
484 577157 : replace_key (node, m_global_min_key);
485 577157 : if (node != m_min)
486 : {
487 0 : fprintf (stderr, "Can't force minimum on fibheap.\n");
488 0 : abort ();
489 : }
490 577157 : extract_min (release);
491 :
492 577157 : 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 12 : fibonacci_heap<K,V>::union_with (fibonacci_heap<K,V> *heapb)
500 : {
501 12 : fibonacci_heap<K,V> *heapa = this;
502 :
503 : fibonacci_node<K,V> *a_root, *b_root;
504 :
505 : /* Both heaps must share allocator. */
506 12 : 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 12 : if ((a_root = heapa->m_root) == NULL)
510 : {
511 4 : delete (heapa);
512 4 : return heapb;
513 : }
514 8 : if ((b_root = heapb->m_root) == NULL)
515 : {
516 0 : delete (heapb);
517 0 : return heapa;
518 : }
519 :
520 : /* Merge them to the next nodes on the opposite chain. */
521 8 : a_root->m_left->m_right = b_root;
522 8 : b_root->m_left->m_right = a_root;
523 8 : std::swap (a_root->m_left, b_root->m_left);
524 8 : heapa->m_nodes += heapb->m_nodes;
525 :
526 : /* And set the new minimum, if it's changed. */
527 8 : if (heapb->m_min->compare (heapa->m_min) < 0)
528 0 : heapa->m_min = heapb->m_min;
529 :
530 : /* Set m_min to NULL to not to delete live fibonacci nodes. */
531 8 : heapb->m_min = NULL;
532 8 : delete (heapb);
533 :
534 8 : return heapa;
535 : }
536 :
537 : /* Insert it into the root list. */
538 :
539 : template<class K, class V>
540 : void
541 108760478 : 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 108760478 : if (m_root == NULL)
546 : {
547 22137497 : m_root = node;
548 22137497 : node->m_left = node;
549 22137497 : node->m_right = node;
550 22137497 : return;
551 : }
552 :
553 : /* Otherwise, insert it in the circular root list between the root
554 : and it's right node. */
555 86622981 : 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 244002 : fibonacci_heap<K,V>::cut (fibonacci_node<K,V> *node,
563 : fibonacci_node<K,V> *parent)
564 : {
565 244002 : node->remove ();
566 244002 : parent->m_degree--;
567 244002 : insert_root (node);
568 244002 : node->m_parent = NULL;
569 244002 : node->m_mark = 0;
570 244002 : }
571 :
572 : /* Process cut of node Y and do it recursivelly. */
573 :
574 : template<class K, class V>
575 : void
576 225032 : fibonacci_heap<K,V>::cascading_cut (fibonacci_node<K,V> *y)
577 : {
578 : fibonacci_node<K,V> *z;
579 :
580 244002 : while ((z = y->m_parent) != NULL)
581 : {
582 162173 : if (y->m_mark == 0)
583 : {
584 143203 : y->m_mark = 1;
585 143203 : return;
586 : }
587 : else
588 : {
589 18970 : cut (y, z);
590 18970 : 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 22128661 : fibonacci_heap<K,V>::extract_minimum_node ()
600 : {
601 22128661 : 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 60969051 : for (x = ret->m_child, orig = NULL; x != orig && x != NULL; x = y)
607 : {
608 38840390 : if (orig == NULL)
609 11748537 : orig = x;
610 38840390 : y = x->m_right;
611 38840390 : x->m_parent = NULL;
612 38840390 : insert_root (x);
613 : }
614 :
615 : /* Remove the old root. */
616 22128661 : remove_root (ret);
617 22128661 : m_nodes--;
618 :
619 : /* If we are left with no nodes, then the min is NULL. */
620 22128661 : if (m_nodes == 0)
621 4513148 : 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 17615513 : m_min = ret->m_right;
627 17615513 : consolidate ();
628 : }
629 :
630 22128661 : return ret;
631 : }
632 :
633 : /* Remove root NODE from the heap. */
634 :
635 : template<class K, class V>
636 : void
637 108741693 : fibonacci_heap<K,V>::remove_root (fibonacci_node<K,V> *node)
638 : {
639 108741693 : if (node->m_left == node)
640 22128661 : m_root = NULL;
641 : else
642 86613032 : m_root = node->remove ();
643 108741693 : }
644 :
645 : /* Consolidate heap. */
646 :
647 : template<class K, class V>
648 17615513 : void fibonacci_heap<K,V>::consolidate ()
649 : {
650 17615513 : 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 17615513 : memset (a, 0, sizeof (a));
656 :
657 104228545 : while ((w = m_root) != NULL)
658 : {
659 86613032 : x = w;
660 86613032 : remove_root (w);
661 86613032 : d = x->m_degree;
662 86613032 : gcc_checking_assert (d < D);
663 125787125 : while (a[d] != NULL)
664 : {
665 39174093 : y = a[d];
666 44741390 : if (x->compare (y) > 0)
667 8585812 : std::swap (x, y);
668 39174093 : y->link (x);
669 39174093 : a[d] = NULL;
670 39174093 : d++;
671 : }
672 86613032 : a[d] = x;
673 : }
674 17615513 : m_min = NULL;
675 1162623858 : for (i = 0; i < D; i++)
676 1145008345 : if (a[i] != NULL)
677 : {
678 47438939 : insert_root (a[i]);
679 974865058 : if (m_min == NULL || a[i]->compare (m_min) < 0)
680 29908977 : m_min = a[i];
681 : }
682 17615513 : }
683 :
684 : #endif // GCC_FIBONACCI_HEAP_H
|
