aboutsummaryrefslogtreecommitdiff
path: root/src/util/test_container_heap.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/util/test_container_heap.c')
-rw-r--r--src/util/test_container_heap.c293
1 files changed, 0 insertions, 293 deletions
diff --git a/src/util/test_container_heap.c b/src/util/test_container_heap.c
deleted file mode 100644
index c83c7810f..000000000
--- a/src/util/test_container_heap.c
+++ /dev/null
@@ -1,293 +0,0 @@
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#include "platform.h"
28#include "gnunet_util_lib.h"
29
30static int
31iterator_callback (void *cls,
32 struct GNUNET_CONTAINER_HeapNode *node,
33 void *element, GNUNET_CONTAINER_HeapCostType cost)
34{
35 return GNUNET_OK;
36}
37
38
39static int
40nstrcmp (const char *a, const char *b)
41{
42 GNUNET_assert (a != NULL);
43 GNUNET_assert (b != NULL);
44 return strcmp (a, b);
45}
46
47
48static int
49check ()
50{
51 struct GNUNET_CONTAINER_Heap *myHeap;
52 struct GNUNET_CONTAINER_HeapNode *n1;
53 struct GNUNET_CONTAINER_HeapNode *n2;
54 struct GNUNET_CONTAINER_HeapNode *n3;
55 struct GNUNET_CONTAINER_HeapNode *n4;
56 struct GNUNET_CONTAINER_HeapNode *n5;
57 struct GNUNET_CONTAINER_HeapNode *n6;
58 struct GNUNET_CONTAINER_HeapNode *n7;
59 struct GNUNET_CONTAINER_HeapNode *n8;
60 const char *r;
61
62 myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
63
64 // GNUNET_CONTAINER_heap_remove_root heap empty, taking if-branch
65 n1 = GNUNET_CONTAINER_heap_remove_root (myHeap);
66 GNUNET_assert (NULL == n1);
67
68 // GNUNET_CONTAINER_heap_peek heap empty, taking if-branch
69 n1 = GNUNET_CONTAINER_heap_peek (myHeap);
70 GNUNET_assert (NULL == n1);
71
72 // GNUNET_CONTAINER_heap_walk_get_next: heap empty, taking if-branch
73 n1 = GNUNET_CONTAINER_heap_walk_get_next (myHeap);
74 GNUNET_assert (NULL == n1);
75
76 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "11", 11);
77 GNUNET_assert (NULL != n1);
78
79
80 // GNUNET_CONTAINER_heap_peek not empty, taking if-branch
81 n2 = NULL;
82 n2 = GNUNET_CONTAINER_heap_peek (myHeap);
83 GNUNET_assert (NULL != n2);
84
85 // GNUNET_CONTAINER_heap_walk_get_next: 1 element
86 n1 = NULL;
87 n1 = GNUNET_CONTAINER_heap_walk_get_next (myHeap);
88 GNUNET_assert (NULL != n1);
89
90 GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
91 GNUNET_assert (1 == GNUNET_CONTAINER_heap_get_size (myHeap));
92 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "78", 78);
93 GNUNET_assert (2 == GNUNET_CONTAINER_heap_get_size (myHeap));
94 GNUNET_assert (0 == strcmp ("78", GNUNET_CONTAINER_heap_remove_node (n2)));
95 GNUNET_assert (1 == GNUNET_CONTAINER_heap_get_size (myHeap));
96 GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
97
98 n3 = GNUNET_CONTAINER_heap_insert (myHeap, "15", 5);
99 GNUNET_CONTAINER_heap_update_cost (n3, 15);
100 GNUNET_assert (2 == GNUNET_CONTAINER_heap_get_size (myHeap));
101 GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
102
103 n4 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50);
104 GNUNET_CONTAINER_heap_update_cost (n4, 50);
105 GNUNET_assert (3 == GNUNET_CONTAINER_heap_get_size (myHeap));
106 GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
107
108 n5 = GNUNET_CONTAINER_heap_insert (myHeap, "100", 100);
109 n6 = GNUNET_CONTAINER_heap_insert (myHeap, "30/200", 30);
110 GNUNET_assert (5 == GNUNET_CONTAINER_heap_get_size (myHeap));
111 GNUNET_CONTAINER_heap_remove_node (n5);
112 r = GNUNET_CONTAINER_heap_remove_root (myHeap); /* n1 */
113 GNUNET_assert (NULL != r);
114 GNUNET_assert (0 == strcmp ("11", r));
115 GNUNET_CONTAINER_heap_update_cost (n6, 200);
116 GNUNET_CONTAINER_heap_remove_node (n3);
117 r = GNUNET_CONTAINER_heap_remove_root (myHeap); /* n4 */
118 GNUNET_assert (NULL != r);
119 GNUNET_assert (0 == strcmp ("50", r));
120 r = GNUNET_CONTAINER_heap_remove_root (myHeap); /* n6 */
121 GNUNET_assert (NULL != r);
122 GNUNET_assert (0 == strcmp ("30/200", r));
123 GNUNET_assert (0 == GNUNET_CONTAINER_heap_get_size (myHeap));
124
125 GNUNET_CONTAINER_heap_destroy (myHeap);
126
127 // My additions to a complete testcase
128 // Testing a GNUNET_CONTAINER_HEAP_ORDER_MIN
129 // Testing remove_node
130
131 myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
132
133 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
134 GNUNET_CONTAINER_heap_update_cost (n1, 15);
135
136 r = GNUNET_CONTAINER_heap_remove_node (n1);
137 GNUNET_assert (NULL != r);
138 GNUNET_assert (0 == strcmp ("10", r));
139
140 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
141 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
142
143 GNUNET_CONTAINER_heap_walk_get_next (myHeap);
144 r = GNUNET_CONTAINER_heap_remove_node (n2);
145 GNUNET_assert (NULL != r);
146 GNUNET_assert (0 == strcmp ("20", r));
147 r = GNUNET_CONTAINER_heap_remove_node (n1);
148 GNUNET_assert (NULL != r);
149 GNUNET_assert (0 == strcmp ("10", r));
150
151 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
152 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
153 n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
154
155 GNUNET_CONTAINER_heap_remove_node (n2);
156 GNUNET_CONTAINER_heap_remove_node (n1);
157 r = GNUNET_CONTAINER_heap_remove_root (myHeap);
158 GNUNET_assert (NULL != r);
159 GNUNET_assert (0 == strcmp ("30", r));
160
161 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
162 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
163 n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
164
165 GNUNET_CONTAINER_heap_remove_node (n2);
166 GNUNET_CONTAINER_heap_remove_node (n1);
167 r = GNUNET_CONTAINER_heap_remove_node (n3);
168 GNUNET_assert (NULL != r);
169 GNUNET_assert (0 == strcmp ("30", r));
170
171 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
172 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20);
173 n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30);
174
175 GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2)));
176 GNUNET_assert (0 ==
177 nstrcmp ("10", GNUNET_CONTAINER_heap_remove_root (myHeap)));
178 GNUNET_assert (0 ==
179 nstrcmp ("30", GNUNET_CONTAINER_heap_remove_root (myHeap)));
180
181 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
182 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20);
183 n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30);
184 n4 = GNUNET_CONTAINER_heap_insert (myHeap, "40", 40);
185 n5 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50);
186 n6 = GNUNET_CONTAINER_heap_insert (myHeap, "60", 60);
187
188 // Inserting nodes deeper in the tree with lower costs
189 n7 = GNUNET_CONTAINER_heap_insert (myHeap, "70", 10);
190 n8 = GNUNET_CONTAINER_heap_insert (myHeap, "80", 10);
191
192 GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_node (n3)));
193
194 // Cleaning up...
195 GNUNET_assert (0 == nstrcmp ("60", GNUNET_CONTAINER_heap_remove_node (n6)));
196 GNUNET_assert (0 == nstrcmp ("50", GNUNET_CONTAINER_heap_remove_node (n5)));
197
198 // Testing heap_walk_get_next
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);
203 GNUNET_CONTAINER_heap_walk_get_next (myHeap);
204
205 GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1)));
206 GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2)));
207 GNUNET_assert (0 == nstrcmp ("40", GNUNET_CONTAINER_heap_remove_node (n4)));
208 GNUNET_assert (0 == nstrcmp ("70", GNUNET_CONTAINER_heap_remove_node (n7)));
209 GNUNET_assert (0 == nstrcmp ("80", GNUNET_CONTAINER_heap_remove_node (n8)));
210
211 // End Testing remove_node
212
213 // Testing a GNUNET_CONTAINER_HEAP_ORDER_MAX
214 GNUNET_CONTAINER_heap_destroy (myHeap);
215
216 myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MAX);
217
218 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
219 GNUNET_CONTAINER_heap_update_cost (n1, 15);
220
221 GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1)));
222
223 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
224 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
225
226 GNUNET_CONTAINER_heap_walk_get_next (myHeap);
227 GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2)));
228 GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1)));
229
230 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
231 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
232 n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
233
234 GNUNET_CONTAINER_heap_remove_node (n2);
235 GNUNET_CONTAINER_heap_remove_node (n1);
236 GNUNET_assert (0 ==
237 nstrcmp ("30", GNUNET_CONTAINER_heap_remove_root (myHeap)));
238
239 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
240 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
241 n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
242
243 GNUNET_CONTAINER_heap_remove_node (n2);
244 GNUNET_CONTAINER_heap_remove_node (n1);
245 GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_node (n3)));
246
247 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
248 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20);
249 n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30);
250 n4 = GNUNET_CONTAINER_heap_insert (myHeap, "40", 40);
251 n5 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50);
252 n6 = GNUNET_CONTAINER_heap_insert (myHeap, "60", 60);
253
254 // Inserting nodes deeper in the tree with lower costs
255 n7 = GNUNET_CONTAINER_heap_insert (myHeap, "70", 10);
256 n8 = GNUNET_CONTAINER_heap_insert (myHeap, "80", 10);
257
258 GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_node (n3)));
259
260 // Cleaning up...
261 GNUNET_assert (0 == nstrcmp ("60", GNUNET_CONTAINER_heap_remove_node (n6)));
262 GNUNET_assert (0 == nstrcmp ("50", GNUNET_CONTAINER_heap_remove_node (n5)));
263
264 // Testing heap_walk_get_next
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);
269 GNUNET_CONTAINER_heap_walk_get_next (myHeap);
270
271 GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1)));
272 GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2)));
273 GNUNET_assert (0 == nstrcmp ("40", GNUNET_CONTAINER_heap_remove_node (n4)));
274 GNUNET_assert (0 == nstrcmp ("70", GNUNET_CONTAINER_heap_remove_node (n7)));
275 GNUNET_assert (0 == nstrcmp ("80", GNUNET_CONTAINER_heap_remove_node (n8)));
276
277 // End Testing remove_node
278
279 GNUNET_CONTAINER_heap_destroy (myHeap);
280
281 return 0;
282}
283
284
285int
286main (int argc, char **argv)
287{
288 GNUNET_log_setup ("test-container-heap", "WARNING", NULL);
289 return check ();
290}
291
292
293/* end of test_container_heap.c */
generated by cgit v1.2.3 (git 2.39.1) at 2024-04-26 12:14:29 +0000