updating heap API and implementation

1 files changed, 428 insertions, 428 deletions

diff --git a/src/util/container_heap.c b/src/util/container_heap.c
index 9c6005beb..dbb391ac4 100644
--- a/src/util/container_heap.c
+++ b/src/util/container_heap.c
@@ -1,540 +1,540 @@
 /*
- This file is part of GNUnet.
- (C) 2008 Christian Grothoff (and other contributing authors)
-
- GNUnet 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.
-
- GNUnet 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 GNUnet; see the file COPYING.  If not, write to the
- Free Software Foundation, Inc., 59 Temple Place - Suite 330,
- Boston, MA 02111-1307, USA.
- */
+  This file is part of GNUnet.
+  (C) 2008, 2009 Christian Grothoff (and other contributing authors)
+  
+  GNUnet 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.
+  
+  GNUnet 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 GNUnet; see the file COPYING.  If not, write to the
+  Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+  Boston, MA 02111-1307, USA.
+*/
 
 /**
- * @author Nathan Evans
  * @file util/container_heap.c
- * @brief Implementation of heap operations
+ * @brief Implementation of a heap
+ * @author Nathan Evans
+ * @author Christian Grothoff
  */
 
 #include "platform.h"
-#include "gnunet_protocols.h"
 #include "gnunet_util_lib.h"
 
+
+#define DEBUG 0
+
 /**
- * Generic heap node structure, contains pointer to parent
- * left child, right child, and actual neighbor.
+ * Node in the heap.
  */
-struct GNUNET_CONTAINER_heap_node
+struct GNUNET_CONTAINER_HeapNode
 {
-  struct GNUNET_CONTAINER_heap_node *parent;
-
-  struct GNUNET_CONTAINER_heap_node *left_child;
-
-  struct GNUNET_CONTAINER_heap_node *right_child;
+  /**
+   * Parent node.
+   */
+  struct GNUNET_CONTAINER_HeapNode *parent;
+
+  /**
+   * Left child.
+   */
+  struct GNUNET_CONTAINER_HeapNode *left_child;
+
+  /**
+   * Right child.
+   */
+  struct GNUNET_CONTAINER_HeapNode *right_child;
+
+  /**
+   * Our element.
+   */
+  void *element;
 
-  GNUNET_CONTAINER_HeapCost cost;
+  /**
+   * Cost for this element.
+   */
+  GNUNET_CONTAINER_HeapCostType cost;
 
-  void *element;
+  /**
+   * Number of elements below this node in the heap
+   * (excluding this node itself).
+   */
+  unsigned int tree_size;
 
 };
 
+/**
+ * Handle to a node in a heap.
+ */
 struct GNUNET_CONTAINER_Heap
 {
-  unsigned int size;
-
-  unsigned int max_size;
 
-  enum GNUNET_CONTAINER_HeapOrder type;
+  /**
+   * Root of the heap.
+   */
+  struct GNUNET_CONTAINER_HeapNode *root;
 
-  struct GNUNET_CONTAINER_heap_node *root;
+  /**
+   * Current position of our random walk.
+   */
+  struct GNUNET_CONTAINER_HeapNode *walk_pos;
 
-  struct GNUNET_CONTAINER_heap_node *traversal_pos;
+  /**
+   * Number of elements in the heap.
+   */
+  unsigned int size;
+  
+  /**
+   * How is the heap sorted?
+   */
+  enum GNUNET_CONTAINER_HeapOrder order;
 
 };
 
 
+#if DEBUG
 /**
- * Returns element stored at root of tree, doesn't effect anything
+ * Check if internal invariants hold for the given node.
  *
- * @param heap the heap
- * @return NULL if the heap is empty
- */
-void *
-GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_Heap *heap)
-{
-  if ((heap == NULL) || (heap->root == NULL))
-    return NULL;
-
-  return heap->root->element;
-}
-
-static int
-next_power_of_2 (int v)
-{
-  v |= v >> 1;
-  v |= v >> 2;
-  v |= v >> 4;
-  v |= v >> 8;
-  v |= v >> 16;
-  v++;
-  return v;
-}
-
-#if 0
+ * @param node subtree to check
+ */ 
 static void
-internal_print (struct GNUNET_CONTAINER_heap_node *root)
-{
-  fprintf (stdout, "%llu\n", (unsigned long long) root->cost);
-  if (root->left_child != NULL)
-    {
-      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 %llu\n", (unsigned long long) root->cost);
-      internal_print (root->right_child);
-    }
+check (const struct GNUNET_CONTAINER_HeapNode *node)
+{  
+  if (NULL == node)
+    return;
+  GNUNET_assert (node->tree_size ==
+                 ( (node->left_child == NULL) ? 0 : 1 + node->left_child->tree_size) +
+                 ( (node->right_child == NULL) ? 0 : 1 + node->right_child->tree_size) );
+  check (node->left_child);
+  check (node->right_child);
 }
 
-static void
-printTree (struct GNUNET_CONTAINER_Heap *root)
-{
-  internal_print (root->root);
-}
+
+#define CHECK(n) check(n)
+#else
+#define CHECK(n) do {} while (0)
 #endif
 
+
+/**
+ * Create a new 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)
+GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order)
 {
   struct GNUNET_CONTAINER_Heap *heap;
-  heap = malloc (sizeof (struct GNUNET_CONTAINER_Heap));
-  heap->max_size = -1;
-  heap->type = type;
-  heap->root = NULL;
-  heap->traversal_pos = NULL;
-  heap->size = 0;
 
+  heap = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_Heap));
+  heap->order = order;
   return heap;
 }
 
+
+/**
+ * Destroys the heap.  Only call on a heap that
+ * is already empty.
+ *
+ * @param heap heap to destroy
+ */
 void
 GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap)
 {
-  while (heap->size > 0)
-    GNUNET_CONTAINER_heap_remove_root (heap);
+  GNUNET_break (heap->size == 0);
   GNUNET_free (heap);
 }
 
-static struct GNUNET_CONTAINER_heap_node *
-find_element (struct GNUNET_CONTAINER_heap_node *node, void *element)
+
+/**
+ * Get element stored at root of heap.
+ *
+ * @param heap heap to inspect
+ * @return NULL if heap is empty
+ */
+void *
+GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap)
 {
-  struct GNUNET_CONTAINER_heap_node *ret;
-  ret = NULL;
-  if (node == NULL)
+  if (heap->root == NULL)
     return NULL;
-
-  if (node->element == element)
-    return node;
-
-  if (node->left_child != NULL)
-    ret = find_element (node->left_child, element);
-
-  if ((ret == NULL) && (node->right_child != NULL))
-    ret = find_element (node->right_child, element);
-
-  return ret;
+  return heap->root->element;
 }
 
-static struct GNUNET_CONTAINER_heap_node *
-getNextPos (struct GNUNET_CONTAINER_Heap *root)
-{
-  struct GNUNET_CONTAINER_heap_node *ret;
-  struct GNUNET_CONTAINER_heap_node *parent;
-  int pos;
-  int i;
-
-  ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_heap_node));
-  pos = root->size + 1;
-  ret->left_child = NULL;
-  ret->right_child = NULL;
-
-  if (0 == root->size)
-    {
-      ret->parent = NULL;
-      root->root = ret;
-    }
-  else
-    {
-      parent = root->root;
-      for (i = next_power_of_2 (pos) >> 2; i > 1; i >>= 1)
-        {
-          if (((pos / i) % 2) == 0)
-            parent = parent->left_child;
-          else
-            parent = parent->right_child;
-        }
-
-      ret->parent = parent;
-      if ((pos % 2) == 0)
-        parent->left_child = ret;
-      else
-        parent->right_child = ret;
-
-    }
-
-  return ret;
-
-}
 
-static struct GNUNET_CONTAINER_heap_node *
-getPos (struct GNUNET_CONTAINER_Heap *root, unsigned int pos)
+/**
+ * Get the current size of the heap
+ *
+ * @param heap the heap to get the size of
+ * @return number of elements stored
+ */
+unsigned int
+GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap)
 {
-  struct GNUNET_CONTAINER_heap_node *ret;
-  unsigned int i;
-
-  ret = NULL;
-  if (pos > root->size)
-    {
-      return ret;
-    }
-  else
-    {
-      ret = root->root;
-      for (i = next_power_of_2 (pos) >> 2; i > 0; i >>= 1)
-        {
-          if (((pos / i) % 2) == 0)
-            ret = ret->left_child;
-          else
-            ret = ret->right_child;
-        }
-    }
+  return heap->size;
+}
 
-  return ret;
 
+/**
+ * Iterate over the children of the given node.
+ *
+ * @param heap argument to give to iterator
+ * @param node node to iterate over
+ * @param iterator function to call on each node
+ * @param iterator_cls closure for iterator
+ * @return GNUNET_YES to continue to iterate
+ */
+static int
+node_iterator (const struct GNUNET_CONTAINER_Heap *heap,
+               struct GNUNET_CONTAINER_HeapNode *node,
+               GNUNET_CONTAINER_HeapIterator iterator, 
+               void *iterator_cls)
+{
+  if (node == NULL)
+    return GNUNET_YES;
+  if (GNUNET_YES != node_iterator (heap,
+                                   node->left_child,
+                                   iterator,
+                                   iterator_cls))
+    return GNUNET_NO;
+  if (GNUNET_YES != node_iterator (heap,
+                                   node->right_child,
+                                   iterator, 
+                                   iterator_cls))
+    return GNUNET_NO;
+  return iterator (iterator_cls,
+                   node,
+                   node->element,
+                   node->cost);
 }
 
+
+/**
+ * Iterate over all entries in the heap.
+ *
+ * @param heap the heap
+ * @param iterator function to call on each entry
+ * @param iterator_cls closure for iterator
+ */
 void
-swapNodes (struct GNUNET_CONTAINER_heap_node *first,
-           struct GNUNET_CONTAINER_heap_node *second,
-           struct GNUNET_CONTAINER_Heap *root)
+GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
+                               GNUNET_CONTAINER_HeapIterator iterator,
+                               void *iterator_cls)
 {
-  void *temp_element;
-  GNUNET_CONTAINER_HeapCost temp_cost;
-
-  temp_element = first->element;
-  temp_cost = first->cost;
-  first->element = second->element;
-  first->cost = second->cost;
-  second->element = temp_element;
-  second->cost = temp_cost;
-
-  return;
+  (void) node_iterator (heap, heap->root, iterator, iterator_cls);
 }
 
-void
-percolateHeap (struct GNUNET_CONTAINER_heap_node *pos,
-               struct GNUNET_CONTAINER_Heap *root)
-{
 
-  while ((pos->parent != NULL) &&
-         (((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
-           && (pos->parent->cost < pos->cost))
-          || ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
-              && (pos->parent->cost > pos->cost))))
-    {
-      swapNodes (pos, pos->parent, root);
-      pos = pos->parent;
-    }
+/**
+ * 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 heap to walk
+ * @return data stored at the next random node in the walk;
+ *         NULL if the tree is empty.
+ */
+void *
+GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap)
+{
+  struct GNUNET_CONTAINER_HeapNode *pos;
+  void *element;
 
-  return;
+  if (heap->root == NULL)
+    return NULL;
+  pos = heap->walk_pos;
+  if (pos == NULL) 
+    pos = heap->root;   
+  element = pos->element;
+  heap->walk_pos 
+    = (0 == GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, 2))
+    ? pos->right_child 
+    : pos->left_child;
+  return element;
 }
 
 
-
-void
-percolateDownHeap (struct GNUNET_CONTAINER_heap_node *pos,
-                   struct GNUNET_CONTAINER_Heap *root)
+/**
+ * Insert the given node 'node' into the subtree starting
+ * at 'pos' (while keeping the tree somewhat balanced).
+ *
+ * @param pos existing tree
+ * @param node node to insert (which may be a subtree itself)
+ */
+static void
+insert_node (struct GNUNET_CONTAINER_Heap *heap,
+             struct GNUNET_CONTAINER_HeapNode *pos,
+             struct GNUNET_CONTAINER_HeapNode *node)
 {
-  struct GNUNET_CONTAINER_heap_node *switchNeighbor;
+  struct GNUNET_CONTAINER_HeapNode *parent;
 
-  switchNeighbor = pos;
-
-  if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX))
+  GNUNET_assert (node->parent == NULL);
+  while ( (pos->cost < node->cost) ^ (heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX) )
     {
-      if ((pos->left_child != NULL)
-          && (pos->left_child->cost > switchNeighbor->cost))
-        {
-          switchNeighbor = pos->left_child;
-        }
-
-      if ((pos->right_child != NULL)
-          && (pos->right_child->cost > switchNeighbor->cost))
-        {
-          switchNeighbor = pos->right_child;
-        }
+      /* node is descendent of pos */
+      pos->tree_size += (1 + node->tree_size);
+      if (pos->left_child == NULL)
+        {
+          pos->left_child = node;
+          node->parent = pos;
+          return;
+        }
+      if (pos->right_child == NULL)
+        {
+          pos->right_child = node;
+          node->parent = pos;
+          return;
+        }
+      /* keep it balanced by descending into smaller subtree */
+      if (pos->left_child->tree_size < pos->right_child->tree_size)
+        pos = pos->left_child;
+      else
+        pos = pos->right_child;
     }
-  else if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN))
+  /* make 'node' parent of 'pos' */
+  parent = pos->parent;
+  pos->parent = NULL;
+  node->parent = parent;
+  if (NULL == parent)
     {
-      if ((pos->left_child != NULL)
-          && (pos->left_child->cost < switchNeighbor->cost))
-        {
-          switchNeighbor = pos->left_child;
-        }
-
-      if ((pos->right_child != NULL)
-          && (pos->right_child->cost < switchNeighbor->cost))
-        {
-          switchNeighbor = pos->right_child;
-        }
+      heap->root = node;
     }
-
-  if (switchNeighbor != pos)
+  else
     {
-      swapNodes (switchNeighbor, pos, root);
-      percolateDownHeap (switchNeighbor, root);
+      if (parent->left_child == pos)
+        parent->left_child = node;
+      else
+        parent->right_child = node;
     }
+  /* insert 'pos' below 'node' */
+  insert_node (heap, node, pos);
+  CHECK (pos);
+}
+
 
-  return;
+/**
+ * Inserts a new element into the heap.
+ *
+ * @param heap heap to modify
+ * @param element element to insert
+ * @param cost cost for the element
+ * @return node for the new element
+ */
+struct GNUNET_CONTAINER_HeapNode *
+GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
+                              void *element,
+                              GNUNET_CONTAINER_HeapCostType cost)
+{
+  struct GNUNET_CONTAINER_HeapNode *node;
+
+  node = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_HeapNode));
+  node->element = element;
+  node->cost = cost;
+  heap->size++;
+  if (NULL == heap->root)
+    heap->root = node;
+  else
+    insert_node (heap, heap->root, node);
+  GNUNET_assert (heap->size == heap->root->tree_size + 1);
+  CHECK (heap->root);
+  return node;
 }
 
+
+/**
+ * Remove root of the heap.
+ *
+ * @param heap heap to modify
+ * @return element data stored at the root node, NULL if heap is empty
+ */
 void *
-GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *root,
-                                   void *element)
+GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap)
 {
   void *ret;
-  struct GNUNET_CONTAINER_heap_node *del_node;
-  struct GNUNET_CONTAINER_heap_node *last;
-  GNUNET_CONTAINER_HeapCost old_cost;
+  struct GNUNET_CONTAINER_HeapNode *root;
 
-  del_node = NULL;
-  del_node = find_element (root->root, element);
-
-  if (del_node == NULL)
+  if (NULL == (root = heap->root))
     return NULL;
-  else if (del_node == root->root)
-    return GNUNET_CONTAINER_heap_remove_root (root);
-
-  ret = del_node->element;
-  last = getPos (root, root->size);
-
-  root->size--;
-
-  old_cost = del_node->cost;
-  del_node->element = last->element;
-  del_node->cost = last->cost;
-
-  if (last->parent->left_child == last)
-    last->parent->left_child = NULL;
-  if (last->parent->right_child == last)
-    last->parent->right_child = NULL;
-
-  if (root->traversal_pos == last)
+  heap->size--;
+  ret = root->element;
+  if (root->left_child == NULL)
     {
-      root->traversal_pos = root->root;
+      heap->root = root->right_child;
+      if (root->right_child != NULL)
+        root->right_child->parent = NULL;
     }
-
-  if (last == del_node)
-  {
-    GNUNET_free (last);
-    return ret;
-  }
-  GNUNET_free (last);
-
-
-  if (del_node->cost > old_cost)
+  else if (root->right_child == NULL)
     {
-      if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
-        percolateHeap (del_node, root);
-      else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
-        percolateDownHeap (del_node, root);
+      heap->root = root->left_child;
+      if (root->left_child != NULL)
+        root->left_child->parent = NULL;
     }
-  else if (del_node->cost < old_cost)
+  else
     {
-      if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
-        percolateDownHeap (del_node, root);
-      else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
-        percolateHeap (del_node, root);
+      root->left_child->parent = NULL;
+      root->right_child->parent = NULL;
+      heap->root = root->left_child;
+      insert_node (heap, heap->root, root->right_child);
     }
-
+  GNUNET_free (root);
+#if DEBUG
+  GNUNET_assert (( (heap->size == 0) && 
+                   (heap->root == NULL) ) ||
+                 (heap->size == heap->root->tree_size + 1) );
+  CHECK (heap->root);
+#endif
   return ret;
 }
 
-int
-GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *root,
-                              void *element, GNUNET_CONTAINER_HeapCost cost)
+
+/**
+ * Remove the given node 'node' from the tree and update
+ * the 'tree_size' fields accordingly.  Preserves the
+ * children of 'node' and does NOT change the overall
+ * 'size' field of the tree.
+ */
+static void
+remove_node (struct GNUNET_CONTAINER_Heap *heap,
+             struct GNUNET_CONTAINER_HeapNode *node)
 {
-  struct GNUNET_CONTAINER_heap_node *new_pos;
-  int ret;
-  ret = GNUNET_YES;
+  struct GNUNET_CONTAINER_HeapNode *ancestor;
 
-  if (root->max_size > root->size)
-    {
-      new_pos = getNextPos (root);
-      new_pos->element = element;
-      new_pos->cost = cost;
-      root->size++;
+  /* update 'size' of the ancestors */
+  ancestor = node;
+  while (NULL != (ancestor = ancestor->parent))    
+    ancestor->tree_size--;
+
+  /* update 'size' of node itself */
+  if (node->left_child != NULL)
+    node->tree_size -= (1 + node->left_child->tree_size);
+  if (node->right_child != NULL)
+    node->tree_size -= (1 + node->right_child->tree_size);
 
-      percolateHeap (new_pos, root);
+  /* unlink 'node' itself and insert children in its place */
+  if (node->parent == NULL)
+    {
+      if (node->left_child != NULL)
+        {
+          heap->root = node->left_child;
+          node->left_child->parent = NULL;
+          if (node->right_child != NULL)
+            {
+              node->right_child->parent = NULL;
+              insert_node (heap, heap->root, node->right_child);        
+            }
+        }
+      else
+        {
+          heap->root = node->right_child;
+          if (node->right_child != NULL)
+            node->right_child->parent = NULL;
+        }
     }
   else
     {
-      ret = GNUNET_NO;
+      if (node->parent->left_child == node)
+        node->parent->left_child = NULL;
+      else
+        node->parent->right_child = NULL;
+      if (node->left_child != NULL)
+        {
+          node->left_child->parent = NULL;
+          node->parent->tree_size -= (1 + node->left_child->tree_size);
+          insert_node (heap, node->parent, node->left_child);
+        }
+      if (node->right_child != NULL)
+        {
+          node->right_child->parent = NULL;
+          node->parent->tree_size -= (1 + node->right_child->tree_size);
+          insert_node (heap, node->parent, node->right_child);
+        }
     }
-
-  return ret;
+  node->parent = NULL;
+  node->left_child = NULL;
+  node->right_child = NULL;
+  GNUNET_assert (node->tree_size == 0);
+  CHECK (heap->root);
 }
 
+
+/**
+ * Removes a node from the heap.
+ * 
+ * @param heap heap to modify
+ * @param node node to remove
+ * @return element data stored at the node
+ */
 void *
-GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *root)
+GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *heap,
+                                   struct GNUNET_CONTAINER_HeapNode *node)
 {
   void *ret;
-  struct GNUNET_CONTAINER_heap_node *root_node;
-  struct GNUNET_CONTAINER_heap_node *last;
-
-  if ((root == NULL) || (root->size == 0) || (root->root == NULL))
-    {
-      GNUNET_break (0);
-      return NULL;
-    }
-
-  root_node = root->root;
-  ret = root_node->element;
-  last = getPos (root, root->size);
-
-  if ((root_node == last) && (root->size == 1))
-    {
-      /* We are removing the last node in the heap! */
-      GNUNET_free (last);
-      root->root = NULL;
-      root->traversal_pos = NULL;
-      GNUNET_assert (0 == --root->size);
-      return ret;
-    }
-
-  if (last->parent->left_child == last)
-    last->parent->left_child = NULL;
-  else if (last->parent->right_child == last)
-    last->parent->right_child = NULL;
-
-  root_node->element = last->element;
-  root_node->cost = last->cost;
-
-  if (root->traversal_pos == last)
-    root->traversal_pos = root->root;
-  GNUNET_free (last);
-  root->size--;
-  percolateDownHeap (root->root, root);
+ 
+  CHECK (heap->root);
+  if (heap->walk_pos == node)
+    (void) GNUNET_CONTAINER_heap_walk_get_next (heap);
+  remove_node (heap, node);
+  heap->size--;
+  ret = node->element;
+  if (heap->walk_pos == node)
+    heap->walk_pos = NULL;
+  GNUNET_free (node);
+#if DEBUG
+  CHECK (heap->root);
+  GNUNET_assert (( (heap->size == 0) && 
+                   (heap->root == NULL) ) ||
+                 (heap->size == heap->root->tree_size + 1) );
+#endif
   return ret;
 }
 
-static int
-updatedCost (struct GNUNET_CONTAINER_Heap *root,
-             struct GNUNET_CONTAINER_heap_node *node)
-{
-  struct GNUNET_CONTAINER_heap_node *parent;
-
-  if (node == NULL)
-    return GNUNET_SYSERR;
-
-  parent = node->parent;
-
-  if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX) && (parent != NULL)
-      && (node->cost > parent->cost))
-    percolateHeap (node, root);
-  else if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN) && (parent != NULL)
-           && (node->cost < parent->cost))
-    percolateHeap (node, root);
-  else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
-    percolateDownHeap (node, root);
-  else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
-    percolateDownHeap (node, root);
-
-  return GNUNET_YES;
-}
-
-
-int
-GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *root,
-                                   void *element,
-                                   GNUNET_CONTAINER_HeapCost new_cost)
-{
-  struct GNUNET_CONTAINER_heap_node *node;
-  int ret = GNUNET_YES;
-  node = find_element (root->root, element);
-  if (node == NULL)
-    return GNUNET_NO;
-
-  node->cost = new_cost;
-  ret = updatedCost (root, node);
-  return ret;
-}
 
+/**
+ * Updates the cost of any node in the tree
+ *
+ * @param heap heap to modify
+ * @param node node for which the cost is to be changed
+ * @param new_cost new cost for the node
+ */
 void
-internal_iterator (struct GNUNET_CONTAINER_Heap *root,
-                   struct GNUNET_CONTAINER_heap_node *node,
-                   GNUNET_CONTAINER_HeapIterator iterator, void *cls)
-{
-  if (node == NULL)
-    return;
-  internal_iterator (root, node->left_child, iterator, cls);
-  internal_iterator (root, node->right_child, iterator, cls);
-  iterator (cls, node->element, node->cost);
-}
-
-int
-GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap,
-                               GNUNET_CONTAINER_HeapIterator iterator,
-                               void *cls)
+GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
+                                   struct GNUNET_CONTAINER_HeapNode *node, 
+                                   GNUNET_CONTAINER_HeapCostType new_cost)
 {
-  internal_iterator (heap, heap->root, iterator, cls);
-  return GNUNET_OK;
-}
-
-void *
-GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *root)
-{
-  unsigned int choice;
-  void *element;
-
-  if ((root->traversal_pos == NULL) && (root->root != NULL))
-    {
-      root->traversal_pos = root->root;
-    }
-
-  if (root->traversal_pos == NULL)
-    return NULL;
-
-  element = root->traversal_pos->element;
-
-  choice = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, 2);
-
-  switch (choice)
-    {
-    case 1:
-      root->traversal_pos = root->traversal_pos->right_child;
-      break;
-    case 0:
-      root->traversal_pos = root->traversal_pos->left_child;
-      break;
-    }
-
-  return element;
-
+#if DEBUG
+  GNUNET_assert ( ( (heap->size == 0) && 
+                    (heap->root == NULL) ) ||
+                  (heap->size == heap->root->tree_size + 1) );
+  CHECK (heap->root);
+#endif
+  remove_node (heap, node);
+#if DEBUG
+  CHECK (heap->root);
+  GNUNET_assert ( ( (heap->size == 1) && 
+                    (heap->root == NULL) ) ||
+                  (heap->size == heap->root->tree_size + 2) );
+#endif
+  node->cost = new_cost;
+  if (heap->root == NULL)
+    heap->root = node;
+  else
+    insert_node (heap, heap->root, node);
+#if DEBUG
+  CHECK (heap->root);
+  GNUNET_assert ( ( (heap->size == 0) && 
+                    (heap->root == NULL) ) ||
+                  (heap->size == heap->root->tree_size + 1) );
+#endif
 }
 
-unsigned int
-GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap)
-{
-  return heap->size;
-}
 
 /* end of heap.c */