gcc/fibonacci_heap.h

   1 /* Fibonacci heap for GNU compiler.
   2    Copyright (C) 1998-2021 Free Software Foundation, Inc.
   3    Contributed by Daniel Berlin (dan@cgsoftware.com).
   4    Re-implemented in C++ by Martin Liska <mliska@suse.cz>
   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   fibonacci_node (): m_parent (NULL), m_child (NULL), m_left (this),
  59     m_right (this), m_data (NULL), m_degree (0), m_mark (0)
  60   {
  61   }
  62
  63   /* Constructor for a node with given KEY.  */
  64   fibonacci_node (K key, V *data = NULL): m_parent (NULL), m_child (NULL),
  65     m_left (this), m_right (this), m_key (key), m_data (data),
  66     m_degree (0), m_mark (0)
  67   {
  68   }
  69
  70   /* Compare fibonacci node with OTHER node.  */
  71   int compare (fibonacci_node_t *other)
  72   {
  73     if (m_key < other->m_key)
  74       return -1;
  75     if (m_key > other->m_key)
  76       return 1;
  77     return 0;
  78   }
  79
  80   /* Compare the node with a given KEY.  */
  81   int compare_data (K key)
  82   {
  83     return fibonacci_node_t (key).compare (this);
  84   }
  85
  86   /* Remove fibonacci heap node.  */
  87   fibonacci_node_t *remove ();
  88
  89   /* Link the node with PARENT.  */
  90   void link (fibonacci_node_t *parent);
  91
  92   /* Return key associated with the node.  */
  93   K get_key ()
  94   {
  95     return m_key;
  96   }
  97
  98   /* Return data associated with the node.  */
  99   V *get_data ()
 100   {
 101     return m_data;
 102   }
 103
 104 private:
 105   /* Put node B after this node.  */
 106   void insert_after (fibonacci_node_t *b);
 107
 108   /* Insert fibonacci node B after this node.  */
 109   void insert_before (fibonacci_node_t *b)
 110   {
 111     m_left->insert_after (b);
 112   }
 113
 114   /* Parent node.  */
 115   fibonacci_node *m_parent;
 116   /* Child node.  */
 117   fibonacci_node *m_child;
 118   /* Left sibling.  */
 119   fibonacci_node *m_left;
 120   /* Right node.  */
 121   fibonacci_node *m_right;
 122   /* Key associated with node.  */
 123   K m_key;
 124   /* Data associated with node.  */
 125   V *m_data;
 126
 127 #if defined (__GNUC__) && (!defined (SIZEOF_INT) || SIZEOF_INT < 4)
 128   /* Degree of the node.  */
 129   __extension__ unsigned long int m_degree : 31;
 130   /* Mark of the node.  */
 131   __extension__ unsigned long int m_mark : 1;
 132 #else
 133   /* Degree of the node.  */
 134   unsigned int m_degree : 31;
 135   /* Mark of the node.  */
 136   unsigned int m_mark : 1;
 137 #endif
 138 };
 139
 140 /* Fibonacci heap class. */
 141 template<class K, class V>
 142 class fibonacci_heap
 143 {
 144   typedef fibonacci_node<K,V> fibonacci_node_t;
 145   friend class fibonacci_node<K,V>;
 146
 147 public:
 148   /* Default constructor.  ALLOCATOR is optional and is primarily useful
 149      when heaps are going to be merged (in that case they need to be allocated
 150      in same alloc pool).  */
 151   fibonacci_heap (K global_min_key, pool_allocator *allocator = NULL):
 152     m_nodes (0), m_min (NULL), m_root (NULL),
 153     m_global_min_key (global_min_key),
 154     m_allocator (allocator), m_own_allocator (false)
 155   {
 156     if (!m_allocator)
 157       {
 158         m_allocator = new pool_allocator ("Fibonacci heap",
 159                                             sizeof (fibonacci_node_t));
 160         m_own_allocator = true;
 161       }
 162   }
 163
 164   /* Destructor.  */
 165   ~fibonacci_heap ()
 166   {
 167     /* Actual memory will be released by the destructor of m_allocator.  */
 168     if (need_finalization_p<fibonacci_node_t> () || !m_own_allocator)
 169       while (m_min != NULL)
 170         {
 171           fibonacci_node_t *n = extract_minimum_node ();
 172           n->~fibonacci_node_t ();
 173           if (!m_own_allocator)
 174             m_allocator->remove (n);
 175         }
 176     if (m_own_allocator)
 177       delete m_allocator;
 178   }
 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   bool empty () const
 185   {
 186     return m_nodes == 0;
 187   }
 188
 189   /* Return the number of nodes.  */
 190   size_t nodes () const
 191   {
 192     return m_nodes;
 193   }
 194
 195   /* Return minimal key presented in the heap.  */
 196   K min_key () const
 197   {
 198     if (m_min == NULL)
 199       gcc_unreachable ();
 200
 201     return m_min->m_key;
 202   }
 203
 204   /* For given NODE, set new KEY value.  */
 205   K replace_key (fibonacci_node_t *node, K key)
 206   {
 207     K okey = node->m_key;
 208
 209     replace_key_data (node, key, node->m_data);
 210     return okey;
 211   }
 212
 213   /* For given NODE, decrease value to new KEY.  */
 214   K decrease_key (fibonacci_node_t *node, K key)
 215   {
 216     gcc_assert (key <= node->m_key);
 217     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   V *min () const
 229   {
 230     if (m_min == NULL)
 231       return NULL;
 232
 233     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 fibonacci_node<K,V>::remove ()
 293 {
 294   fibonacci_node<K,V> *ret;
 295
 296   if (this == m_left)
 297     ret = NULL;
 298   else
 299     ret = m_left;
 300
 301   if (m_parent != NULL && m_parent->m_child == this)
 302     m_parent->m_child = ret;
 303
 304   m_right->m_left = m_left;
 305   m_left->m_right = m_right;
 306
 307   m_parent = NULL;
 308   m_left = this;
 309   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 fibonacci_node<K,V>::link (fibonacci_node<K,V> *parent)
 319 {
 320   if (parent->m_child == NULL)
 321     parent->m_child = this;
 322   else
 323     parent->m_child->insert_before (this);
 324   m_parent = parent;
 325   parent->m_degree++;
 326   m_mark = 0;
 327 }
 328
 329 /* Put node B after this node.  */
 330
 331 template<class K, class V>
 332 void
 333 fibonacci_node<K,V>::insert_after (fibonacci_node<K,V> *b)
 334 {
 335   fibonacci_node<K,V> *a = this;
 336
 337   if (a == a->m_right)
 338     {
 339       a->m_right = b;
 340       a->m_left = b;
 341       b->m_right = a;
 342       b->m_left = a;
 343     }
 344   else
 345     {
 346       b->m_right = a->m_right;
 347       a->m_right->m_left = b;
 348       a->m_right = b;
 349       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 fibonacci_heap<K,V>::insert (K key, V *data)
 358 {
 359   /* Create the new node.  */
 360   fibonacci_node<K,V> *node = new (m_allocator->allocate ())
 361                                   fibonacci_node_t (key, data);
 362
 363   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 fibonacci_heap<K,V>::insert (fibonacci_node_t *node, K key, V *data)
 371 {
 372   /* Set the node's data.  */
 373   node->m_data = data;
 374   node->m_key = key;
 375
 376   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 fibonacci_heap<K,V>::insert_node (fibonacci_node_t *node)
 384 {
 385   /* Insert it into the root list.  */
 386   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   if (m_min == NULL || node->m_key < m_min->m_key)
 391     m_min = node;
 392
 393   m_nodes++;
 394
 395   return node;
 396 }
 397
 398 /* For given NODE, set new KEY and DATA value.  */
 399
 400 template<class K, class V>
 401 V*
 402 fibonacci_heap<K,V>::replace_key_data (fibonacci_node<K,V> *node, K key,
 403                                        V *data)
 404 {
 405   K okey;
 406   fibonacci_node<K,V> *y;
 407   V *odata = node->m_data;
 408
 409   /* If we wanted to, we do a real increase by redeleting and
 410      inserting.  */
 411   if (node->compare_data (key) > 0)
 412     {
 413       delete_node (node, false);
 414
 415       node = new (node) fibonacci_node_t ();
 416       insert (node, key, data);
 417
 418       return odata;
 419     }
 420
 421   okey = node->m_key;
 422   node->m_data = data;
 423   node->m_key = key;
 424   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   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   if (y != NULL && node->compare (y) <= 0)
 436     {
 437       cut (node, y);
 438       cascading_cut (y);
 439     }
 440
 441   if (node->compare (m_min) <= 0)
 442     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 fibonacci_heap<K,V>::extract_min (bool release)
 453 {
 454   fibonacci_node<K,V> *z;
 455   V *ret = NULL;
 456
 457   /* If we don't have a min set, it means we have no nodes.  */
 458   if (m_min != NULL)
 459     {
 460       /* Otherwise, extract the min node, free the node, and return the
 461        node's data.  */
 462       z = extract_minimum_node ();
 463       ret = z->m_data;
 464
 465       if (release)
 466         {
 467           z->~fibonacci_node_t ();
 468           m_allocator->remove (z);
 469         }
 470     }
 471
 472   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 fibonacci_heap<K,V>::delete_node (fibonacci_node<K,V> *node, bool release)
 480 {
 481   V *ret = node->m_data;
 482
 483   /* To perform delete, we just make it the min key, and extract.  */
 484   replace_key (node, m_global_min_key);
 485   if (node != m_min)
 486     {
 487       fprintf (stderr, "Can't force minimum on fibheap.\n");
 488       abort ();
 489     }
 490   extract_min (release);
 491
 492   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 fibonacci_heap<K,V>::union_with (fibonacci_heap<K,V> *heapb)
 500 {
 501   fibonacci_heap<K,V> *heapa = this;
 502
 503   fibonacci_node<K,V> *a_root, *b_root;
 504
 505   /* Both heaps must share allocator.  */
 506   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   if ((a_root = heapa->m_root) == NULL)
 510     {
 511       delete (heapa);
 512       return heapb;
 513     }
 514   if ((b_root = heapb->m_root) == NULL)
 515     {
 516       delete (heapb);
 517       return heapa;
 518     }
 519
 520   /* Merge them to the next nodes on the opposite chain.  */
 521   a_root->m_left->m_right = b_root;
 522   b_root->m_left->m_right = a_root;
 523   std::swap (a_root->m_left, b_root->m_left);
 524   heapa->m_nodes += heapb->m_nodes;
 525
 526   /* And set the new minimum, if it's changed.  */
 527   if (heapb->m_min->compare (heapa->m_min) < 0)
 528     heapa->m_min = heapb->m_min;
 529
 530   /* Set m_min to NULL to not to delete live fibonacci nodes.  */
 531   heapb->m_min = NULL;
 532   delete (heapb);
 533
 534   return heapa;
 535 }
 536
 537 /* Insert it into the root list.  */
 538
 539 template<class K, class V>
 540 void
 541 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   if (m_root == NULL)
 546     {
 547       m_root = node;
 548       node->m_left = node;
 549       node->m_right = node;
 550       return;
 551     }
 552
 553   /* Otherwise, insert it in the circular root list between the root
 554      and it's right node.  */
 555   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 fibonacci_heap<K,V>::cut (fibonacci_node<K,V> *node,
 563                           fibonacci_node<K,V> *parent)
 564 {
 565   node->remove ();
 566   parent->m_degree--;
 567   insert_root (node);
 568   node->m_parent = NULL;
 569   node->m_mark = 0;
 570 }
 571
 572 /* Process cut of node Y and do it recursivelly.  */
 573
 574 template<class K, class V>
 575 void
 576 fibonacci_heap<K,V>::cascading_cut (fibonacci_node<K,V> *y)
 577 {
 578   fibonacci_node<K,V> *z;
 579
 580   while ((z = y->m_parent) != NULL)
 581     {
 582       if (y->m_mark == 0)
 583         {
 584           y->m_mark = 1;
 585           return;
 586         }
 587       else
 588         {
 589           cut (y, z);
 590           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 fibonacci_heap<K,V>::extract_minimum_node ()
 600 {
 601   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   for (x = ret->m_child, orig = NULL; x != orig && x != NULL; x = y)
 607     {
 608       if (orig == NULL)
 609         orig = x;
 610       y = x->m_right;
 611       x->m_parent = NULL;
 612       insert_root (x);
 613     }
 614
 615   /* Remove the old root.  */
 616   remove_root (ret);
 617   m_nodes--;
 618
 619   /* If we are left with no nodes, then the min is NULL.  */
 620   if (m_nodes == 0)
 621     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       m_min = ret->m_right;
 627       consolidate ();
 628     }
 629
 630   return ret;
 631 }
 632
 633 /* Remove root NODE from the heap.  */
 634
 635 template<class K, class V>
 636 void
 637 fibonacci_heap<K,V>::remove_root (fibonacci_node<K,V> *node)
 638 {
 639   if (node->m_left == node)
 640     m_root = NULL;
 641   else
 642     m_root = node->remove ();
 643 }
 644
 645 /* Consolidate heap.  */
 646
 647 template<class K, class V>
 648 void fibonacci_heap<K,V>::consolidate ()
 649 {
 650   const int D = 1 + 8 * sizeof (long);
 651   fibonacci_node<K,V> *a[D];
 652   fibonacci_node<K,V> *w, *x, *y;
 653   int i, d;
 654
 655   memset (a, 0, sizeof (a));
 656
 657   while ((w = m_root) != NULL)
 658     {
 659       x = w;
 660       remove_root (w);
 661       d = x->m_degree;
 662       gcc_checking_assert (d < D);
 663       while (a[d] != NULL)
 664         {
 665           y = a[d];
 666           if (x->compare (y) > 0)
 667             std::swap (x, y);
 668           y->link (x);
 669           a[d] = NULL;
 670           d++;
 671         }
 672       a[d] = x;
 673     }
 674   m_min = NULL;
 675   for (i = 0; i < D; i++)
 676     if (a[i] != NULL)
 677       {
 678         insert_root (a[i]);
 679         if (m_min == NULL || a[i]->compare (m_min) < 0)
 680           m_min = a[i];
 681       }
 682 }
 683
 684 #endif  // GCC_FIBONACCI_HEAP_H