[GNUnet-SVN] r10247 - in GNUnet/src: include util/containers

[gnunet]

Author: nevans
Date: 2010-02-08 11:18:07 +0100 (Mon, 08 Feb 2010)
New Revision: 10247

Modified:
   GNUnet/src/include/gnunet_util_containers.h
   GNUnet/src/util/containers/heap.c
   GNUnet/src/util/containers/heaptest.c
Log:
fix of heap, hopefully better tested/coded this time

Modified: GNUnet/src/include/gnunet_util_containers.h
===================================================================
--- GNUnet/src/include/gnunet_util_containers.h 2010-02-07 19:33:11 UTC (rev 
10246)
+++ GNUnet/src/include/gnunet_util_containers.h 2010-02-08 10:18:07 UTC (rev 
10247)
@@ -676,7 +676,7 @@
  * @param iterator_cls closure for iterator
  */
 void
-GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
+GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap,
                                GNUNET_CONTAINER_HeapIterator iterator,
                                void *iterator_cls);
 

Modified: GNUnet/src/util/containers/heap.c
===================================================================
--- GNUnet/src/util/containers/heap.c   2010-02-07 19:33:11 UTC (rev 10246)
+++ GNUnet/src/util/containers/heap.c   2010-02-08 10:18:07 UTC (rev 10247)
@@ -69,6 +69,11 @@
    */
   unsigned int tree_size;
 
+  /*
+   * Is this node scheduled to be deleted?
+   */
+  unsigned int delete;
+
 };
 
 /**
@@ -97,6 +102,20 @@
    */
   enum GNUNET_CONTAINER_HeapOrder order;
 
+  /*
+   * Is the heap dirty (needs expunged)?
+   */
+  unsigned int dirty;
+
+  /*
+   * How many iterations are we into this heap?
+   *
+   * 0 - if no iteration(s) taking place
+   *   > 0 if iteration(s) in progress
+   *   < 0 if we are currently cleaning up the heap (removing dead nodes)!
+   */
+  int iterator_count;
+
 };
 
 
@@ -140,6 +159,8 @@
   struct GNUNET_CONTAINER_Heap *heap;
 
   heap = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_Heap));
+  heap->dirty = GNUNET_NO;
+  heap->iterator_count = 0;
   heap->order = order;
   return heap;
 }
@@ -209,11 +230,51 @@
   if (GNUNET_YES != node_iterator (heap,
                                    node->right_child, iterator, iterator_cls))
     return GNUNET_NO;
-  return iterator (iterator_cls, node, node->element, node->cost);
+
+  if (node->delete == GNUNET_NO)
+    return iterator (iterator_cls, node, node->element, node->cost);
+  else
+    return GNUNET_NO;
 }
 
 
 /**
+ * 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
+ */
+void
+cleanup_node_iterator (struct GNUNET_CONTAINER_Heap *heap,
+               struct GNUNET_CONTAINER_HeapNode *node)
+{
+  if (node == NULL)
+    return;
+
+  if (node->left_child != NULL)
+    cleanup_node_iterator(heap, node->left_child);
+  if (node->right_child != NULL)
+    cleanup_node_iterator(heap, node->right_child);
+
+  if (node->delete == GNUNET_YES)
+    {
+      if (heap->root == node)
+        GNUNET_CONTAINER_heap_remove_root (heap);
+      else
+        GNUNET_CONTAINER_heap_remove_node (heap, node);
+    }
+  return;
+}
+
+void cleanup_heap(struct GNUNET_CONTAINER_Heap *heap)
+{
+  cleanup_node_iterator(heap, heap->root);
+  heap->dirty = GNUNET_NO;
+}
+/**
  * Iterate over all entries in the heap.
  *
  * @param heap the heap
@@ -221,11 +282,18 @@
  * @param iterator_cls closure for iterator
  */
 void
-GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
+GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap,
                                GNUNET_CONTAINER_HeapIterator iterator,
                                void *iterator_cls)
 {
+  heap->iterator_count++;
   (void) node_iterator (heap, heap->root, iterator, iterator_cls);
+  heap->iterator_count--;
+
+  if (heap->iterator_count == 0)
+  {
+    cleanup_heap(heap);
+  }
 }
 
 
@@ -361,8 +429,20 @@
 
   if (NULL == (root = heap->root))
     return NULL;
+
+  ret = root->element;
+  if (heap->iterator_count != 0)
+    {
+      heap->root->delete = GNUNET_YES;
+      if (heap->dirty == GNUNET_NO)
+      {
+        heap->dirty = GNUNET_YES;
+      }
+
+      return ret;
+    }
   heap->size--;
-  ret = root->element;
+
   if (root->left_child == NULL)
     {
       heap->root = root->right_child;
@@ -466,7 +546,7 @@
 
 /**
  * Removes a node from the heap.
- * 
+ *
  * @param heap heap to modify
  * @param node node to remove
  * @return element data stored at the node
@@ -478,6 +558,18 @@
   void *ret;
 
   CHECK (heap->root);
+
+  ret = node->element;
+  if (heap->iterator_count != 0)
+    {
+      node->delete = GNUNET_YES;
+      if (heap->dirty == GNUNET_NO)
+      {
+        heap->dirty = GNUNET_YES;
+      }
+      return ret;
+    }
+
   if (heap->walk_pos == node)
     (void) GNUNET_CONTAINER_heap_walk_get_next (heap);
   remove_node (heap, node);

Modified: GNUnet/src/util/containers/heaptest.c
===================================================================
--- GNUnet/src/util/containers/heaptest.c       2010-02-07 19:33:11 UTC (rev 
10246)
+++ GNUnet/src/util/containers/heaptest.c       2010-02-08 10:18:07 UTC (rev 
10247)
@@ -49,21 +49,44 @@
   unsigned int cost;
 };
 
+static struct GNUNET_CONTAINER_Heap *minHeap;
+static struct GNUNET_CONTAINER_Heap *maxHeap;
+static int cur_pos = 0;
+struct GNUNET_neighbor *neighbors[TESTS];
 
+static int
+iterator_callback (void *cls,
+                   struct GNUNET_CONTAINER_HeapNode * node,
+                   void *element,
+                   GNUNET_CONTAINER_HeapCostType cost)
+{
+  struct GNUNET_neighbor *neighbor = element;
+  struct GNUNET_neighbor *to_remove = cls;
+
+  if (to_remove == neighbor)
+  {
+#if DEBUG
+  fprintf(stderr, "Iterating, removing: neighbor %u with cost %u\n", 
neighbor->neighbor, neighbor->cost);
+#endif
+    GNUNET_CONTAINER_heap_remove_node (maxHeap, node);
+    GNUNET_free (neighbors[cur_pos - 1]);
+    neighbors[cur_pos - 1] = NULL;
+    cur_pos--;
+  }
+  return GNUNET_YES;
+
+}
+
 int
 main (int argc, char **argv)
 {
-
-  struct GNUNET_CONTAINER_Heap *minHeap;
-  struct GNUNET_CONTAINER_Heap *maxHeap;
   int i;
   int ret;
-  int cur_pos = 0;
+
   unsigned int temp_rand;
   unsigned int temp_node;
   unsigned int temp_id;
 
-  struct GNUNET_neighbor *neighbors[TESTS];
   struct GNUNET_CONTAINER_HeapNode *min_nodes[TESTS];
   struct GNUNET_CONTAINER_HeapNode *max_nodes[TESTS];
 
@@ -130,6 +153,19 @@
           cur_pos--;
           break;
         case 4:
+#if DEBUG
+          fprintf (stderr, "First removing from minheap, pre removal size is 
%d\n", GNUNET_CONTAINER_heap_get_size(minHeap));
+#endif
+          GNUNET_CONTAINER_heap_remove_node (minHeap, min_nodes[cur_pos - 1]);
+#if DEBUG
+          fprintf (stderr, "removal from minheap, post removal size is %d\n", 
GNUNET_CONTAINER_heap_get_size(minHeap));
+          fprintf (stderr, "Iterating over heap, pre removal size is %d\n", 
GNUNET_CONTAINER_heap_get_size(maxHeap));
+#endif
+          GNUNET_CONTAINER_heap_iterate(maxHeap, &iterator_callback, 
neighbors[cur_pos - 1]);
+#if DEBUG
+          fprintf (stderr, "post removal size is %d\n", 
GNUNET_CONTAINER_heap_get_size(maxHeap));
+#endif
+
           break;
         }
 
@@ -137,6 +173,9 @@
         return GNUNET_SYSERR;
 
     }
+
+
+
   while (GNUNET_CONTAINER_heap_get_size (maxHeap) > 0)
     {
       GNUNET_CONTAINER_heap_remove_root (maxHeap);