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