2 This file is part of GNUnet.
3 (C) 2008 Christian Grothoff (and other contributing authors)
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 option) any later version.
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
22 * @author Nathan Evans
23 * @file util/test_container_heap.c
24 * @brief Test of heap operations
28 #include "gnunet_common.h"
29 #include "gnunet_container_lib.h"
32 iterator_callback (void *cls,
33 struct GNUNET_CONTAINER_HeapNode *node,
34 void *element, GNUNET_CONTAINER_HeapCostType cost)
40 nstrcmp (const char *a, const char *b)
42 GNUNET_assert (a != NULL);
43 GNUNET_assert (b != NULL);
50 struct GNUNET_CONTAINER_Heap *myHeap;
51 struct GNUNET_CONTAINER_HeapNode *n1;
52 struct GNUNET_CONTAINER_HeapNode *n2;
53 struct GNUNET_CONTAINER_HeapNode *n3;
54 struct GNUNET_CONTAINER_HeapNode *n4;
55 struct GNUNET_CONTAINER_HeapNode *n5;
56 struct GNUNET_CONTAINER_HeapNode *n6;
57 struct GNUNET_CONTAINER_HeapNode *n7;
58 struct GNUNET_CONTAINER_HeapNode *n8;
61 myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
63 // GNUNET_CONTAINER_heap_remove_root heap empty, taking if-branch
64 n1 = GNUNET_CONTAINER_heap_remove_root (myHeap);
65 GNUNET_assert (NULL == n1);
67 // GNUNET_CONTAINER_heap_peek heap empty, taking if-branch
68 n1 = GNUNET_CONTAINER_heap_peek (myHeap);
69 GNUNET_assert (NULL == n1);
71 // GNUNET_CONTAINER_heap_walk_get_next: heap empty, taking if-branch
72 n1 = GNUNET_CONTAINER_heap_walk_get_next (myHeap);
73 GNUNET_assert (NULL == n1);
75 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "11", 11);
76 GNUNET_assert (NULL != n1);
79 // GNUNET_CONTAINER_heap_peek not empty, taking if-branch
81 n2 = GNUNET_CONTAINER_heap_peek (myHeap);
82 GNUNET_assert (NULL != n2);
84 // GNUNET_CONTAINER_heap_walk_get_next: 1 element
86 n1 = GNUNET_CONTAINER_heap_walk_get_next (myHeap);
87 GNUNET_assert (NULL != n1);
89 GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
90 GNUNET_assert (1 == GNUNET_CONTAINER_heap_get_size (myHeap));
91 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "78", 78);
92 GNUNET_assert (2 == GNUNET_CONTAINER_heap_get_size (myHeap));
93 GNUNET_assert (0 == strcmp ("78", GNUNET_CONTAINER_heap_remove_node (n2)));
94 GNUNET_assert (1 == GNUNET_CONTAINER_heap_get_size (myHeap));
95 GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
97 n3 = GNUNET_CONTAINER_heap_insert (myHeap, "15", 5);
98 GNUNET_CONTAINER_heap_update_cost (myHeap, n3, 15);
99 GNUNET_assert (2 == GNUNET_CONTAINER_heap_get_size (myHeap));
100 GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
102 n4 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50);
103 GNUNET_CONTAINER_heap_update_cost (myHeap, n4, 50);
104 GNUNET_assert (3 == GNUNET_CONTAINER_heap_get_size (myHeap));
105 GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
107 n5 = GNUNET_CONTAINER_heap_insert (myHeap, "100", 100);
108 n6 = GNUNET_CONTAINER_heap_insert (myHeap, "30/200", 30);
109 GNUNET_assert (5 == GNUNET_CONTAINER_heap_get_size (myHeap));
110 GNUNET_CONTAINER_heap_remove_node (n5);
111 r = GNUNET_CONTAINER_heap_remove_root (myHeap); /* n1 */
112 GNUNET_assert (NULL != r);
113 GNUNET_assert (0 == strcmp ("11", r));
114 GNUNET_CONTAINER_heap_update_cost (myHeap, n6, 200);
115 GNUNET_CONTAINER_heap_remove_node (n3);
116 r = GNUNET_CONTAINER_heap_remove_root (myHeap); /* n4 */
117 GNUNET_assert (NULL != r);
118 GNUNET_assert (0 == strcmp ("50", r));
119 r = GNUNET_CONTAINER_heap_remove_root (myHeap); /* n6 */
120 GNUNET_assert (NULL != r);
121 GNUNET_assert (0 == strcmp ("30/200", r));
122 GNUNET_assert (0 == GNUNET_CONTAINER_heap_get_size (myHeap));
124 GNUNET_CONTAINER_heap_destroy (myHeap);
126 // My additions to a complete testcase
127 // Testing a GNUNET_CONTAINER_HEAP_ORDER_MIN
128 // Testing remove_node
130 myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
132 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
133 GNUNET_CONTAINER_heap_update_cost (myHeap, n1, 15);
135 r = GNUNET_CONTAINER_heap_remove_node (n1);
136 GNUNET_assert (NULL != r);
137 GNUNET_assert (0 == strcmp ("10", r));
139 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
140 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
142 GNUNET_CONTAINER_heap_walk_get_next (myHeap);
143 r = GNUNET_CONTAINER_heap_remove_node (n2);
144 GNUNET_assert (NULL != r);
145 GNUNET_assert (0 == strcmp ("20", r));
146 r = GNUNET_CONTAINER_heap_remove_node (n1);
147 GNUNET_assert (NULL != r);
148 GNUNET_assert (0 == strcmp ("10", r));
150 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
151 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
152 n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
154 GNUNET_CONTAINER_heap_remove_node (n2);
155 GNUNET_CONTAINER_heap_remove_node (n1);
156 r = GNUNET_CONTAINER_heap_remove_root (myHeap);
157 GNUNET_assert (NULL != r);
158 GNUNET_assert (0 == strcmp ("30", r));
160 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
161 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
162 n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
164 GNUNET_CONTAINER_heap_remove_node (n2);
165 GNUNET_CONTAINER_heap_remove_node (n1);
166 r = GNUNET_CONTAINER_heap_remove_node (n3);
167 GNUNET_assert (NULL != r);
168 GNUNET_assert (0 == strcmp ("30", r));
170 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
171 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20);
172 n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30);
174 GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2)));
176 nstrcmp ("10", GNUNET_CONTAINER_heap_remove_root (myHeap)));
178 nstrcmp ("30", GNUNET_CONTAINER_heap_remove_root (myHeap)));
180 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
181 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20);
182 n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30);
183 n4 = GNUNET_CONTAINER_heap_insert (myHeap, "40", 40);
184 n5 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50);
185 n6 = GNUNET_CONTAINER_heap_insert (myHeap, "60", 60);
187 // Inserting nodes deeper in the tree with lower costs
188 n7 = GNUNET_CONTAINER_heap_insert (myHeap, "70", 10);
189 n8 = GNUNET_CONTAINER_heap_insert (myHeap, "80", 10);
191 GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_node (n3)));
194 GNUNET_assert (0 == nstrcmp ("60", GNUNET_CONTAINER_heap_remove_node (n6)));
195 GNUNET_assert (0 == nstrcmp ("50", GNUNET_CONTAINER_heap_remove_node (n5)));
197 // Testing heap_walk_get_next
198 GNUNET_CONTAINER_heap_walk_get_next (myHeap);
199 GNUNET_CONTAINER_heap_walk_get_next (myHeap);
200 GNUNET_CONTAINER_heap_walk_get_next (myHeap);;
201 GNUNET_CONTAINER_heap_walk_get_next (myHeap);
202 GNUNET_CONTAINER_heap_walk_get_next (myHeap);
204 GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1)));
205 GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2)));
206 GNUNET_assert (0 == nstrcmp ("40", GNUNET_CONTAINER_heap_remove_node (n4)));
207 GNUNET_assert (0 == nstrcmp ("70", GNUNET_CONTAINER_heap_remove_node (n7)));
208 GNUNET_assert (0 == nstrcmp ("80", GNUNET_CONTAINER_heap_remove_node (n8)));
210 // End Testing remove_node
212 // Testing a GNUNET_CONTAINER_HEAP_ORDER_MAX
213 GNUNET_CONTAINER_heap_destroy (myHeap);
215 myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MAX);
217 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
218 GNUNET_CONTAINER_heap_update_cost (myHeap, n1, 15);
220 GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1)));
222 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
223 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
225 GNUNET_CONTAINER_heap_walk_get_next (myHeap);
226 GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2)));
227 GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1)));
229 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
230 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
231 n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
233 GNUNET_CONTAINER_heap_remove_node (n2);
234 GNUNET_CONTAINER_heap_remove_node (n1);
236 nstrcmp ("30", GNUNET_CONTAINER_heap_remove_root (myHeap)));
238 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
239 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
240 n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
242 GNUNET_CONTAINER_heap_remove_node (n2);
243 GNUNET_CONTAINER_heap_remove_node (n1);
244 GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_node (n3)));
246 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
247 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20);
248 n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30);
249 n4 = GNUNET_CONTAINER_heap_insert (myHeap, "40", 40);
250 n5 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50);
251 n6 = GNUNET_CONTAINER_heap_insert (myHeap, "60", 60);
253 // Inserting nodes deeper in the tree with lower costs
254 n7 = GNUNET_CONTAINER_heap_insert (myHeap, "70", 10);
255 n8 = GNUNET_CONTAINER_heap_insert (myHeap, "80", 10);
257 GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_node (n3)));
260 GNUNET_assert (0 == nstrcmp ("60", GNUNET_CONTAINER_heap_remove_node (n6)));
261 GNUNET_assert (0 == nstrcmp ("50", GNUNET_CONTAINER_heap_remove_node (n5)));
263 // Testing heap_walk_get_next
264 GNUNET_CONTAINER_heap_walk_get_next (myHeap);
265 GNUNET_CONTAINER_heap_walk_get_next (myHeap);
266 GNUNET_CONTAINER_heap_walk_get_next (myHeap);;
267 GNUNET_CONTAINER_heap_walk_get_next (myHeap);
268 GNUNET_CONTAINER_heap_walk_get_next (myHeap);
270 GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1)));
271 GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2)));
272 GNUNET_assert (0 == nstrcmp ("40", GNUNET_CONTAINER_heap_remove_node (n4)));
273 GNUNET_assert (0 == nstrcmp ("70", GNUNET_CONTAINER_heap_remove_node (n7)));
274 GNUNET_assert (0 == nstrcmp ("80", GNUNET_CONTAINER_heap_remove_node (n8)));
276 // End Testing remove_node
278 GNUNET_CONTAINER_heap_destroy (myHeap);
285 main (int argc, char **argv)
287 GNUNET_log_setup ("test-container-heap", "WARNING", NULL);
291 /* end of test_container_heap.c */