libiberty/fibheap.c

   1
   2 /* A Fibonacci heap datatype.
   3    Copyright 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
   4    Contributed by Daniel Berlin (dan@cgsoftware.com).
   5
   6 This file is part of GNU CC.
   7
   8 GNU CC is free software; you can redistribute it and/or modify it
   9 under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 2, or (at your option)
  11 any later version.
  12
  13 GNU CC is distributed in the hope that it will be useful, but
  14 WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16 General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GNU CC; see the file COPYING.  If not, write to
  20 the Free Software Foundation, 59 Temple Place - Suite 330,
  21 Boston, MA 02111-1307, USA.  */
  22
  23 /* Fibonacci heaps */
  24 #include <limits.h>
  25 #include <stdlib.h>
  26 #include "libiberty.h"
  27 #include "fibheap.h"
  28
  29
  30 static void fibheap_init PARAMS ((fibheap_t));
  31 static void fibheap_ins_root PARAMS ((fibheap_t, fibnode_t));
  32 static void fibheap_rem_root PARAMS ((fibheap_t, fibnode_t));
  33 static void fibheap_consolidate PARAMS ((fibheap_t));
  34 static void fibheap_link PARAMS ((fibheap_t, fibnode_t, fibnode_t));
  35 static void fibheap_cut PARAMS ((fibheap_t, fibnode_t, fibnode_t));
  36 static void fibheap_cascading_cut PARAMS ((fibheap_t, fibnode_t));
  37 static fibnode_t fibheap_extr_min_node PARAMS ((fibheap_t));
  38 static int fibheap_compare PARAMS ((fibheap_t, fibnode_t, fibnode_t));
  39 static int fibheap_comp_data PARAMS ((fibheap_t, fibheapkey_t, void *, fibnode_t));
  40 static fibnode_t fibnode_new PARAMS ((void));
  41 static void fibnode_init PARAMS ((fibnode_t));
  42 static void fibnode_insert_after PARAMS ((fibnode_t, fibnode_t));
  43 #define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b)
  44 static fibnode_t fibnode_remove PARAMS ((fibnode_t));
  45
  46 /* Create a new fibonacci heap.  */
  47 fibheap_t
  48 fibheap_new ()
  49 {
  50   fibheap_t result;
  51
  52   if ((result = xmalloc (sizeof (*result))) == NULL)
  53     return NULL;
  54
  55   fibheap_init (result);
  56
  57   return result;
  58 }
  59
  60 /* Initialize the passed in fibonacci heap.  */
  61 static void
  62 fibheap_init (heap)
  63      fibheap_t heap;
  64 {
  65   heap->nodes = 0;
  66   heap->min = NULL;
  67   heap->root = NULL;
  68 }
  69
  70 /* Insert DATA, with priority KEY, into HEAP.  */
  71 fibnode_t
  72 fibheap_insert (heap, key, data)
  73      fibheap_t heap;
  74      fibheapkey_t key;
  75      void *data;
  76 {
  77   fibnode_t node;
  78   /* Create the new node, if we fail, return NULL.  */
  79   if ((node = fibnode_new ()) == NULL)
  80     return NULL;
  81   /* Set the node's data.  */
  82   node->data = data;
  83   node->key = key;
  84
  85   /* Insert it into the root list.  */
  86   fibheap_ins_root (heap, node);
  87
  88   /* If their was no minimum, or this key is less than the min, it's the new
  89      min.  */
  90   if (heap->min == NULL || node->key < heap->min->key)
  91     heap->min = node;
  92
  93   heap->nodes++;
  94
  95   return node;
  96 }
  97
  98 /* Return the data of the minimum node (if we know it).  */
  99 void *
 100 fibheap_min (heap)
 101      fibheap_t heap;
 102 {
 103   /* If there is no min, we can't easily return it.  */
 104   if (heap->min == NULL)
 105     return NULL;
 106   return heap->min->data;
 107 }
 108
 109 /* Return the key of the minimum node (if we know it).  */
 110 fibheapkey_t
 111 fibheap_min_key (heap)
 112      fibheap_t heap;
 113 {
 114   /* If there is no min, we can't easily return it.  */
 115   if (heap->min == NULL)
 116     return 0;
 117   return heap->min->key;
 118 }
 119
 120 /* Union HEAPA and HEAPB into a new heap.  */
 121 fibheap_t
 122 fibheap_union (heapa, heapb)
 123      fibheap_t heapa;
 124      fibheap_t heapb;
 125 {
 126   fibnode_t temp;
 127
 128   /* If one of the heaps is empty, the union is just the other heap.  */
 129   if (heapa->root == NULL || heapb->root == NULL)
 130     {
 131       if (heapa->root == NULL)
 132         {
 133           free (heapa);
 134           return heapb;
 135         }
 136       else
 137         {
 138           free (heapb);
 139           return heapa;
 140         }
 141     }
 142   /* Merge them to the next nodes on the opposite chain.  */
 143   heapa->root->left->right = heapb->root;
 144   heapb->root->left->right = heapa->root;
 145   temp = heapa->root->left;
 146   heapa->root->left = heapb->root->left;
 147   heapb->root->left = temp;
 148   heapa->nodes += heapb->nodes;
 149
 150   /* And set the new minimum, if it's changed.  */
 151   if (fibheap_compare (heapa, heapb->min, heapa->min) < 0)
 152     heapa->min = heapb->min;
 153
 154   free (heapb);
 155   return heapa;
 156 }
 157
 158 /* Extract the data of the minimum node from HEAP.  */
 159 void *
 160 fibheap_extract_min (heap)
 161      fibheap_t heap;
 162 {
 163   fibnode_t z;
 164   void *ret;
 165
 166   ret = NULL;
 167   /* If we don't have a min set, it means we have no nodes.  */
 168   if (heap->min != NULL)
 169     {
 170       /* Otherwise, extract the min node, free the node, and return the
 171          node's data.  */
 172       z = fibheap_extr_min_node (heap);
 173       ret = z->data;
 174       free (z);
 175     }
 176
 177   return ret;
 178 }
 179
 180 /* Replace the DATA associated with NODE.  */
 181 void *
 182 fibheap_replace_data (heap, node, data)
 183      fibheap_t heap;
 184      fibnode_t node;
 185      void *data;
 186 {
 187   return fibheap_replace_key_data (heap, node, node->key, data);
 188 }
 189
 190 /* Replace the KEY associated with NODE.  */
 191 fibheapkey_t
 192 fibheap_replace_key (heap, node, key)
 193      fibheap_t heap;
 194      fibnode_t node;
 195      fibheapkey_t key;
 196 {
 197   int ret;
 198
 199   ret = node->key;
 200   (void) fibheap_replace_key_data (heap, node, key, node->data);
 201
 202   return ret;
 203 }
 204
 205 /* Replace both the KEY and the DATA associated with NODE.  */
 206 void *
 207 fibheap_replace_key_data (heap, node, key, data)
 208      fibheap_t heap;
 209      fibnode_t node;
 210      fibheapkey_t key;
 211      void *data;
 212 {
 213   void *odata;
 214   int okey;
 215   fibnode_t y;
 216
 217   /* If we wanted to, we could actually do a real increase by redeleting and
 218      inserting. However, this would require O (log n) time. So just bail out
 219      for now.  */
 220   if (fibheap_comp_data (heap, key, data, node) > 0)
 221     return NULL;
 222
 223   odata = node->data;
 224   okey = node->key;
 225   node->data = data;
 226   node->key = key;
 227   y = node->parent;
 228
 229   if (okey == key)
 230     return odata;
 231
 232   /* These two compares are specifically <= 0 to make sure that in the case
 233      of equality, a node we replaced the data on, becomes the new min.  This
 234      is needed so that delete's call to extractmin gets the right node.  */
 235   if (y != NULL && fibheap_compare (heap, node, y) <= 0)
 236     {
 237       fibheap_cut (heap, node, y);
 238       fibheap_cascading_cut (heap, y);
 239     }
 240
 241   if (fibheap_compare (heap, node, heap->min) <= 0)
 242     heap->min = node;
 243
 244   return odata;
 245 }
 246
 247 /* Delete NODE from HEAP.  */
 248 void *
 249 fibheap_delete_node (heap, node)
 250      fibheap_t heap;
 251      fibnode_t node;
 252 {
 253   void *k;
 254   /* To perform delete, we just make it the min key, and extract.  */
 255   k = node->data;
 256   fibheap_replace_key (heap, node, LONG_MIN);
 257   fibheap_extract_min (heap);
 258
 259   return k;
 260 }
 261
 262 /* Delete HEAP.  */
 263 void
 264 fibheap_delete (heap)
 265      fibheap_t heap;
 266 {
 267   while (heap->min != NULL)
 268     free (fibheap_extr_min_node (heap));
 269
 270   free (heap);
 271 }
 272
 273 /* Determine if HEAP is empty.  */
 274 int
 275 fibheap_empty (heap)
 276      fibheap_t heap;
 277 {
 278   return heap->nodes == 0;
 279 }
 280
 281
 282 /* Extract the minimum node of the heap.  */
 283 static fibnode_t
 284 fibheap_extr_min_node (heap)
 285      fibheap_t heap;
 286 {
 287   fibnode_t ret;
 288   fibnode_t x, y, orig;
 289
 290   ret = heap->min;
 291
 292   orig = NULL;
 293   /* Attach the child list of the minimum node to the root list of the heap.
 294      If there is no child list, we don't do squat.  */
 295   for (x = ret->child; x != orig && x != NULL;)
 296     {
 297       if (orig == NULL)
 298         orig = x;
 299       y = x->right;
 300       x->parent = NULL;
 301       fibheap_ins_root (heap, x);
 302       x = y;
 303     }
 304   /* Remove the old root.  */
 305   fibheap_rem_root (heap, ret);
 306   heap->nodes--;
 307   /* If we are left with no nodes, then the min is NULL.  */
 308   if (heap->nodes == 0)
 309     heap->min = NULL;
 310   else
 311     {
 312       /* Otherwise, consolidate to find new minimum, as well as do the reorg
 313          work that needs to be done.  */
 314       heap->min = ret->right;
 315       fibheap_consolidate (heap);
 316     }
 317
 318   return ret;
 319 }
 320
 321 /* Insert NODE into the root list of HEAP.  */
 322 static void
 323 fibheap_ins_root (heap, node)
 324      fibheap_t heap;
 325      fibnode_t node;
 326 {
 327   /* If the heap is currently empty, the new node becomes the singleton
 328      circular root list.  */
 329   if (heap->root == NULL)
 330     {
 331       heap->root = node;
 332       node->left = node;
 333       node->right = node;
 334       return;
 335     }
 336   /* Otherwise, insert it in the circular root list between the root and it's
 337      right node.  */
 338   fibnode_insert_after (heap->root, node);
 339 }
 340
 341 /* Remove NODE from the rootlist of HEAP.  */
 342 static void
 343 fibheap_rem_root (heap, node)
 344      fibheap_t heap;
 345      fibnode_t node;
 346 {
 347   if (node->left == node)
 348     heap->root = NULL;
 349   else
 350     heap->root = fibnode_remove (node);
 351 }
 352
 353 /* Consolidate the heap.  */
 354 static void
 355 fibheap_consolidate (heap)
 356      fibheap_t heap;
 357 {
 358   fibnode_t a[1 + 8 * sizeof (long)];
 359   fibnode_t w;
 360   fibnode_t y;
 361   fibnode_t x;
 362   int i;
 363   int d;
 364   int D;
 365
 366   D = 1 + 8 * sizeof (long);
 367
 368   memset (a, 0, sizeof (fibnode_t) * D);
 369
 370   while ((w = heap->root) != NULL)
 371     {
 372       x = w;
 373       fibheap_rem_root (heap, w);
 374       d = x->degree;
 375       while (a[d] != NULL)
 376         {
 377           y = a[d];
 378           if (fibheap_compare (heap, x, y) > 0)
 379             {
 380               fibnode_t temp;
 381               temp = x;
 382               x = y;
 383               y = temp;
 384             }
 385           fibheap_link (heap, y, x);
 386           a[d] = NULL;
 387           d++;
 388         }
 389       a[d] = x;
 390     }
 391   heap->min = NULL;
 392   for (i = 0; i < D; i++)
 393     if (a[i] != NULL)
 394       {
 395         fibheap_ins_root (heap, a[i]);
 396         if (heap->min == NULL || fibheap_compare (heap, a[i], heap->min) < 0)
 397           heap->min = a[i];
 398       }
 399 }
 400
 401 /* Make NODE a child of PARENT.  */
 402 static void
 403 fibheap_link (heap, node, parent)
 404      fibheap_t heap ATTRIBUTE_UNUSED;
 405      fibnode_t node;
 406      fibnode_t parent;
 407 {
 408   if (parent->child == NULL)
 409     parent->child = node;
 410   else
 411     fibnode_insert_before (parent->child, node);
 412   node->parent = parent;
 413   parent->degree++;
 414   node->mark = 0;
 415 }
 416
 417 /* Remove NODE from PARENT's child list.  */
 418 static void
 419 fibheap_cut (heap, node, parent)
 420      fibheap_t heap;
 421      fibnode_t node;
 422      fibnode_t parent;
 423 {
 424   fibnode_remove (node);
 425   parent->degree--;
 426   fibheap_ins_root (heap, node);
 427   node->parent = NULL;
 428   node->mark = 0;
 429 }
 430
 431 static void
 432 fibheap_cascading_cut (heap, y)
 433      fibheap_t heap;
 434      fibnode_t y;
 435 {
 436   fibnode_t z;
 437
 438   while ((z = y->parent) != NULL)
 439     {
 440       if (y->mark == 0)
 441         {
 442           y->mark = 1;
 443           return;
 444         }
 445       else
 446         {
 447           fibheap_cut (heap, y, z);
 448           y = z;
 449         }
 450     }
 451 }
 452
 453
 454 static fibnode_t
 455 fibnode_new ()
 456 {
 457   fibnode_t e;
 458
 459   if ((e = xmalloc (sizeof *e)) == NULL)
 460     return NULL;
 461
 462   fibnode_init (e);
 463
 464   return e;
 465 }
 466
 467 static void
 468 fibnode_init (node)
 469      fibnode_t node;
 470 {
 471   node->degree = 0;
 472   node->mark = 0;
 473   node->parent = NULL;
 474   node->child = NULL;
 475   node->left = node;
 476   node->right = node;
 477   node->data = NULL;
 478 }
 479
 480 static void
 481 fibnode_insert_after (a, b)
 482      fibnode_t a;
 483      fibnode_t b;
 484 {
 485   if (a == a->right)
 486     {
 487       a->right = b;
 488       a->left = b;
 489       b->right = a;
 490       b->left = a;
 491     }
 492   else
 493     {
 494       b->right = a->right;
 495       a->right->left = b;
 496       a->right = b;
 497       b->left = a;
 498     }
 499 }
 500
 501
 502 static fibnode_t
 503 fibnode_remove (node)
 504      fibnode_t node;
 505 {
 506   fibnode_t ret;
 507
 508   if (node == node->left)
 509     ret = NULL;
 510   else
 511     ret = node->left;
 512
 513   if (node->parent != NULL && node->parent->child == node)
 514     node->parent->child = ret;
 515
 516   node->right->left = node->left;
 517   node->left->right = node->right;
 518
 519   node->parent = NULL;
 520   node->left = node;
 521   node->right = node;
 522
 523   return ret;
 524 }
 525
 526 static int
 527 fibheap_compare (heap, a, b)
 528      fibheap_t heap ATTRIBUTE_UNUSED;
 529      fibnode_t a;
 530      fibnode_t b;
 531 {
 532   if (a->key < b->key)
 533     return -1;
 534   if (a->key > b->key)
 535     return 1;
 536   return 0;
 537 }
 538
 539 static int
 540 fibheap_comp_data (heap, key, data, b)
 541      fibheap_t heap;
 542      fibheapkey_t key;
 543      void *data;
 544      fibnode_t b;
 545 {
 546   struct fibnode a;
 547
 548   a.key = key;
 549   a.data = data;
 550
 551   return fibheap_compare (heap, &a, b);
 552 }