Back to index

cell-binutils  2.17cvs20070401
fibheap.c
Go to the documentation of this file.
00001 /* A Fibonacci heap datatype.
00002    Copyright 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
00003    Contributed by Daniel Berlin (dan@cgsoftware.com).
00004    
00005 This file is part of GNU CC.
00006    
00007 GNU CC is free software; you can redistribute it and/or modify it
00008 under the terms of the GNU General Public License as published by
00009 the Free Software Foundation; either version 2, or (at your option)
00010 any later version.
00011 
00012 GNU CC is distributed in the hope that it will be useful, but
00013 WITHOUT ANY WARRANTY; without even the implied warranty of
00014 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00015 General Public License for more details.
00016 
00017 You should have received a copy of the GNU General Public License
00018 along with GNU CC; see the file COPYING.  If not, write to
00019 the Free Software Foundation, 51 Franklin Street - Fifth Floor,
00020 Boston, MA 02110-1301, USA.  */
00021 
00022 #ifdef HAVE_CONFIG_H
00023 #include "config.h"
00024 #endif
00025 #ifdef HAVE_LIMITS_H
00026 #include <limits.h>
00027 #endif
00028 #ifdef HAVE_STDLIB_H
00029 #include <stdlib.h>
00030 #endif
00031 #ifdef HAVE_STRING_H
00032 #include <string.h>
00033 #endif
00034 #include "libiberty.h"
00035 #include "fibheap.h"
00036 
00037 
00038 #define FIBHEAPKEY_MIN      LONG_MIN
00039 
00040 static void fibheap_ins_root (fibheap_t, fibnode_t);
00041 static void fibheap_rem_root (fibheap_t, fibnode_t);
00042 static void fibheap_consolidate (fibheap_t);
00043 static void fibheap_link (fibheap_t, fibnode_t, fibnode_t);
00044 static void fibheap_cut (fibheap_t, fibnode_t, fibnode_t);
00045 static void fibheap_cascading_cut (fibheap_t, fibnode_t);
00046 static fibnode_t fibheap_extr_min_node (fibheap_t);
00047 static int fibheap_compare (fibheap_t, fibnode_t, fibnode_t);
00048 static int fibheap_comp_data (fibheap_t, fibheapkey_t, void *, fibnode_t);
00049 static fibnode_t fibnode_new (void);
00050 static void fibnode_insert_after (fibnode_t, fibnode_t);
00051 #define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b)
00052 static fibnode_t fibnode_remove (fibnode_t);
00053 
00054 
00055 /* Create a new fibonacci heap.  */
00056 fibheap_t
00057 fibheap_new (void)
00058 {
00059   return (fibheap_t) xcalloc (1, sizeof (struct fibheap));
00060 }
00061 
00062 /* Create a new fibonacci heap node.  */
00063 static fibnode_t
00064 fibnode_new (void)
00065 {
00066   fibnode_t node;
00067 
00068   node = (fibnode_t) xcalloc (1, sizeof *node);
00069   node->left = node;
00070   node->right = node;
00071 
00072   return node;
00073 }
00074 
00075 static inline int
00076 fibheap_compare (fibheap_t heap ATTRIBUTE_UNUSED, fibnode_t a, fibnode_t b)
00077 {
00078   if (a->key < b->key)
00079     return -1;
00080   if (a->key > b->key)
00081     return 1;
00082   return 0;
00083 }
00084 
00085 static inline int
00086 fibheap_comp_data (fibheap_t heap, fibheapkey_t key, void *data, fibnode_t b)
00087 {
00088   struct fibnode a;
00089 
00090   a.key = key;
00091   a.data = data;
00092 
00093   return fibheap_compare (heap, &a, b);
00094 }
00095 
00096 /* Insert DATA, with priority KEY, into HEAP.  */
00097 fibnode_t
00098 fibheap_insert (fibheap_t heap, fibheapkey_t key, void *data)
00099 {
00100   fibnode_t node;
00101 
00102   /* Create the new node.  */
00103   node = fibnode_new ();
00104 
00105   /* Set the node's data.  */
00106   node->data = data;
00107   node->key = key;
00108 
00109   /* Insert it into the root list.  */
00110   fibheap_ins_root (heap, node);
00111 
00112   /* If their was no minimum, or this key is less than the min,
00113      it's the new min.  */
00114   if (heap->min == NULL || node->key < heap->min->key)
00115     heap->min = node;
00116 
00117   heap->nodes++;
00118 
00119   return node;
00120 }
00121 
00122 /* Return the data of the minimum node (if we know it).  */
00123 void *
00124 fibheap_min (fibheap_t heap)
00125 {
00126   /* If there is no min, we can't easily return it.  */
00127   if (heap->min == NULL)
00128     return NULL;
00129   return heap->min->data;
00130 }
00131 
00132 /* Return the key of the minimum node (if we know it).  */
00133 fibheapkey_t
00134 fibheap_min_key (fibheap_t heap)
00135 {
00136   /* If there is no min, we can't easily return it.  */
00137   if (heap->min == NULL)
00138     return 0;
00139   return heap->min->key;
00140 }
00141 
00142 /* Union HEAPA and HEAPB into a new heap.  */
00143 fibheap_t
00144 fibheap_union (fibheap_t heapa, fibheap_t heapb)
00145 {
00146   fibnode_t a_root, b_root, temp;
00147 
00148   /* If one of the heaps is empty, the union is just the other heap.  */
00149   if ((a_root = heapa->root) == NULL)
00150     {
00151       free (heapa);
00152       return heapb;
00153     }
00154   if ((b_root = heapb->root) == NULL)
00155     {
00156       free (heapb);
00157       return heapa;
00158     }
00159 
00160   /* Merge them to the next nodes on the opposite chain.  */
00161   a_root->left->right = b_root;
00162   b_root->left->right = a_root;
00163   temp = a_root->left;
00164   a_root->left = b_root->left;
00165   b_root->left = temp;
00166   heapa->nodes += heapb->nodes;
00167 
00168   /* And set the new minimum, if it's changed.  */
00169   if (fibheap_compare (heapa, heapb->min, heapa->min) < 0)
00170     heapa->min = heapb->min;
00171 
00172   free (heapb);
00173   return heapa;
00174 }
00175 
00176 /* Extract the data of the minimum node from HEAP.  */
00177 void *
00178 fibheap_extract_min (fibheap_t heap)
00179 {
00180   fibnode_t z;
00181   void *ret = NULL;
00182 
00183   /* If we don't have a min set, it means we have no nodes.  */
00184   if (heap->min != NULL)
00185     {
00186       /* Otherwise, extract the min node, free the node, and return the
00187          node's data.  */
00188       z = fibheap_extr_min_node (heap);
00189       ret = z->data;
00190       free (z);
00191     }
00192 
00193   return ret;
00194 }
00195 
00196 /* Replace both the KEY and the DATA associated with NODE.  */
00197 void *
00198 fibheap_replace_key_data (fibheap_t heap, fibnode_t node,
00199                           fibheapkey_t key, void *data)
00200 {
00201   void *odata;
00202   fibheapkey_t okey;
00203   fibnode_t y;
00204 
00205   /* If we wanted to, we could actually do a real increase by redeleting and
00206      inserting. However, this would require O (log n) time. So just bail out
00207      for now.  */
00208   if (fibheap_comp_data (heap, key, data, node) > 0)
00209     return NULL;
00210 
00211   odata = node->data;
00212   okey = node->key;
00213   node->data = data;
00214   node->key = key;
00215   y = node->parent;
00216 
00217   if (okey == key)
00218     return odata;
00219 
00220   /* These two compares are specifically <= 0 to make sure that in the case
00221      of equality, a node we replaced the data on, becomes the new min.  This
00222      is needed so that delete's call to extractmin gets the right node.  */
00223   if (y != NULL && fibheap_compare (heap, node, y) <= 0)
00224     {
00225       fibheap_cut (heap, node, y);
00226       fibheap_cascading_cut (heap, y);
00227     }
00228 
00229   if (fibheap_compare (heap, node, heap->min) <= 0)
00230     heap->min = node;
00231 
00232   return odata;
00233 }
00234 
00235 /* Replace the DATA associated with NODE.  */
00236 void *
00237 fibheap_replace_data (fibheap_t heap, fibnode_t node, void *data)
00238 {
00239   return fibheap_replace_key_data (heap, node, node->key, data);
00240 }
00241 
00242 /* Replace the KEY associated with NODE.  */
00243 fibheapkey_t
00244 fibheap_replace_key (fibheap_t heap, fibnode_t node, fibheapkey_t key)
00245 {
00246   int okey = node->key;
00247   fibheap_replace_key_data (heap, node, key, node->data);
00248   return okey;
00249 }
00250 
00251 /* Delete NODE from HEAP.  */
00252 void *
00253 fibheap_delete_node (fibheap_t heap, fibnode_t node)
00254 {
00255   void *ret = node->data;
00256 
00257   /* To perform delete, we just make it the min key, and extract.  */
00258   fibheap_replace_key (heap, node, FIBHEAPKEY_MIN);
00259   fibheap_extract_min (heap);
00260 
00261   return ret;
00262 }
00263 
00264 /* Delete HEAP.  */
00265 void
00266 fibheap_delete (fibheap_t heap)
00267 {
00268   while (heap->min != NULL)
00269     free (fibheap_extr_min_node (heap));
00270 
00271   free (heap);
00272 }
00273 
00274 /* Determine if HEAP is empty.  */
00275 int
00276 fibheap_empty (fibheap_t heap)
00277 {
00278   return heap->nodes == 0;
00279 }
00280 
00281 /* Extract the minimum node of the heap.  */
00282 static fibnode_t
00283 fibheap_extr_min_node (fibheap_t heap)
00284 {
00285   fibnode_t ret = heap->min;
00286   fibnode_t x, y, orig;
00287 
00288   /* Attach the child list of the minimum node to the root list of the heap.
00289      If there is no child list, we don't do squat.  */
00290   for (x = ret->child, orig = NULL; x != orig && x != NULL; x = y)
00291     {
00292       if (orig == NULL)
00293        orig = x;
00294       y = x->right;
00295       x->parent = NULL;
00296       fibheap_ins_root (heap, x);
00297     }
00298 
00299   /* Remove the old root.  */
00300   fibheap_rem_root (heap, ret);
00301   heap->nodes--;
00302 
00303   /* If we are left with no nodes, then the min is NULL.  */
00304   if (heap->nodes == 0)
00305     heap->min = NULL;
00306   else
00307     {
00308       /* Otherwise, consolidate to find new minimum, as well as do the reorg
00309          work that needs to be done.  */
00310       heap->min = ret->right;
00311       fibheap_consolidate (heap);
00312     }
00313 
00314   return ret;
00315 }
00316 
00317 /* Insert NODE into the root list of HEAP.  */
00318 static void
00319 fibheap_ins_root (fibheap_t heap, fibnode_t node)
00320 {
00321   /* If the heap is currently empty, the new node becomes the singleton
00322      circular root list.  */
00323   if (heap->root == NULL)
00324     {
00325       heap->root = node;
00326       node->left = node;
00327       node->right = node;
00328       return;
00329     }
00330 
00331   /* Otherwise, insert it in the circular root list between the root
00332      and it's right node.  */
00333   fibnode_insert_after (heap->root, node);
00334 }
00335 
00336 /* Remove NODE from the rootlist of HEAP.  */
00337 static void
00338 fibheap_rem_root (fibheap_t heap, fibnode_t node)
00339 {
00340   if (node->left == node)
00341     heap->root = NULL;
00342   else
00343     heap->root = fibnode_remove (node);
00344 }
00345 
00346 /* Consolidate the heap.  */
00347 static void
00348 fibheap_consolidate (fibheap_t heap)
00349 {
00350   fibnode_t a[1 + 8 * sizeof (long)];
00351   fibnode_t w;
00352   fibnode_t y;
00353   fibnode_t x;
00354   int i;
00355   int d;
00356   int D;
00357 
00358   D = 1 + 8 * sizeof (long);
00359 
00360   memset (a, 0, sizeof (fibnode_t) * D);
00361 
00362   while ((w = heap->root) != NULL)
00363     {
00364       x = w;
00365       fibheap_rem_root (heap, w);
00366       d = x->degree;
00367       while (a[d] != NULL)
00368        {
00369          y = a[d];
00370          if (fibheap_compare (heap, x, y) > 0)
00371            {
00372              fibnode_t temp;
00373              temp = x;
00374              x = y;
00375              y = temp;
00376            }
00377          fibheap_link (heap, y, x);
00378          a[d] = NULL;
00379          d++;
00380        }
00381       a[d] = x;
00382     }
00383   heap->min = NULL;
00384   for (i = 0; i < D; i++)
00385     if (a[i] != NULL)
00386       {
00387        fibheap_ins_root (heap, a[i]);
00388        if (heap->min == NULL || fibheap_compare (heap, a[i], heap->min) < 0)
00389          heap->min = a[i];
00390       }
00391 }
00392 
00393 /* Make NODE a child of PARENT.  */
00394 static void
00395 fibheap_link (fibheap_t heap ATTRIBUTE_UNUSED,
00396               fibnode_t node, fibnode_t parent)
00397 {
00398   if (parent->child == NULL)
00399     parent->child = node;
00400   else
00401     fibnode_insert_before (parent->child, node);
00402   node->parent = parent;
00403   parent->degree++;
00404   node->mark = 0;
00405 }
00406 
00407 /* Remove NODE from PARENT's child list.  */
00408 static void
00409 fibheap_cut (fibheap_t heap, fibnode_t node, fibnode_t parent)
00410 {
00411   fibnode_remove (node);
00412   parent->degree--;
00413   fibheap_ins_root (heap, node);
00414   node->parent = NULL;
00415   node->mark = 0;
00416 }
00417 
00418 static void
00419 fibheap_cascading_cut (fibheap_t heap, fibnode_t y)
00420 {
00421   fibnode_t z;
00422 
00423   while ((z = y->parent) != NULL)
00424     {
00425       if (y->mark == 0)
00426        {
00427          y->mark = 1;
00428          return;
00429        }
00430       else
00431        {
00432          fibheap_cut (heap, y, z);
00433          y = z;
00434        }
00435     }
00436 }
00437 
00438 static void
00439 fibnode_insert_after (fibnode_t a, fibnode_t b)
00440 {
00441   if (a == a->right)
00442     {
00443       a->right = b;
00444       a->left = b;
00445       b->right = a;
00446       b->left = a;
00447     }
00448   else
00449     {
00450       b->right = a->right;
00451       a->right->left = b;
00452       a->right = b;
00453       b->left = a;
00454     }
00455 }
00456 
00457 static fibnode_t
00458 fibnode_remove (fibnode_t node)
00459 {
00460   fibnode_t ret;
00461 
00462   if (node == node->left)
00463     ret = NULL;
00464   else
00465     ret = node->left;
00466 
00467   if (node->parent != NULL && node->parent->child == node)
00468     node->parent->child = ret;
00469 
00470   node->right->left = node->left;
00471   node->left->right = node->right;
00472 
00473   node->parent = NULL;
00474   node->left = node;
00475   node->right = node;
00476 
00477   return ret;
00478 }