2 This file is part of GNUnet.
3 Copyright (C) 2008 GNUnet e.V.
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.
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.
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/>.
18 SPDX-License-Identifier: AGPL3.0-or-later
22 * @author Nathan Evans
23 * @file util/test_container_heap.c
24 * @brief Test of heap operations
28 #include "gnunet_util_lib.h"
31 iterator_callback (void *cls,
32 struct GNUNET_CONTAINER_HeapNode *node,
33 void *element, GNUNET_CONTAINER_HeapCostType cost)
40 nstrcmp (const char *a, const char *b)
42 GNUNET_assert (a != NULL);
43 GNUNET_assert (b != NULL);
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;
62 myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
64 // GNUNET_CONTAINER_heap_remove_root heap empty, taking if-branch
65 n1 = GNUNET_CONTAINER_heap_remove_root (myHeap);
66 GNUNET_assert (NULL == n1);
68 // GNUNET_CONTAINER_heap_peek heap empty, taking if-branch
69 n1 = GNUNET_CONTAINER_heap_peek (myHeap);
70 GNUNET_assert (NULL == n1);
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);
76 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "11", 11);
77 GNUNET_assert (NULL != n1);
80 // GNUNET_CONTAINER_heap_peek not empty, taking if-branch
82 n2 = GNUNET_CONTAINER_heap_peek (myHeap);
83 GNUNET_assert (NULL != n2);
85 // GNUNET_CONTAINER_heap_walk_get_next: 1 element
87 n1 = GNUNET_CONTAINER_heap_walk_get_next (myHeap);
88 GNUNET_assert (NULL != n1);
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);
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);
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);
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));
125 GNUNET_CONTAINER_heap_destroy (myHeap);
127 // My additions to a complete testcase
128 // Testing a GNUNET_CONTAINER_HEAP_ORDER_MIN
129 // Testing remove_node
131 myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
133 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
134 GNUNET_CONTAINER_heap_update_cost (n1, 15);
136 r = GNUNET_CONTAINER_heap_remove_node (n1);
137 GNUNET_assert (NULL != r);
138 GNUNET_assert (0 == strcmp ("10", r));
140 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
141 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
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));
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);
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));
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);
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));
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);
175 GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2)));
177 nstrcmp ("10", GNUNET_CONTAINER_heap_remove_root (myHeap)));
179 nstrcmp ("30", GNUNET_CONTAINER_heap_remove_root (myHeap)));
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);
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);
192 GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_node (n3)));
195 GNUNET_assert (0 == nstrcmp ("60", GNUNET_CONTAINER_heap_remove_node (n6)));
196 GNUNET_assert (0 == nstrcmp ("50", GNUNET_CONTAINER_heap_remove_node (n5)));
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);
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)));
211 // End Testing remove_node
213 // Testing a GNUNET_CONTAINER_HEAP_ORDER_MAX
214 GNUNET_CONTAINER_heap_destroy (myHeap);
216 myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MAX);
218 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
219 GNUNET_CONTAINER_heap_update_cost (n1, 15);
221 GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1)));
223 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
224 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
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)));
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);
234 GNUNET_CONTAINER_heap_remove_node (n2);
235 GNUNET_CONTAINER_heap_remove_node (n1);
237 nstrcmp ("30", GNUNET_CONTAINER_heap_remove_root (myHeap)));
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);
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)));
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);
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);
258 GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_node (n3)));
261 GNUNET_assert (0 == nstrcmp ("60", GNUNET_CONTAINER_heap_remove_node (n6)));
262 GNUNET_assert (0 == nstrcmp ("50", GNUNET_CONTAINER_heap_remove_node (n5)));
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);
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)));
277 // End Testing remove_node
279 GNUNET_CONTAINER_heap_destroy (myHeap);
286 main (int argc, char **argv)
288 GNUNET_log_setup ("test-container-heap", "WARNING", NULL);
293 /* end of test_container_heap.c */