updating heap API and implementation

1 files changed, 87 insertions, 74 deletions

diff --git a/src/include/gnunet_container_lib.h b/src/include/gnunet_container_lib.h
index 1f707e44c..db9e10ef8 100644
--- a/src/include/gnunet_container_lib.h
+++ b/src/include/gnunet_container_lib.h
@@ -710,7 +710,7 @@ int GNUNET_CONTAINER_multihashmap_get_multiple (const struct
 /**
  * Cost by which elements in a heap can be ordered.
  */
-typedef uint64_t GNUNET_CONTAINER_HeapCost;
+typedef uint64_t GNUNET_CONTAINER_HeapCostType;
 
 
 /*
@@ -736,132 +736,145 @@ enum GNUNET_CONTAINER_HeapOrder
  */
 struct GNUNET_CONTAINER_Heap;
 
+
+
+/**
+ * Handle to a node in a heap.
+ */
+struct GNUNET_CONTAINER_HeapNode;
+
+
 /**
  * Create a new heap.
  *
- * @param type should the minimum or the maximum element be the root
- * @return NULL on error, otherwise a fresh heap
+ * @param order how should the heap be sorted?
+ * @return handle to the heap
  */
-struct GNUNET_CONTAINER_Heap *GNUNET_CONTAINER_heap_create (enum
-                                                            GNUNET_CONTAINER_HeapOrder
-                                                            type);
+struct GNUNET_CONTAINER_Heap *
+GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order);
 
 
 /**
- * Free a heap
+ * Destroys the heap.  Only call on a heap that
+ * is already empty.
  *
- * @param h heap to free.
+ * @param heap heap to destroy
  */
-void GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *h);
+void GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap);
 
 
 /**
- * Function called on elements of a heap.
+ * Get element stored at root of heap.
  *
- * @param cls closure
- * @param element obj stored in heap
- * @param cost cost of the element
- * @return GNUNET_YES if we should continue to iterate,
- *         GNUNET_NO if not.
+ * @param heap heap to inspect
+ * @return NULL if heap is empty
  */
-typedef int (*GNUNET_CONTAINER_HeapIterator) (void *cls,
-                                              void *element,
-                                              GNUNET_CONTAINER_HeapCost cost);
+void *
+GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap);
 
 
 /**
- * Iterate over all entries in the map.
+ * Get the current size of the heap
  *
- * @param heap the heap
- * @param iterator function to call on each entry
- * @param iterator_cls closure for iterator
- * @return number of items handled
- *         GNUNET_SYSERR if iteration was aborted by iterator
+ * @param heap the heap to get the size of
+ * @return number of elements stored
  */
-int GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap,
-                                   GNUNET_CONTAINER_HeapIterator iterator,
-                                   void *iterator_cls);
-
+unsigned int
+GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap);
 
 
 /**
- * Inserts a new item into the heap, item is always neighbor now.
- * @param heap the heap
- * @param element element to insert
- * @param cost cost of the element
- * @return FIXME
+ * Iterator for heap
+ *
+ * @param cls closure
+ * @param node internal node of the heap
+ * @param element value stored at the node
+ * @param cost cost associated with the node
+ * @return GNUNET_YES if we should continue to iterate,
+ *         GNUNET_NO if not.
  */
-int
-GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
-                              void *element, GNUNET_CONTAINER_HeapCost cost);
+typedef int (*GNUNET_CONTAINER_HeapIterator) (void *cls,
+                                              struct GNUNET_CONTAINER_HeapNode *node,
+                                              void *element,
+                                              GNUNET_CONTAINER_HeapCostType 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.
+ * Iterate over all entries in the heap.
  *
  * @param heap the heap
- * @return NULL if the heap is empty
+ * @param iterator function to call on each entry
+ * @param iterator_cls closure for iterator
  */
-void *GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap);
+void
+GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
+                               GNUNET_CONTAINER_HeapIterator iterator,
+                               void *iterator_cls);
 
 
 /**
- * Returns element stored at root of tree, doesn't effect anything
+ * Perform a random walk of the tree.  The walk is biased
+ * towards elements closer to the root of the tree (since
+ * each walk starts at the root and ends at a random leaf).
+ * The heap internally tracks the current position of the
+ * walk.
  *
- * @param heap the heap
- * @return NULL if the heap is empty
+ * @param heap heap to walk
+ * @return data stored at the next random node in the walk;
+ *         NULL if the tree is empty.
  */
-void *GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_Heap *heap);
+void *
+GNUNET_CONTAINER_heap_walk_get_next (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
- * percolation of nodes.
+ * Inserts a new element into the heap.
  *
- * @param heap the heap
- * @param element the element to remove
- * @return NULL if "element" was not found in the heap, otherwise element
+ * @param heap heap to modify
+ * @param element element to insert
+ * @param cost cost for the element
+ * @return node for the new element
  */
-void *GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *heap,
-                                         void *element);
+struct GNUNET_CONTAINER_HeapNode *
+GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
+                              void *element,
+                              GNUNET_CONTAINER_HeapCostType cost);
 
 
 /**
- * Updates the cost of any node in the tree
+ * Remove root of the heap.
  *
- * @param heap the heap
- * @param element the element for which the cost is updated
- * @param new_cost new cost for the element
- * @return FIXME
+ * @param heap heap to modify
+ * @return element data stored at the root node
  */
-int
-GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
-                                   void *element,
-                                   GNUNET_CONTAINER_HeapCost new_cost);
+void *
+GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap);
 
 
 /**
- * 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
- * or some other problem crops up.
- *
- * @param heap the heap
- * @return the next element from the random walk
+ * Removes a node from the heap.
+ * 
+ * @param heap heap to modify
+ * @param node node to remove
+ * @return element data stored at the node, NULL if heap is empty
  */
-void *GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap
-                                           *heap);
+void *
+GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *heap,
+                                   struct GNUNET_CONTAINER_HeapNode *node);
 
 
 /**
- * Returns the current size of the heap
+ * Updates the cost of any node in the tree
  *
- * @param heap the heap to get the size of
- * @return number of elements in the heap
+ * @param heap heap to modify
+ * @param node node for which the cost is to be changed
+ * @param new_cost new cost for the node
  */
-unsigned int
-GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap);
+void
+GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
+                                   struct GNUNET_CONTAINER_HeapNode *node, 
+                                   GNUNET_CONTAINER_HeapCostType new_cost);
+
 
 /* ******************** Singly linked list *************** */