X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=src%2Futil%2Fcontainer_heap.c;h=54da89f7a28dbf008290475df7918abd9bd95dcd;hb=9edc29a3c924554eecc00aa856bf3b0eb95ead52;hp=1e7077c8003ea19d2a7fe134707971ba7ac2462d;hpb=0a217a8df1657b4334b55b0e4a6c7837a8dbcfd9;p=oweals%2Fgnunet.git

diff --git a/src/util/container_heap.c b/src/util/container_heap.c
index 1e7077c80..54da89f7a 100644
--- a/src/util/container_heap.c
+++ b/src/util/container_heap.c
@@ -1,533 +1,552 @@
 /*
- 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 3, 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.h"
-#include "gnunet_util_containers.h"
+#include "gnunet_util_lib.h"
 
-/*
- * Struct that is stored in hashmap, pointers to
- * locations in min_heap and max_heap.
- */
-struct GNUNET_CONTAINER_heap_info
-{
-  struct GNUNET_CONTAINER_heap_node *min_loc;
+#define LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__)
 
-  struct GNUNET_CONTAINER_heap_node *max_loc;
+#define EXTRA_CHECKS 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;
+  /**
+   * Heap this node belongs to.
+   */
+  struct GNUNET_CONTAINER_Heap *heap;
 
-  struct GNUNET_CONTAINER_heap_node *left_child;
+  /**
+   * Parent node.
+   */
+  struct GNUNET_CONTAINER_HeapNode *parent;
 
-  struct GNUNET_CONTAINER_heap_node *right_child;
+  /**
+   * Left child.
+   */
+  struct GNUNET_CONTAINER_HeapNode *left_child;
 
-  GNUNET_CONTAINER_HeapCost cost;
+  /**
+   * Right child.
+   */
+  struct GNUNET_CONTAINER_HeapNode *right_child;
 
+  /**
+   * Our element.
+   */
   void *element;
 
+  /**
+   * Cost for this element.
+   */
+  GNUNET_CONTAINER_HeapCostType cost;
+
+  /**
+   * 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;
+  /**
+   * Root of the heap.
+   */
+  struct GNUNET_CONTAINER_HeapNode *root;
 
-  enum type;
+  /**
+   * Current position of our random walk.
+   */
+  struct GNUNET_CONTAINER_HeapNode *walk_pos;
 
-  struct GNUNET_CONTAINER_heap_node *root;
+  /**
+   * Number of elements in the heap.
+   */
+  unsigned int size;
 
-  struct GNUNET_CONTAINER_heap_node *traversal_pos;
+  /**
+   * How is the heap sorted?
+   */
+  enum GNUNET_CONTAINER_HeapOrder order;
 
 };
 
-void
-internal_print (struct GNUNET_CONTAINER_heap_node *root)
-{
-  fprintf (stdout, "%d\n", root->cost);
-  if (root->left_child != NULL)
-    {
-      fprintf (stdout, "LEFT of %d\n", root->cost);
-      internal_print (root->left_child);
-    }
-  if (root->right_child != NULL)
-    {
-      fprintf (stdout, "RIGHT of %d\n", root->cost);
-      internal_print (root->right_child);
-    }
-}
 
-void
-printTree (struct GNUNET_CONTAINER_Heap *root)
+#if EXTRA_CHECKS
+/**
+ * Check if internal invariants hold for the given node.
+ *
+ * @param node subtree to check
+ */
+static void
+check (const struct GNUNET_CONTAINER_HeapNode *node)
 {
-  internal_print (root->root);
+  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);
 }
 
+
+#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 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_new (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)
 {
-  void *unused;
-  while (heap->size > 0)
-    {
-      unused = GNUNET_CONTAINER_heap_remove_root (heap);
-    }
-
+  GNUNET_break (heap->size == 0);
   GNUNET_free (heap);
-  return;
 }
 
-struct GNUNET_CONTAINER_heap_node *
-find_element (struct GNUNET_CONTAINER_heap_node *node, void *element)
-{
-  struct GNUNET_CONTAINER_heap_node *ret;
-  ret = NULL;
-  if ((node != NULL) && (node->element == element))
-    {
-      ret = node;
-    }
-
-  if ((ret == NULL) && (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;
+/**
+ * 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)
+{
+  if (heap->root == NULL)
+    return NULL;
+  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 depth;
-  int i;
-
-  ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_heap_node));
-  pos = root->size + 1;
-  depth = (int) log2 (pos);
-  ret->left_child = NULL;
-  ret->right_child = NULL;
-
-  if (depth == 0)
-    {
-      ret->parent = NULL;
-      root->root = ret;
-    }
-  else
-    {
-      parent = root->root;
-      for (i = depth; i > 1; i--)
-        {
-          if (((pos / (1 << (i - 1))) % 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;
 
-    }
+/**
+ * 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)
+{
+  return heap->size;
+}
 
-  return ret;
 
+/**
+ * Get the current cost of the node
+ *
+ * @param node the node to get the cost of
+ * @return cost of the node
+ */
+GNUNET_CONTAINER_HeapCostType
+GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode
+                                     *node)
+{
+  return node->cost;
 }
 
-static struct GNUNET_CONTAINER_heap_node *
-getPos (struct GNUNET_CONTAINER_Heap *root, unsigned int pos)
+/**
+ * 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)
 {
-  struct GNUNET_CONTAINER_heap_node *ret;
-
-  int depth;
-  int i;
-
-  depth = (int) log2 (pos);
-  ret = NULL;
-  if (pos > root->size)
-    {
-      return ret;
-    }
-  else
-    {
-      ret = root->root;
-      for (i = depth; i > 0; i--)
-        {
-          if (((pos / (1 << (i - 1))) % 2) == 0)
-            ret = ret->left_child;
-          else
-            ret = ret->right_child;
-        }
-    }
-
-  return ret;
-
+  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;
-
-/*
- * I still worry that there is some good reason for
- * elements being location aware... but it eludes me
- * for the moment...
-  if ((root->type == GNUNET_DV_MAX_HEAP))
-    {
-      first->neighbor->max_loc = first;
-      second->neighbor->max_loc = second;
-    }
-  else if ((root->type == GNUNET_DV_MIN_HEAP))
-    {
-      first->neighbor->min_loc = first;
-      second->neighbor->min_loc = second;
-    }
-*/
-  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 heap heap to modify
+ * @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;
-
-  switchNeighbor = pos;
-
-  if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX))
+  struct GNUNET_CONTAINER_HeapNode *parent;
+
+  GNUNET_assert (node->parent == NULL);
+  while ((heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX) ? (pos->cost >=
+                                                             node->cost)
+         : (pos->cost <= node->cost))
+  {
+    /* node is descendent of pos */
+    pos->tree_size += (1 + node->tree_size);
+    if (pos->left_child == NULL)
     {
-      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;
-        }
+      pos->left_child = node;
+      node->parent = pos;
+      return;
     }
-  else if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN))
+    if (pos->right_child == NULL)
     {
-      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;
-        }
+      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;
+  }
+  /* make 'node' parent of 'pos' */
+  parent = pos->parent;
+  pos->parent = NULL;
+  node->parent = parent;
+  if (NULL == parent)
+  {
+    heap->root = node;
+  }
+  else
+  {
+    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);
+}
 
-  if (switchNeighbor != pos)
-    {
-      swapNodes (switchNeighbor, pos, root);
-      percolateDownHeap (switchNeighbor, root);
-    }
 
-  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_new (struct GNUNET_CONTAINER_HeapNode);
+  node->heap = heap;
+  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;
-
-  del_node = NULL;
-  del_node = find_element (root->root, element);
+  struct GNUNET_CONTAINER_HeapNode *root;
 
-  if (del_node == NULL)
+  if (NULL == (root = heap->root))
     return NULL;
+  heap->size--;
+  ret = root->element;
+  if (root->left_child == NULL)
+  {
+    heap->root = root->right_child;
+    if (root->right_child != NULL)
+      root->right_child->parent = NULL;
+  }
+  else if (root->right_child == NULL)
+  {
+    heap->root = root->left_child;
+    root->left_child->parent = NULL;
+  }
+  else
+  {
+    root->left_child->parent = NULL;
+    root->right_child->parent = NULL;
+    heap->root = root->left_child;
+    insert_node (heap, heap->root, root->right_child);
+  }
+  if (heap->walk_pos == root)
+    heap->walk_pos = heap->root;
+  GNUNET_free (root);
+#if EXTRA_CHECKS
+  GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
+                 (heap->size == heap->root->tree_size + 1));
+  CHECK (heap->root);
+#endif
+  return ret;
+}
 
-  ret = del_node->element;
-  last = getPos (root, 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)
-    {
-      root->traversal_pos = root->root;
-    }
-  GNUNET_free (last);
-  root->size--;
 
-  if (del_node->cost > old_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_HeapNode *node)
+{
+  struct GNUNET_CONTAINER_HeapNode *ancestor;
+  struct GNUNET_CONTAINER_Heap *heap = node->heap;
+
+  /* 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);
+
+  /* unlink 'node' itself and insert children in its place */
+  if (node->parent == NULL)
+  {
+    if (node->left_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 = 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 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);
+      heap->root = node->right_child;
+      if (node->right_child != NULL)
+        node->right_child->parent = NULL;
     }
-
-  return ret;
-}
-
-int
-GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *root,
-                              void *element, GNUNET_CONTAINER_HeapCost cost)
-{
-  struct GNUNET_CONTAINER_heap_node *new_pos;
-  int ret;
-  ret = GNUNET_YES;
-
-  if (root->max_size > root->size)
+  }
+  else
+  {
+    if (node->parent->left_child == node)
+      node->parent->left_child = NULL;
+    else
+      node->parent->right_child = NULL;
+    if (node->left_child != NULL)
     {
-      new_pos = getNextPos (root);
-      new_pos->element = element;
-      new_pos->cost = cost;
-      root->size++;
-      /*We no longer can tolerate pointers between heaps :( */
-      /*if (root->type == GNUNET_DV_MIN_HEAP)
-         new_pos->neighbor->min_loc = new_pos;
-         else if (root->type == GNUNET_DV_MAX_HEAP)
-         new_pos->neighbor->max_loc = new_pos; */
-
-      percolateHeap (new_pos, root);
+      node->left_child->parent = NULL;
+      node->parent->tree_size -= (1 + node->left_child->tree_size);
+      insert_node (heap, node->parent, node->left_child);
     }
-  else
+    if (node->right_child != NULL)
     {
-      ret = GNUNET_NO;
+      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 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_HeapNode *node)
 {
   void *ret;
-  struct GNUNET_CONTAINER_heap_node *root_node;
-  struct GNUNET_CONTAINER_heap_node *last;
-
-  root_node = root->root;
-  ret = root_node->element;
-  last = getPos (root, root->size);
-
-  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;
-    }
+  struct GNUNET_CONTAINER_Heap *heap;
 
-  GNUNET_free (last);
-  root->size--;
-  percolateDownHeap (root->root, root);
+  heap = node->heap;
+  CHECK (heap->root);
+  if (heap->walk_pos == node)
+    (void) GNUNET_CONTAINER_heap_walk_get_next (heap);
+  remove_node (node);
+  heap->size--;
+  ret = node->element;
+  if (heap->walk_pos == node)
+    heap->walk_pos = NULL;
+  GNUNET_free (node);
+#if EXTRA_CHECKS
+  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)
+GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
+                                   struct GNUNET_CONTAINER_HeapNode *node,
+                                   GNUNET_CONTAINER_HeapCostType new_cost)
 {
-  if (node == NULL)
-    return;
-  internal_iterator (root, node->left_child, iterator, cls);
-  internal_iterator (root, node->right_child, iterator, cls);
-  iterator (node->element, node->cost, root, cls);
-}
-
-int
-GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap,
-                               GNUNET_CONTAINER_HeapIterator iterator,
-                               void *cls)
-{
-  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_random_u32 (GNUNET_RANDOM_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 EXTRA_CHECKS
+  GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
+                 (heap->size == heap->root->tree_size + 1));
+  CHECK (heap->root);
+#endif
+  remove_node (node);
+#if EXTRA_CHECKS
+  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 EXTRA_CHECKS
+  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 */