diff options
-rw-r--r-- | src/util/Makefile.am | 6 | ||||
-rw-r--r-- | src/util/container_heap.c | 51 | ||||
-rw-r--r-- | src/util/test_container_heap.c | 92 |
3 files changed, 59 insertions, 90 deletions
diff --git a/src/util/Makefile.am b/src/util/Makefile.am index c0e64b3f4..240c86247 100644 --- a/src/util/Makefile.am +++ b/src/util/Makefile.am | |||
@@ -84,6 +84,7 @@ check_PROGRAMS = \ | |||
84 | test_container_bloomfilter \ | 84 | test_container_bloomfilter \ |
85 | test_container_meta_data \ | 85 | test_container_meta_data \ |
86 | test_container_multihashmap \ | 86 | test_container_multihashmap \ |
87 | test_container_heap \ | ||
87 | test_crypto_aes \ | 88 | test_crypto_aes \ |
88 | test_crypto_aes_weak \ | 89 | test_crypto_aes_weak \ |
89 | test_crypto_crc \ | 90 | test_crypto_crc \ |
@@ -156,6 +157,11 @@ test_container_multihashmap_SOURCES = \ | |||
156 | test_container_multihashmap.c | 157 | test_container_multihashmap.c |
157 | test_container_multihashmap_LDADD = \ | 158 | test_container_multihashmap_LDADD = \ |
158 | $(top_builddir)/src/util/libgnunetutil.la | 159 | $(top_builddir)/src/util/libgnunetutil.la |
160 | |||
161 | test_container_heap_SOURCES = \ | ||
162 | test_container_heap.c | ||
163 | test_container_heap_LDADD = \ | ||
164 | $(top_builddir)/src/util/libgnunetutil.la | ||
159 | 165 | ||
160 | test_crypto_aes_SOURCES = \ | 166 | test_crypto_aes_SOURCES = \ |
161 | test_crypto_aes.c | 167 | test_crypto_aes.c |
diff --git a/src/util/container_heap.c b/src/util/container_heap.c index c420a0ae4..c7afd6f71 100644 --- a/src/util/container_heap.c +++ b/src/util/container_heap.c | |||
@@ -81,7 +81,10 @@ struct GNUNET_CONTAINER_Heap | |||
81 | */ | 81 | */ |
82 | void *GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_Heap *heap) | 82 | void *GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_Heap *heap) |
83 | { | 83 | { |
84 | return heap->root; | 84 | if ((heap == NULL) || (heap->root == NULL)) |
85 | return NULL; | ||
86 | |||
87 | return heap->root->element; | ||
85 | } | 88 | } |
86 | 89 | ||
87 | 90 | ||
@@ -135,20 +138,17 @@ find_element (struct GNUNET_CONTAINER_heap_node *node, void *element) | |||
135 | { | 138 | { |
136 | struct GNUNET_CONTAINER_heap_node *ret; | 139 | struct GNUNET_CONTAINER_heap_node *ret; |
137 | ret = NULL; | 140 | ret = NULL; |
138 | if ((node != NULL) && (node->element == element)) | 141 | if (node == NULL) |
139 | { | 142 | return NULL; |
140 | ret = node; | ||
141 | } | ||
142 | 143 | ||
143 | if ((ret == NULL) && (node->left_child != NULL)) | 144 | if (node->element == element) |
144 | { | 145 | return node; |
145 | ret = find_element (node->left_child, element); | ||
146 | } | ||
147 | 146 | ||
148 | if ((ret == NULL) && (node->right_child != NULL)) | 147 | if (node->left_child != NULL) |
149 | { | 148 | ret = find_element (node->left_child, element); |
150 | ret = find_element (node->right_child, element); | 149 | |
151 | } | 150 | if (node->right_child != NULL) |
151 | ret = find_element (node->right_child, element); | ||
152 | 152 | ||
153 | return ret; | 153 | return ret; |
154 | } | 154 | } |
@@ -241,21 +241,6 @@ swapNodes (struct GNUNET_CONTAINER_heap_node *first, | |||
241 | second->element = temp_element; | 241 | second->element = temp_element; |
242 | second->cost = temp_cost; | 242 | second->cost = temp_cost; |
243 | 243 | ||
244 | /* | ||
245 | * I still worry that there is some good reason for | ||
246 | * elements being location aware... but it eludes me | ||
247 | * for the moment... | ||
248 | if ((root->type == GNUNET_DV_MAX_HEAP)) | ||
249 | { | ||
250 | first->neighbor->max_loc = first; | ||
251 | second->neighbor->max_loc = second; | ||
252 | } | ||
253 | else if ((root->type == GNUNET_DV_MIN_HEAP)) | ||
254 | { | ||
255 | first->neighbor->min_loc = first; | ||
256 | second->neighbor->min_loc = second; | ||
257 | } | ||
258 | */ | ||
259 | return; | 244 | return; |
260 | } | 245 | } |
261 | 246 | ||
@@ -393,11 +378,6 @@ GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *root, | |||
393 | new_pos->element = element; | 378 | new_pos->element = element; |
394 | new_pos->cost = cost; | 379 | new_pos->cost = cost; |
395 | root->size++; | 380 | root->size++; |
396 | /*We no longer can tolerate pointers between heaps :( */ | ||
397 | /*if (root->type == GNUNET_DV_MIN_HEAP) | ||
398 | new_pos->neighbor->min_loc = new_pos; | ||
399 | else if (root->type == GNUNET_DV_MAX_HEAP) | ||
400 | new_pos->neighbor->max_loc = new_pos; */ | ||
401 | 381 | ||
402 | percolateHeap (new_pos, root); | 382 | percolateHeap (new_pos, root); |
403 | } | 383 | } |
@@ -416,11 +396,14 @@ GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *root) | |||
416 | struct GNUNET_CONTAINER_heap_node *root_node; | 396 | struct GNUNET_CONTAINER_heap_node *root_node; |
417 | struct GNUNET_CONTAINER_heap_node *last; | 397 | struct GNUNET_CONTAINER_heap_node *last; |
418 | 398 | ||
399 | if ((root == NULL) || (root->size == 0) || (root->root == NULL)) | ||
400 | return NULL; | ||
401 | |||
419 | root_node = root->root; | 402 | root_node = root->root; |
420 | ret = root_node->element; | 403 | ret = root_node->element; |
421 | last = getPos (root, root->size); | 404 | last = getPos (root, root->size); |
422 | 405 | ||
423 | if ((root_node == last) && (root->size == 1)) | 406 | if ((root_node == last) && (root->size == 1)) |
424 | { | 407 | { |
425 | /* We are removing the last node in the heap! */ | 408 | /* We are removing the last node in the heap! */ |
426 | root->root = NULL; | 409 | root->root = NULL; |
diff --git a/src/util/test_container_heap.c b/src/util/test_container_heap.c index 84f992686..9e6a29ea4 100644 --- a/src/util/test_container_heap.c +++ b/src/util/test_container_heap.c | |||
@@ -20,94 +20,74 @@ | |||
20 | 20 | ||
21 | /** | 21 | /** |
22 | * @author Nathan Evans | 22 | * @author Nathan Evans |
23 | * @file util/containers/heaptest.c | 23 | * @file util/test_container_heap.c |
24 | * @brief Test of heap operations | 24 | * @brief Test of heap operations |
25 | */ | 25 | */ |
26 | 26 | ||
27 | #include "gnunet_util.h" | 27 | #include "platform.h" |
28 | #include "gnunet_util_containers.h" | 28 | #include "gnunet_common.h" |
29 | #include "dv.h" | 29 | #include "gnunet_container_lib.h" |
30 | |||
31 | struct TestItem | ||
32 | { | ||
33 | unsigned int cost; | ||
34 | }; | ||
30 | 35 | ||
31 | static int | 36 | static int |
32 | iterator_callback (void *element, GNUNET_CONTAINER_HeapCost cost, | 37 | iterator_callback (void *cls, void *element, GNUNET_CONTAINER_HeapCost cost) |
33 | struct GNUNET_CONTAINER_Heap *root, void *cls) | ||
34 | { | 38 | { |
35 | struct GNUNET_dv_neighbor *node; | 39 | struct TestItem *node; |
36 | node = (struct GNUNET_dv_neighbor *) element; | 40 | node = (struct TestItem *) element; |
41 | #ifdef VERBOSE | ||
37 | fprintf (stdout, "%d\n", node->cost); | 42 | fprintf (stdout, "%d\n", node->cost); |
38 | //fprintf (stdout, "%d\n", ((struct GNUNET_dv_neighbor *)element)->cost); | 43 | #endif |
39 | 44 | ||
40 | return GNUNET_OK; | 45 | return GNUNET_OK; |
41 | } | 46 | } |
42 | 47 | ||
43 | |||
44 | int | 48 | int |
45 | main (int argc, char **argv) | 49 | main (int argc, char **argv) |
46 | { | 50 | { |
47 | struct GNUNET_CONTAINER_Heap *myHeap; | 51 | struct GNUNET_CONTAINER_Heap *myHeap; |
48 | struct GNUNET_dv_neighbor *neighbor1; | 52 | struct TestItem neighbor1; |
49 | struct GNUNET_dv_neighbor *neighbor2; | 53 | struct TestItem neighbor2; |
50 | struct GNUNET_dv_neighbor *neighbor3; | 54 | struct TestItem neighbor3; |
51 | struct GNUNET_dv_neighbor *neighbor4; | 55 | struct TestItem neighbor4; |
52 | struct GNUNET_dv_neighbor *neighbor5; | 56 | struct TestItem neighbor5; |
53 | struct GNUNET_dv_neighbor *neighbor6; | 57 | struct TestItem neighbor6; |
54 | 58 | ||
55 | GNUNET_log_setup ("test-container-heap", "WARNING", NULL); | 59 | GNUNET_log_setup ("test-container-heap", "WARNING", NULL); |
56 | 60 | ||
57 | myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MAX); | 61 | myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MAX); |
58 | 62 | ||
59 | neighbor1 = malloc (sizeof (struct GNUNET_dv_neighbor)); | 63 | neighbor1.cost = 60; |
60 | neighbor2 = malloc (sizeof (struct GNUNET_dv_neighbor)); | 64 | neighbor2.cost = 50; |
61 | neighbor3 = malloc (sizeof (struct GNUNET_dv_neighbor)); | 65 | neighbor3.cost = 70; |
62 | neighbor4 = malloc (sizeof (struct GNUNET_dv_neighbor)); | 66 | neighbor4.cost = 120; |
63 | neighbor5 = malloc (sizeof (struct GNUNET_dv_neighbor)); | 67 | neighbor5.cost = 100; |
64 | neighbor6 = malloc (sizeof (struct GNUNET_dv_neighbor)); | 68 | neighbor6.cost = 30; |
65 | |||
66 | neighbor1->cost = 60; | ||
67 | neighbor2->cost = 50; | ||
68 | neighbor3->cost = 70; | ||
69 | neighbor4->cost = 120; | ||
70 | neighbor5->cost = 100; | ||
71 | neighbor6->cost = 30; | ||
72 | 69 | ||
73 | GNUNET_CONTAINER_heap_insert (myHeap, neighbor1, neighbor1->cost); | 70 | GNUNET_CONTAINER_heap_insert (myHeap, &neighbor1, neighbor1.cost); |
74 | GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL); | 71 | GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL); |
75 | 72 | GNUNET_CONTAINER_heap_insert (myHeap, &neighbor2, neighbor2.cost); | |
76 | fprintf (stdout, "\n"); | ||
77 | GNUNET_CONTAINER_heap_insert (myHeap, neighbor2, neighbor2->cost); | ||
78 | |||
79 | GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL); | 73 | GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL); |
80 | fprintf (stdout, "\n"); | 74 | GNUNET_CONTAINER_heap_insert (myHeap, &neighbor3, neighbor3.cost); |
81 | GNUNET_CONTAINER_heap_insert (myHeap, neighbor3, neighbor3->cost); | ||
82 | |||
83 | GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL); | 75 | GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL); |
84 | fprintf (stdout, "\n"); | 76 | GNUNET_CONTAINER_heap_insert (myHeap, &neighbor4, neighbor4.cost); |
85 | GNUNET_CONTAINER_heap_insert (myHeap, neighbor4, neighbor4->cost); | ||
86 | |||
87 | GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL); | 77 | GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL); |
88 | fprintf (stdout, "\n"); | 78 | GNUNET_CONTAINER_heap_insert (myHeap, &neighbor5, neighbor5.cost); |
89 | GNUNET_CONTAINER_heap_insert (myHeap, neighbor5, neighbor5->cost); | ||
90 | |||
91 | GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL); | 79 | GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL); |
92 | fprintf (stdout, "\n"); | 80 | GNUNET_CONTAINER_heap_insert (myHeap, &neighbor6, neighbor6.cost); |
93 | GNUNET_CONTAINER_heap_insert (myHeap, neighbor6, neighbor6->cost); | ||
94 | |||
95 | GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL); | 81 | GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL); |
96 | fprintf (stdout, "\n"); | 82 | GNUNET_CONTAINER_heap_remove_node (myHeap, &neighbor5); |
97 | GNUNET_CONTAINER_heap_remove_node (myHeap, neighbor5); | ||
98 | |||
99 | GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL); | 83 | GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL); |
100 | fprintf (stdout, "\n"); | ||
101 | GNUNET_CONTAINER_heap_remove_root (myHeap); | 84 | GNUNET_CONTAINER_heap_remove_root (myHeap); |
102 | |||
103 | GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL); | 85 | GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL); |
104 | fprintf (stdout, "\n"); | 86 | GNUNET_CONTAINER_heap_update_cost (myHeap, &neighbor6, 200); |
105 | GNUNET_CONTAINER_heap_update_cost (myHeap, neighbor6, 200); | ||
106 | |||
107 | GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL); | 87 | GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL); |
108 | fprintf (stdout, "\n"); | ||
109 | GNUNET_CONTAINER_heap_destroy (myHeap); | 88 | GNUNET_CONTAINER_heap_destroy (myHeap); |
89 | |||
110 | return 0; | 90 | return 0; |
111 | } | 91 | } |
112 | 92 | ||
113 | /* end of heaptest.c */ | 93 | /* end of test_container_heap.c */ |