aboutsummaryrefslogtreecommitdiff
path: root/src/lib/util/test_container_heap.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/util/test_container_heap.c')
-rw-r--r--src/lib/util/test_container_heap.c294
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
31static int
32iterator_callback (void *cls,
33 struct GNUNET_CONTAINER_HeapNode *node,
34 void *element, GNUNET_CONTAINER_HeapCostType cost)
35{
36 return GNUNET_OK;
37}
38
39
40static int
41nstrcmp (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
49static int
50check ()
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
286int
287main (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 */
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-07 22:42:46 +0000