Daily bump.
[official-gcc.git] / gcc / fibonacci_heap.h
bloba0f444be52b2f425a1410ad85147c60f2c3e8ded
1 /* Fibonacci heap for GNU compiler.
2 Copyright (C) 1998-2021 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin (dan@cgsoftware.com).
4 Re-implemented in C++ by Martin Liska <mliska@suse.cz>
6 This file is part of GCC.
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.
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.
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/>. */
22 /* Fibonacci heaps are somewhat complex, but, there's an article in
23 DDJ that explains them pretty well:
25 http://www.ddj.com/articles/1997/9701/9701o/9701o.htm?topic=algoritms
27 Introduction to algorithms by Corman and Rivest also goes over them.
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).
33 Amortized and real worst case time for operations:
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. */
40 #ifndef GCC_FIBONACCI_HEAP_H
41 #define GCC_FIBONACCI_HEAP_H
43 /* Forward definition. */
45 template<class K, class V>
46 class fibonacci_heap;
48 /* Fibonacci heap node class. */
50 template<class K, class V>
51 class fibonacci_node
53 typedef fibonacci_node<K,V> fibonacci_node_t;
54 friend class fibonacci_heap<K,V>;
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)
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)
70 /* Compare fibonacci node with OTHER node. */
71 int compare (fibonacci_node_t *other)
73 if (m_key < other->m_key)
74 return -1;
75 if (m_key > other->m_key)
76 return 1;
77 return 0;
80 /* Compare the node with a given KEY. */
81 int compare_data (K key)
83 return fibonacci_node_t (key).compare (this);
86 /* Remove fibonacci heap node. */
87 fibonacci_node_t *remove ();
89 /* Link the node with PARENT. */
90 void link (fibonacci_node_t *parent);
92 /* Return key associated with the node. */
93 K get_key ()
95 return m_key;
98 /* Return data associated with the node. */
99 V *get_data ()
101 return m_data;
104 private:
105 /* Put node B after this node. */
106 void insert_after (fibonacci_node_t *b);
108 /* Insert fibonacci node B after this node. */
109 void insert_before (fibonacci_node_t *b)
111 m_left->insert_after (b);
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;
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
140 /* Fibonacci heap class. */
141 template<class K, class V>
142 class fibonacci_heap
144 typedef fibonacci_node<K,V> fibonacci_node_t;
145 friend class fibonacci_node<K,V>;
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)
156 if (!m_allocator)
158 m_allocator = new pool_allocator ("Fibonacci heap",
159 sizeof (fibonacci_node_t));
160 m_own_allocator = true;
164 /* Destructor. */
165 ~fibonacci_heap ()
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)
171 fibonacci_node_t *n = extract_minimum_node ();
172 n->~fibonacci_node_t ();
173 if (!m_own_allocator)
174 m_allocator->remove (n);
176 if (m_own_allocator)
177 delete m_allocator;
180 /* Insert new node given by KEY and DATA associated with the key. */
181 fibonacci_node_t *insert (K key, V *data);
183 /* Return true if no entry is present. */
184 bool empty () const
186 return m_nodes == 0;
189 /* Return the number of nodes. */
190 size_t nodes () const
192 return m_nodes;
195 /* Return minimal key presented in the heap. */
196 K min_key () const
198 if (m_min == NULL)
199 gcc_unreachable ();
201 return m_min->m_key;
204 /* For given NODE, set new KEY value. */
205 K replace_key (fibonacci_node_t *node, K key)
207 K okey = node->m_key;
209 replace_key_data (node, key, node->m_data);
210 return okey;
213 /* For given NODE, decrease value to new KEY. */
214 K decrease_key (fibonacci_node_t *node, K key)
216 gcc_assert (key <= node->m_key);
217 return replace_key (node, key);
220 /* For given NODE, set new KEY and DATA value. */
221 V *replace_key_data (fibonacci_node_t *node, K key, V *data);
223 /* Extract minimum node in the heap. If RELEASE is specified,
224 memory is released. */
225 V *extract_min (bool release = true);
227 /* Return value associated with minimum node in the heap. */
228 V *min () const
230 if (m_min == NULL)
231 return NULL;
233 return m_min->m_data;
236 /* Replace data associated with NODE and replace it with DATA. */
237 V *replace_data (fibonacci_node_t *node, V *data)
239 return replace_key_data (node, node->m_key, data);
242 /* Delete NODE in the heap. */
243 V *delete_node (fibonacci_node_t *node, bool release = true);
245 /* Union the heap with HEAPB. */
246 fibonacci_heap *union_with (fibonacci_heap *heapb);
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);
252 /* Insert new NODE that has already filled key and value. */
253 fibonacci_node_t *insert_node (fibonacci_node_t *node);
255 /* Insert it into the root list. */
256 void insert_root (fibonacci_node_t *node);
258 /* Remove NODE from PARENT's child list. */
259 void cut (fibonacci_node_t *node, fibonacci_node_t *parent);
261 /* Process cut of node Y and do it recursivelly. */
262 void cascading_cut (fibonacci_node_t *y);
264 /* Extract minimum node from the heap. */
265 fibonacci_node_t * extract_minimum_node ();
267 /* Remove root NODE from the heap. */
268 void remove_root (fibonacci_node_t *node);
270 /* Consolidate heap. */
271 void consolidate ();
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;
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;
288 /* Remove fibonacci heap node. */
290 template<class K, class V>
291 fibonacci_node<K,V> *
292 fibonacci_node<K,V>::remove ()
294 fibonacci_node<K,V> *ret;
296 if (this == m_left)
297 ret = NULL;
298 else
299 ret = m_left;
301 if (m_parent != NULL && m_parent->m_child == this)
302 m_parent->m_child = ret;
304 m_right->m_left = m_left;
305 m_left->m_right = m_right;
307 m_parent = NULL;
308 m_left = this;
309 m_right = this;
311 return ret;
314 /* Link the node with PARENT. */
316 template<class K, class V>
317 void
318 fibonacci_node<K,V>::link (fibonacci_node<K,V> *parent)
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;
329 /* Put node B after this node. */
331 template<class K, class V>
332 void
333 fibonacci_node<K,V>::insert_after (fibonacci_node<K,V> *b)
335 fibonacci_node<K,V> *a = this;
337 if (a == a->m_right)
339 a->m_right = b;
340 a->m_left = b;
341 b->m_right = a;
342 b->m_left = a;
344 else
346 b->m_right = a->m_right;
347 a->m_right->m_left = b;
348 a->m_right = b;
349 b->m_left = a;
353 /* Insert new node given by KEY and DATA associated with the key. */
355 template<class K, class V>
356 fibonacci_node<K,V>*
357 fibonacci_heap<K,V>::insert (K key, V *data)
359 /* Create the new node. */
360 fibonacci_node<K,V> *node = new (m_allocator->allocate ())
361 fibonacci_node_t (key, data);
363 return insert_node (node);
366 /* Insert new NODE given by DATA associated with the key. */
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)
372 /* Set the node's data. */
373 node->m_data = data;
374 node->m_key = key;
376 return insert_node (node);
379 /* Insert new NODE that has already filled key and value. */
381 template<class K, class V>
382 fibonacci_node<K,V>*
383 fibonacci_heap<K,V>::insert_node (fibonacci_node_t *node)
385 /* Insert it into the root list. */
386 insert_root (node);
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;
393 m_nodes++;
395 return node;
398 /* For given NODE, set new KEY and DATA value. */
400 template<class K, class V>
402 fibonacci_heap<K,V>::replace_key_data (fibonacci_node<K,V> *node, K key,
403 V *data)
405 K okey;
406 fibonacci_node<K,V> *y;
407 V *odata = node->m_data;
409 /* If we wanted to, we do a real increase by redeleting and
410 inserting. */
411 if (node->compare_data (key) > 0)
413 delete_node (node, false);
415 node = new (node) fibonacci_node_t ();
416 insert (node, key, data);
418 return odata;
421 okey = node->m_key;
422 node->m_data = data;
423 node->m_key = key;
424 y = node->m_parent;
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;
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)
437 cut (node, y);
438 cascading_cut (y);
441 if (node->compare (m_min) <= 0)
442 m_min = node;
444 return odata;
447 /* Extract minimum node in the heap. Delete fibonacci node if RELEASE
448 is true. */
450 template<class K, class V>
452 fibonacci_heap<K,V>::extract_min (bool release)
454 fibonacci_node<K,V> *z;
455 V *ret = NULL;
457 /* If we don't have a min set, it means we have no nodes. */
458 if (m_min != NULL)
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;
465 if (release)
467 z->~fibonacci_node_t ();
468 m_allocator->remove (z);
472 return ret;
475 /* Delete NODE in the heap, if RELEASE is specified memory is released. */
477 template<class K, class V>
479 fibonacci_heap<K,V>::delete_node (fibonacci_node<K,V> *node, bool release)
481 V *ret = node->m_data;
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)
487 fprintf (stderr, "Can't force minimum on fibheap.\n");
488 abort ();
490 extract_min (release);
492 return ret;
495 /* Union the heap with HEAPB. One of the heaps is going to be deleted. */
497 template<class K, class V>
498 fibonacci_heap<K,V>*
499 fibonacci_heap<K,V>::union_with (fibonacci_heap<K,V> *heapb)
501 fibonacci_heap<K,V> *heapa = this;
503 fibonacci_node<K,V> *a_root, *b_root;
505 /* Both heaps must share allocator. */
506 gcc_checking_assert (m_allocator == heapb->m_allocator);
508 /* If one of the heaps is empty, the union is just the other heap. */
509 if ((a_root = heapa->m_root) == NULL)
511 delete (heapa);
512 return heapb;
514 if ((b_root = heapb->m_root) == NULL)
516 delete (heapb);
517 return heapa;
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;
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;
530 /* Set m_min to NULL to not to delete live fibonacci nodes. */
531 heapb->m_min = NULL;
532 delete (heapb);
534 return heapa;
537 /* Insert it into the root list. */
539 template<class K, class V>
540 void
541 fibonacci_heap<K,V>::insert_root (fibonacci_node_t *node)
543 /* If the heap is currently empty, the new node becomes the singleton
544 circular root list. */
545 if (m_root == NULL)
547 m_root = node;
548 node->m_left = node;
549 node->m_right = node;
550 return;
553 /* Otherwise, insert it in the circular root list between the root
554 and it's right node. */
555 m_root->insert_after (node);
558 /* Remove NODE from PARENT's child list. */
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)
565 node->remove ();
566 parent->m_degree--;
567 insert_root (node);
568 node->m_parent = NULL;
569 node->m_mark = 0;
572 /* Process cut of node Y and do it recursivelly. */
574 template<class K, class V>
575 void
576 fibonacci_heap<K,V>::cascading_cut (fibonacci_node<K,V> *y)
578 fibonacci_node<K,V> *z;
580 while ((z = y->m_parent) != NULL)
582 if (y->m_mark == 0)
584 y->m_mark = 1;
585 return;
587 else
589 cut (y, z);
590 y = z;
595 /* Extract minimum node from the heap. */
597 template<class K, class V>
598 fibonacci_node<K,V>*
599 fibonacci_heap<K,V>::extract_minimum_node ()
601 fibonacci_node<K,V> *ret = m_min;
602 fibonacci_node<K,V> *x, *y, *orig;
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)
608 if (orig == NULL)
609 orig = x;
610 y = x->m_right;
611 x->m_parent = NULL;
612 insert_root (x);
615 /* Remove the old root. */
616 remove_root (ret);
617 m_nodes--;
619 /* If we are left with no nodes, then the min is NULL. */
620 if (m_nodes == 0)
621 m_min = NULL;
622 else
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 ();
630 return ret;
633 /* Remove root NODE from the heap. */
635 template<class K, class V>
636 void
637 fibonacci_heap<K,V>::remove_root (fibonacci_node<K,V> *node)
639 if (node->m_left == node)
640 m_root = NULL;
641 else
642 m_root = node->remove ();
645 /* Consolidate heap. */
647 template<class K, class V>
648 void fibonacci_heap<K,V>::consolidate ()
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;
655 memset (a, 0, sizeof (a));
657 while ((w = m_root) != NULL)
659 x = w;
660 remove_root (w);
661 d = x->m_degree;
662 gcc_checking_assert (d < D);
663 while (a[d] != NULL)
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++;
672 a[d] = x;
674 m_min = NULL;
675 for (i = 0; i < D; i++)
676 if (a[i] != NULL)
678 insert_root (a[i]);
679 if (m_min == NULL || a[i]->compare (m_min) < 0)
680 m_min = a[i];
684 #endif // GCC_FIBONACCI_HEAP_H