LCOV - code coverage report
Current view: top level - gcc - fibonacci_heap.h (source / functions) Coverage Total Hit
Test: gcc.info Lines: 95.3 % 214 204
Test Date: 2024-12-14 13:15:07 Functions: 97.2 % 108 105
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-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                 :    22462320 :   fibonacci_node (K key, V *data = NULL): m_parent (NULL), m_child (NULL),
      65                 :    20871369 :     m_left (this), m_right (this), m_key (key), m_data (data),
      66                 :    20871369 :     m_degree (0), m_mark (0)
      67                 :             :   {
      68                 :             :   }
      69                 :             : 
      70                 :             :   /* Compare fibonacci node with OTHER node.  */
      71                 :    66205044 :   int compare (fibonacci_node_t *other)
      72                 :             :   {
      73                 :    37493814 :     if (m_key < other->m_key)
      74                 :             :       return -1;
      75                 :    27816761 :     if (m_key > other->m_key)
      76                 :    10392316 :       return 1;
      77                 :             :     return 0;
      78                 :             :   }
      79                 :             : 
      80                 :             :   /* Compare the node with a given KEY.  */
      81                 :     2355635 :   int compare_data (K key)
      82                 :             :   {
      83                 :     3946586 :     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                 :     6310241 :   K get_key ()
      94                 :             :   {
      95                 :     6310241 :     return m_key;
      96                 :             :   }
      97                 :             : 
      98                 :             :   /* Return data associated with the node.  */
      99                 :     3232915 :   V *get_data ()
     100                 :             :   {
     101                 :     3232915 :     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                 :    23544889 :   void insert_before (fibonacci_node_t *b)
     110                 :             :   {
     111                 :    47089778 :     m_left->insert_after (b);
     112                 :    23544889 :   }
     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                 :     4209262 :   fibonacci_heap (K global_min_key, pool_allocator *allocator = NULL):
     152                 :     4209262 :     m_nodes (0), m_min (NULL), m_root (NULL),
     153                 :     4209262 :     m_global_min_key (global_min_key),
     154                 :     4209262 :     m_allocator (allocator), m_own_allocator (false)
     155                 :             :   {
     156                 :     4209238 :     if (!m_allocator)
     157                 :             :       {
     158                 :     4209238 :         m_allocator = new pool_allocator ("Fibonacci heap",
     159                 :             :                                             sizeof (fibonacci_node_t));
     160                 :     4209238 :         m_own_allocator = true;
     161                 :             :       }
     162                 :     4209238 :   }
     163                 :             : 
     164                 :             :   /* Destructor.  */
     165                 :     4200624 :   ~fibonacci_heap ()
     166                 :             :   {
     167                 :             :     /* Actual memory will be released by the destructor of m_allocator.  */
     168                 :     4200624 :     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                 :     4200624 :     if (m_own_allocator)
     177                 :     8401200 :       delete m_allocator;
     178                 :     4200624 :   }
     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                 :    24383093 :   bool empty () const
     185                 :             :   {
     186                 :    23413396 :     return m_nodes == 0;
     187                 :             :   }
     188                 :             : 
     189                 :             :   /* Return the number of nodes.  */
     190                 :      332404 :   size_t nodes () const
     191                 :             :   {
     192                 :      332404 :     return m_nodes;
     193                 :             :   }
     194                 :             : 
     195                 :             :   /* Return minimal key presented in the heap.  */
     196                 :     3530160 :   K min_key () const
     197                 :             :   {
     198                 :     3530160 :     if (m_min == NULL)
     199                 :           0 :       gcc_unreachable ();
     200                 :             : 
     201                 :     3530160 :     return m_min->m_key;
     202                 :             :   }
     203                 :             : 
     204                 :             :   /* For given NODE, set new KEY value.  */
     205                 :     2355635 :   K replace_key (fibonacci_node_t *node, K key)
     206                 :             :   {
     207                 :     2355635 :     K okey = node->m_key;
     208                 :             : 
     209                 :     2355635 :     replace_key_data (node, key, node->m_data);
     210                 :     1993071 :     return okey;
     211                 :             :   }
     212                 :             : 
     213                 :             :   /* For given NODE, decrease value to new KEY.  */
     214                 :      687021 :   K decrease_key (fibonacci_node_t *node, K key)
     215                 :             :   {
     216                 :      687021 :     gcc_assert (key <= node->m_key);
     217                 :      687021 :     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                 :     1868653 :   V *min () const
     229                 :             :   {
     230                 :     1868653 :     if (m_min == NULL)
     231                 :             :       return NULL;
     232                 :             : 
     233                 :     1789406 :     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                 :    76737418 : fibonacci_node<K,V>::remove ()
     293                 :             : {
     294                 :             :   fibonacci_node<K,V> *ret;
     295                 :             : 
     296                 :    76737418 :   if (this == m_left)
     297                 :             :     ret = NULL;
     298                 :             :   else
     299                 :    76661564 :     ret = m_left;
     300                 :             : 
     301                 :    76737418 :   if (m_parent != NULL && m_parent->m_child == this)
     302                 :      120002 :     m_parent->m_child = ret;
     303                 :             : 
     304                 :    76737418 :   m_right->m_left = m_left;
     305                 :    76737418 :   m_left->m_right = m_right;
     306                 :             : 
     307                 :    76737418 :   m_parent = NULL;
     308                 :    76737418 :   m_left = this;
     309                 :    76737418 :   m_right = this;
     310                 :             : 
     311                 :    76737418 :   return ret;
     312                 :             : }
     313                 :             : 
     314                 :             : /* Link the node with PARENT.  */
     315                 :             : 
     316                 :             : template<class K, class V>
     317                 :             : void
     318                 :    34168102 : fibonacci_node<K,V>::link (fibonacci_node<K,V> *parent)
     319                 :             : {
     320                 :    34168102 :   if (parent->m_child == NULL)
     321                 :    10623213 :     parent->m_child = this;
     322                 :             :   else
     323                 :    23544889 :     parent->m_child->insert_before (this);
     324                 :    34168102 :   m_parent = parent;
     325                 :    34168102 :   parent->m_degree++;
     326                 :    34168102 :   m_mark = 0;
     327                 :    34168102 : }
     328                 :             : 
     329                 :             : /* Put node B after this node.  */
     330                 :             : 
     331                 :             : template<class K, class V>
     332                 :             : void
     333                 :   100063022 : fibonacci_node<K,V>::insert_after (fibonacci_node<K,V> *b)
     334                 :             : {
     335                 :   100063022 :   fibonacci_node<K,V> *a = this;
     336                 :             : 
     337                 :    23544889 :   if (a == a->m_right)
     338                 :             :     {
     339                 :    23329376 :       a->m_right = b;
     340                 :    23329376 :       a->m_left = b;
     341                 :    23329376 :       b->m_right = a;
     342                 :    23329376 :       b->m_left = a;
     343                 :             :     }
     344                 :             :   else
     345                 :             :     {
     346                 :    76733646 :       b->m_right = a->m_right;
     347                 :    76733646 :       a->m_right->m_left = b;
     348                 :    76733646 :       a->m_right = b;
     349                 :    76733646 :       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                 :    20106685 : fibonacci_heap<K,V>::insert (K key, V *data)
     358                 :             : {
     359                 :             :   /* Create the new node.  */
     360                 :    20106685 :   fibonacci_node<K,V> *node = new (m_allocator->allocate ())
     361                 :             :                                   fibonacci_node_t (key, data);
     362                 :             : 
     363                 :    20106685 :   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                 :    20106725 : fibonacci_heap<K,V>::insert_node (fibonacci_node_t *node)
     384                 :             : {
     385                 :             :   /* Insert it into the root list.  */
     386                 :    20106725 :   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                 :    20106725 :   if (m_min == NULL || node->m_key < m_min->m_key)
     391                 :     5987713 :     m_min = node;
     392                 :             : 
     393                 :    20106725 :   m_nodes++;
     394                 :             : 
     395                 :    20106725 :   return node;
     396                 :             : }
     397                 :             : 
     398                 :             : /* For given NODE, set new KEY and DATA value.  */
     399                 :             : 
     400                 :             : template<class K, class V>
     401                 :             : V*
     402                 :     2355635 : fibonacci_heap<K,V>::replace_key_data (fibonacci_node<K,V> *node, K key,
     403                 :             :                                        V *data)
     404                 :             : {
     405                 :      764684 :   K okey;
     406                 :             :   fibonacci_node<K,V> *y;
     407                 :     2355635 :   V *odata = node->m_data;
     408                 :             : 
     409                 :             :   /* If we wanted to, we do a real increase by redeleting and
     410                 :             :      inserting.  */
     411                 :     2355635 :   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                 :     2355595 :   okey = node->m_key;
     422                 :     2355595 :   node->m_data = data;
     423                 :     2355595 :   node->m_key = key;
     424                 :     2355595 :   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                 :     2355595 :   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                 :     2355595 :   if (y != NULL && node->compare (y) <= 0)
     436                 :             :     {
     437                 :      205877 :       cut (node, y);
     438                 :      205877 :       cascading_cut (y);
     439                 :             :     }
     440                 :             : 
     441                 :     2355595 :   if (node->compare (m_min) <= 0)
     442                 :     1433227 :     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                 :    20005789 : fibonacci_heap<K,V>::extract_min (bool release)
     453                 :             : {
     454                 :             :   fibonacci_node<K,V> *z;
     455                 :    20005789 :   V *ret = NULL;
     456                 :             : 
     457                 :             :   /* If we don't have a min set, it means we have no nodes.  */
     458                 :    20005789 :   if (m_min != NULL)
     459                 :             :     {
     460                 :             :       /* Otherwise, extract the min node, free the node, and return the
     461                 :             :        node's data.  */
     462                 :    20005739 :       z = extract_minimum_node ();
     463                 :    20005739 :       ret = z->m_data;
     464                 :             : 
     465                 :    20005739 :       if (release)
     466                 :             :         {
     467                 :    20005699 :           z->~fibonacci_node_t ();
     468                 :    20005699 :           m_allocator->remove (z);
     469                 :             :         }
     470                 :             :     }
     471                 :             : 
     472                 :    20005789 :   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                 :      515930 : fibonacci_heap<K,V>::delete_node (fibonacci_node<K,V> *node, bool release)
     480                 :             : {
     481                 :      515930 :   V *ret = node->m_data;
     482                 :             : 
     483                 :             :   /* To perform delete, we just make it the min key, and extract.  */
     484                 :      515930 :   replace_key (node, m_global_min_key);
     485                 :      515930 :   if (node != m_min)
     486                 :             :     {
     487                 :           0 :       fprintf (stderr, "Can't force minimum on fibheap.\n");
     488                 :           0 :       abort ();
     489                 :             :     }
     490                 :      515930 :   extract_min (release);
     491                 :             : 
     492                 :      515930 :   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                 :    96532178 : 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                 :    96532178 :   if (m_root == NULL)
     546                 :             :     {
     547                 :    20014045 :       m_root = node;
     548                 :    20014045 :       node->m_left = node;
     549                 :    20014045 :       node->m_right = node;
     550                 :    20014045 :       return;
     551                 :             :     }
     552                 :             : 
     553                 :             :   /* Otherwise, insert it in the circular root list between the root
     554                 :             :      and it's right node.  */
     555                 :    76518133 :   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                 :      228536 : fibonacci_heap<K,V>::cut (fibonacci_node<K,V> *node,
     563                 :             :                           fibonacci_node<K,V> *parent)
     564                 :             : {
     565                 :      228536 :   node->remove ();
     566                 :      228536 :   parent->m_degree--;
     567                 :      228536 :   insert_root (node);
     568                 :      228536 :   node->m_parent = NULL;
     569                 :      228536 :   node->m_mark = 0;
     570                 :      228536 : }
     571                 :             : 
     572                 :             : /* Process cut of node Y and do it recursivelly.  */
     573                 :             : 
     574                 :             : template<class K, class V>
     575                 :             : void
     576                 :      205877 : fibonacci_heap<K,V>::cascading_cut (fibonacci_node<K,V> *y)
     577                 :             : {
     578                 :             :   fibonacci_node<K,V> *z;
     579                 :             : 
     580                 :      228536 :   while ((z = y->m_parent) != NULL)
     581                 :             :     {
     582                 :      147630 :       if (y->m_mark == 0)
     583                 :             :         {
     584                 :      124971 :           y->m_mark = 1;
     585                 :      124971 :           return;
     586                 :             :         }
     587                 :             :       else
     588                 :             :         {
     589                 :       22659 :           cut (y, z);
     590                 :       22659 :           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                 :    20005739 : fibonacci_heap<K,V>::extract_minimum_node ()
     600                 :             : {
     601                 :    20005739 :   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                 :    53861876 :   for (x = ret->m_child, orig = NULL; x != orig && x != NULL; x = y)
     607                 :             :     {
     608                 :    33856137 :       if (orig == NULL)
     609                 :    10500491 :         orig = x;
     610                 :    33856137 :       y = x->m_right;
     611                 :    33856137 :       x->m_parent = NULL;
     612                 :    33856137 :       insert_root (x);
     613                 :             :     }
     614                 :             : 
     615                 :             :   /* Remove the old root.  */
     616                 :    20005739 :   remove_root (ret);
     617                 :    20005739 :   m_nodes--;
     618                 :             : 
     619                 :             :   /* If we are left with no nodes, then the min is NULL.  */
     620                 :    20005739 :   if (m_nodes == 0)
     621                 :     4193023 :     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                 :    15812716 :       m_min = ret->m_right;
     627                 :    15812716 :       consolidate ();
     628                 :             :     }
     629                 :             : 
     630                 :    20005739 :   return ret;
     631                 :             : }
     632                 :             : 
     633                 :             : /* Remove root NODE from the heap.  */
     634                 :             : 
     635                 :             : template<class K, class V>
     636                 :             : void
     637                 :    96514621 : fibonacci_heap<K,V>::remove_root (fibonacci_node<K,V> *node)
     638                 :             : {
     639                 :    96514621 :   if (node->m_left == node)
     640                 :    20005739 :     m_root = NULL;
     641                 :             :   else
     642                 :    76508882 :     m_root = node->remove ();
     643                 :    96514621 : }
     644                 :             : 
     645                 :             : /* Consolidate heap.  */
     646                 :             : 
     647                 :             : template<class K, class V>
     648                 :    15812716 : void fibonacci_heap<K,V>::consolidate ()
     649                 :             : {
     650                 :    15812716 :   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                 :    15812716 :   memset (a, 0, sizeof (a));
     656                 :             : 
     657                 :    92321598 :   while ((w = m_root) != NULL)
     658                 :             :     {
     659                 :    76508882 :       x = w;
     660                 :    76508882 :       remove_root (w);
     661                 :    76508882 :       d = x->m_degree;
     662                 :    76508882 :       gcc_checking_assert (d < D);
     663                 :   110676984 :       while (a[d] != NULL)
     664                 :             :         {
     665                 :    34168102 :           y = a[d];
     666                 :    39523560 :           if (x->compare (y) > 0)
     667                 :     6596943 :             std::swap (x, y);
     668                 :    34168102 :           y->link (x);
     669                 :    34168102 :           a[d] = NULL;
     670                 :    34168102 :           d++;
     671                 :             :         }
     672                 :    76508882 :       a[d] = x;
     673                 :             :     }
     674                 :    15812716 :   m_min = NULL;
     675                 :  1043639256 :   for (i = 0; i < D; i++)
     676                 :  1027826540 :     if (a[i] != NULL)
     677                 :             :       {
     678                 :    42340780 :         insert_root (a[i]);
     679                 :   892928966 :         if (m_min == NULL || a[i]->compare (m_min) < 0)
     680                 :    26294794 :           m_min = a[i];
     681                 :             :       }
     682                 :    15812716 : }
     683                 :             : 
     684                 :             : #endif  // GCC_FIBONACCI_HEAP_H
        

Generated by: LCOV version 2.1-beta

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,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.