[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNUnet-SVN] r10247 - in GNUnet/src: include util/containers
From: |
gnunet |
Subject: |
[GNUnet-SVN] r10247 - in GNUnet/src: include util/containers |
Date: |
Mon, 8 Feb 2010 11:18:07 +0100 |
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);
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNUnet-SVN] r10247 - in GNUnet/src: include util/containers,
gnunet <=