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   if (okey == key)
 218     return odata;
 219
 220   /* These two compares are specifically <= 0 to make sure that in the case
 221      of equality, a node we replaced the data on, becomes the new min.  This
 222      is needed so that delete's call to extractmin gets the right node.  */
 223   if (y != NULL && fibheap_compare (heap, node, y) <= 0)
 224     {
 225       fibheap_cut (heap, node, y);
 226       fibheap_cascading_cut (heap, y);
 227     }
 228
 229   if (fibheap_compare (heap, node, heap->min) <= 0)
 230     heap->min = node;
 231
 232   return odata;
 233 }
 234
 235 /* Replace the DATA associated with NODE.  */
 236 void *
 237 fibheap_replace_data (fibheap_t heap, fibnode_t node, void *data)
 238 {
 239   return fibheap_replace_key_data (heap, node, node->key, data);
 240 }
 241
 242 /* Replace the KEY associated with NODE.  */
 243 fibheapkey_t
 244 fibheap_replace_key (fibheap_t heap, fibnode_t node, fibheapkey_t key)
 245 {
 246   int okey = node->key;
 247   fibheap_replace_key_data (heap, node, key, node->data);
 248   return okey;
 249 }
 250
 251 /* Delete NODE from HEAP.  */
 252 void *
 253 fibheap_delete_node (fibheap_t heap, fibnode_t node)
 254 {
 255   void *ret = node->data;
 256
 257   /* To perform delete, we just make it the min key, and extract.  */
 258   fibheap_replace_key (heap, node, FIBHEAPKEY_MIN);
 259   fibheap_extract_min (heap);
 260
 261   return ret;
 262 }
 263
 264 /* Delete HEAP.  */
 265 void
 266 fibheap_delete (fibheap_t heap)
 267 {
 268   while (heap->min != NULL)
 269     free (fibheap_extr_min_node (heap));
 270
 271   free (heap);
 272 }
 273
 274 /* Determine if HEAP is empty.  */
 275 int
 276 fibheap_empty (fibheap_t heap)
 277 {
 278   return heap->nodes == 0;
 279 }
 280
 281 /* Extract the minimum node of the heap.  */
 282 static fibnode_t
 283 fibheap_extr_min_node (fibheap_t heap)
 284 {
 285   fibnode_t ret = heap->min;
 286   fibnode_t x, y, orig;
 287
 288   /* Attach the child list of the minimum node to the root list of the heap.
 289      If there is no child list, we don't do squat.  */
 290   for (x = ret->child, orig = NULL; x != orig && x != NULL; x = y)
 291     {
 292       if (orig == NULL)
 293         orig = x;
 294       y = x->right;
 295       x->parent = NULL;
 296       fibheap_ins_root (heap, x);
 297     }
 298
 299   /* Remove the old root.  */
 300   fibheap_rem_root (heap, ret);
 301   heap->nodes--;
 302
 303   /* If we are left with no nodes, then the min is NULL.  */
 304   if (heap->nodes == 0)
 305     heap->min = NULL;
 306   else
 307     {
 308       /* Otherwise, consolidate to find new minimum, as well as do the reorg
 309          work that needs to be done.  */
 310       heap->min = ret->right;
 311       fibheap_consolidate (heap);
 312     }
 313
 314   return ret;
 315 }
 316
 317 /* Insert NODE into the root list of HEAP.  */
 318 static void
 319 fibheap_ins_root (fibheap_t heap, fibnode_t node)
 320 {
 321   /* If the heap is currently empty, the new node becomes the singleton
 322      circular root list.  */
 323   if (heap->root == NULL)
 324     {
 325       heap->root = node;
 326       node->left = node;
 327       node->right = node;
 328       return;
 329     }
 330
 331   /* Otherwise, insert it in the circular root list between the root
 332      and it's right node.  */
 333   fibnode_insert_after (heap->root, node);
 334 }
 335
 336 /* Remove NODE from the rootlist of HEAP.  */
 337 static void
 338 fibheap_rem_root (fibheap_t heap, fibnode_t node)
 339 {
 340   if (node->left == node)
 341     heap->root = NULL;
 342   else
 343     heap->root = fibnode_remove (node);
 344 }
 345
 346 /* Consolidate the heap.  */
 347 static void
 348 fibheap_consolidate (fibheap_t heap)
 349 {
 350   fibnode_t a[1 + 8 * sizeof (long)];
 351   fibnode_t w;
 352   fibnode_t y;
 353   fibnode_t x;
 354   int i;
 355   int d;
 356   int D;
 357
 358   D = 1 + 8 * sizeof (long);
 359
 360   memset (a, 0, sizeof (fibnode_t) * D);
 361
 362   while ((w = heap->root) != NULL)
 363     {
 364       x = w;
 365       fibheap_rem_root (heap, w);
 366       d = x->degree;
 367       while (a[d] != NULL)
 368         {
 369           y = a[d];
 370           if (fibheap_compare (heap, x, y) > 0)
 371             {
 372               fibnode_t temp;
 373               temp = x;
 374               x = y;
 375               y = temp;
 376             }
 377           fibheap_link (heap, y, x);
 378           a[d] = NULL;
 379           d++;
 380         }
 381       a[d] = x;
 382     }
 383   heap->min = NULL;
 384   for (i = 0; i < D; i++)
 385     if (a[i] != NULL)
 386       {
 387         fibheap_ins_root (heap, a[i]);
 388         if (heap->min == NULL || fibheap_compare (heap, a[i], heap->min) < 0)
 389           heap->min = a[i];
 390       }
 391 }
 392
 393 /* Make NODE a child of PARENT.  */
 394 static void
 395 fibheap_link (fibheap_t heap ATTRIBUTE_UNUSED,
 396               fibnode_t node, fibnode_t parent)
 397 {
 398   if (parent->child == NULL)
 399     parent->child = node;
 400   else
 401     fibnode_insert_before (parent->child, node);
 402   node->parent = parent;
 403   parent->degree++;
 404   node->mark = 0;
 405 }
 406
 407 /* Remove NODE from PARENT's child list.  */
 408 static void
 409 fibheap_cut (fibheap_t heap, fibnode_t node, fibnode_t parent)
 410 {
 411   fibnode_remove (node);
 412   parent->degree--;
 413   fibheap_ins_root (heap, node);
 414   node->parent = NULL;
 415   node->mark = 0;
 416 }
 417
 418 static void
 419 fibheap_cascading_cut (fibheap_t heap, fibnode_t y)
 420 {
 421   fibnode_t z;
 422
 423   while ((z = y->parent) != NULL)
 424     {
 425       if (y->mark == 0)
 426         {
 427           y->mark = 1;
 428           return;
 429         }
 430       else
 431         {
 432           fibheap_cut (heap, y, z);
 433           y = z;
 434         }
 435     }
 436 }
 437
 438 static void
 439 fibnode_insert_after (fibnode_t a, fibnode_t b)
 440 {
 441   if (a == a->right)
 442     {
 443       a->right = b;
 444       a->left = b;
 445       b->right = a;
 446       b->left = a;
 447     }
 448   else
 449     {
 450       b->right = a->right;
 451       a->right->left = b;
 452       a->right = b;
 453       b->left = a;
 454     }
 455 }
 456
 457 static fibnode_t
 458 fibnode_remove (fibnode_t node)
 459 {
 460   fibnode_t ret;
 461
 462   if (node == node->left)
 463     ret = NULL;
 464   else
 465     ret = node->left;
 466
 467   if (node->parent != NULL && node->parent->child == node)
 468     node->parent->child = ret;
 469
 470   node->right->left = node->left;
 471   node->left->right = node->right;
 472
 473   node->parent = NULL;
 474   node->left = node;
 475   node->right = node;
 476
 477   return ret;
 478 }