From 0df346263a1bd8c4369258aa9b7de8336e2cf4f2 Mon Sep 17 00:00:00 2001 From: Matthias Wachs Date: Fri, 19 Mar 2010 14:28:12 +0000 Subject: [PATCH] --- src/util/test_container_heap.c | 175 ++++++++++++++++++++++++++++++++- 1 file changed, 172 insertions(+), 3 deletions(-) diff --git a/src/util/test_container_heap.c b/src/util/test_container_heap.c index 78bae229f..b4e206e57 100644 --- a/src/util/test_container_heap.c +++ b/src/util/test_container_heap.c @@ -37,7 +37,6 @@ iterator_callback (void *cls, return GNUNET_OK; } - static int check () { @@ -48,10 +47,37 @@ check () struct GNUNET_CONTAINER_HeapNode *n4; struct GNUNET_CONTAINER_HeapNode *n5; struct GNUNET_CONTAINER_HeapNode *n6; + struct GNUNET_CONTAINER_HeapNode *n7; + struct GNUNET_CONTAINER_HeapNode *n8; myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN); + + // GNUNET_CONTAINER_heap_remove_root heap empty, taking if-branch + n1 = GNUNET_CONTAINER_heap_remove_root (myHeap); + GNUNET_assert (NULL == n1); + + // GNUNET_CONTAINER_heap_peek heap empty, taking if-branch + n1 = GNUNET_CONTAINER_heap_peek (myHeap); + GNUNET_assert (NULL == n1); + + // GNUNET_CONTAINER_heap_walk_get_next: heap empty, taking if-branch + n1 = GNUNET_CONTAINER_heap_walk_get_next (myHeap); + GNUNET_assert (NULL == n1); + n1 = GNUNET_CONTAINER_heap_insert (myHeap, "11", 11); GNUNET_assert (NULL != n1); + + + // GNUNET_CONTAINER_heap_peek not empty, taking if-branch + n2 = NULL; + n2 = GNUNET_CONTAINER_heap_peek (myHeap); + GNUNET_assert (NULL != n2); + + // GNUNET_CONTAINER_heap_walk_get_next: 1 element + n1 = NULL; + n1 = GNUNET_CONTAINER_heap_walk_get_next(myHeap); + GNUNET_assert (NULL != n1); + GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL); GNUNET_assert (1 == GNUNET_CONTAINER_heap_get_size (myHeap)); n2 = GNUNET_CONTAINER_heap_insert (myHeap, "78", 78); @@ -60,12 +86,12 @@ check () GNUNET_CONTAINER_heap_remove_node (myHeap, n2))); GNUNET_assert (1 == GNUNET_CONTAINER_heap_get_size (myHeap)); GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL); - + n3 = GNUNET_CONTAINER_heap_insert (myHeap, "15", 5); GNUNET_CONTAINER_heap_update_cost (myHeap, n3, 15); GNUNET_assert (2 == GNUNET_CONTAINER_heap_get_size (myHeap)); GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL); - + n4 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50); GNUNET_CONTAINER_heap_update_cost (myHeap, n4, 50); GNUNET_assert (3 == GNUNET_CONTAINER_heap_get_size (myHeap)); @@ -84,7 +110,150 @@ check () GNUNET_assert (0 == strcmp ("30/200", GNUNET_CONTAINER_heap_remove_root (myHeap))); /* n6 */ GNUNET_assert (0 == GNUNET_CONTAINER_heap_get_size (myHeap)); + + GNUNET_CONTAINER_heap_destroy (myHeap); + + // My additions to a complete testcase + // Testing a GNUNET_CONTAINER_HEAP_ORDER_MIN + // Testing remove_node + + myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN); + + n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10); + GNUNET_CONTAINER_heap_update_cost (myHeap, n1, 15); + + GNUNET_assert (0 == strcmp ("10", GNUNET_CONTAINER_heap_remove_node (myHeap,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 == strcmp ("20", GNUNET_CONTAINER_heap_remove_node (myHeap,n2))); + GNUNET_assert (0 == strcmp ("10", GNUNET_CONTAINER_heap_remove_node (myHeap,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_assert (0 == strcmp ("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 == strcmp ("30", GNUNET_CONTAINER_heap_remove_node (myHeap,n3))); + + n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10); + n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20); + n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30); + + GNUNET_assert (0 == strcmp ("20", GNUNET_CONTAINER_heap_remove_node (myHeap,n2))); + GNUNET_assert (0 == strcmp ("10", GNUNET_CONTAINER_heap_remove_root (myHeap))); + GNUNET_assert (0 == strcmp ("30", GNUNET_CONTAINER_heap_remove_root (myHeap))); + + n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10); + n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20); + n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30); + n4 = GNUNET_CONTAINER_heap_insert (myHeap, "40", 40); + n5 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50); + n6 = GNUNET_CONTAINER_heap_insert (myHeap, "60", 60); + + // Inserting nodes deeper in the tree with lower costs + n7 = GNUNET_CONTAINER_heap_insert (myHeap, "70", 10); + n8 = GNUNET_CONTAINER_heap_insert (myHeap, "80", 10); + + GNUNET_assert (0 == strcmp ("30", GNUNET_CONTAINER_heap_remove_node (myHeap,n3))); + + // Cleaning up... + GNUNET_assert (0 == strcmp ("60", GNUNET_CONTAINER_heap_remove_node (myHeap,n6))); + GNUNET_assert (0 == strcmp ("50", GNUNET_CONTAINER_heap_remove_node (myHeap,n5))); + + // Testing heap_walk_get_next + GNUNET_CONTAINER_heap_walk_get_next (myHeap); + GNUNET_CONTAINER_heap_walk_get_next (myHeap); + GNUNET_CONTAINER_heap_walk_get_next (myHeap);; + GNUNET_CONTAINER_heap_walk_get_next (myHeap); + GNUNET_CONTAINER_heap_walk_get_next (myHeap); + + GNUNET_assert (0 == strcmp ("10", GNUNET_CONTAINER_heap_remove_node (myHeap,n1))); + GNUNET_assert (0 == strcmp ("20", GNUNET_CONTAINER_heap_remove_node (myHeap,n2))); + GNUNET_assert (0 == strcmp ("40", GNUNET_CONTAINER_heap_remove_node (myHeap,n4))); + GNUNET_assert (0 == strcmp ("70", GNUNET_CONTAINER_heap_remove_node (myHeap,n7))); + GNUNET_assert (0 == strcmp ("80", GNUNET_CONTAINER_heap_remove_node (myHeap,n8))); + + // End Testing remove_node + + // Testing a GNUNET_CONTAINER_HEAP_ORDER_MAX + GNUNET_CONTAINER_heap_destroy (myHeap); + + myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MAX); + + n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10); + GNUNET_CONTAINER_heap_update_cost (myHeap, n1, 15); + + GNUNET_assert (0 == strcmp ("10", GNUNET_CONTAINER_heap_remove_node (myHeap,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 == strcmp ("20", GNUNET_CONTAINER_heap_remove_node (myHeap,n2))); + GNUNET_assert (0 == strcmp ("10", GNUNET_CONTAINER_heap_remove_node (myHeap,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_assert (0 == strcmp ("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 == strcmp ("30", GNUNET_CONTAINER_heap_remove_node (myHeap,n3))); + + n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10); + n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20); + n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30); + n4 = GNUNET_CONTAINER_heap_insert (myHeap, "40", 40); + n5 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50); + n6 = GNUNET_CONTAINER_heap_insert (myHeap, "60", 60); + + // Inserting nodes deeper in the tree with lower costs + n7 = GNUNET_CONTAINER_heap_insert (myHeap, "70", 10); + n8 = GNUNET_CONTAINER_heap_insert (myHeap, "80", 10); + + GNUNET_assert (0 == strcmp ("30", GNUNET_CONTAINER_heap_remove_node (myHeap,n3))); + + // Cleaning up... + GNUNET_assert (0 == strcmp ("60", GNUNET_CONTAINER_heap_remove_node (myHeap,n6))); + GNUNET_assert (0 == strcmp ("50", GNUNET_CONTAINER_heap_remove_node (myHeap,n5))); + + // Testing heap_walk_get_next + GNUNET_CONTAINER_heap_walk_get_next (myHeap); + GNUNET_CONTAINER_heap_walk_get_next (myHeap); + GNUNET_CONTAINER_heap_walk_get_next (myHeap);; + GNUNET_CONTAINER_heap_walk_get_next (myHeap); + GNUNET_CONTAINER_heap_walk_get_next (myHeap); + + GNUNET_assert (0 == strcmp ("10", GNUNET_CONTAINER_heap_remove_node (myHeap,n1))); + GNUNET_assert (0 == strcmp ("20", GNUNET_CONTAINER_heap_remove_node (myHeap,n2))); + GNUNET_assert (0 == strcmp ("40", GNUNET_CONTAINER_heap_remove_node (myHeap,n4))); + GNUNET_assert (0 == strcmp ("70", GNUNET_CONTAINER_heap_remove_node (myHeap,n7))); + GNUNET_assert (0 == strcmp ("80", GNUNET_CONTAINER_heap_remove_node (myHeap,n8))); + + // End Testing remove_node + GNUNET_CONTAINER_heap_destroy (myHeap); + return 0; } -- 2.25.1