Branch data Line data Source code
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 : :
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 : 22536025 : fibonacci_node (K key, V *data = NULL): m_parent (NULL), m_child (NULL),
65 : 20941808 : m_left (this), m_right (this), m_key (key), m_data (data),
66 : 20941808 : m_degree (0), m_mark (0)
67 : : {
68 : : }
69 : :
70 : : /* Compare fibonacci node with OTHER node. */
71 : 66402372 : int compare (fibonacci_node_t *other)
72 : : {
73 : 37650061 : if (m_key < other->m_key)
74 : : return -1;
75 : 27914076 : if (m_key > other->m_key)
76 : 10444880 : return 1;
77 : : return 0;
78 : : }
79 : :
80 : : /* Compare the node with a given KEY. */
81 : 2361290 : int compare_data (K key)
82 : : {
83 : 3955507 : 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 : 6324128 : K get_key ()
94 : : {
95 : 6324128 : return m_key;
96 : : }
97 : :
98 : : /* Return data associated with the node. */
99 : 3237363 : V *get_data ()
100 : : {
101 : 3237363 : 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 : 23633866 : void insert_before (fibonacci_node_t *b)
110 : : {
111 : 47267732 : m_left->insert_after (b);
112 : 23633866 : }
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 : 4219783 : fibonacci_heap (K global_min_key, pool_allocator *allocator = NULL):
152 : 4219783 : m_nodes (0), m_min (NULL), m_root (NULL),
153 : 4219783 : m_global_min_key (global_min_key),
154 : 4219783 : m_allocator (allocator), m_own_allocator (false)
155 : : {
156 : 4219759 : if (!m_allocator)
157 : : {
158 : 4219759 : m_allocator = new pool_allocator ("Fibonacci heap",
159 : : sizeof (fibonacci_node_t));
160 : 4219759 : m_own_allocator = true;
161 : : }
162 : 4219759 : }
163 : :
164 : : /* Destructor. */
165 : 4211146 : ~fibonacci_heap ()
166 : : {
167 : : /* Actual memory will be released by the destructor of m_allocator. */
168 : 4211146 : 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 : 4211146 : if (m_own_allocator)
177 : 8422244 : delete m_allocator;
178 : 4211146 : }
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 : 24479874 : bool empty () const
185 : : {
186 : 23501487 : return m_nodes == 0;
187 : : }
188 : :
189 : : /* Return the number of nodes. */
190 : 332702 : size_t nodes () const
191 : : {
192 : 332702 : return m_nodes;
193 : : }
194 : :
195 : : /* Return minimal key presented in the heap. */
196 : 3540618 : K min_key () const
197 : : {
198 : 3540618 : if (m_min == NULL)
199 : 0 : gcc_unreachable ();
200 : :
201 : 3540618 : return m_min->m_key;
202 : : }
203 : :
204 : : /* For given NODE, set new KEY value. */
205 : 2361290 : K replace_key (fibonacci_node_t *node, K key)
206 : : {
207 : 2361290 : K okey = node->m_key;
208 : :
209 : 2361290 : replace_key_data (node, key, node->m_data);
210 : 1999463 : return okey;
211 : : }
212 : :
213 : : /* For given NODE, decrease value to new KEY. */
214 : 688705 : K decrease_key (fibonacci_node_t *node, K key)
215 : : {
216 : 688705 : gcc_assert (key <= node->m_key);
217 : 688705 : 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 : 1870282 : V *min () const
229 : : {
230 : 1870282 : if (m_min == NULL)
231 : : return NULL;
232 : :
233 : 1790687 : 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 : 76972510 : fibonacci_node<K,V>::remove ()
293 : : {
294 : : fibonacci_node<K,V> *ret;
295 : :
296 : 76972510 : if (this == m_left)
297 : : ret = NULL;
298 : : else
299 : 76895909 : ret = m_left;
300 : :
301 : 76972510 : if (m_parent != NULL && m_parent->m_child == this)
302 : 120952 : m_parent->m_child = ret;
303 : :
304 : 76972510 : m_right->m_left = m_left;
305 : 76972510 : m_left->m_right = m_right;
306 : :
307 : 76972510 : m_parent = NULL;
308 : 76972510 : m_left = this;
309 : 76972510 : m_right = this;
310 : :
311 : 76972510 : return ret;
312 : : }
313 : :
314 : : /* Link the node with PARENT. */
315 : :
316 : : template<class K, class V>
317 : : void
318 : 34291022 : fibonacci_node<K,V>::link (fibonacci_node<K,V> *parent)
319 : : {
320 : 34291022 : if (parent->m_child == NULL)
321 : 10657156 : parent->m_child = this;
322 : : else
323 : 23633866 : parent->m_child->insert_before (this);
324 : 34291022 : m_parent = parent;
325 : 34291022 : parent->m_degree++;
326 : 34291022 : m_mark = 0;
327 : 34291022 : }
328 : :
329 : : /* Put node B after this node. */
330 : :
331 : : template<class K, class V>
332 : : void
333 : 100386017 : fibonacci_node<K,V>::insert_after (fibonacci_node<K,V> *b)
334 : : {
335 : 100386017 : fibonacci_node<K,V> *a = this;
336 : :
337 : 23633866 : if (a == a->m_right)
338 : : {
339 : 23402852 : a->m_right = b;
340 : 23402852 : a->m_left = b;
341 : 23402852 : b->m_right = a;
342 : 23402852 : b->m_left = a;
343 : : }
344 : : else
345 : : {
346 : 76983165 : b->m_right = a->m_right;
347 : 76983165 : a->m_right->m_left = b;
348 : 76983165 : a->m_right = b;
349 : 76983165 : 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 : 20174735 : fibonacci_heap<K,V>::insert (K key, V *data)
358 : : {
359 : : /* Create the new node. */
360 : 20174735 : fibonacci_node<K,V> *node = new (m_allocator->allocate ())
361 : : fibonacci_node_t (key, data);
362 : :
363 : 20174735 : 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 : 20174775 : fibonacci_heap<K,V>::insert_node (fibonacci_node_t *node)
384 : : {
385 : : /* Insert it into the root list. */
386 : 20174775 : 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 : 20174775 : if (m_min == NULL || node->m_key < m_min->m_key)
391 : 6011142 : m_min = node;
392 : :
393 : 20174775 : m_nodes++;
394 : :
395 : 20174775 : return node;
396 : : }
397 : :
398 : : /* For given NODE, set new KEY and DATA value. */
399 : :
400 : : template<class K, class V>
401 : : V*
402 : 2361290 : fibonacci_heap<K,V>::replace_key_data (fibonacci_node<K,V> *node, K key,
403 : : V *data)
404 : : {
405 : 767073 : K okey;
406 : : fibonacci_node<K,V> *y;
407 : 2361290 : V *odata = node->m_data;
408 : :
409 : : /* If we wanted to, we do a real increase by redeleting and
410 : : inserting. */
411 : 2361290 : 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 : 2361250 : okey = node->m_key;
422 : 2361250 : node->m_data = data;
423 : 2361250 : node->m_key = key;
424 : 2361250 : 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 : 2361250 : 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 : 2361250 : if (y != NULL && node->compare (y) <= 0)
436 : : {
437 : 207111 : cut (node, y);
438 : 207111 : cascading_cut (y);
439 : : }
440 : :
441 : 2361250 : if (node->compare (m_min) <= 0)
442 : 1437596 : 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 : 20073714 : fibonacci_heap<K,V>::extract_min (bool release)
453 : : {
454 : : fibonacci_node<K,V> *z;
455 : 20073714 : V *ret = NULL;
456 : :
457 : : /* If we don't have a min set, it means we have no nodes. */
458 : 20073714 : if (m_min != NULL)
459 : : {
460 : : /* Otherwise, extract the min node, free the node, and return the
461 : : node's data. */
462 : 20073664 : z = extract_minimum_node ();
463 : 20073664 : ret = z->m_data;
464 : :
465 : 20073664 : if (release)
466 : : {
467 : 20073624 : z->~fibonacci_node_t ();
468 : 20073624 : m_allocator->remove (z);
469 : : }
470 : : }
471 : :
472 : 20073714 : 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 : 515969 : fibonacci_heap<K,V>::delete_node (fibonacci_node<K,V> *node, bool release)
480 : : {
481 : 515969 : V *ret = node->m_data;
482 : :
483 : : /* To perform delete, we just make it the min key, and extract. */
484 : 515969 : replace_key (node, m_global_min_key);
485 : 515969 : if (node != m_min)
486 : : {
487 : 0 : fprintf (stderr, "Can't force minimum on fibheap.\n");
488 : 0 : abort ();
489 : : }
490 : 515969 : extract_min (release);
491 : :
492 : 515969 : 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 : 96834131 : 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 : 96834131 : if (m_root == NULL)
546 : : {
547 : 20081980 : m_root = node;
548 : 20081980 : node->m_left = node;
549 : 20081980 : node->m_right = node;
550 : 20081980 : return;
551 : : }
552 : :
553 : : /* Otherwise, insert it in the circular root list between the root
554 : : and it's right node. */
555 : 76752151 : 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 : 229628 : fibonacci_heap<K,V>::cut (fibonacci_node<K,V> *node,
563 : : fibonacci_node<K,V> *parent)
564 : : {
565 : 229628 : node->remove ();
566 : 229628 : parent->m_degree--;
567 : 229628 : insert_root (node);
568 : 229628 : node->m_parent = NULL;
569 : 229628 : node->m_mark = 0;
570 : 229628 : }
571 : :
572 : : /* Process cut of node Y and do it recursivelly. */
573 : :
574 : : template<class K, class V>
575 : : void
576 : 207111 : fibonacci_heap<K,V>::cascading_cut (fibonacci_node<K,V> *y)
577 : : {
578 : : fibonacci_node<K,V> *z;
579 : :
580 : 229628 : while ((z = y->m_parent) != NULL)
581 : : {
582 : 148176 : if (y->m_mark == 0)
583 : : {
584 : 125659 : y->m_mark = 1;
585 : 125659 : return;
586 : : }
587 : : else
588 : : {
589 : 22517 : cut (y, z);
590 : 22517 : 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 : 20073664 : fibonacci_heap<K,V>::extract_minimum_node ()
600 : : {
601 : 20073664 : 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 : 54051532 : for (x = ret->m_child, orig = NULL; x != orig && x != NULL; x = y)
607 : : {
608 : 33977868 : if (orig == NULL)
609 : 10533630 : orig = x;
610 : 33977868 : y = x->m_right;
611 : 33977868 : x->m_parent = NULL;
612 : 33977868 : insert_root (x);
613 : : }
614 : :
615 : : /* Remove the old root. */
616 : 20073664 : remove_root (ret);
617 : 20073664 : m_nodes--;
618 : :
619 : : /* If we are left with no nodes, then the min is NULL. */
620 : 20073664 : if (m_nodes == 0)
621 : 4210568 : 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 : 15863096 : m_min = ret->m_right;
627 : 15863096 : consolidate ();
628 : : }
629 : :
630 : 20073664 : return ret;
631 : : }
632 : :
633 : : /* Remove root NODE from the heap. */
634 : :
635 : : template<class K, class V>
636 : : void
637 : 96816546 : fibonacci_heap<K,V>::remove_root (fibonacci_node<K,V> *node)
638 : : {
639 : 96816546 : if (node->m_left == node)
640 : 20073664 : m_root = NULL;
641 : : else
642 : 76742882 : m_root = node->remove ();
643 : 96816546 : }
644 : :
645 : : /* Consolidate heap. */
646 : :
647 : : template<class K, class V>
648 : 15863096 : void fibonacci_heap<K,V>::consolidate ()
649 : : {
650 : 15863096 : 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 : 15863096 : memset (a, 0, sizeof (a));
656 : :
657 : 92605978 : while ((w = m_root) != NULL)
658 : : {
659 : 76742882 : x = w;
660 : 76742882 : remove_root (w);
661 : 76742882 : d = x->m_degree;
662 : 76742882 : gcc_checking_assert (d < D);
663 : 111033904 : while (a[d] != NULL)
664 : : {
665 : 34291022 : y = a[d];
666 : 39662642 : if (x->compare (y) > 0)
667 : 6640182 : std::swap (x, y);
668 : 34291022 : y->link (x);
669 : 34291022 : a[d] = NULL;
670 : 34291022 : d++;
671 : : }
672 : 76742882 : a[d] = x;
673 : : }
674 : 15863096 : m_min = NULL;
675 : 1046964336 : for (i = 0; i < D; i++)
676 : 1031101240 : if (a[i] != NULL)
677 : : {
678 : 42451860 : insert_root (a[i]);
679 : 895655710 : if (m_min == NULL || a[i]->compare (m_min) < 0)
680 : 26382276 : m_min = a[i];
681 : : }
682 : 15863096 : }
683 : :
684 : : #endif // GCC_FIBONACCI_HEAP_H
|
