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 (object: 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, data: 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, key: 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, release: 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, parent: 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>:: (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 (object: 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, key: m_global_min_key); |
485 | if (node != m_min) |
486 | { |
487 | fprintf (stderr, format: "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 (node: y, parent: 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>:: () |
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 (node: x); |
613 | } |
614 | |
615 | /* Remove the old root. */ |
616 | remove_root (node: 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 (node: 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 (node: 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 |
685 | |