[GNUnet-SVN] r10244 - GNUnet/src/util/containers

[gnunet]

Author: nevans
Date: 2010-02-07 16:00:02 +0100 (Sun, 07 Feb 2010)
New Revision: 10244

Modified:
   GNUnet/src/util/containers/heap.c
   GNUnet/src/util/containers/heaptest.c
Log:
heap changes to fix strange dv iteration bug

Modified: GNUnet/src/util/containers/heap.c
===================================================================
--- GNUnet/src/util/containers/heap.c   2010-02-07 00:40:22 UTC (rev 10243)
+++ GNUnet/src/util/containers/heap.c   2010-02-07 15:00:02 UTC (rev 10244)
@@ -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_node (heap, node);
+      else
+        GNUNET_CONTAINER_heap_remove_root (heap);
+    }
+  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,16 @@
  * @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 +427,18 @@
 
   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 +542,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 +554,16 @@
   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 00:40:22 UTC (rev 
10243)
+++ GNUnet/src/util/containers/heaptest.c       2010-02-07 15:00:02 UTC (rev 
10244)
@@ -49,13 +49,27 @@
   unsigned int cost;
 };
 
+static struct GNUNET_CONTAINER_Heap *minHeap;
+static struct GNUNET_CONTAINER_Heap *maxHeap;
 
+static int
+iterator_callback (void *cls,
+                   struct GNUNET_CONTAINER_HeapNode * node,
+                   void *element,
+                   GNUNET_CONTAINER_HeapCostType cost)
+{
+  struct GNUNET_neighbor *neighbor = element;
+#if DEBUG
+  fprintf(stderr, "Iterating, at neighbor %u with cost %u\n", 
neighbor->neighbor, neighbor->cost);
+#endif
+  GNUNET_CONTAINER_heap_remove_node (maxHeap, node);
+  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;
@@ -137,6 +151,9 @@
         return GNUNET_SYSERR;
 
     }
+
+  GNUNET_CONTAINER_heap_iterate(maxHeap, &iterator_callback, NULL);
+
   while (GNUNET_CONTAINER_heap_get_size (maxHeap) > 0)
     {
       GNUNET_CONTAINER_heap_remove_root (maxHeap);