libiberty/fibheap.c

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