diff options
Diffstat (limited to 'src/lib/util/test_container_heap.c')
-rw-r--r-- | src/lib/util/test_container_heap.c | 294 |
1 files changed, 294 insertions, 0 deletions
diff --git a/src/lib/util/test_container_heap.c b/src/lib/util/test_container_heap.c new file mode 100644 index 000000000..f11070ed5 --- /dev/null +++ b/src/lib/util/test_container_heap.c | |||
@@ -0,0 +1,294 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet. | ||
3 | Copyright (C) 2008 GNUnet e.V. | ||
4 | |||
5 | GNUnet is free software: you can redistribute it and/or modify it | ||
6 | under the terms of the GNU Affero General Public License as published | ||
7 | by the Free Software Foundation, either version 3 of the License, | ||
8 | or (at your option) any later version. | ||
9 | |||
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 | Affero General Public License for more details. | ||
14 | |||
15 | You should have received a copy of the GNU Affero General Public License | ||
16 | along with this program. If not, see <http://www.gnu.org/licenses/>. | ||
17 | |||
18 | SPDX-License-Identifier: AGPL3.0-or-later | ||
19 | */ | ||
20 | |||
21 | /** | ||
22 | * @author Nathan Evans | ||
23 | * @file util/test_container_heap.c | ||
24 | * @brief Test of heap operations | ||
25 | */ | ||
26 | |||
27 | |||
28 | #include "platform.h" | ||
29 | #include "gnunet_util_lib.h" | ||
30 | |||
31 | static int | ||
32 | iterator_callback (void *cls, | ||
33 | struct GNUNET_CONTAINER_HeapNode *node, | ||
34 | void *element, GNUNET_CONTAINER_HeapCostType cost) | ||
35 | { | ||
36 | return GNUNET_OK; | ||
37 | } | ||
38 | |||
39 | |||
40 | static int | ||
41 | nstrcmp (const char *a, const char *b) | ||
42 | { | ||
43 | GNUNET_assert (a != NULL); | ||
44 | GNUNET_assert (b != NULL); | ||
45 | return strcmp (a, b); | ||
46 | } | ||
47 | |||
48 | |||
49 | static int | ||
50 | check () | ||
51 | { | ||
52 | struct GNUNET_CONTAINER_Heap *myHeap; | ||
53 | struct GNUNET_CONTAINER_HeapNode *n1; | ||
54 | struct GNUNET_CONTAINER_HeapNode *n2; | ||
55 | struct GNUNET_CONTAINER_HeapNode *n3; | ||
56 | struct GNUNET_CONTAINER_HeapNode *n4; | ||
57 | struct GNUNET_CONTAINER_HeapNode *n5; | ||
58 | struct GNUNET_CONTAINER_HeapNode *n6; | ||
59 | struct GNUNET_CONTAINER_HeapNode *n7; | ||
60 | struct GNUNET_CONTAINER_HeapNode *n8; | ||
61 | const char *r; | ||
62 | |||
63 | myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN); | ||
64 | |||
65 | // GNUNET_CONTAINER_heap_remove_root heap empty, taking if-branch | ||
66 | n1 = GNUNET_CONTAINER_heap_remove_root (myHeap); | ||
67 | GNUNET_assert (NULL == n1); | ||
68 | |||
69 | // GNUNET_CONTAINER_heap_peek heap empty, taking if-branch | ||
70 | n1 = GNUNET_CONTAINER_heap_peek (myHeap); | ||
71 | GNUNET_assert (NULL == n1); | ||
72 | |||
73 | // GNUNET_CONTAINER_heap_walk_get_next: heap empty, taking if-branch | ||
74 | n1 = GNUNET_CONTAINER_heap_walk_get_next (myHeap); | ||
75 | GNUNET_assert (NULL == n1); | ||
76 | |||
77 | n1 = GNUNET_CONTAINER_heap_insert (myHeap, "11", 11); | ||
78 | GNUNET_assert (NULL != n1); | ||
79 | |||
80 | |||
81 | // GNUNET_CONTAINER_heap_peek not empty, taking if-branch | ||
82 | n2 = NULL; | ||
83 | n2 = GNUNET_CONTAINER_heap_peek (myHeap); | ||
84 | GNUNET_assert (NULL != n2); | ||
85 | |||
86 | // GNUNET_CONTAINER_heap_walk_get_next: 1 element | ||
87 | n1 = NULL; | ||
88 | n1 = GNUNET_CONTAINER_heap_walk_get_next (myHeap); | ||
89 | GNUNET_assert (NULL != n1); | ||
90 | |||
91 | GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL); | ||
92 | GNUNET_assert (1 == GNUNET_CONTAINER_heap_get_size (myHeap)); | ||
93 | n2 = GNUNET_CONTAINER_heap_insert (myHeap, "78", 78); | ||
94 | GNUNET_assert (2 == GNUNET_CONTAINER_heap_get_size (myHeap)); | ||
95 | GNUNET_assert (0 == strcmp ("78", GNUNET_CONTAINER_heap_remove_node (n2))); | ||
96 | GNUNET_assert (1 == GNUNET_CONTAINER_heap_get_size (myHeap)); | ||
97 | GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL); | ||
98 | |||
99 | n3 = GNUNET_CONTAINER_heap_insert (myHeap, "15", 5); | ||
100 | GNUNET_CONTAINER_heap_update_cost (n3, 15); | ||
101 | GNUNET_assert (2 == GNUNET_CONTAINER_heap_get_size (myHeap)); | ||
102 | GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL); | ||
103 | |||
104 | n4 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50); | ||
105 | GNUNET_CONTAINER_heap_update_cost (n4, 50); | ||
106 | GNUNET_assert (3 == GNUNET_CONTAINER_heap_get_size (myHeap)); | ||
107 | GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL); | ||
108 | |||
109 | n5 = GNUNET_CONTAINER_heap_insert (myHeap, "100", 100); | ||
110 | n6 = GNUNET_CONTAINER_heap_insert (myHeap, "30/200", 30); | ||
111 | GNUNET_assert (5 == GNUNET_CONTAINER_heap_get_size (myHeap)); | ||
112 | GNUNET_CONTAINER_heap_remove_node (n5); | ||
113 | r = GNUNET_CONTAINER_heap_remove_root (myHeap); /* n1 */ | ||
114 | GNUNET_assert (NULL != r); | ||
115 | GNUNET_assert (0 == strcmp ("11", r)); | ||
116 | GNUNET_CONTAINER_heap_update_cost (n6, 200); | ||
117 | GNUNET_CONTAINER_heap_remove_node (n3); | ||
118 | r = GNUNET_CONTAINER_heap_remove_root (myHeap); /* n4 */ | ||
119 | GNUNET_assert (NULL != r); | ||
120 | GNUNET_assert (0 == strcmp ("50", r)); | ||
121 | r = GNUNET_CONTAINER_heap_remove_root (myHeap); /* n6 */ | ||
122 | GNUNET_assert (NULL != r); | ||
123 | GNUNET_assert (0 == strcmp ("30/200", r)); | ||
124 | GNUNET_assert (0 == GNUNET_CONTAINER_heap_get_size (myHeap)); | ||
125 | |||
126 | GNUNET_CONTAINER_heap_destroy (myHeap); | ||
127 | |||
128 | // My additions to a complete testcase | ||
129 | // Testing a GNUNET_CONTAINER_HEAP_ORDER_MIN | ||
130 | // Testing remove_node | ||
131 | |||
132 | myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN); | ||
133 | |||
134 | n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10); | ||
135 | GNUNET_CONTAINER_heap_update_cost (n1, 15); | ||
136 | |||
137 | r = GNUNET_CONTAINER_heap_remove_node (n1); | ||
138 | GNUNET_assert (NULL != r); | ||
139 | GNUNET_assert (0 == strcmp ("10", r)); | ||
140 | |||
141 | n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10); | ||
142 | n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10); | ||
143 | |||
144 | GNUNET_CONTAINER_heap_walk_get_next (myHeap); | ||
145 | r = GNUNET_CONTAINER_heap_remove_node (n2); | ||
146 | GNUNET_assert (NULL != r); | ||
147 | GNUNET_assert (0 == strcmp ("20", r)); | ||
148 | r = GNUNET_CONTAINER_heap_remove_node (n1); | ||
149 | GNUNET_assert (NULL != r); | ||
150 | GNUNET_assert (0 == strcmp ("10", r)); | ||
151 | |||
152 | n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10); | ||
153 | n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10); | ||
154 | n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10); | ||
155 | |||
156 | GNUNET_CONTAINER_heap_remove_node (n2); | ||
157 | GNUNET_CONTAINER_heap_remove_node (n1); | ||
158 | r = GNUNET_CONTAINER_heap_remove_root (myHeap); | ||
159 | GNUNET_assert (NULL != r); | ||
160 | GNUNET_assert (0 == strcmp ("30", r)); | ||
161 | |||
162 | n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10); | ||
163 | n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10); | ||
164 | n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10); | ||
165 | |||
166 | GNUNET_CONTAINER_heap_remove_node (n2); | ||
167 | GNUNET_CONTAINER_heap_remove_node (n1); | ||
168 | r = GNUNET_CONTAINER_heap_remove_node (n3); | ||
169 | GNUNET_assert (NULL != r); | ||
170 | GNUNET_assert (0 == strcmp ("30", r)); | ||
171 | |||
172 | n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10); | ||
173 | n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20); | ||
174 | n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30); | ||
175 | |||
176 | GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2))); | ||
177 | GNUNET_assert (0 == | ||
178 | nstrcmp ("10", GNUNET_CONTAINER_heap_remove_root (myHeap))); | ||
179 | GNUNET_assert (0 == | ||
180 | nstrcmp ("30", GNUNET_CONTAINER_heap_remove_root (myHeap))); | ||
181 | |||
182 | n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10); | ||
183 | n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20); | ||
184 | n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30); | ||
185 | n4 = GNUNET_CONTAINER_heap_insert (myHeap, "40", 40); | ||
186 | n5 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50); | ||
187 | n6 = GNUNET_CONTAINER_heap_insert (myHeap, "60", 60); | ||
188 | |||
189 | // Inserting nodes deeper in the tree with lower costs | ||
190 | n7 = GNUNET_CONTAINER_heap_insert (myHeap, "70", 10); | ||
191 | n8 = GNUNET_CONTAINER_heap_insert (myHeap, "80", 10); | ||
192 | |||
193 | GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_node (n3))); | ||
194 | |||
195 | // Cleaning up... | ||
196 | GNUNET_assert (0 == nstrcmp ("60", GNUNET_CONTAINER_heap_remove_node (n6))); | ||
197 | GNUNET_assert (0 == nstrcmp ("50", GNUNET_CONTAINER_heap_remove_node (n5))); | ||
198 | |||
199 | // Testing heap_walk_get_next | ||
200 | GNUNET_CONTAINER_heap_walk_get_next (myHeap); | ||
201 | GNUNET_CONTAINER_heap_walk_get_next (myHeap); | ||
202 | GNUNET_CONTAINER_heap_walk_get_next (myHeap);; | ||
203 | GNUNET_CONTAINER_heap_walk_get_next (myHeap); | ||
204 | GNUNET_CONTAINER_heap_walk_get_next (myHeap); | ||
205 | |||
206 | GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1))); | ||
207 | GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2))); | ||
208 | GNUNET_assert (0 == nstrcmp ("40", GNUNET_CONTAINER_heap_remove_node (n4))); | ||
209 | GNUNET_assert (0 == nstrcmp ("70", GNUNET_CONTAINER_heap_remove_node (n7))); | ||
210 | GNUNET_assert (0 == nstrcmp ("80", GNUNET_CONTAINER_heap_remove_node (n8))); | ||
211 | |||
212 | // End Testing remove_node | ||
213 | |||
214 | // Testing a GNUNET_CONTAINER_HEAP_ORDER_MAX | ||
215 | GNUNET_CONTAINER_heap_destroy (myHeap); | ||
216 | |||
217 | myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MAX); | ||
218 | |||
219 | n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10); | ||
220 | GNUNET_CONTAINER_heap_update_cost (n1, 15); | ||
221 | |||
222 | GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1))); | ||
223 | |||
224 | n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10); | ||
225 | n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10); | ||
226 | |||
227 | GNUNET_CONTAINER_heap_walk_get_next (myHeap); | ||
228 | GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2))); | ||
229 | GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1))); | ||
230 | |||
231 | n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10); | ||
232 | n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10); | ||
233 | n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10); | ||
234 | |||
235 | GNUNET_CONTAINER_heap_remove_node (n2); | ||
236 | GNUNET_CONTAINER_heap_remove_node (n1); | ||
237 | GNUNET_assert (0 == | ||
238 | nstrcmp ("30", GNUNET_CONTAINER_heap_remove_root (myHeap))); | ||
239 | |||
240 | n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10); | ||
241 | n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10); | ||
242 | n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10); | ||
243 | |||
244 | GNUNET_CONTAINER_heap_remove_node (n2); | ||
245 | GNUNET_CONTAINER_heap_remove_node (n1); | ||
246 | GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_node (n3))); | ||
247 | |||
248 | n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10); | ||
249 | n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20); | ||
250 | n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30); | ||
251 | n4 = GNUNET_CONTAINER_heap_insert (myHeap, "40", 40); | ||
252 | n5 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50); | ||
253 | n6 = GNUNET_CONTAINER_heap_insert (myHeap, "60", 60); | ||
254 | |||
255 | // Inserting nodes deeper in the tree with lower costs | ||
256 | n7 = GNUNET_CONTAINER_heap_insert (myHeap, "70", 10); | ||
257 | n8 = GNUNET_CONTAINER_heap_insert (myHeap, "80", 10); | ||
258 | |||
259 | GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_node (n3))); | ||
260 | |||
261 | // Cleaning up... | ||
262 | GNUNET_assert (0 == nstrcmp ("60", GNUNET_CONTAINER_heap_remove_node (n6))); | ||
263 | GNUNET_assert (0 == nstrcmp ("50", GNUNET_CONTAINER_heap_remove_node (n5))); | ||
264 | |||
265 | // Testing heap_walk_get_next | ||
266 | GNUNET_CONTAINER_heap_walk_get_next (myHeap); | ||
267 | GNUNET_CONTAINER_heap_walk_get_next (myHeap); | ||
268 | GNUNET_CONTAINER_heap_walk_get_next (myHeap);; | ||
269 | GNUNET_CONTAINER_heap_walk_get_next (myHeap); | ||
270 | GNUNET_CONTAINER_heap_walk_get_next (myHeap); | ||
271 | |||
272 | GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1))); | ||
273 | GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2))); | ||
274 | GNUNET_assert (0 == nstrcmp ("40", GNUNET_CONTAINER_heap_remove_node (n4))); | ||
275 | GNUNET_assert (0 == nstrcmp ("70", GNUNET_CONTAINER_heap_remove_node (n7))); | ||
276 | GNUNET_assert (0 == nstrcmp ("80", GNUNET_CONTAINER_heap_remove_node (n8))); | ||
277 | |||
278 | // End Testing remove_node | ||
279 | |||
280 | GNUNET_CONTAINER_heap_destroy (myHeap); | ||
281 | |||
282 | return 0; | ||
283 | } | ||
284 | |||
285 | |||
286 | int | ||
287 | main (int argc, char **argv) | ||
288 | { | ||
289 | GNUNET_log_setup ("test-container-heap", "WARNING", NULL); | ||
290 | return check (); | ||
291 | } | ||
292 | |||
293 | |||
294 | /* end of test_container_heap.c */ | ||