From 377b5e6c3615d2d482cb3341520bd5e84a0704b7 Mon Sep 17 00:00:00 2001
From: Christian Grothoff <christian@grothoff.org>
Date: Tue, 22 Sep 2009 17:33:51 +0000
Subject: [PATCH] heap fixes

---
 src/include/gnunet_container_lib.h | 16 +++++++++++++++-
 src/util/container_heap.c          | 19 ++++++++++++++++---
 2 files changed, 31 insertions(+), 4 deletions(-)

diff --git a/src/include/gnunet_container_lib.h b/src/include/gnunet_container_lib.h
index 79d7866ed..61dee9918 100644
--- a/src/include/gnunet_container_lib.h
+++ b/src/include/gnunet_container_lib.h
@@ -689,7 +689,8 @@ void *GNUNET_CONTAINER_multihashmap_get_random (const struct
 /**
  * Cost by which elements in a heap can be ordered.
  */
-typedef unsigned int GNUNET_CONTAINER_HeapCost;
+typedef uint64_t GNUNET_CONTAINER_HeapCost;
+
 
 /*
  * Heap type, either max or min.  Hopefully makes the
@@ -708,6 +709,7 @@ enum GNUNET_CONTAINER_HeapOrder
   GNUNET_CONTAINER_HEAP_ORDER_MIN
 };
 
+
 /**
  * Handle to a Heap.
  */
@@ -723,6 +725,7 @@ struct GNUNET_CONTAINER_Heap *GNUNET_CONTAINER_heap_create (enum
                                                             GNUNET_CONTAINER_HeapOrder
                                                             type);
 
+
 /**
  * Free a heap
  *
@@ -730,6 +733,7 @@ struct GNUNET_CONTAINER_Heap *GNUNET_CONTAINER_heap_create (enum
  */
 void GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *h);
 
+
 /**
  * Function called on elements of a heap.
  *
@@ -742,6 +746,8 @@ void GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *h);
 typedef int (*GNUNET_CONTAINER_HeapIterator) (void *cls,
                                               void *element,
                                               GNUNET_CONTAINER_HeapCost cost);
+
+
 /**
  * Iterate over all entries in the map.
  *
@@ -756,6 +762,7 @@ int GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap,
                                    void *iterator_cls);
 
 
+
 /**
  * Inserts a new item into the heap, item is always neighbor now.
  * @param heap the heap
@@ -764,6 +771,7 @@ int
 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
                               void *element, GNUNET_CONTAINER_HeapCost cost);
 
+
 /**
  * Removes root of the tree, is remove max if a max heap and remove min
  * if a min heap, returns the data stored at the node.
@@ -773,6 +781,7 @@ GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
  */
 void *GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap);
 
+
 /**
  * Returns element stored at root of tree, doesn't effect anything
  *
@@ -781,6 +790,7 @@ void *GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap);
  */
 void *GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_Heap *heap);
 
+
 /**
  * Removes any node from the tree based on the neighbor given, does
  * not traverse the tree (backpointers) but may take more time due to
@@ -790,6 +800,7 @@ void *GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_Heap *heap);
 void *GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *heap,
                                          void *element);
 
+
 /**
  * Updates the cost of any node in the tree
  *
@@ -803,6 +814,7 @@ GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
                                    void *element,
                                    GNUNET_CONTAINER_HeapCost new_cost);
 
+
 /**
  * Random walk of the tree, returns the data stored at the next random node
  * in the walk.  Calls callee with the data, or NULL if the tree is empty
@@ -814,6 +826,7 @@ GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
 void *GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap
                                            *heap);
 
+
 /**
  * Returns the current size of the heap
  *
@@ -824,6 +837,7 @@ unsigned int
 GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap);
 
 
+
 #if 0                           /* keep Emacsens' auto-indent happy */
 {
 #endif
diff --git a/src/util/container_heap.c b/src/util/container_heap.c
index 7e41c40f2..fd5838f60 100644
--- a/src/util/container_heap.c
+++ b/src/util/container_heap.c
@@ -72,18 +72,31 @@ struct GNUNET_CONTAINER_Heap
 
 };
 
+
+/**
+ * Returns element stored at root of tree, doesn't effect anything
+ *
+ * @param heap the heap
+ * @return NULL if the heap is empty
+ */
+void *GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_Heap *heap)
+{
+  return heap->root;
+}
+
+
 void
 internal_print (struct GNUNET_CONTAINER_heap_node *root)
 {
-  fprintf (stdout, "%d\n", root->cost);
+  fprintf (stdout, "%llu\n", (unsigned long long) root->cost);
   if (root->left_child != NULL)
     {
-      fprintf (stdout, "LEFT of %d\n", root->cost);
+      fprintf (stdout, "LEFT of %llu\n", (unsigned long long) root->cost);
       internal_print (root->left_child);
     }
   if (root->right_child != NULL)
     {
-      fprintf (stdout, "RIGHT of %d\n", root->cost);
+      fprintf (stdout, "RIGHT of %llu\n", (unsigned long long) root->cost);
       internal_print (root->right_child);
     }
 }
-- 
2.25.1