From 562b33143ee9fa431a68ea6741e4feb3ba388f83 Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Fri, 11 Mar 2011 16:58:27 +0000 Subject: changing heap remove node api to not pass heap; more fs hacking --- src/util/Makefile.am | 5 +-- src/util/container_heap.c | 22 ++++++++----- src/util/test_container_heap.c | 72 +++++++++++++++++++++--------------------- 3 files changed, 53 insertions(+), 46 deletions(-) (limited to 'src/util') diff --git a/src/util/Makefile.am b/src/util/Makefile.am index 9b43b5f05..b24b3ab7c 100644 --- a/src/util/Makefile.am +++ b/src/util/Makefile.am @@ -92,7 +92,7 @@ gnunet_service_resolver_LDADD = \ $(GN_LIBINTL) gnunet_service_resolver_DEPENDENCIES = \ libgnunetutil.la - + gnunet_resolver_SOURCES = \ gnunet-resolver.c @@ -229,7 +229,8 @@ test_crypto_aes_LDADD = \ test_crypto_aes_weak_SOURCES = \ test_crypto_aes_weak.c test_crypto_aes_weak_LDADD = \ - $(top_builddir)/src/util/libgnunetutil.la + $(top_builddir)/src/util/libgnunetutil.la \ + -lgcrypt test_crypto_crc_SOURCES = \ test_crypto_crc.c diff --git a/src/util/container_heap.c b/src/util/container_heap.c index 7cd30a0a7..c332cdd63 100644 --- a/src/util/container_heap.c +++ b/src/util/container_heap.c @@ -36,6 +36,11 @@ */ struct GNUNET_CONTAINER_HeapNode { + /** + * Heap this node belongs to. + */ + struct GNUNET_CONTAINER_Heap *heap; + /** * Parent node. */ @@ -340,6 +345,7 @@ GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, struct GNUNET_CONTAINER_HeapNode *node; node = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_HeapNode)); + node->heap = heap; node->element = element; node->cost = cost; heap->size++; @@ -405,10 +411,10 @@ GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap) * 'size' field of the tree. */ static void -remove_node (struct GNUNET_CONTAINER_Heap *heap, - struct GNUNET_CONTAINER_HeapNode *node) +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; @@ -471,20 +477,20 @@ remove_node (struct GNUNET_CONTAINER_Heap *heap, /** * 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_node (struct GNUNET_CONTAINER_Heap *heap, - struct GNUNET_CONTAINER_HeapNode *node) +GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node) { void *ret; - + struct GNUNET_CONTAINER_Heap *heap; + + heap = node->heap; CHECK (heap->root); if (heap->walk_pos == node) (void) GNUNET_CONTAINER_heap_walk_get_next (heap); - remove_node (heap, node); + remove_node (node); heap->size--; ret = node->element; if (heap->walk_pos == node) @@ -518,7 +524,7 @@ GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap, (heap->size == heap->root->tree_size + 1) ); CHECK (heap->root); #endif - remove_node (heap, node); + remove_node (node); #if DEBUG CHECK (heap->root); GNUNET_assert ( ( (heap->size == 1) && diff --git a/src/util/test_container_heap.c b/src/util/test_container_heap.c index 87bc49129..6a0d5d68d 100644 --- a/src/util/test_container_heap.c +++ b/src/util/test_container_heap.c @@ -93,7 +93,7 @@ check () n2 = GNUNET_CONTAINER_heap_insert (myHeap, "78", 78); GNUNET_assert (2 == GNUNET_CONTAINER_heap_get_size (myHeap)); GNUNET_assert (0 == strcmp ("78", - GNUNET_CONTAINER_heap_remove_node (myHeap, n2))); + GNUNET_CONTAINER_heap_remove_node (n2))); GNUNET_assert (1 == GNUNET_CONTAINER_heap_get_size (myHeap)); GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL); @@ -110,13 +110,13 @@ check () n5 = GNUNET_CONTAINER_heap_insert (myHeap, "100", 100); n6 = GNUNET_CONTAINER_heap_insert (myHeap, "30/200", 30); GNUNET_assert (5 == GNUNET_CONTAINER_heap_get_size (myHeap)); - GNUNET_CONTAINER_heap_remove_node (myHeap, n5); + GNUNET_CONTAINER_heap_remove_node (n5); r = GNUNET_CONTAINER_heap_remove_root (myHeap); /* n1 */ GNUNET_assert (NULL != r); GNUNET_assert (0 == strcmp ("11", r)); GNUNET_CONTAINER_heap_update_cost (myHeap, n6, 200); - GNUNET_CONTAINER_heap_remove_node (myHeap, n3); + GNUNET_CONTAINER_heap_remove_node (n3); r = GNUNET_CONTAINER_heap_remove_root (myHeap); /* n4 */ GNUNET_assert (NULL != r); GNUNET_assert (0 == strcmp ("50", @@ -137,7 +137,7 @@ check () n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10); GNUNET_CONTAINER_heap_update_cost (myHeap, n1, 15); - r = GNUNET_CONTAINER_heap_remove_node (myHeap,n1); + r = GNUNET_CONTAINER_heap_remove_node (n1); GNUNET_assert (NULL != r); GNUNET_assert (0 == strcmp ("10", r)); @@ -145,10 +145,10 @@ check () n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10); GNUNET_CONTAINER_heap_walk_get_next (myHeap); - r = GNUNET_CONTAINER_heap_remove_node (myHeap,n2); + r = GNUNET_CONTAINER_heap_remove_node (n2); GNUNET_assert (NULL != r); GNUNET_assert (0 == strcmp ("20", r)); - r = GNUNET_CONTAINER_heap_remove_node (myHeap,n1); + r = GNUNET_CONTAINER_heap_remove_node (n1); GNUNET_assert (NULL != r); GNUNET_assert (0 == strcmp ("10", r)); @@ -156,8 +156,8 @@ check () n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10); n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10); - GNUNET_CONTAINER_heap_remove_node (myHeap,n2); - GNUNET_CONTAINER_heap_remove_node (myHeap,n1); + GNUNET_CONTAINER_heap_remove_node (n2); + GNUNET_CONTAINER_heap_remove_node (n1); r = GNUNET_CONTAINER_heap_remove_root (myHeap); GNUNET_assert (NULL != r); GNUNET_assert (0 == strcmp ("30", r)); @@ -166,9 +166,9 @@ check () n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10); n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10); - GNUNET_CONTAINER_heap_remove_node (myHeap,n2); - GNUNET_CONTAINER_heap_remove_node (myHeap,n1); - r = GNUNET_CONTAINER_heap_remove_node (myHeap, n3); + GNUNET_CONTAINER_heap_remove_node (n2); + GNUNET_CONTAINER_heap_remove_node (n1); + r = GNUNET_CONTAINER_heap_remove_node ( n3); GNUNET_assert (NULL != r); GNUNET_assert (0 == strcmp ("30", r)); @@ -176,7 +176,7 @@ check () n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20); n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30); - GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (myHeap,n2))); + GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2))); GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_root (myHeap))); GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_root (myHeap))); @@ -191,11 +191,11 @@ check () n7 = GNUNET_CONTAINER_heap_insert (myHeap, "70", 10); n8 = GNUNET_CONTAINER_heap_insert (myHeap, "80", 10); - GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_node (myHeap,n3))); + GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_node (n3))); // Cleaning up... - GNUNET_assert (0 == nstrcmp ("60", GNUNET_CONTAINER_heap_remove_node (myHeap,n6))); - GNUNET_assert (0 == nstrcmp ("50", GNUNET_CONTAINER_heap_remove_node (myHeap,n5))); + GNUNET_assert (0 == nstrcmp ("60", GNUNET_CONTAINER_heap_remove_node (n6))); + GNUNET_assert (0 == nstrcmp ("50", GNUNET_CONTAINER_heap_remove_node (n5))); // Testing heap_walk_get_next GNUNET_CONTAINER_heap_walk_get_next (myHeap); @@ -204,11 +204,11 @@ check () GNUNET_CONTAINER_heap_walk_get_next (myHeap); GNUNET_CONTAINER_heap_walk_get_next (myHeap); - GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (myHeap,n1))); - GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (myHeap,n2))); - GNUNET_assert (0 == nstrcmp ("40", GNUNET_CONTAINER_heap_remove_node (myHeap,n4))); - GNUNET_assert (0 == nstrcmp ("70", GNUNET_CONTAINER_heap_remove_node (myHeap,n7))); - GNUNET_assert (0 == nstrcmp ("80", GNUNET_CONTAINER_heap_remove_node (myHeap,n8))); + GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1))); + GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2))); + GNUNET_assert (0 == nstrcmp ("40", GNUNET_CONTAINER_heap_remove_node (n4))); + GNUNET_assert (0 == nstrcmp ("70", GNUNET_CONTAINER_heap_remove_node (n7))); + GNUNET_assert (0 == nstrcmp ("80", GNUNET_CONTAINER_heap_remove_node (n8))); // End Testing remove_node @@ -220,30 +220,30 @@ check () n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10); GNUNET_CONTAINER_heap_update_cost (myHeap, n1, 15); - GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (myHeap,n1))); + GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1))); n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10); n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10); GNUNET_CONTAINER_heap_walk_get_next (myHeap); - GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (myHeap,n2))); - GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (myHeap,n1))); + GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2))); + GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1))); n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10); n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10); n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10); - GNUNET_CONTAINER_heap_remove_node (myHeap,n2); - GNUNET_CONTAINER_heap_remove_node (myHeap,n1); + GNUNET_CONTAINER_heap_remove_node (n2); + GNUNET_CONTAINER_heap_remove_node (n1); GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_root (myHeap))); n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10); n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10); n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10); - GNUNET_CONTAINER_heap_remove_node (myHeap,n2); - GNUNET_CONTAINER_heap_remove_node (myHeap,n1); - GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_node (myHeap,n3))); + GNUNET_CONTAINER_heap_remove_node (n2); + GNUNET_CONTAINER_heap_remove_node (n1); + GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_node (n3))); n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10); n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20); @@ -256,11 +256,11 @@ check () n7 = GNUNET_CONTAINER_heap_insert (myHeap, "70", 10); n8 = GNUNET_CONTAINER_heap_insert (myHeap, "80", 10); - GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_node (myHeap,n3))); + GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_node (n3))); // Cleaning up... - GNUNET_assert (0 == nstrcmp ("60", GNUNET_CONTAINER_heap_remove_node (myHeap,n6))); - GNUNET_assert (0 == nstrcmp ("50", GNUNET_CONTAINER_heap_remove_node (myHeap,n5))); + GNUNET_assert (0 == nstrcmp ("60", GNUNET_CONTAINER_heap_remove_node (n6))); + GNUNET_assert (0 == nstrcmp ("50", GNUNET_CONTAINER_heap_remove_node (n5))); // Testing heap_walk_get_next GNUNET_CONTAINER_heap_walk_get_next (myHeap); @@ -269,11 +269,11 @@ check () GNUNET_CONTAINER_heap_walk_get_next (myHeap); GNUNET_CONTAINER_heap_walk_get_next (myHeap); - GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (myHeap,n1))); - GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (myHeap,n2))); - GNUNET_assert (0 == nstrcmp ("40", GNUNET_CONTAINER_heap_remove_node (myHeap,n4))); - GNUNET_assert (0 == nstrcmp ("70", GNUNET_CONTAINER_heap_remove_node (myHeap,n7))); - GNUNET_assert (0 == nstrcmp ("80", GNUNET_CONTAINER_heap_remove_node (myHeap,n8))); + GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1))); + GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2))); + GNUNET_assert (0 == nstrcmp ("40", GNUNET_CONTAINER_heap_remove_node (n4))); + GNUNET_assert (0 == nstrcmp ("70", GNUNET_CONTAINER_heap_remove_node (n7))); + GNUNET_assert (0 == nstrcmp ("80", GNUNET_CONTAINER_heap_remove_node (n8))); // End Testing remove_node -- cgit v1.2.3