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 2, 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,
35 GNUNET_CONTAINER_HeapCostType cost)
43 struct GNUNET_CONTAINER_Heap *myHeap;
44 struct GNUNET_CONTAINER_HeapNode *n1;
45 struct GNUNET_CONTAINER_HeapNode *n2;
46 struct GNUNET_CONTAINER_HeapNode *n3;
47 struct GNUNET_CONTAINER_HeapNode *n4;
48 struct GNUNET_CONTAINER_HeapNode *n5;
49 struct GNUNET_CONTAINER_HeapNode *n6;
50 struct GNUNET_CONTAINER_HeapNode *n7;
51 struct GNUNET_CONTAINER_HeapNode *n8;
53 myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
55 // GNUNET_CONTAINER_heap_remove_root heap empty, taking if-branch
56 n1 = GNUNET_CONTAINER_heap_remove_root (myHeap);
57 GNUNET_assert (NULL == n1);
59 // GNUNET_CONTAINER_heap_peek heap empty, taking if-branch
60 n1 = GNUNET_CONTAINER_heap_peek (myHeap);
61 GNUNET_assert (NULL == n1);
63 // GNUNET_CONTAINER_heap_walk_get_next: heap empty, taking if-branch
64 n1 = GNUNET_CONTAINER_heap_walk_get_next (myHeap);
65 GNUNET_assert (NULL == n1);
67 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "11", 11);
68 GNUNET_assert (NULL != n1);
71 // GNUNET_CONTAINER_heap_peek not empty, taking if-branch
73 n2 = GNUNET_CONTAINER_heap_peek (myHeap);
74 GNUNET_assert (NULL != n2);
76 // GNUNET_CONTAINER_heap_walk_get_next: 1 element
78 n1 = GNUNET_CONTAINER_heap_walk_get_next(myHeap);
79 GNUNET_assert (NULL != n1);
81 GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
82 GNUNET_assert (1 == GNUNET_CONTAINER_heap_get_size (myHeap));
83 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "78", 78);
84 GNUNET_assert (2 == GNUNET_CONTAINER_heap_get_size (myHeap));
85 GNUNET_assert (0 == strcmp ("78",
86 GNUNET_CONTAINER_heap_remove_node (myHeap, n2)));
87 GNUNET_assert (1 == GNUNET_CONTAINER_heap_get_size (myHeap));
88 GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
90 n3 = GNUNET_CONTAINER_heap_insert (myHeap, "15", 5);
91 GNUNET_CONTAINER_heap_update_cost (myHeap, n3, 15);
92 GNUNET_assert (2 == GNUNET_CONTAINER_heap_get_size (myHeap));
93 GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
95 n4 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50);
96 GNUNET_CONTAINER_heap_update_cost (myHeap, n4, 50);
97 GNUNET_assert (3 == GNUNET_CONTAINER_heap_get_size (myHeap));
98 GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
100 n5 = GNUNET_CONTAINER_heap_insert (myHeap, "100", 100);
101 n6 = GNUNET_CONTAINER_heap_insert (myHeap, "30/200", 30);
102 GNUNET_assert (5 == GNUNET_CONTAINER_heap_get_size (myHeap));
103 GNUNET_CONTAINER_heap_remove_node (myHeap, n5);
104 GNUNET_assert (0 == strcmp ("11",
105 GNUNET_CONTAINER_heap_remove_root (myHeap))); /* n1 */
106 GNUNET_CONTAINER_heap_update_cost (myHeap, n6, 200);
107 GNUNET_CONTAINER_heap_remove_node (myHeap, n3);
108 GNUNET_assert (0 == strcmp ("50",
109 GNUNET_CONTAINER_heap_remove_root (myHeap))); /* n4 */
110 GNUNET_assert (0 == strcmp ("30/200",
111 GNUNET_CONTAINER_heap_remove_root (myHeap))); /* n6 */
112 GNUNET_assert (0 == GNUNET_CONTAINER_heap_get_size (myHeap));
114 GNUNET_CONTAINER_heap_destroy (myHeap);
116 // My additions to a complete testcase
117 // Testing a GNUNET_CONTAINER_HEAP_ORDER_MIN
118 // Testing remove_node
120 myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
122 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
123 GNUNET_CONTAINER_heap_update_cost (myHeap, n1, 15);
125 GNUNET_assert (0 == strcmp ("10", GNUNET_CONTAINER_heap_remove_node (myHeap,n1)));
127 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
128 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
130 GNUNET_CONTAINER_heap_walk_get_next (myHeap);
131 GNUNET_assert (0 == strcmp ("20", GNUNET_CONTAINER_heap_remove_node (myHeap,n2)));
132 GNUNET_assert (0 == strcmp ("10", GNUNET_CONTAINER_heap_remove_node (myHeap,n1)));
134 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
135 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
136 n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
138 GNUNET_CONTAINER_heap_remove_node (myHeap,n2);
139 GNUNET_CONTAINER_heap_remove_node (myHeap,n1);
140 GNUNET_assert (0 == strcmp ("30", GNUNET_CONTAINER_heap_remove_root (myHeap)));
142 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
143 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
144 n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
146 GNUNET_CONTAINER_heap_remove_node (myHeap,n2);
147 GNUNET_CONTAINER_heap_remove_node (myHeap,n1);
148 GNUNET_assert (0 == strcmp ("30", GNUNET_CONTAINER_heap_remove_node (myHeap,n3)));
150 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
151 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20);
152 n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30);
154 GNUNET_assert (0 == strcmp ("20", GNUNET_CONTAINER_heap_remove_node (myHeap,n2)));
155 GNUNET_assert (0 == strcmp ("10", GNUNET_CONTAINER_heap_remove_root (myHeap)));
156 GNUNET_assert (0 == strcmp ("30", GNUNET_CONTAINER_heap_remove_root (myHeap)));
158 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
159 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20);
160 n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30);
161 n4 = GNUNET_CONTAINER_heap_insert (myHeap, "40", 40);
162 n5 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50);
163 n6 = GNUNET_CONTAINER_heap_insert (myHeap, "60", 60);
165 // Inserting nodes deeper in the tree with lower costs
166 n7 = GNUNET_CONTAINER_heap_insert (myHeap, "70", 10);
167 n8 = GNUNET_CONTAINER_heap_insert (myHeap, "80", 10);
169 GNUNET_assert (0 == strcmp ("30", GNUNET_CONTAINER_heap_remove_node (myHeap,n3)));
172 GNUNET_assert (0 == strcmp ("60", GNUNET_CONTAINER_heap_remove_node (myHeap,n6)));
173 GNUNET_assert (0 == strcmp ("50", GNUNET_CONTAINER_heap_remove_node (myHeap,n5)));
175 // Testing heap_walk_get_next
176 GNUNET_CONTAINER_heap_walk_get_next (myHeap);
177 GNUNET_CONTAINER_heap_walk_get_next (myHeap);
178 GNUNET_CONTAINER_heap_walk_get_next (myHeap);;
179 GNUNET_CONTAINER_heap_walk_get_next (myHeap);
180 GNUNET_CONTAINER_heap_walk_get_next (myHeap);
182 GNUNET_assert (0 == strcmp ("10", GNUNET_CONTAINER_heap_remove_node (myHeap,n1)));
183 GNUNET_assert (0 == strcmp ("20", GNUNET_CONTAINER_heap_remove_node (myHeap,n2)));
184 GNUNET_assert (0 == strcmp ("40", GNUNET_CONTAINER_heap_remove_node (myHeap,n4)));
185 GNUNET_assert (0 == strcmp ("70", GNUNET_CONTAINER_heap_remove_node (myHeap,n7)));
186 GNUNET_assert (0 == strcmp ("80", GNUNET_CONTAINER_heap_remove_node (myHeap,n8)));
188 // End Testing remove_node
190 // Testing a GNUNET_CONTAINER_HEAP_ORDER_MAX
191 GNUNET_CONTAINER_heap_destroy (myHeap);
193 myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MAX);
195 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
196 GNUNET_CONTAINER_heap_update_cost (myHeap, n1, 15);
198 GNUNET_assert (0 == strcmp ("10", GNUNET_CONTAINER_heap_remove_node (myHeap,n1)));
200 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
201 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
203 GNUNET_CONTAINER_heap_walk_get_next (myHeap);
204 GNUNET_assert (0 == strcmp ("20", GNUNET_CONTAINER_heap_remove_node (myHeap,n2)));
205 GNUNET_assert (0 == strcmp ("10", GNUNET_CONTAINER_heap_remove_node (myHeap,n1)));
207 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
208 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
209 n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
211 GNUNET_CONTAINER_heap_remove_node (myHeap,n2);
212 GNUNET_CONTAINER_heap_remove_node (myHeap,n1);
213 GNUNET_assert (0 == strcmp ("30", GNUNET_CONTAINER_heap_remove_root (myHeap)));
215 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
216 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
217 n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
219 GNUNET_CONTAINER_heap_remove_node (myHeap,n2);
220 GNUNET_CONTAINER_heap_remove_node (myHeap,n1);
221 GNUNET_assert (0 == strcmp ("30", GNUNET_CONTAINER_heap_remove_node (myHeap,n3)));
223 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
224 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20);
225 n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30);
226 n4 = GNUNET_CONTAINER_heap_insert (myHeap, "40", 40);
227 n5 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50);
228 n6 = GNUNET_CONTAINER_heap_insert (myHeap, "60", 60);
230 // Inserting nodes deeper in the tree with lower costs
231 n7 = GNUNET_CONTAINER_heap_insert (myHeap, "70", 10);
232 n8 = GNUNET_CONTAINER_heap_insert (myHeap, "80", 10);
234 GNUNET_assert (0 == strcmp ("30", GNUNET_CONTAINER_heap_remove_node (myHeap,n3)));
237 GNUNET_assert (0 == strcmp ("60", GNUNET_CONTAINER_heap_remove_node (myHeap,n6)));
238 GNUNET_assert (0 == strcmp ("50", GNUNET_CONTAINER_heap_remove_node (myHeap,n5)));
240 // Testing heap_walk_get_next
241 GNUNET_CONTAINER_heap_walk_get_next (myHeap);
242 GNUNET_CONTAINER_heap_walk_get_next (myHeap);
243 GNUNET_CONTAINER_heap_walk_get_next (myHeap);;
244 GNUNET_CONTAINER_heap_walk_get_next (myHeap);
245 GNUNET_CONTAINER_heap_walk_get_next (myHeap);
247 GNUNET_assert (0 == strcmp ("10", GNUNET_CONTAINER_heap_remove_node (myHeap,n1)));
248 GNUNET_assert (0 == strcmp ("20", GNUNET_CONTAINER_heap_remove_node (myHeap,n2)));
249 GNUNET_assert (0 == strcmp ("40", GNUNET_CONTAINER_heap_remove_node (myHeap,n4)));
250 GNUNET_assert (0 == strcmp ("70", GNUNET_CONTAINER_heap_remove_node (myHeap,n7)));
251 GNUNET_assert (0 == strcmp ("80", GNUNET_CONTAINER_heap_remove_node (myHeap,n8)));
253 // End Testing remove_node
255 GNUNET_CONTAINER_heap_destroy (myHeap);
262 main (int argc, char **argv)
264 GNUNET_log_setup ("test-container-heap", "WARNING", NULL);
268 /* end of test_container_heap.c */