LCOV - code coverage report
Current view: top level - gcc - fibonacci_heap.h (source / functions) Hit Total Coverage
Test: gcc.info Lines: 193 203 95.1 %
Date: 2020-04-04 11:58:09 Functions: 60 62 96.8 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Fibonacci heap for GNU compiler.
       2                 :            :    Copyright (C) 1998-2020 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                 :         20 :   fibonacci_node (): m_parent (NULL), m_child (NULL), m_left (this),
      59                 :         20 :     m_right (this), m_data (NULL), m_degree (0), m_mark (0)
      60                 :            :   {
      61                 :            :   }
      62                 :            : 
      63                 :            :   /* Constructor for a node with given KEY.  */
      64                 :   15672950 :   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                 :   14581210 :     m_degree (0), m_mark (0)
      67                 :            :   {
      68                 :            :   }
      69                 :            : 
      70                 :            :   /* Compare fibonacci node with OTHER node.  */
      71                 :   52647016 :   int compare (fibonacci_node_t *other)
      72                 :            :   {
      73                 :   61171286 :     if (m_key < other->m_key)
      74                 :            :       return -1;
      75                 :   19471052 :     if (m_key > other->m_key)
      76                 :    3441946 :       return 1;
      77                 :            :     return 0;
      78                 :            :   }
      79                 :            : 
      80                 :            :   /* Compare the node with a given KEY.  */
      81                 :    1182095 :   int compare_data (K key)
      82                 :            :   {
      83                 :    1182095 :     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                 :    3303210 :   K get_key ()
      94                 :            :   {
      95                 :            :     return m_key;
      96                 :            :   }
      97                 :            : 
      98                 :            :   /* Return data associated with the node.  */
      99                 :    1055470 :   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                 :   19961848 :   void insert_before (fibonacci_node_t *b)
     110                 :            :   {
     111                 :   48153782 :     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                 :    3042916 :   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                 :    3042916 :     m_allocator (allocator), m_own_allocator (false)
     155                 :            :   {
     156                 :    3042904 :     if (!m_allocator)
     157                 :            :       {
     158                 :    3042904 :         m_allocator = new pool_allocator ("Fibonacci heap",
     159                 :            :                                             sizeof (fibonacci_node_t));
     160                 :    3042904 :         m_own_allocator = true;
     161                 :            :       }
     162                 :    3042904 :   }
     163                 :            : 
     164                 :            :   /* Destructor.  */
     165                 :    3035756 :   ~fibonacci_heap ()
     166                 :            :   {
     167                 :            :     /* Actual memory will be released by the destructor of m_allocator.  */
     168                 :    3035756 :     if (need_finalization_p<fibonacci_node_t> () || !m_own_allocator)
     169                 :         12 :       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                 :    3035756 :     if (m_own_allocator)
     177                 :    6071484 :       delete m_allocator;
     178                 :    3035756 :   }
     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                 :   17366154 :   bool empty () const
     185                 :            :   {
     186                 :            :     return m_nodes == 0;
     187                 :            :   }
     188                 :            : 
     189                 :            :   /* Return the number of nodes.  */
     190                 :      27570 :   size_t nodes () const
     191                 :            :   {
     192                 :            :     return m_nodes;
     193                 :            :   }
     194                 :            : 
     195                 :            :   /* Return minimal key presented in the heap.  */
     196                 :    1712126 :   K min_key () const
     197                 :            :   {
     198                 :    1054146 :     if (m_min == NULL)
     199                 :          0 :       gcc_unreachable ();
     200                 :            : 
     201                 :    1712126 :     return m_min->m_key;
     202                 :            :   }
     203                 :            : 
     204                 :            :   /* For given NODE, set new KEY value.  */
     205                 :    1182096 :   K replace_key (fibonacci_node_t *node, K key)
     206                 :            :   {
     207                 :    1182096 :     K okey = node->m_key;
     208                 :            : 
     209                 :    1182096 :     replace_key_data (node, key, node->m_data);
     210                 :    1132095 :     return okey;
     211                 :            :   }
     212                 :            : 
     213                 :            :   /* For given NODE, decrease value to new KEY.  */
     214                 :      49981 :   K decrease_key (fibonacci_node_t *node, K key)
     215                 :            :   {
     216                 :      49981 :     gcc_assert (key <= node->m_key);
     217                 :      49981 :     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                 :     690605 :   V *min () const
     229                 :            :   {
     230                 :     690605 :     if (m_min == NULL)
     231                 :            :       return NULL;
     232                 :            : 
     233                 :     679221 :     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                 :   62101501 : fibonacci_node<K,V>::remove ()
     293                 :            : {
     294                 :            :   fibonacci_node<K,V> *ret;
     295                 :            : 
     296                 :     116211 :   if (this == m_left)
     297                 :            :     ret = NULL;
     298                 :            :   else
     299                 :      70737 :     ret = m_left;
     300                 :            : 
     301                 :   62101501 :   if (m_parent != NULL && m_parent->m_child == this)
     302                 :      67510 :     m_parent->m_child = ret;
     303                 :            : 
     304                 :   62101501 :   m_right->m_left = m_left;
     305                 :   62101501 :   m_left->m_right = m_right;
     306                 :            : 
     307                 :   62101501 :   m_parent = NULL;
     308                 :   62101501 :   m_left = this;
     309                 :   62101501 :   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                 :   28191924 : fibonacci_node<K,V>::link (fibonacci_node<K,V> *parent)
     319                 :            : {
     320                 :   28191924 :   if (parent->m_child == NULL)
     321                 :    8230026 :     parent->m_child = this;
     322                 :            :   else
     323                 :   48153782 :     parent->m_child->insert_before (this);
     324                 :   28191924 :   m_parent = parent;
     325                 :   28191924 :   parent->m_degree++;
     326                 :   28191924 :   m_mark = 0;
     327                 :            : }
     328                 :            : 
     329                 :            : /* Put node B after this node.  */
     330                 :            : 
     331                 :            : template<class K, class V>
     332                 :            : void
     333                 :   81953429 : fibonacci_node<K,V>::insert_after (fibonacci_node<K,V> *b)
     334                 :            : {
     335                 :   81953429 :   fibonacci_node<K,V> *a = this;
     336                 :            : 
     337                 :   19961848 :   if (a == a->m_right)
     338                 :            :     {
     339                 :   17980090 :       a->m_right = b;
     340                 :   17980090 :       a->m_left = b;
     341                 :   17980090 :       b->m_right = a;
     342                 :   17980090 :       b->m_left = a;
     343                 :            :     }
     344                 :            :   else
     345                 :            :     {
     346                 :   63973309 :       b->m_right = a->m_right;
     347                 :   63973309 :       a->m_right->m_left = b;
     348                 :   63973309 :       a->m_right = b;
     349                 :   63973309 :       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                 :   14490820 : fibonacci_heap<K,V>::insert (K key, V *data)
     358                 :            : {
     359                 :            :   /* Create the new node.  */
     360                 :   14490820 :   fibonacci_node<K,V> *node = new (m_allocator->allocate ())
     361                 :            :                                   fibonacci_node_t (key, data);
     362                 :            : 
     363                 :   14490820 :   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                 :         20 : fibonacci_heap<K,V>::insert (fibonacci_node_t *node, K key, V *data)
     371                 :            : {
     372                 :            :   /* Set the node's data.  */
     373                 :         20 :   node->m_data = data;
     374                 :         20 :   node->m_key = key;
     375                 :            : 
     376                 :         20 :   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                 :   14490840 : fibonacci_heap<K,V>::insert_node (fibonacci_node_t *node)
     384                 :            : {
     385                 :            :   /* Insert it into the root list.  */
     386                 :   28981670 :   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                 :   12970580 :   if (m_min == NULL || node->m_key < m_min->m_key)
     391                 :    4053896 :     m_min = node;
     392                 :            : 
     393                 :   14490840 :   m_nodes++;
     394                 :            : 
     395                 :   14490840 :   return node;
     396                 :            : }
     397                 :            : 
     398                 :            : /* For given NODE, set new KEY and DATA value.  */
     399                 :            : 
     400                 :            : template<class K, class V>
     401                 :            : V*
     402                 :    1182095 : fibonacci_heap<K,V>::replace_key_data (fibonacci_node<K,V> *node, K key,
     403                 :            :                                        V *data)
     404                 :            : {
     405                 :      90395 :   K okey;
     406                 :            :   fibonacci_node<K,V> *y;
     407                 :    1182095 :   V *odata = node->m_data;
     408                 :            : 
     409                 :            :   /* If we wanted to, we do a real increase by redeleting and
     410                 :            :      inserting.  */
     411                 :    1182095 :   if (node->compare_data (key) > 0)
     412                 :            :     {
     413                 :         20 :       delete_node (node, false);
     414                 :            : 
     415                 :         20 :       node = new (node) fibonacci_node_t ();
     416                 :         20 :       insert (node, key, data);
     417                 :            : 
     418                 :         20 :       return odata;
     419                 :            :     }
     420                 :            : 
     421                 :    1182075 :   okey = node->m_key;
     422                 :    1182075 :   node->m_data = data;
     423                 :    1182075 :   node->m_key = key;
     424                 :    1182075 :   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                 :    1182075 :   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                 :    1182075 :   if (y != NULL && node->compare (y) <= 0)
     436                 :            :     {
     437                 :     107686 :       cut (node, y);
     438                 :     107686 :       cascading_cut (y);
     439                 :            :     }
     440                 :            : 
     441                 :    1182075 :   if (node->compare (m_min) <= 0)
     442                 :     998804 :     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                 :   14425029 : fibonacci_heap<K,V>::extract_min (bool release)
     453                 :            : {
     454                 :            :   fibonacci_node<K,V> *z;
     455                 :   14425029 :   V *ret = NULL;
     456                 :            : 
     457                 :            :   /* If we don't have a min set, it means we have no nodes.  */
     458                 :   14425029 :   if (m_min != NULL)
     459                 :            :     {
     460                 :            :       /* Otherwise, extract the min node, free the node, and return the
     461                 :            :        node's data.  */
     462                 :   14425029 :       z = extract_minimum_node ();
     463                 :   14425029 :       ret = z->m_data;
     464                 :            : 
     465                 :   14425029 :       if (release)
     466                 :            :         {
     467                 :   14425009 :           z->~fibonacci_node_t ();
     468                 :   14425009 :           m_allocator->remove (z);
     469                 :            :         }
     470                 :            :     }
     471                 :            : 
     472                 :   14425029 :   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                 :     355169 : fibonacci_heap<K,V>::delete_node (fibonacci_node<K,V> *node, bool release)
     480                 :            : {
     481                 :     355169 :   V *ret = node->m_data;
     482                 :            : 
     483                 :            :   /* To perform delete, we just make it the min key, and extract.  */
     484                 :     355169 :   replace_key (node, m_global_min_key);
     485                 :     355169 :   if (node != m_min)
     486                 :            :     {
     487                 :          0 :       fprintf (stderr, "Can't force minimum on fibheap.\n");
     488                 :          0 :       abort ();
     489                 :            :     }
     490                 :     355169 :   extract_min (release);
     491                 :            : 
     492                 :     355169 :   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                 :          6 : fibonacci_heap<K,V>::union_with (fibonacci_heap<K,V> *heapb)
     500                 :            : {
     501                 :          6 :   fibonacci_heap<K,V> *heapa = this;
     502                 :            : 
     503                 :            :   fibonacci_node<K,V> *a_root, *b_root;
     504                 :            : 
     505                 :            :   /* Both heaps must share allocator.  */
     506                 :          6 :   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                 :          6 :   if ((a_root = heapa->m_root) == NULL)
     510                 :            :     {
     511                 :          2 :       delete (heapa);
     512                 :          2 :       return heapb;
     513                 :            :     }
     514                 :          4 :   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                 :          4 :   a_root->m_left->m_right = b_root;
     522                 :          4 :   b_root->m_left->m_right = a_root;
     523                 :          4 :   std::swap (a_root->m_left, b_root->m_left);
     524                 :          4 :   heapa->m_nodes += heapb->m_nodes;
     525                 :            : 
     526                 :            :   /* And set the new minimum, if it's changed.  */
     527                 :          4 :   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                 :          4 :   heapb->m_min = NULL;
     532                 :          4 :   delete (heapb);
     533                 :            : 
     534                 :          4 :   return heapa;
     535                 :            : }
     536                 :            : 
     537                 :            : /* Insert it into the root list.  */
     538                 :            : 
     539                 :            : template<class K, class V>
     540                 :            : void
     541                 :   76421800 : 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                 :   14490840 :   if (m_root == NULL)
     546                 :            :     {
     547                 :   14430369 :       m_root = node;
     548                 :   14430369 :       node->m_left = node;
     549                 :   14430369 :       node->m_right = node;
     550                 :   14430369 :       return;
     551                 :            :     }
     552                 :            : 
     553                 :            :   /* Otherwise, insert it in the circular root list between the root
     554                 :            :      and it's right node.  */
     555                 :   76482281 :   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                 :     116211 : fibonacci_heap<K,V>::cut (fibonacci_node<K,V> *node,
     563                 :            :                           fibonacci_node<K,V> *parent)
     564                 :            : {
     565                 :     116211 :   node->remove ();
     566                 :     116211 :   parent->m_degree--;
     567                 :     116211 :   insert_root (node);
     568                 :     116211 :   node->m_parent = NULL;
     569                 :     116211 :   node->m_mark = 0;
     570                 :     116211 : }
     571                 :            : 
     572                 :            : /* Process cut of node Y and do it recursivelly.  */
     573                 :            : 
     574                 :            : template<class K, class V>
     575                 :            : void
     576                 :     107686 : fibonacci_heap<K,V>::cascading_cut (fibonacci_node<K,V> *y)
     577                 :            : {
     578                 :            :   fibonacci_node<K,V> *z;
     579                 :            : 
     580                 :     116211 :   while ((z = y->m_parent) != NULL)
     581                 :            :     {
     582                 :      69557 :       if (y->m_mark == 0)
     583                 :            :         {
     584                 :      61032 :           y->m_mark = 1;
     585                 :      61032 :           return;
     586                 :            :         }
     587                 :            :       else
     588                 :            :         {
     589                 :       8525 :           cut (y, z);
     590                 :       8525 :           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                 :   14425029 : fibonacci_heap<K,V>::extract_minimum_node ()
     600                 :            : {
     601                 :   14425029 :   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                 :   14425029 :   for (x = ret->m_child, orig = NULL; x != orig && x != NULL; x = y)
     607                 :            :     {
     608                 :   28021503 :       if (orig == NULL)
     609                 :    8154128 :         orig = x;
     610                 :   28021503 :       y = x->m_right;
     611                 :   28021503 :       x->m_parent = NULL;
     612                 :   70467965 :       insert_root (x);
     613                 :            :     }
     614                 :            : 
     615                 :            :   /* Remove the old root.  */
     616                 :   28850058 :   remove_root (ret);
     617                 :   14425029 :   m_nodes--;
     618                 :            : 
     619                 :            :   /* If we are left with no nodes, then the min is NULL.  */
     620                 :   14425029 :   if (m_nodes == 0)
     621                 :    2585397 :     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                 :   11839629 :       m_min = ret->m_right;
     627                 :   11839629 :       consolidate ();
     628                 :            :     }
     629                 :            : 
     630                 :   14425029 :   return ret;
     631                 :            : }
     632                 :            : 
     633                 :            : /* Remove root NODE from the heap.  */
     634                 :            : 
     635                 :            : template<class K, class V>
     636                 :            : void
     637                 :   76410260 : fibonacci_heap<K,V>::remove_root (fibonacci_node<K,V> *node)
     638                 :            : {
     639                 :   14425029 :   if (node->m_left == node)
     640                 :   14425029 :     m_root = NULL;
     641                 :            :   else
     642                 :   61985311 :     m_root = node->remove ();
     643                 :            : }
     644                 :            : 
     645                 :            : /* Consolidate heap.  */
     646                 :            : 
     647                 :            : template<class K, class V>
     648                 :   11839629 : void fibonacci_heap<K,V>::consolidate ()
     649                 :            : {
     650                 :   11839629 :   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                 :   11839629 :   memset (a, 0, sizeof (a));
     656                 :            : 
     657                 :   73824920 :   while ((w = m_root) != NULL)
     658                 :            :     {
     659                 :   61985311 :       x = w;
     660                 :   61985311 :       remove_root (w);
     661                 :   61985311 :       d = x->m_degree;
     662                 :   61985311 :       gcc_checking_assert (d < D);
     663                 :   90177145 :       while (a[d] != NULL)
     664                 :            :         {
     665                 :   28191924 :           y = a[d];
     666                 :   28191924 :           if (x->compare (y) > 0)
     667                 :   28191924 :             std::swap (x, y);
     668                 :   28191924 :           y->link (x);
     669                 :   28191924 :           a[d] = NULL;
     670                 :   28191924 :           d++;
     671                 :            :         }
     672                 :   61985311 :       a[d] = x;
     673                 :            :     }
     674                 :   11839629 :   m_min = NULL;
     675                 :  781415132 :   for (i = 0; i < D; i++)
     676                 :  769576030 :     if (a[i] != NULL)
     677                 :            :       {
     678                 :   33793307 :         insert_root (a[i]);
     679                 :   33793695 :         if (m_min == NULL || a[i]->compare (m_min) < 0)
     680                 :   20073262 :           m_min = a[i];
     681                 :            :       }
     682                 :   11839629 : }
     683                 :            : 
     684                 :            : #endif  // GCC_FIBONACCI_HEAP_H

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.