GCC Middle and Back End API Reference
fibonacci_heap.h
Go to the documentation of this file.
1/* Fibonacci heap for GNU compiler.
2 Copyright (C) 1998-2024 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin (dan@cgsoftware.com).
4 Re-implemented in C++ by Martin Liska <mliska@suse.cz>
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify it under
9the terms of the GNU General Public License as published by the Free
10Software Foundation; either version 3, or (at your option) any later
11version.
12
13GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14WARRANTY; without even the implied warranty of MERCHANTABILITY or
15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16for more details.
17
18You should have received a copy of the GNU General Public License
19along 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
45template<class K, class V>
46class fibonacci_heap;
47
48/* Fibonacci heap node class. */
49
50template<class K, class V>
52{
54 friend class fibonacci_heap<K,V>;
55
56public:
57 /* Default constructor. */
59 m_right (this), m_data (NULL), m_degree (0), m_mark (0)
60 {
61 }
62
63 /* Constructor for a node with given KEY. */
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. */
72 {
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. */
88
89 /* Link the node with PARENT. */
90 void link (fibonacci_node_t *parent);
91
92 /* Return key associated with the node. */
94 {
95 return m_key;
96 }
97
98 /* Return data associated with the node. */
100 {
101 return m_data;
102 }
103
104private:
105 /* Put node B after this node. */
107
108 /* Insert fibonacci node B after this node. */
113
114 /* Parent node. */
116 /* Child node. */
118 /* Left sibling. */
120 /* Right node. */
122 /* Key associated with node. */
124 /* Data associated with node. */
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. */
141template<class K, class V>
143{
145 friend class fibonacci_node<K,V>;
146
147public:
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. */
166 {
167 /* Actual memory will be released by the destructor of m_allocator. */
169 while (m_min != NULL)
170 {
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. */
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)
200
201 return m_min->m_key;
202 }
203
204 /* For given NODE, set new KEY value. */
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. */
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. */
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. */
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. */
247
248private:
249 /* Insert new NODE given by KEY and DATA associated with the key. */
251
252 /* Insert new NODE that has already filled key and value. */
254
255 /* Insert it into the root list. */
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. */
263
264 /* Extract minimum node from the heap. */
266
267 /* Remove root NODE from the heap. */
269
270 /* Consolidate heap. */
271 void consolidate ();
272
273 /* Number of nodes. */
274 size_t m_nodes;
275 /* Minimum node of the heap. */
277 /* Root node of the heap. */
279 /* Global minimum given in the heap construction. */
281
282 /* Allocator used to hold nodes. */
284 /* True if alocator is owned by the current heap only. */
286};
287
288/* Remove fibonacci heap node. */
289
290template<class K, class V>
293{
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
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
316template<class K, class V>
317void
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
331template<class K, class V>
332void
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
355template<class K, class V>
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
368template<class K, class V>
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
381template<class K, class V>
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
400template<class K, class V>
401V*
403 V *data)
404{
405 K okey;
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
450template<class K, class V>
451V*
453{
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
477template<class K, class V>
478V*
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
497template<class K, class V>
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
539template<class K, class V>
540void
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
560template<class K, class V>
561void
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
574template<class K, class V>
575void
577{
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
597template<class K, class 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 (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
635template<class K, class V>
636void
638{
639 if (node->m_left == node)
640 m_root = NULL;
641 else
642 m_root = node->remove ();
643}
644
645/* Consolidate heap. */
646
647template<class K, class V>
649{
650 const int D = 1 + 8 * sizeof (long);
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
base_pool_allocator< memory_block_pool > pool_allocator
Definition alloc-pool.h:477
void remove(void *object)
Definition alloc-pool.h:430
Definition genoutput.cc:150
Definition fibonacci_heap.h:143
size_t nodes() const
Definition fibonacci_heap.h:190
size_t m_nodes
Definition fibonacci_heap.h:274
fibonacci_heap * union_with(fibonacci_heap *heapb)
Definition fibonacci_heap.h:499
void insert_root(fibonacci_node_t *node)
Definition fibonacci_heap.h:541
void cut(fibonacci_node_t *node, fibonacci_node_t *parent)
Definition fibonacci_heap.h:562
void remove_root(fibonacci_node_t *node)
Definition fibonacci_heap.h:637
V * min() const
Definition fibonacci_heap.h:228
fibonacci_node< K, V > fibonacci_node_t
Definition fibonacci_heap.h:144
V * replace_data(fibonacci_node_t *node, V *data)
Definition fibonacci_heap.h:237
V * delete_node(fibonacci_node_t *node, bool release=true)
Definition fibonacci_heap.h:479
fibonacci_node_t * m_root
Definition fibonacci_heap.h:278
fibonacci_node_t * insert_node(fibonacci_node_t *node)
Definition fibonacci_heap.h:383
~fibonacci_heap()
Definition fibonacci_heap.h:165
void consolidate()
Definition fibonacci_heap.h:648
pool_allocator * m_allocator
Definition fibonacci_heap.h:283
fibonacci_node_t * insert(fibonacci_node_t *node, K key, V *data)
Definition fibonacci_heap.h:370
V * extract_min(bool release=true)
Definition fibonacci_heap.h:452
K decrease_key(fibonacci_node_t *node, K key)
Definition fibonacci_heap.h:214
bool empty() const
Definition fibonacci_heap.h:184
fibonacci_node_t * m_min
Definition fibonacci_heap.h:276
V * replace_key_data(fibonacci_node_t *node, K key, V *data)
Definition fibonacci_heap.h:402
K m_global_min_key
Definition fibonacci_heap.h:280
bool m_own_allocator
Definition fibonacci_heap.h:285
K min_key() const
Definition fibonacci_heap.h:196
void cascading_cut(fibonacci_node_t *y)
Definition fibonacci_heap.h:576
fibonacci_node_t * extract_minimum_node()
Definition fibonacci_heap.h:599
fibonacci_heap(K global_min_key, pool_allocator *allocator=NULL)
Definition fibonacci_heap.h:151
fibonacci_node_t * insert(K key, V *data)
Definition fibonacci_heap.h:357
K replace_key(fibonacci_node_t *node, K key)
Definition fibonacci_heap.h:205
Definition fibonacci_heap.h:52
fibonacci_node * m_parent
Definition fibonacci_heap.h:115
fibonacci_node * m_left
Definition fibonacci_heap.h:119
fibonacci_node * m_child
Definition fibonacci_heap.h:117
fibonacci_node(K key, V *data=NULL)
Definition fibonacci_heap.h:64
fibonacci_node * m_right
Definition fibonacci_heap.h:121
fibonacci_node()
Definition fibonacci_heap.h:58
void link(fibonacci_node_t *parent)
Definition fibonacci_heap.h:318
K get_key()
Definition fibonacci_heap.h:93
int compare_data(K key)
Definition fibonacci_heap.h:81
V * m_data
Definition fibonacci_heap.h:125
void insert_before(fibonacci_node_t *b)
Definition fibonacci_heap.h:109
unsigned int m_mark
Definition fibonacci_heap.h:136
unsigned int m_degree
Definition fibonacci_heap.h:134
V * get_data()
Definition fibonacci_heap.h:99
fibonacci_node_t * remove()
Definition fibonacci_heap.h:292
K m_key
Definition fibonacci_heap.h:123
void insert_after(fibonacci_node_t *b)
Definition fibonacci_heap.h:333
int compare(fibonacci_node_t *other)
Definition fibonacci_heap.h:71
fibonacci_node< K, V > fibonacci_node_t
Definition fibonacci_heap.h:53
static struct operand_data * odata
Definition genoutput.cc:136
bool need_finalization_p()
Definition ggc.h:173
i
Definition poly-int.h:776
Ca const poly_int< N, Cb > & b
Definition poly-int.h:771
Ca & a
Definition poly-int.h:770
#define NULL
Definition system.h:50
#define gcc_assert(EXPR)
Definition system.h:821
#define gcc_unreachable()
Definition system.h:848
#define false
Definition system.h:895
#define abort()
Definition system.h:810
#define gcc_checking_assert(EXPR)
Definition system.h:828
static void insert(void)
Definition tree-ssa-pre.cc:3804
const T2 & y
Definition wide-int.h:3870