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