1 /* Fibonacci heap for GNU compiler.
2    Copyright (C) 1998-2018 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.  */
fibonacci_node()58   fibonacci_node (): m_parent (NULL), m_child (NULL), m_left (this),
59     m_right (this), m_degree (0), m_mark (0)
60   {
61   }
62 
63   /* Constructor for a node with given KEY.  */
m_parent(NULL)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.  */
compare(fibonacci_node_t * other)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.  */
compare_data(K 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.  */
get_key()93   K get_key ()
94   {
95     return m_key;
96   }
97 
98   /* Return data associated with the node.  */
get_data()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.  */
insert_before(fibonacci_node_t * b)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.  */
fibonacci_heap(K global_min_key)149   fibonacci_heap (K global_min_key): m_nodes (0), m_min (NULL), m_root (NULL),
150     m_global_min_key (global_min_key)
151   {
152   }
153 
154   /* Destructor.  */
~fibonacci_heap()155   ~fibonacci_heap ()
156   {
157     while (m_min != NULL)
158       delete (extract_minimum_node ());
159   }
160 
161   /* Insert new node given by KEY and DATA associated with the key.  */
162   fibonacci_node_t *insert (K key, V *data);
163 
164   /* Return true if no entry is present.  */
empty()165   bool empty ()
166   {
167     return m_nodes == 0;
168   }
169 
170   /* Return the number of nodes.  */
nodes()171   size_t nodes ()
172   {
173     return m_nodes;
174   }
175 
176   /* Return minimal key presented in the heap.  */
min_key()177   K min_key ()
178   {
179     if (m_min == NULL)
180       gcc_unreachable ();
181 
182     return m_min->m_key;
183   }
184 
185   /* For given NODE, set new KEY value.  */
replace_key(fibonacci_node_t * node,K key)186   K replace_key (fibonacci_node_t *node, K key)
187   {
188     K okey = node->m_key;
189 
190     replace_key_data (node, key, node->m_data);
191     return okey;
192   }
193 
194   /* For given NODE, decrease value to new KEY.  */
decrease_key(fibonacci_node_t * node,K key)195   K decrease_key (fibonacci_node_t *node, K key)
196   {
197     gcc_assert (key <= node->m_key);
198     return replace_key (node, key);
199   }
200 
201   /* For given NODE, set new KEY and DATA value.  */
202   V *replace_key_data (fibonacci_node_t *node, K key, V *data);
203 
204   /* Extract minimum node in the heap. If RELEASE is specified,
205      memory is released.  */
206   V *extract_min (bool release = true);
207 
208   /* Return value associated with minimum node in the heap.  */
min()209   V *min ()
210   {
211     if (m_min == NULL)
212       return NULL;
213 
214     return m_min->m_data;
215   }
216 
217   /* Replace data associated with NODE and replace it with DATA.  */
replace_data(fibonacci_node_t * node,V * data)218   V *replace_data (fibonacci_node_t *node, V *data)
219   {
220     return replace_key_data (node, node->m_key, data);
221   }
222 
223   /* Delete NODE in the heap.  */
224   V *delete_node (fibonacci_node_t *node, bool release = true);
225 
226   /* Union the heap with HEAPB.  */
227   fibonacci_heap *union_with (fibonacci_heap *heapb);
228 
229 private:
230   /* Insert new NODE given by KEY and DATA associated with the key.  */
231   fibonacci_node_t *insert (fibonacci_node_t *node, K key, V *data);
232 
233   /* Insert new NODE that has already filled key and value.  */
234   fibonacci_node_t *insert_node (fibonacci_node_t *node);
235 
236   /* Insert it into the root list.  */
237   void insert_root (fibonacci_node_t *node);
238 
239   /* Remove NODE from PARENT's child list.  */
240   void cut (fibonacci_node_t *node, fibonacci_node_t *parent);
241 
242   /* Process cut of node Y and do it recursivelly.  */
243   void cascading_cut (fibonacci_node_t *y);
244 
245   /* Extract minimum node from the heap.  */
246   fibonacci_node_t * extract_minimum_node ();
247 
248   /* Remove root NODE from the heap.  */
249   void remove_root (fibonacci_node_t *node);
250 
251   /* Consolidate heap.  */
252   void consolidate ();
253 
254   /* Number of nodes.  */
255   size_t m_nodes;
256   /* Minimum node of the heap.  */
257   fibonacci_node_t *m_min;
258   /* Root node of the heap.  */
259   fibonacci_node_t *m_root;
260   /* Global minimum given in the heap construction.  */
261   K m_global_min_key;
262 };
263 
264 /* Remove fibonacci heap node.  */
265 
266 template<class K, class V>
267 fibonacci_node<K,V> *
remove()268 fibonacci_node<K,V>::remove ()
269 {
270   fibonacci_node<K,V> *ret;
271 
272   if (this == m_left)
273     ret = NULL;
274   else
275     ret = m_left;
276 
277   if (m_parent != NULL && m_parent->m_child == this)
278     m_parent->m_child = ret;
279 
280   m_right->m_left = m_left;
281   m_left->m_right = m_right;
282 
283   m_parent = NULL;
284   m_left = this;
285   m_right = this;
286 
287   return ret;
288 }
289 
290 /* Link the node with PARENT.  */
291 
292 template<class K, class V>
293 void
link(fibonacci_node<K,V> * parent)294 fibonacci_node<K,V>::link (fibonacci_node<K,V> *parent)
295 {
296   if (parent->m_child == NULL)
297     parent->m_child = this;
298   else
299     parent->m_child->insert_before (this);
300   m_parent = parent;
301   parent->m_degree++;
302   m_mark = 0;
303 }
304 
305 /* Put node B after this node.  */
306 
307 template<class K, class V>
308 void
insert_after(fibonacci_node<K,V> * b)309 fibonacci_node<K,V>::insert_after (fibonacci_node<K,V> *b)
310 {
311   fibonacci_node<K,V> *a = this;
312 
313   if (a == a->m_right)
314     {
315       a->m_right = b;
316       a->m_left = b;
317       b->m_right = a;
318       b->m_left = a;
319     }
320   else
321     {
322       b->m_right = a->m_right;
323       a->m_right->m_left = b;
324       a->m_right = b;
325       b->m_left = a;
326     }
327 }
328 
329 /* Insert new node given by KEY and DATA associated with the key.  */
330 
331 template<class K, class V>
332 fibonacci_node<K,V>*
insert(K key,V * data)333 fibonacci_heap<K,V>::insert (K key, V *data)
334 {
335   /* Create the new node.  */
336   fibonacci_node<K,V> *node = new fibonacci_node_t (key, data);
337 
338   return insert_node (node);
339 }
340 
341 /* Insert new NODE given by DATA associated with the key.  */
342 
343 template<class K, class V>
344 fibonacci_node<K,V>*
insert(fibonacci_node_t * node,K key,V * data)345 fibonacci_heap<K,V>::insert (fibonacci_node_t *node, K key, V *data)
346 {
347   /* Set the node's data.  */
348   node->m_data = data;
349   node->m_key = key;
350 
351   return insert_node (node);
352 }
353 
354 /* Insert new NODE that has already filled key and value.  */
355 
356 template<class K, class V>
357 fibonacci_node<K,V>*
insert_node(fibonacci_node_t * node)358 fibonacci_heap<K,V>::insert_node (fibonacci_node_t *node)
359 {
360   /* Insert it into the root list.  */
361   insert_root (node);
362 
363   /* If their was no minimum, or this key is less than the min,
364      it's the new min.  */
365   if (m_min == NULL || node->m_key < m_min->m_key)
366     m_min = node;
367 
368   m_nodes++;
369 
370   return node;
371 }
372 
373 /* For given NODE, set new KEY and DATA value.  */
374 
375 template<class K, class V>
376 V*
replace_key_data(fibonacci_node<K,V> * node,K key,V * data)377 fibonacci_heap<K,V>::replace_key_data (fibonacci_node<K,V> *node, K key,
378 				       V *data)
379 {
380   K okey;
381   fibonacci_node<K,V> *y;
382   V *odata = node->m_data;
383 
384   /* If we wanted to, we do a real increase by redeleting and
385      inserting.  */
386   if (node->compare_data (key) > 0)
387     {
388       delete_node (node, false);
389 
390       node = new (node) fibonacci_node_t ();
391       insert (node, key, data);
392 
393       return odata;
394     }
395 
396   okey = node->m_key;
397   node->m_data = data;
398   node->m_key = key;
399   y = node->m_parent;
400 
401   /* Short-circuit if the key is the same, as we then don't have to
402      do anything.  Except if we're trying to force the new node to
403      be the new minimum for delete.  */
404   if (okey == key && okey != m_global_min_key)
405     return odata;
406 
407   /* These two compares are specifically <= 0 to make sure that in the case
408      of equality, a node we replaced the data on, becomes the new min.  This
409      is needed so that delete's call to extractmin gets the right node.  */
410   if (y != NULL && node->compare (y) <= 0)
411     {
412       cut (node, y);
413       cascading_cut (y);
414     }
415 
416   if (node->compare (m_min) <= 0)
417     m_min = node;
418 
419   return odata;
420 }
421 
422 /* Extract minimum node in the heap.  Delete fibonacci node if RELEASE
423    is true.  */
424 
425 template<class K, class V>
426 V*
extract_min(bool release)427 fibonacci_heap<K,V>::extract_min (bool release)
428 {
429   fibonacci_node<K,V> *z;
430   V *ret = NULL;
431 
432   /* If we don't have a min set, it means we have no nodes.  */
433   if (m_min != NULL)
434     {
435       /* Otherwise, extract the min node, free the node, and return the
436        node's data.  */
437       z = extract_minimum_node ();
438       ret = z->m_data;
439 
440       if (release)
441         delete (z);
442     }
443 
444   return ret;
445 }
446 
447 /* Delete NODE in the heap, if RELEASE is specified memory is released.  */
448 
449 template<class K, class V>
450 V*
delete_node(fibonacci_node<K,V> * node,bool release)451 fibonacci_heap<K,V>::delete_node (fibonacci_node<K,V> *node, bool release)
452 {
453   V *ret = node->m_data;
454 
455   /* To perform delete, we just make it the min key, and extract.  */
456   replace_key (node, m_global_min_key);
457   if (node != m_min)
458     {
459       fprintf (stderr, "Can't force minimum on fibheap.\n");
460       abort ();
461     }
462   extract_min (release);
463 
464   return ret;
465 }
466 
467 /* Union the heap with HEAPB.  One of the heaps is going to be deleted.  */
468 
469 template<class K, class V>
470 fibonacci_heap<K,V>*
union_with(fibonacci_heap<K,V> * heapb)471 fibonacci_heap<K,V>::union_with (fibonacci_heap<K,V> *heapb)
472 {
473   fibonacci_heap<K,V> *heapa = this;
474 
475   fibonacci_node<K,V> *a_root, *b_root;
476 
477   /* If one of the heaps is empty, the union is just the other heap.  */
478   if ((a_root = heapa->m_root) == NULL)
479     {
480       delete (heapa);
481       return heapb;
482     }
483   if ((b_root = heapb->m_root) == NULL)
484     {
485       delete (heapb);
486       return heapa;
487     }
488 
489   /* Merge them to the next nodes on the opposite chain.  */
490   a_root->m_left->m_right = b_root;
491   b_root->m_left->m_right = a_root;
492   std::swap (a_root->m_left, b_root->m_left);
493   heapa->m_nodes += heapb->m_nodes;
494 
495   /* And set the new minimum, if it's changed.  */
496   if (heapb->m_min->compare (heapa->m_min) < 0)
497     heapa->m_min = heapb->m_min;
498 
499   /* Set m_min to NULL to not to delete live fibonacci nodes.  */
500   heapb->m_min = NULL;
501   delete (heapb);
502 
503   return heapa;
504 }
505 
506 /* Insert it into the root list.  */
507 
508 template<class K, class V>
509 void
insert_root(fibonacci_node_t * node)510 fibonacci_heap<K,V>::insert_root (fibonacci_node_t *node)
511 {
512   /* If the heap is currently empty, the new node becomes the singleton
513      circular root list.  */
514   if (m_root == NULL)
515     {
516       m_root = node;
517       node->m_left = node;
518       node->m_right = node;
519       return;
520     }
521 
522   /* Otherwise, insert it in the circular root list between the root
523      and it's right node.  */
524   m_root->insert_after (node);
525 }
526 
527 /* Remove NODE from PARENT's child list.  */
528 
529 template<class K, class V>
530 void
cut(fibonacci_node<K,V> * node,fibonacci_node<K,V> * parent)531 fibonacci_heap<K,V>::cut (fibonacci_node<K,V> *node,
532 			  fibonacci_node<K,V> *parent)
533 {
534   node->remove ();
535   parent->m_degree--;
536   insert_root (node);
537   node->m_parent = NULL;
538   node->m_mark = 0;
539 }
540 
541 /* Process cut of node Y and do it recursivelly.  */
542 
543 template<class K, class V>
544 void
cascading_cut(fibonacci_node<K,V> * y)545 fibonacci_heap<K,V>::cascading_cut (fibonacci_node<K,V> *y)
546 {
547   fibonacci_node<K,V> *z;
548 
549   while ((z = y->m_parent) != NULL)
550     {
551       if (y->m_mark == 0)
552 	{
553 	  y->m_mark = 1;
554 	  return;
555 	}
556       else
557 	{
558 	  cut (y, z);
559 	  y = z;
560 	}
561     }
562 }
563 
564 /* Extract minimum node from the heap.  */
565 
566 template<class K, class V>
567 fibonacci_node<K,V>*
extract_minimum_node()568 fibonacci_heap<K,V>::extract_minimum_node ()
569 {
570   fibonacci_node<K,V> *ret = m_min;
571   fibonacci_node<K,V> *x, *y, *orig;
572 
573   /* Attach the child list of the minimum node to the root list of the heap.
574      If there is no child list, we don't do squat.  */
575   for (x = ret->m_child, orig = NULL; x != orig && x != NULL; x = y)
576     {
577       if (orig == NULL)
578 	orig = x;
579       y = x->m_right;
580       x->m_parent = NULL;
581       insert_root (x);
582     }
583 
584   /* Remove the old root.  */
585   remove_root (ret);
586   m_nodes--;
587 
588   /* If we are left with no nodes, then the min is NULL.  */
589   if (m_nodes == 0)
590     m_min = NULL;
591   else
592     {
593       /* Otherwise, consolidate to find new minimum, as well as do the reorg
594        work that needs to be done.  */
595       m_min = ret->m_right;
596       consolidate ();
597     }
598 
599   return ret;
600 }
601 
602 /* Remove root NODE from the heap.  */
603 
604 template<class K, class V>
605 void
remove_root(fibonacci_node<K,V> * node)606 fibonacci_heap<K,V>::remove_root (fibonacci_node<K,V> *node)
607 {
608   if (node->m_left == node)
609     m_root = NULL;
610   else
611     m_root = node->remove ();
612 }
613 
614 /* Consolidate heap.  */
615 
616 template<class K, class V>
consolidate()617 void fibonacci_heap<K,V>::consolidate ()
618 {
619   int D = 1 + 8 * sizeof (long);
620   auto_vec<fibonacci_node<K,V> *> a (D);
621   a.safe_grow_cleared (D);
622   fibonacci_node<K,V> *w, *x, *y;
623   int i, d;
624 
625   while ((w = m_root) != NULL)
626     {
627       x = w;
628       remove_root (w);
629       d = x->m_degree;
630       while (a[d] != NULL)
631 	{
632 	  y = a[d];
633 	  if (x->compare (y) > 0)
634 	    std::swap (x, y);
635 	  y->link (x);
636 	  a[d] = NULL;
637 	  d++;
638 	}
639       a[d] = x;
640     }
641   m_min = NULL;
642   for (i = 0; i < D; i++)
643     if (a[i] != NULL)
644       {
645 	insert_root (a[i]);
646 	if (m_min == NULL || a[i]->compare (m_min) < 0)
647 	  m_min = a[i];
648       }
649 }
650 
651 #endif  // GCC_FIBONACCI_HEAP_H
652