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_ins_root PARAMS ((fibheap_t, fibnode_t));
  41 static void fibheap_rem_root PARAMS ((fibheap_t, fibnode_t));
  42 static void fibheap_consolidate PARAMS ((fibheap_t));
  43 static void fibheap_link PARAMS ((fibheap_t, fibnode_t, fibnode_t));
  44 static void fibheap_cut PARAMS ((fibheap_t, fibnode_t, fibnode_t));
  45 static void fibheap_cascading_cut PARAMS ((fibheap_t, fibnode_t));
  46 static fibnode_t fibheap_extr_min_node PARAMS ((fibheap_t));
  47 static int fibheap_compare PARAMS ((fibheap_t, fibnode_t, fibnode_t));
  48 static int fibheap_comp_data PARAMS ((fibheap_t, fibheapkey_t, void *,
  49                                       fibnode_t));
  50 static fibnode_t fibnode_new PARAMS ((void));
  51 static void fibnode_insert_after PARAMS ((fibnode_t, fibnode_t));
  52 #define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b)
  53 static fibnode_t fibnode_remove PARAMS ((fibnode_t));
  54
  55 \f
  56 /* Create a new fibonacci heap.  */
  57 fibheap_t
  58 fibheap_new ()
  59 {
  60   return (fibheap_t) xcalloc (1, sizeof (struct fibheap));
  61 }
  62
  63 /* Create a new fibonacci heap node.  */
  64 static fibnode_t
  65 fibnode_new ()
  66 {
  67   fibnode_t node;
  68
  69   node = (fibnode_t) xcalloc (1, sizeof *node);
  70   node->left = node;
  71   node->right = node;
  72
  73   return node;
  74 }
  75
  76 static inline int
  77 fibheap_compare (heap, a, b)
  78      fibheap_t heap ATTRIBUTE_UNUSED;
  79      fibnode_t a;
  80      fibnode_t b;
  81 {
  82   if (a->key < b->key)
  83     return -1;
  84   if (a->key > b->key)
  85     return 1;
  86   return 0;
  87 }
  88
  89 static inline int
  90 fibheap_comp_data (heap, key, data, b)
  91      fibheap_t heap;
  92      fibheapkey_t key;
  93      void *data;
  94      fibnode_t b;
  95 {
  96   struct fibnode a;
  97
  98   a.key = key;
  99   a.data = data;
 100
 101   return fibheap_compare (heap, &a, b);
 102 }
 103
 104 /* Insert DATA, with priority KEY, into HEAP.  */
 105 fibnode_t
 106 fibheap_insert (heap, key, data)
 107      fibheap_t heap;
 108      fibheapkey_t key;
 109      void *data;
 110 {
 111   fibnode_t node;
 112
 113   /* Create the new node.  */
 114   node = fibnode_new ();
 115
 116   /* Set the node's data.  */
 117   node->data = data;
 118   node->key = key;
 119
 120   /* Insert it into the root list.  */
 121   fibheap_ins_root (heap, node);
 122
 123   /* If their was no minimum, or this key is less than the min,
 124      it's the new min.  */
 125   if (heap->min == NULL || node->key < heap->min->key)
 126     heap->min = node;
 127
 128   heap->nodes++;
 129
 130   return node;
 131 }
 132
 133 /* Return the data of the minimum node (if we know it).  */
 134 void *
 135 fibheap_min (heap)
 136      fibheap_t heap;
 137 {
 138   /* If there is no min, we can't easily return it.  */
 139   if (heap->min == NULL)
 140     return NULL;
 141   return heap->min->data;
 142 }
 143
 144 /* Return the key of the minimum node (if we know it).  */
 145 fibheapkey_t
 146 fibheap_min_key (heap)
 147      fibheap_t heap;
 148 {
 149   /* If there is no min, we can't easily return it.  */
 150   if (heap->min == NULL)
 151     return 0;
 152   return heap->min->key;
 153 }
 154
 155 /* Union HEAPA and HEAPB into a new heap.  */
 156 fibheap_t
 157 fibheap_union (heapa, heapb)
 158      fibheap_t heapa;
 159      fibheap_t heapb;
 160 {
 161   fibnode_t a_root, b_root, temp;
 162
 163   /* If one of the heaps is empty, the union is just the other heap.  */
 164   if ((a_root = heapa->root) == NULL)
 165     {
 166       free (heapa);
 167       return heapb;
 168     }
 169   if ((b_root = heapb->root) == NULL)
 170     {
 171       free (heapb);
 172       return heapa;
 173     }
 174
 175   /* Merge them to the next nodes on the opposite chain.  */
 176   a_root->left->right = b_root;
 177   b_root->left->right = a_root;
 178   temp = a_root->left;
 179   a_root->left = b_root->left;
 180   b_root->left = temp;
 181   heapa->nodes += heapb->nodes;
 182
 183   /* And set the new minimum, if it's changed.  */
 184   if (fibheap_compare (heapa, heapb->min, heapa->min) < 0)
 185     heapa->min = heapb->min;
 186
 187   free (heapb);
 188   return heapa;
 189 }
 190
 191 /* Extract the data of the minimum node from HEAP.  */
 192 void *
 193 fibheap_extract_min (heap)
 194      fibheap_t heap;
 195 {
 196   fibnode_t z;
 197   void *ret = NULL;
 198
 199   /* If we don't have a min set, it means we have no nodes.  */
 200   if (heap->min != NULL)
 201     {
 202       /* Otherwise, extract the min node, free the node, and return the
 203          node's data.  */
 204       z = fibheap_extr_min_node (heap);
 205       ret = z->data;
 206       free (z);
 207     }
 208
 209   return ret;
 210 }
 211
 212 /* Replace both the KEY and the DATA associated with NODE.  */
 213 void *
 214 fibheap_replace_key_data (heap, node, key, data)
 215      fibheap_t heap;
 216      fibnode_t node;
 217      fibheapkey_t key;
 218      void *data;
 219 {
 220   void *odata;
 221   int okey;
 222   fibnode_t y;
 223
 224   /* If we wanted to, we could actually do a real increase by redeleting and
 225      inserting. However, this would require O (log n) time. So just bail out
 226      for now.  */
 227   if (fibheap_comp_data (heap, key, data, node) > 0)
 228     return NULL;
 229
 230   odata = node->data;
 231   okey = node->key;
 232   node->data = data;
 233   node->key = key;
 234   y = node->parent;
 235
 236   if (okey == key)
 237     return odata;
 238
 239   /* These two compares are specifically <= 0 to make sure that in the case
 240      of equality, a node we replaced the data on, becomes the new min.  This
 241      is needed so that delete's call to extractmin gets the right node.  */
 242   if (y != NULL && fibheap_compare (heap, node, y) <= 0)
 243     {
 244       fibheap_cut (heap, node, y);
 245       fibheap_cascading_cut (heap, y);
 246     }
 247
 248   if (fibheap_compare (heap, node, heap->min) <= 0)
 249     heap->min = node;
 250
 251   return odata;
 252 }
 253
 254 /* Replace the DATA associated with NODE.  */
 255 void *
 256 fibheap_replace_data (heap, node, data)
 257      fibheap_t heap;
 258      fibnode_t node;
 259      void *data;
 260 {
 261   return fibheap_replace_key_data (heap, node, node->key, data);
 262 }
 263
 264 /* Replace the KEY associated with NODE.  */
 265 fibheapkey_t
 266 fibheap_replace_key (heap, node, key)
 267      fibheap_t heap;
 268      fibnode_t node;
 269      fibheapkey_t key;
 270 {
 271   int okey = node->key;
 272   fibheap_replace_key_data (heap, node, key, node->data);
 273   return okey;
 274 }
 275
 276 /* Delete NODE from HEAP.  */
 277 void *
 278 fibheap_delete_node (heap, node)
 279      fibheap_t heap;
 280      fibnode_t node;
 281 {
 282   void *ret = node->data;
 283
 284   /* To perform delete, we just make it the min key, and extract.  */
 285   fibheap_replace_key (heap, node, FIBHEAPKEY_MIN);
 286   fibheap_extract_min (heap);
 287
 288   return ret;
 289 }
 290
 291 /* Delete HEAP.  */
 292 void
 293 fibheap_delete (heap)
 294      fibheap_t heap;
 295 {
 296   while (heap->min != NULL)
 297     free (fibheap_extr_min_node (heap));
 298
 299   free (heap);
 300 }
 301
 302 /* Determine if HEAP is empty.  */
 303 int
 304 fibheap_empty (heap)
 305      fibheap_t heap;
 306 {
 307   return heap->nodes == 0;
 308 }
 309
 310 /* Extract the minimum node of the heap.  */
 311 static fibnode_t
 312 fibheap_extr_min_node (heap)
 313      fibheap_t heap;
 314 {
 315   fibnode_t ret = heap->min;
 316   fibnode_t x, y, orig;
 317
 318   /* Attach the child list of the minimum node to the root list of the heap.
 319      If there is no child list, we don't do squat.  */
 320   for (x = ret->child, orig = NULL; x != orig && x != NULL; x = y)
 321     {
 322       if (orig == NULL)
 323         orig = x;
 324       y = x->right;
 325       x->parent = NULL;
 326       fibheap_ins_root (heap, x);
 327     }
 328
 329   /* Remove the old root.  */
 330   fibheap_rem_root (heap, ret);
 331   heap->nodes--;
 332
 333   /* If we are left with no nodes, then the min is NULL.  */
 334   if (heap->nodes == 0)
 335     heap->min = NULL;
 336   else
 337     {
 338       /* Otherwise, consolidate to find new minimum, as well as do the reorg
 339          work that needs to be done.  */
 340       heap->min = ret->right;
 341       fibheap_consolidate (heap);
 342     }
 343
 344   return ret;
 345 }
 346
 347 /* Insert NODE into the root list of HEAP.  */
 348 static void
 349 fibheap_ins_root (heap, node)
 350      fibheap_t heap;
 351      fibnode_t node;
 352 {
 353   /* If the heap is currently empty, the new node becomes the singleton
 354      circular root list.  */
 355   if (heap->root == NULL)
 356     {
 357       heap->root = node;
 358       node->left = node;
 359       node->right = node;
 360       return;
 361     }
 362
 363   /* Otherwise, insert it in the circular root list between the root
 364      and it's right node.  */
 365   fibnode_insert_after (heap->root, node);
 366 }
 367
 368 /* Remove NODE from the rootlist of HEAP.  */
 369 static void
 370 fibheap_rem_root (heap, node)
 371      fibheap_t heap;
 372      fibnode_t node;
 373 {
 374   if (node->left == node)
 375     heap->root = NULL;
 376   else
 377     heap->root = fibnode_remove (node);
 378 }
 379
 380 /* Consolidate the heap.  */
 381 static void
 382 fibheap_consolidate (heap)
 383      fibheap_t heap;
 384 {
 385   fibnode_t a[1 + 8 * sizeof (long)];
 386   fibnode_t w;
 387   fibnode_t y;
 388   fibnode_t x;
 389   int i;
 390   int d;
 391   int D;
 392
 393   D = 1 + 8 * sizeof (long);
 394
 395   memset (a, 0, sizeof (fibnode_t) * D);
 396
 397   while ((w = heap->root) != NULL)
 398     {
 399       x = w;
 400       fibheap_rem_root (heap, w);
 401       d = x->degree;
 402       while (a[d] != NULL)
 403         {
 404           y = a[d];
 405           if (fibheap_compare (heap, x, y) > 0)
 406             {
 407               fibnode_t temp;
 408               temp = x;
 409               x = y;
 410               y = temp;
 411             }
 412           fibheap_link (heap, y, x);
 413           a[d] = NULL;
 414           d++;
 415         }
 416       a[d] = x;
 417     }
 418   heap->min = NULL;
 419   for (i = 0; i < D; i++)
 420     if (a[i] != NULL)
 421       {
 422         fibheap_ins_root (heap, a[i]);
 423         if (heap->min == NULL || fibheap_compare (heap, a[i], heap->min) < 0)
 424           heap->min = a[i];
 425       }
 426 }
 427
 428 /* Make NODE a child of PARENT.  */
 429 static void
 430 fibheap_link (heap, node, parent)
 431      fibheap_t heap ATTRIBUTE_UNUSED;
 432      fibnode_t node;
 433      fibnode_t parent;
 434 {
 435   if (parent->child == NULL)
 436     parent->child = node;
 437   else
 438     fibnode_insert_before (parent->child, node);
 439   node->parent = parent;
 440   parent->degree++;
 441   node->mark = 0;
 442 }
 443
 444 /* Remove NODE from PARENT's child list.  */
 445 static void
 446 fibheap_cut (heap, node, parent)
 447      fibheap_t heap;
 448      fibnode_t node;
 449      fibnode_t parent;
 450 {
 451   fibnode_remove (node);
 452   parent->degree--;
 453   fibheap_ins_root (heap, node);
 454   node->parent = NULL;
 455   node->mark = 0;
 456 }
 457
 458 static void
 459 fibheap_cascading_cut (heap, y)
 460      fibheap_t heap;
 461      fibnode_t y;
 462 {
 463   fibnode_t z;
 464
 465   while ((z = y->parent) != NULL)
 466     {
 467       if (y->mark == 0)
 468         {
 469           y->mark = 1;
 470           return;
 471         }
 472       else
 473         {
 474           fibheap_cut (heap, y, z);
 475           y = z;
 476         }
 477     }
 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 static fibnode_t
 502 fibnode_remove (node)
 503      fibnode_t node;
 504 {
 505   fibnode_t ret;
 506
 507   if (node == node->left)
 508     ret = NULL;
 509   else
 510     ret = node->left;
 511
 512   if (node->parent != NULL && node->parent->child == node)
 513     node->parent->child = ret;
 514
 515   node->right->left = node->left;
 516   node->left->right = node->right;
 517
 518   node->parent = NULL;
 519   node->left = node;
 520   node->right = node;
 521
 522   return ret;
 523 }