This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

[PATCH]: Fibheap (commented more)


No functional changes, just commented more.
See http://gcc.gnu.org/ml/gcc-patches/2001-08/msg00238.html for the
changelog.

Index: libiberty/fibheap.c
===================================================================
RCS file: fibheap.c
diff -N fibheap.c
*** /dev/null	Tue May  5 13:32:27 1998
--- fibheap.c	Fri Aug 17 09:32:08 2001
***************
*** 0 ****
--- 1,547 ----
+ 
+ /* A Fibonacci heap datatype.
+    Copyright 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
+    Contributed by Daniel Berlin (dan@cgsoftware.com).
+    
+ This file is part of GNU CC.
+    
+ GNU CC is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2, or (at your option)
+ any later version.
+ 
+ GNU CC is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ General Public License for more details.
+ 
+ You should have received a copy of the GNU General Public License
+ along with GNU CC; see the file COPYING.  If not, write to
+ the Free Software Foundation, 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, USA.  */
+ 
+ /* Fibonacci heaps */
+ #include <limits.h>
+ #include <stdlib.h>
+ #include "libiberty.h"
+ #include "fibheap.h"
+ 
+ 
+ static void fibheap_init PARAMS ((fibheap_t));
+ static void fibheap_ins_root PARAMS ((fibheap_t, fibnode_t));
+ static void fibheap_rem_root PARAMS ((fibheap_t, fibnode_t));
+ static void fibheap_consolidate PARAMS ((fibheap_t));
+ static void fibheap_link PARAMS ((fibheap_t, fibnode_t, fibnode_t));
+ static void fibheap_cut PARAMS ((fibheap_t, fibnode_t, fibnode_t));
+ static void fibheap_cascading_cut PARAMS ((fibheap_t, fibnode_t));
+ static fibnode_t fibheap_extr_min_node PARAMS ((fibheap_t));
+ static int fibheap_compare PARAMS ((fibheap_t, fibnode_t, fibnode_t));
+ static int fibheap_comp_data PARAMS ((fibheap_t, int, void *, fibnode_t));
+ static fibnode_t fibnode_new PARAMS ((void));
+ static void fibnode_init PARAMS ((fibnode_t));
+ static void fibnode_insert_after PARAMS ((fibnode_t, fibnode_t));
+ #define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b)
+ static fibnode_t fibnode_remove PARAMS ((fibnode_t));
+ 
+ /* Create a new fibonacci heap. */
+ fibheap_t
+ fibheap_new ()
+ {
+   fibheap_t result;
+ 
+   if ((result = xmalloc (sizeof (*result))) == NULL)
+     return NULL;
+ 
+   fibheap_init (result);
+ 
+   return result;
+ }
+ 
+ /* Initialize the passed in fibonacci heap. */
+ static void
+ fibheap_init (heap)
+      fibheap_t heap;
+ {
+   heap->nodes = 0;
+   heap->min = NULL;
+   heap->root = NULL;
+ }
+ 
+ /* Insert DATA, with priority KEY, into HEAP. */
+ fibnode_t
+ fibheap_insert (heap, key, data)
+      fibheap_t heap;
+      int key;
+      void *data;
+ {
+   fibnode_t node;
+   /* Create the new node, if we fail, return NULL. */
+   if ((node = fibnode_new ()) == NULL)
+     return NULL;
+   /* Set the node's data. */
+   node->data = data;
+   node->key = key;
+ 
+   /* Insert it into the root list. */
+   fibheap_ins_root (heap, node);
+ 
+   /* If their was no minimum, or this key is less than the min, it's
+      the new min. */
+   if (heap->min == NULL || node->key < heap->min->key)
+     heap->min = node;
+ 
+   heap->nodes++;
+ 
+   return node;
+ }
+ 
+ /* Return the data of the minimum node (if we know it).*/
+ void *
+ fibheap_min (heap)
+      fibheap_t heap;
+ {
+   /* If there is no min, we can't easily return it. */
+   if (heap->min == NULL)
+     return NULL;
+   return heap->min->data;
+ }
+ 
+ /* Return the key of the minimum node (if we know it).*/
+ int
+ fibheap_min_key (heap)
+      fibheap_t heap;
+ {
+   /* If there is no min, we can't easily return it. */
+   if (heap->min == NULL)
+     return 0;
+   return heap->min->key;
+ }
+ 
+ /* Union HEAPA and HEAPB into a new heap.*/
+ fibheap_t
+ fibheap_union (heapa, heapb)
+      fibheap_t heapa;
+      fibheap_t heapb;
+ {
+   fibnode_t temp;
+ 
+   /* If one of the heaps is empty, the union is just the other heap. */
+   if (heapa->root == NULL || heapb->root == NULL)
+     {
+       if (heapa->root == NULL)
+ 	{
+ 	  free (heapa);
+ 	  return heapb;
+ 	}
+       else
+ 	{
+ 	  free (heapb);
+ 	  return heapa;
+ 	}
+     }
+   /* Merge them to the next nodes on the opposite chain. */
+   heapa->root->left->right = heapb->root;
+   heapb->root->left->right = heapa->root;
+   temp = heapa->root->left;
+   heapa->root->left = heapb->root->left;
+   heapb->root->left = temp;
+   heapa->nodes += heapb->nodes;
+ 
+   /* And set the new minimum, if it's changed. */
+   if (fibheap_compare (heapa, heapb->min, heapa->min) < 0)
+     heapa->min = heapb->min;
+ 
+   free (heapb);
+   return heapa;
+ }
+ 
+ /* Extract the data of the minimum node from HEAP.*/
+ void *
+ fibheap_extract_min (heap)
+      fibheap_t heap;
+ {
+   fibnode_t z;
+   void *ret;
+ 
+   ret = NULL;
+   /* If we don't have a min set, it means we have no nodes. */
+   if (heap->min != NULL)
+     {
+       /* Otherwise, extract the min node, free the node, and return
+          the node's data. */
+       z = fibheap_extr_min_node (heap);
+       ret = z->data;
+       free (z);
+     }
+ 
+   return ret;
+ }
+ 
+ /* Replace the DATA associated with NODE. */
+ void *
+ fibheap_replace_data (heap, node, data)
+      fibheap_t heap;
+      fibnode_t node;
+      void *data;
+ {
+   return fibheap_replace_key_data (heap, node, node->key, data);
+ }
+ 
+ /* Replace the KEY associated with NODE.*/
+ int
+ fibheap_replace_key (heap, node, key)
+      fibheap_t heap;
+      fibnode_t node;
+      int key;
+ {
+   int ret;
+ 
+   ret = node->key;
+   (void) fibheap_replace_key_data (heap, node, key, node->data);
+ 
+   return ret;
+ }
+ 
+ /* Replace both the KEY and the DATA associated with NODE.*/
+ void *
+ fibheap_replace_key_data (heap, node, key, data)
+      fibheap_t heap;
+      fibnode_t node;
+      int key;
+      void *data;
+ {
+   void *odata;
+   int okey;
+   fibnode_t y;
+ 
+   /* If we wanted to, we could actually do a real increase by
+      redeleting and inserting.  
+      However, this would require O (log n) time. So just bail out for
+      now.  */
+   if (fibheap_comp_data (heap, key, data, node) > 0)
+     return NULL;
+ 
+   odata = node->data;
+   okey = node->key;
+   node->data = data;
+   node->key = key;
+   y = node->parent;
+ 
+   if (okey == key)
+     return odata;
+ 
+   if (y != NULL && fibheap_compare (heap, node, y) <= 0)
+     {
+       fibheap_cut (heap, node, y);
+       fibheap_cascading_cut (heap, y);
+     }
+ 
+   if (fibheap_compare (heap, node, heap->min) <= 0)
+     heap->min = node;
+ 
+   return odata;
+ }
+ 
+ /* Delete NODE from HEAP. */
+ void *
+ fibheap_delete_node (heap, node)
+      fibheap_t heap;
+      fibnode_t node;
+ {
+   void *k;
+   /* To perform delete, we just make it the min key, and extract. */
+   k = node->data;
+   fibheap_replace_key (heap, node, INT_MIN);
+   fibheap_extract_min (heap);
+ 
+   return k;
+ }
+ 
+ /* Delete HEAP.*/
+ void
+ fibheap_delete (heap)
+      fibheap_t heap;
+ {
+   while (heap->min != NULL)
+     free (fibheap_extr_min_node (heap));
+ 
+   free (heap);
+ }
+ 
+ /* Determine if HEAP is empty.*/
+ int
+ fibheap_empty (heap)
+      fibheap_t heap;
+ {
+   return heap->nodes == 0;
+ }
+ 
+ 
+ /* Extract the minimum node of the heap.*/
+ static fibnode_t
+ fibheap_extr_min_node (heap)
+      fibheap_t heap;
+ {
+   fibnode_t ret;
+   fibnode_t x, y, orig;
+ 
+   ret = heap->min;
+ 
+   orig = NULL;
+   /* Attach the child list of the minimum node to the root list of the
+      heap. If there is no child list, we don't do squat. */
+   for (x = ret->child; x != orig && x != NULL;)
+     {
+       if (orig == NULL)
+ 	orig = x;
+       y = x->right;
+       x->parent = NULL;
+       fibheap_ins_root (heap, x);
+       x = y;
+     }
+   /* Remove the old root. */
+   fibheap_rem_root (heap, ret);
+   heap->nodes--;
+   /* If we are left with no nodes, then the min is NULL. */
+   if (heap->nodes == 0)
+     heap->min = NULL;
+   else
+     {
+       /*Otherwise, consolidate to find new minimum, as well as do the
+          reorg work that needs to be done. */
+       heap->min = ret->right;
+       fibheap_consolidate (heap);
+     }
+ 
+   return ret;
+ }
+ 
+ /* Insert NODE into the root list of HEAP. */
+ static void
+ fibheap_ins_root (heap, node)
+      fibheap_t heap;
+      fibnode_t node;
+ {
+   /* If the heap is currently empty, the new node becomes the
+      singleton circular root list. */
+   if (heap->root == NULL)
+     {
+       heap->root = node;
+       node->left = node;
+       node->right = node;
+       return;
+     }
+   /* Otherwise, insert it in the circular root list between the root
+      and it's right node. */
+   fibnode_insert_after (heap->root, node);
+ }
+ 
+ /* Remove NODE from the rootlist of HEAP.*/
+ static void
+ fibheap_rem_root (heap, node)
+      fibheap_t heap;
+      fibnode_t node;
+ {
+   if (node->left == node)
+     heap->root = NULL;
+   else
+     heap->root = fibnode_remove (node);
+ }
+ 
+ /* Consolidate the heap.*/
+ static void
+ fibheap_consolidate (heap)
+      fibheap_t heap;
+ {
+   fibnode_t a[1 + 8 * sizeof (long)];
+   fibnode_t w;
+   fibnode_t y;
+   fibnode_t x;
+   int i;
+   int d;
+   int D;
+ 
+   D = 1 + 8 * sizeof (long);
+ 
+   for (i = 0; i < D; i++)
+     a[i] = NULL;
+ 
+   while ((w = heap->root) != NULL)
+     {
+       x = w;
+       fibheap_rem_root (heap, w);
+       d = x->degree;
+       while (a[d] != NULL)
+ 	{
+ 	  y = a[d];
+ 	  if (fibheap_compare (heap, x, y) > 0)
+ 	    {
+ 	      fibnode_t temp;
+ 	      temp = x;
+ 	      x = y;
+ 	      y = temp;
+ 	    }
+ 	  fibheap_link (heap, y, x);
+ 	  a[d] = NULL;
+ 	  d++;
+ 	}
+       a[d] = x;
+     }
+   heap->min = NULL;
+   for (i = 0; i < D; i++)
+     if (a[i] != NULL)
+       {
+ 	fibheap_ins_root (heap, a[i]);
+ 	if (heap->min == NULL || fibheap_compare (heap, a[i], heap->min) < 0)
+ 	  heap->min = a[i];
+       }
+ }
+ 
+ /* Make NODE a child of PARENT. */
+ static void
+ fibheap_link (heap, node, parent)
+      fibheap_t heap ATTRIBUTE_UNUSED;
+      fibnode_t node;
+      fibnode_t parent;
+ {
+   if (parent->child == NULL)
+     parent->child = node;
+   else
+     fibnode_insert_before (parent->child, node);
+   node->parent = parent;
+   parent->degree++;
+   node->mark = 0;
+ }
+ 
+ /* Remove NODE from PARENT's child list. */
+ static void
+ fibheap_cut (heap, node, parent)
+      fibheap_t heap;
+      fibnode_t node;
+      fibnode_t parent;
+ {
+   fibnode_remove (node);
+   parent->degree--;
+   fibheap_ins_root (heap, node);
+   node->parent = NULL;
+   node->mark = 0;
+ }
+ 
+ static void
+ fibheap_cascading_cut (heap, y)
+      fibheap_t heap;
+      fibnode_t y;
+ {
+   fibnode_t z;
+ 
+   while ((z = y->parent) != NULL)
+     {
+       if (y->mark == 0)
+ 	{
+ 	  y->mark = 1;
+ 	  return;
+ 	}
+       else
+ 	{
+ 	  fibheap_cut (heap, y, z);
+ 	  y = z;
+ 	}
+     }
+ }
+ 
+ 
+ static fibnode_t
+ fibnode_new ()
+ {
+   fibnode_t e;
+ 
+   if ((e = xmalloc (sizeof *e)) == NULL)
+     return NULL;
+ 
+   fibnode_init (e);
+ 
+   return e;
+ }
+ 
+ static void
+ fibnode_init (node)
+      fibnode_t node;
+ {
+   node->degree = 0;
+   node->mark = 0;
+   node->parent = NULL;
+   node->child = NULL;
+   node->left = node;
+   node->right = node;
+   node->data = NULL;
+ }
+ 
+ static void
+ fibnode_insert_after (a, b)
+      fibnode_t a;
+      fibnode_t b;
+ {
+   if (a == a->right)
+     {
+       a->right = b;
+       a->left = b;
+       b->right = a;
+       b->left = a;
+     }
+   else
+     {
+       b->right = a->right;
+       a->right->left = b;
+       a->right = b;
+       b->left = a;
+     }
+ }
+ 
+ 
+ static fibnode_t
+ fibnode_remove (node)
+      fibnode_t node;
+ {
+   fibnode_t ret;
+ 
+   if (node == node->left)
+     ret = NULL;
+   else
+     ret = node->left;
+ 
+   if (node->parent != NULL && node->parent->child == node)
+     node->parent->child = ret;
+ 
+   node->right->left = node->left;
+   node->left->right = node->right;
+ 
+   node->parent = NULL;
+   node->left = node;
+   node->right = node;
+ 
+   return ret;
+ }
+ 
+ static int
+ fibheap_compare (heap, a, b)
+      fibheap_t heap ATTRIBUTE_UNUSED;
+      fibnode_t a;
+      fibnode_t b;
+ {
+   return a->key - b->key;
+ }
+ 
+ static int
+ fibheap_comp_data (heap, key, data, b)
+      fibheap_t heap;
+      int key;
+      void *data;
+      fibnode_t b;
+ {
+   struct fibnode a;
+ 
+   a.key = key;
+   a.data = data;
+ 
+   return fibheap_compare (heap, &a, b);
+ }
Index: include/fibheap.h
===================================================================
RCS file: fibheap.h
diff -N fibheap.h
*** /dev/null	Tue May  5 13:32:27 1998
--- fibheap.h	Fri Aug 17 09:32:08 2001
***************
*** 0 ****
--- 1,80 ----
+ /* A Fibonacci heap datatype.
+    Copyright 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
+    Contributed by Daniel Berlin (dan@cgsoftware.com).
+ 
+ This file is part of GNU CC.
+    
+ GNU CC is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2, or (at your option)
+ any later version.
+ 
+ GNU CC is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ General Public License for more details.
+ 
+ You should have received a copy of the GNU General Public License
+ along with GNU CC; see the file COPYING.  If not, write to
+ the Free Software Foundation, 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, USA.  */
+ 
+ /* Fibonacci heaps are somewhat complex, but, there's an
+    article in DDJ on them  that explains them pretty well:
+ 
+    http://www.ddj.com/articles/1997/9701/9701o/9701o.htm?topic=algoritms
+ 
+    Introduction to algorithms by Corman and Rivest also goes over
+    them.
+ 
+    The original paper that introduced them is "Fibonacci heaps and their
+    uses in improved network optimization algorithms" by Tarjan and
+    Fredman (JACM 34(3), July 1987).
+ 
+    Amortized and real worst case time for operations:
+ 
+    ExtractMin: O(lg n) amortized. O(n) worst case.
+    DecreaseKey: O(1) amortized.  O(lg n) worst case. 
+    Insert: O(2) amortized. O(1) actual.  
+    Union: O(1) amortized. O(1) actual.
+ 
+   
+ */
+ 
+ #ifndef _FIBHEAP_H_
+ #define _FIBHEAP_H_
+ 
+ #include <ansidecl.h>
+ 
+ typedef struct fibheap
+ {
+   int nodes;
+   struct fibnode *min;
+   struct fibnode *root;
+ } *fibheap_t;
+ 
+ typedef struct fibnode
+ {
+   struct fibnode *parent;
+   struct fibnode *child;
+   struct fibnode *left;
+   struct fibnode *right;
+   int degree;
+   unsigned char mark;
+   int key;
+   void *data;
+ } *fibnode_t;
+ 
+ extern fibheap_t fibheap_new PARAMS ((void));
+ extern fibnode_t fibheap_insert PARAMS ((fibheap_t, int, void *));
+ extern int fibheap_empty PARAMS ((fibheap_t));
+ extern int fibheap_min_key PARAMS ((fibheap_t));
+ extern int fibheap_replace_key PARAMS ((fibheap_t, fibnode_t, int));
+ extern void *fibheap_replace_key_data PARAMS ((fibheap_t, fibnode_t, int, void *));
+ extern void *fibheap_extract_min PARAMS ((fibheap_t));
+ extern void *fibheap_min PARAMS ((fibheap_t));
+ extern void *fibheap_replace_data PARAMS ((fibheap_t, fibnode_t, void *));
+ extern void *fibheap_delete_node PARAMS ((fibheap_t, fibnode_t));
+ extern void fibheap_delete PARAMS ((fibheap_t));
+ extern fibheap_t fibheap_union PARAMS ((fibheap_t, fibheap_t));
+ #endif /* _FIBHEAP_H_ */

-- 
"I saw a sign:  "Rest Area 25 Miles".  That's pretty big.  Some
people must be really tired.
"-Steven Wright


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]