[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNUnet-SVN] r9888 - GNUnet/src/util/containers
|
From: |
gnunet |
|
Subject: |
[GNUnet-SVN] r9888 - GNUnet/src/util/containers |
|
Date: |
Wed, 23 Dec 2009 23:56:29 +0100 |
Author: nevans
Date: 2009-12-23 23:56:29 +0100 (Wed, 23 Dec 2009)
New Revision: 9888
Modified:
GNUnet/src/util/containers/heap.c
GNUnet/src/util/containers/heaptest.c
Log:
pre-commit (heap.c) and MUCH better heaptest testcase
Modified: GNUnet/src/util/containers/heap.c
===================================================================
--- GNUnet/src/util/containers/heap.c 2009-12-23 22:54:29 UTC (rev 9887)
+++ GNUnet/src/util/containers/heap.c 2009-12-23 22:56:29 UTC (rev 9888)
@@ -91,7 +91,7 @@
* Number of elements in the heap.
*/
unsigned int size;
-
+
/**
* How is the heap sorted?
*/
@@ -105,16 +105,18 @@
* Check if internal invariants hold for the given node.
*
* @param node subtree to check
- */
+ */
static void
check (const struct GNUNET_CONTAINER_HeapNode *node)
-{
+{
if (NULL == node)
return;
GNUNET_GE_ASSERT (NULL,
- node->tree_size ==
- ( (node->left_child == NULL) ? 0 : 1 +
node->left_child->tree_size) +
- ( (node->right_child == NULL) ? 0 : 1 +
node->right_child->tree_size) );
+ node->tree_size ==
+ ((node->left_child ==
+ NULL) ? 0 : 1 + node->left_child->tree_size) +
+ ((node->right_child ==
+ NULL) ? 0 : 1 + node->right_child->tree_size));
check (node->left_child);
check (node->right_child);
}
@@ -196,26 +198,18 @@
*/
static int
node_iterator (const struct GNUNET_CONTAINER_Heap *heap,
- struct GNUNET_CONTAINER_HeapNode *node,
- GNUNET_CONTAINER_HeapIterator iterator,
- void *iterator_cls)
+ struct GNUNET_CONTAINER_HeapNode *node,
+ GNUNET_CONTAINER_HeapIterator iterator, void *iterator_cls)
{
if (node == NULL)
return GNUNET_YES;
if (GNUNET_YES != node_iterator (heap,
- node->left_child,
- iterator,
- iterator_cls))
+ node->left_child, iterator, iterator_cls))
return GNUNET_NO;
if (GNUNET_YES != node_iterator (heap,
- node->right_child,
- iterator,
- iterator_cls))
+ node->right_child, iterator, iterator_cls))
return GNUNET_NO;
- return iterator (iterator_cls,
- node,
- node->element,
- node->cost);
+ return iterator (iterator_cls, node, node->element, node->cost);
}
@@ -255,13 +249,12 @@
if (heap->root == NULL)
return NULL;
pos = heap->walk_pos;
- if (pos == NULL)
- pos = heap->root;
+ if (pos == NULL)
+ pos = heap->root;
element = pos->element;
- heap->walk_pos
+ heap->walk_pos
= (0 == GNUNET_random_u32 (GNUNET_RANDOM_QUALITY_WEAK, 2))
- ? pos->right_child
- : pos->left_child;
+ ? pos->right_child : pos->left_child;
return element;
}
@@ -275,35 +268,34 @@
*/
static void
insert_node (struct GNUNET_CONTAINER_Heap *heap,
- struct GNUNET_CONTAINER_HeapNode *pos,
- struct GNUNET_CONTAINER_HeapNode *node)
+ struct GNUNET_CONTAINER_HeapNode *pos,
+ struct GNUNET_CONTAINER_HeapNode *node)
{
struct GNUNET_CONTAINER_HeapNode *parent;
GNUNET_GE_ASSERT (NULL, node->parent == NULL);
- while ( (heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX)
- ? (pos->cost >= node->cost)
- : (pos->cost <= node->cost) )
+ while ((heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX)
+ ? (pos->cost >= node->cost) : (pos->cost <= node->cost))
{
/* node is descendent of pos */
pos->tree_size += (1 + node->tree_size);
if (pos->left_child == NULL)
- {
- pos->left_child = node;
- node->parent = pos;
- return;
- }
+ {
+ pos->left_child = node;
+ node->parent = pos;
+ return;
+ }
if (pos->right_child == NULL)
- {
- pos->right_child = node;
- node->parent = pos;
- return;
- }
+ {
+ pos->right_child = node;
+ node->parent = pos;
+ return;
+ }
/* keep it balanced by descending into smaller subtree */
if (pos->left_child->tree_size < pos->right_child->tree_size)
- pos = pos->left_child;
+ pos = pos->left_child;
else
- pos = pos->right_child;
+ pos = pos->right_child;
}
/* make 'node' parent of 'pos' */
parent = pos->parent;
@@ -316,9 +308,9 @@
else
{
if (parent->left_child == pos)
- parent->left_child = node;
+ parent->left_child = node;
else
- parent->right_child = node;
+ parent->right_child = node;
}
/* insert 'pos' below 'node' */
insert_node (heap, node, pos);
@@ -337,7 +329,7 @@
struct GNUNET_CONTAINER_HeapNode *
GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
void *element,
- GNUNET_CONTAINER_HeapCostType cost)
+ GNUNET_CONTAINER_HeapCostType cost)
{
struct GNUNET_CONTAINER_HeapNode *node;
@@ -375,13 +367,13 @@
{
heap->root = root->right_child;
if (root->right_child != NULL)
- root->right_child->parent = NULL;
+ root->right_child->parent = NULL;
}
else if (root->right_child == NULL)
{
heap->root = root->left_child;
if (root->left_child != NULL)
- root->left_child->parent = NULL;
+ root->left_child->parent = NULL;
}
else
{
@@ -392,10 +384,10 @@
}
GNUNET_free (root);
#if DEBUG
- GNUNET_GE_ASSERT (NULL,
- ( (heap->size == 0) &&
- (heap->root == NULL) ) ||
- (heap->size == heap->root->tree_size + 1) );
+ GNUNET_GE_ASSERT (NULL,
+ ((heap->size == 0) &&
+ (heap->root == NULL)) ||
+ (heap->size == heap->root->tree_size + 1));
CHECK (heap->root);
#endif
return ret;
@@ -410,13 +402,13 @@
*/
static void
remove_node (struct GNUNET_CONTAINER_Heap *heap,
- struct GNUNET_CONTAINER_HeapNode *node)
+ struct GNUNET_CONTAINER_HeapNode *node)
{
struct GNUNET_CONTAINER_HeapNode *ancestor;
/* update 'size' of the ancestors */
ancestor = node;
- while (NULL != (ancestor = ancestor->parent))
+ while (NULL != (ancestor = ancestor->parent))
ancestor->tree_size--;
/* update 'size' of node itself */
@@ -429,40 +421,40 @@
if (node->parent == NULL)
{
if (node->left_child != NULL)
- {
- heap->root = node->left_child;
- node->left_child->parent = NULL;
- if (node->right_child != NULL)
- {
- node->right_child->parent = NULL;
- insert_node (heap, heap->root, node->right_child);
- }
- }
+ {
+ heap->root = node->left_child;
+ node->left_child->parent = NULL;
+ if (node->right_child != NULL)
+ {
+ node->right_child->parent = NULL;
+ insert_node (heap, heap->root, node->right_child);
+ }
+ }
else
- {
- heap->root = node->right_child;
- if (node->right_child != NULL)
- node->right_child->parent = NULL;
- }
+ {
+ heap->root = node->right_child;
+ if (node->right_child != NULL)
+ node->right_child->parent = NULL;
+ }
}
else
{
if (node->parent->left_child == node)
- node->parent->left_child = NULL;
+ node->parent->left_child = NULL;
else
- node->parent->right_child = NULL;
+ node->parent->right_child = NULL;
if (node->left_child != NULL)
- {
- node->left_child->parent = NULL;
- node->parent->tree_size -= (1 + node->left_child->tree_size);
- insert_node (heap, node->parent, node->left_child);
- }
+ {
+ node->left_child->parent = NULL;
+ node->parent->tree_size -= (1 + node->left_child->tree_size);
+ insert_node (heap, node->parent, node->left_child);
+ }
if (node->right_child != NULL)
- {
- node->right_child->parent = NULL;
- node->parent->tree_size -= (1 + node->right_child->tree_size);
- insert_node (heap, node->parent, node->right_child);
- }
+ {
+ node->right_child->parent = NULL;
+ node->parent->tree_size -= (1 + node->right_child->tree_size);
+ insert_node (heap, node->parent, node->right_child);
+ }
}
node->parent = NULL;
node->left_child = NULL;
@@ -484,7 +476,7 @@
struct GNUNET_CONTAINER_HeapNode *node)
{
void *ret;
-
+
CHECK (heap->root);
if (heap->walk_pos == node)
(void) GNUNET_CONTAINER_heap_walk_get_next (heap);
@@ -496,10 +488,10 @@
GNUNET_free (node);
#if DEBUG
CHECK (heap->root);
- GNUNET_GE_ASSERT (NULL,
- ( (heap->size == 0) &&
- (heap->root == NULL) ) ||
- (heap->size == heap->root->tree_size + 1) );
+ GNUNET_GE_ASSERT (NULL,
+ ((heap->size == 0) &&
+ (heap->root == NULL)) ||
+ (heap->size == heap->root->tree_size + 1));
#endif
return ret;
}
@@ -514,23 +506,23 @@
*/
void
GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
- struct GNUNET_CONTAINER_HeapNode *node,
- GNUNET_CONTAINER_HeapCostType new_cost)
+ struct GNUNET_CONTAINER_HeapNode *node,
+ GNUNET_CONTAINER_HeapCostType new_cost)
{
#if DEBUG
- GNUNET_GE_ASSERT (NULL,
- ( (heap->size == 0) &&
- (heap->root == NULL) ) ||
- (heap->size == heap->root->tree_size + 1) );
+ GNUNET_GE_ASSERT (NULL,
+ ((heap->size == 0) &&
+ (heap->root == NULL)) ||
+ (heap->size == heap->root->tree_size + 1));
CHECK (heap->root);
#endif
remove_node (heap, node);
#if DEBUG
CHECK (heap->root);
- GNUNET_GE_ASSERT (NULL,
- ( (heap->size == 1) &&
- (heap->root == NULL) ) ||
- (heap->size == heap->root->tree_size + 2) );
+ GNUNET_GE_ASSERT (NULL,
+ ((heap->size == 1) &&
+ (heap->root == NULL)) ||
+ (heap->size == heap->root->tree_size + 2));
#endif
node->cost = new_cost;
if (heap->root == NULL)
@@ -539,10 +531,10 @@
insert_node (heap, heap->root, node);
#if DEBUG
CHECK (heap->root);
- GNUNET_GE_ASSERT (NULL,
- ( (heap->size == 0) &&
- (heap->root == NULL) ) ||
- (heap->size == heap->root->tree_size + 1) );
+ GNUNET_GE_ASSERT (NULL,
+ ((heap->size == 0) &&
+ (heap->root == NULL)) ||
+ (heap->size == heap->root->tree_size + 1));
#endif
}
Modified: GNUnet/src/util/containers/heaptest.c
===================================================================
--- GNUnet/src/util/containers/heaptest.c 2009-12-23 22:54:29 UTC (rev
9887)
+++ GNUnet/src/util/containers/heaptest.c 2009-12-23 22:56:29 UTC (rev
9888)
@@ -20,82 +20,135 @@
/**
* @author Nathan Evans
- * @author Christian Grothoff
* @file util/containers/heaptest.c
- * @brief Test of heap operations
+ * @brief Test of heap operations in churny like conditions...
*/
+
+#include "gnunet_util.h"
+#include "gnunet_util_crypto.h"
#include "platform.h"
-#include "gnunet_util.h"
-#include "gnunet_util_containers.h"
-#include "dv.h"
-#define VERBOSE GNUNET_NO
+#define MAX_SIZE 100
+#define TESTS 75
+#define DEBUG GNUNET_NO
-static int
-iterator_callback (void *cls,
- struct GNUNET_CONTAINER_HeapNode *node,
- void *element,
- GNUNET_CONTAINER_HeapCostType cost)
+/* Test struct so we have something to actually
+ * put into the heap */
+
+struct GNUNET_neighbor
{
- return GNUNET_OK;
-}
+ /**
+ * Identity of neighbor.
+ */
+ unsigned int neighbor;
+ /**
+ * Cost to neighbor
+ */
+ unsigned int cost;
+};
+
+
int
main (int argc, char **argv)
{
- struct GNUNET_CONTAINER_Heap *myHeap;
- struct GNUNET_CONTAINER_HeapNode *n1;
- struct GNUNET_CONTAINER_HeapNode *n2;
- struct GNUNET_CONTAINER_HeapNode *n3;
- struct GNUNET_CONTAINER_HeapNode *n4;
- struct GNUNET_CONTAINER_HeapNode *n5;
- struct GNUNET_CONTAINER_HeapNode *n6;
- myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
- n1 = GNUNET_CONTAINER_heap_insert (myHeap, "11", 11);
- GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
- GNUNET_GE_ASSERT (NULL,
- 1 == GNUNET_CONTAINER_heap_get_size (myHeap));
- n2 = GNUNET_CONTAINER_heap_insert (myHeap, "78", 78);
- GNUNET_GE_ASSERT (NULL,
- 2 == GNUNET_CONTAINER_heap_get_size (myHeap));
- GNUNET_GE_ASSERT (NULL,
- 0 == strcmp ("78",
- GNUNET_CONTAINER_heap_remove_node (myHeap,
n2)));
- GNUNET_GE_ASSERT (NULL,
- 1 == GNUNET_CONTAINER_heap_get_size (myHeap));
- GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
+ 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;
- n3 = GNUNET_CONTAINER_heap_insert (myHeap, "15", 5);
- GNUNET_CONTAINER_heap_update_cost (myHeap, n3, 15);
- GNUNET_GE_ASSERT (NULL,
- 2 == GNUNET_CONTAINER_heap_get_size (myHeap));
- GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
+ struct GNUNET_neighbor *neighbors[TESTS];
+ struct GNUNET_CONTAINER_HeapNode *min_nodes[TESTS];
+ struct GNUNET_CONTAINER_HeapNode *max_nodes[TESTS];
- n4 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50);
- GNUNET_GE_ASSERT (NULL,
- 3 == GNUNET_CONTAINER_heap_get_size (myHeap));
- GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
+ ret = GNUNET_OK;
+ maxHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MAX);
+ minHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
- n5 = GNUNET_CONTAINER_heap_insert (myHeap, "100", 100);
- n6 = GNUNET_CONTAINER_heap_insert (myHeap, "30/200", 30);
- GNUNET_GE_ASSERT (NULL,
- 5 == GNUNET_CONTAINER_heap_get_size (myHeap));
- GNUNET_CONTAINER_heap_remove_node (myHeap, n5);
- GNUNET_GE_ASSERT (NULL,
- 0 == strcmp ("11",
- GNUNET_CONTAINER_heap_remove_root (myHeap)));
/* n1 */
- GNUNET_CONTAINER_heap_update_cost (myHeap, n6, 200);
- GNUNET_CONTAINER_heap_remove_node (myHeap, n3);
- GNUNET_GE_ASSERT (NULL,
- 0 == strcmp ("50",
- GNUNET_CONTAINER_heap_remove_root (myHeap)));
/* n4 */
- GNUNET_GE_ASSERT (NULL,
- 0 == strcmp ("30/200",
- GNUNET_CONTAINER_heap_remove_root (myHeap)));
/* n6 */
- GNUNET_GE_ASSERT (NULL, 0 == GNUNET_CONTAINER_heap_get_size (myHeap));
- GNUNET_CONTAINER_heap_destroy (myHeap);
+ for (i = 0; i < TESTS; i++)
+ {
+ neighbors[i] = NULL;
+ }
+
+ for (i = 0; i < TESTS; i++)
+ {
+ temp_rand = GNUNET_random_u32 (GNUNET_RANDOM_QUALITY_WEAK, 5);
+ while ((cur_pos <= 1) && (temp_rand != 0))
+ temp_rand = GNUNET_random_u32 (GNUNET_RANDOM_QUALITY_WEAK, 5);
+
+ switch (temp_rand)
+ {
+ case 0:
+ case 1:
+ temp_rand = GNUNET_random_u32 (GNUNET_RANDOM_QUALITY_WEAK, 100) + 1;
+ temp_id =
+ GNUNET_random_u32 (GNUNET_RANDOM_QUALITY_WEAK, 100000) + 1;
+#if DEBUG
+ fprintf (stderr, "Adding node with cost %d\n", temp_rand);
+#endif
+ neighbors[cur_pos] =
+ GNUNET_malloc (sizeof (struct GNUNET_neighbor));
+ neighbors[cur_pos]->neighbor = temp_id;
+ neighbors[cur_pos]->cost = temp_rand;
+ max_nodes[cur_pos] =
+ GNUNET_CONTAINER_heap_insert (maxHeap, neighbors[cur_pos],
+ temp_rand);
+ min_nodes[cur_pos] =
+ GNUNET_CONTAINER_heap_insert (minHeap, neighbors[cur_pos],
+ temp_rand);
+ cur_pos++;
+ break;
+
+ case 2:
+ temp_node = GNUNET_random_u32 (GNUNET_RANDOM_QUALITY_WEAK, cur_pos);
+ temp_rand = GNUNET_random_u32 (GNUNET_RANDOM_QUALITY_WEAK, 100) + 1;
+#if DEBUG
+ fprintf (stderr, "Updating node %d (cost %d) with new cost %d\n",
+ temp_node + 1, neighbors[temp_node]->cost, temp_rand);
+#endif
+ GNUNET_CONTAINER_heap_update_cost (maxHeap, max_nodes[temp_node],
+ temp_rand);
+ GNUNET_CONTAINER_heap_update_cost (minHeap, min_nodes[temp_node],
+ temp_rand);
+ neighbors[temp_node]->cost = temp_rand;
+ break;
+ case 3:
+#if DEBUG
+ fprintf (stderr, "Removing node %d with cost %d\n", cur_pos,
+ neighbors[cur_pos - 1]->cost);
+#endif
+ GNUNET_CONTAINER_heap_remove_node (maxHeap, max_nodes[cur_pos - 1]);
+ GNUNET_CONTAINER_heap_remove_node (minHeap, min_nodes[cur_pos - 1]);
+ GNUNET_free (neighbors[cur_pos - 1]);
+ neighbors[cur_pos - 1] = NULL;
+ cur_pos--;
+ break;
+ case 4:
+ break;
+ }
+
+ if (ret != GNUNET_OK)
+ return GNUNET_SYSERR;
+
+ }
+ while (GNUNET_CONTAINER_heap_get_size (maxHeap) > 0)
+ {
+ GNUNET_CONTAINER_heap_remove_root (maxHeap);
+ }
+
+ while (GNUNET_CONTAINER_heap_get_size (minHeap) > 0)
+ {
+ GNUNET_CONTAINER_heap_remove_root (minHeap);
+ }
+
+ GNUNET_CONTAINER_heap_destroy (maxHeap);
+ GNUNET_CONTAINER_heap_destroy (minHeap);
return 0;
}
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNUnet-SVN] r9888 - GNUnet/src/util/containers,
gnunet <=