source: trunk/src/cutest_zAVLTree.c@ 399

Last change on this file since 399 was 366, checked in by katerina, 13 years ago

Fix for ticket #270 (Unit tests for numeric key for AVL tree).
File size: 14.9 KB
Line 
1
2#include "config_xor.h"
3
4#include <string.h>
5#include "CuTest.h"
6#include "zAVLTree.h"
7
8struct ztest {
9 char name[32];
10 int iname;
11};
12
13static zAVLTree * ztest_tree = NULL;
14
15static zAVLKey ztest_key (void const * arg)
16{
17 const struct ztest * sa = (const struct ztest *) arg;
18 return (zAVLKey) sa->name;
19}
20
21static zAVLKey ztest_intkey(void const *item)
22{
23 return (&((struct ztest *)item)->iname);
24}
25
26
27static void free_node (void * inptr)
28{
29 struct ztest * ptr = (struct ztest *) inptr;
30 ptr->name[0] = '\0';
31 ptr->iname = 0;
32}
33
34void Test_zAVLTree(CuTest *tc) {
35 zAVLCursor cursor;
36
37 int result;
38 int counter = 0;
39
40 struct ztest z1 = { "abc" , 1 };
41 struct ztest z2 = { "aac" , 2 };
42 struct ztest z3 = { "aaa1" , 3 };
43 struct ztest z4 = { "aaa3" , 4 };
44 struct ztest z5 = { "aaa2" , 5 };
45 struct ztest z6 = { "aaa6" , 6 };
46 struct ztest z7 = { "aaa5" , 7 };
47 struct ztest z8 = { "aaa4" , 8 };
48
49 struct ztest iz1 = { "aaa1" , 8 };
50 struct ztest iz2 = { "aaa2" , 7 };
51 struct ztest iz3 = { "aaa3" , 1 };
52 struct ztest iz4 = { "aaa4" , 3 };
53 struct ztest iz5 = { "aaa5" , 2 };
54 struct ztest iz6 = { "aaa5" , 6 };
55 struct ztest iz7 = { "aaa7" , 5 };
56 struct ztest iz8 = { "aaa8" , 4 };
57
58 struct ztest * ptr;
59
60 ptr = zAVLFirst(&cursor, ztest_tree);
61 CuAssertTrue(tc, NULL == ptr);
62
63 ztest_tree = zAVLAllocTree (ztest_key, zAVL_KEY_STRING);
64 CuAssertPtrNotNull(tc, ztest_tree);
65
66 do {
67
68 ++counter;
69
70 result = zAVLInsert(ztest_tree, &z1);
71 CuAssertTrue(tc, 0 == result);
72 result = zAVLInsert(ztest_tree, &z2);
73 CuAssertTrue(tc, 0 == result);
74 result = zAVLInsert(ztest_tree, &z3);
75 CuAssertTrue(tc, 0 == result);
76 result = zAVLInsert(ztest_tree, &z4);
77 CuAssertTrue(tc, 0 == result);
78 result = zAVLInsert(ztest_tree, &z5);
79 CuAssertTrue(tc, 0 == result);
80 result = zAVLInsert(ztest_tree, &z6);
81 CuAssertTrue(tc, 0 == result);
82 result = zAVLInsert(ztest_tree, &z7);
83 CuAssertTrue(tc, 0 == result);
84 result = zAVLInsert(ztest_tree, &z8);
85 CuAssertTrue(tc, 0 == result);
86
87 ptr = zAVLFirst(&cursor, ztest_tree);
88 CuAssertStrEquals(tc, ptr->name, z3.name);
89 ptr = zAVLNext(&cursor);
90 CuAssertStrEquals(tc, ptr->name, z5.name);
91 ptr = zAVLNext(&cursor);
92 CuAssertStrEquals(tc, ptr->name, z4.name);
93 ptr = zAVLNext(&cursor);
94 CuAssertStrEquals(tc, ptr->name, z8.name);
95 ptr = zAVLNext(&cursor);
96 CuAssertStrEquals(tc, ptr->name, z7.name);
97 ptr = zAVLNext(&cursor);
98 CuAssertStrEquals(tc, ptr->name, z6.name);
99 ptr = zAVLNext(&cursor);
100 CuAssertStrEquals(tc, ptr->name, z2.name);
101 ptr = zAVLNext(&cursor);
102 CuAssertStrEquals(tc, ptr->name, z1.name);
103 ptr = zAVLNext(&cursor);
104 CuAssertTrue(tc, NULL == ptr);
105
106 result = zAVLInsert(ztest_tree, &z8);
107 CuAssertTrue(tc, 0 != result);
108 result = zAVLInsert(ztest_tree, &z7);
109 CuAssertTrue(tc, 0 != result);
110 result = zAVLInsert(ztest_tree, &z6);
111 CuAssertTrue(tc, 0 != result);
112 result = zAVLInsert(ztest_tree, &z5);
113 CuAssertTrue(tc, 0 != result);
114
115 ptr = zAVLSearch(ztest_tree, z1.name);
116 CuAssertStrEquals(tc, ptr->name, z1.name);
117 ptr = zAVLSearch(ztest_tree, z2.name);
118 CuAssertStrEquals(tc, ptr->name, z2.name);
119 ptr = zAVLSearch(ztest_tree, z3.name);
120 CuAssertStrEquals(tc, ptr->name, z3.name);
121 ptr = zAVLSearch(ztest_tree, z4.name);
122 CuAssertStrEquals(tc, ptr->name, z4.name);
123
124 ptr = zAVLFirst(&cursor, ztest_tree);
125 CuAssertStrEquals(tc, ptr->name, z3.name);
126 ptr = zAVLNext(&cursor);
127 CuAssertStrEquals(tc, ptr->name, z5.name);
128 ptr = zAVLNext(&cursor);
129 CuAssertStrEquals(tc, ptr->name, z4.name);
130 ptr = zAVLNext(&cursor);
131 CuAssertStrEquals(tc, ptr->name, z8.name);
132 ptr = zAVLNext(&cursor);
133 CuAssertStrEquals(tc, ptr->name, z7.name);
134 ptr = zAVLNext(&cursor);
135 CuAssertStrEquals(tc, ptr->name, z6.name);
136 ptr = zAVLNext(&cursor);
137 CuAssertStrEquals(tc, ptr->name, z2.name);
138 ptr = zAVLNext(&cursor);
139 CuAssertStrEquals(tc, ptr->name, z1.name);
140 ptr = zAVLNext(&cursor);
141 CuAssertTrue(tc, NULL == ptr);
142
143
144 ptr = zAVLSearch(ztest_tree, z5.name);
145 CuAssertStrEquals(tc, ptr->name, z5.name);
146 ptr = zAVLSearch(ztest_tree, z6.name);
147 CuAssertStrEquals(tc, ptr->name, z6.name);
148 ptr = zAVLSearch(ztest_tree, z7.name);
149 CuAssertStrEquals(tc, ptr->name, z7.name);
150 ptr = zAVLSearch(ztest_tree, z8.name);
151 CuAssertStrEquals(tc, ptr->name, z8.name);
152 ptr = zAVLSearch(ztest_tree, "foobar");
153 CuAssertTrue(tc, NULL == ptr);
154
155 result = zAVLDelete(ztest_tree, z8.name);
156 CuAssertTrue(tc, 0 == result);
157 ptr = zAVLSearch(ztest_tree, z8.name);
158 CuAssertTrue(tc, NULL == ptr);
159
160 result = zAVLDelete(ztest_tree, z3.name);
161 CuAssertTrue(tc, 0 == result);
162 ptr = zAVLSearch(ztest_tree, z3.name);
163 CuAssertTrue(tc, NULL == ptr);
164
165 result = zAVLDelete(ztest_tree, z1.name);
166 CuAssertTrue(tc, 0 == result);
167 ptr = zAVLSearch(ztest_tree, z1.name);
168 CuAssertTrue(tc, NULL == ptr);
169
170 result = zAVLInsert(ztest_tree, &z1);
171 CuAssertTrue(tc, 0 == result);
172 result = zAVLInsert(ztest_tree, &z8);
173 CuAssertTrue(tc, 0 == result);
174 result = zAVLInsert(ztest_tree, &z3);
175 CuAssertTrue(tc, 0 == result);
176
177 ptr = zAVLFirst(&cursor, ztest_tree);
178 CuAssertStrEquals(tc, ptr->name, z3.name);
179 ptr = zAVLNext(&cursor);
180 CuAssertStrEquals(tc, ptr->name, z5.name);
181 ptr = zAVLNext(&cursor);
182 CuAssertStrEquals(tc, ptr->name, z4.name);
183 ptr = zAVLNext(&cursor);
184 CuAssertStrEquals(tc, ptr->name, z8.name);
185 ptr = zAVLNext(&cursor);
186 CuAssertStrEquals(tc, ptr->name, z7.name);
187 ptr = zAVLNext(&cursor);
188 CuAssertStrEquals(tc, ptr->name, z6.name);
189 ptr = zAVLNext(&cursor);
190 CuAssertStrEquals(tc, ptr->name, z2.name);
191 ptr = zAVLNext(&cursor);
192 CuAssertStrEquals(tc, ptr->name, z1.name);
193 ptr = zAVLNext(&cursor);
194 CuAssertTrue(tc, NULL == ptr);
195
196 result = zAVLDelete(ztest_tree, z1.name);
197 CuAssertTrue(tc, 0 == result);
198 ptr = zAVLSearch(ztest_tree, z1.name);
199 CuAssertTrue(tc, NULL == ptr);
200
201 result = zAVLDelete(ztest_tree, z2.name);
202 CuAssertTrue(tc, 0 == result);
203 ptr = zAVLSearch(ztest_tree, z2.name);
204 CuAssertTrue(tc, NULL == ptr);
205
206 result = zAVLDelete(ztest_tree, z3.name);
207 CuAssertTrue(tc, 0 == result);
208 ptr = zAVLSearch(ztest_tree, z3.name);
209 CuAssertTrue(tc, NULL == ptr);
210
211 result = zAVLDelete(ztest_tree, z4.name);
212 CuAssertTrue(tc, 0 == result);
213 ptr = zAVLSearch(ztest_tree, z4.name);
214 CuAssertTrue(tc, NULL == ptr);
215
216 result = zAVLDelete(ztest_tree, z5.name);
217 CuAssertTrue(tc, 0 == result);
218 ptr = zAVLSearch(ztest_tree, z5.name);
219 CuAssertTrue(tc, NULL == ptr);
220
221 result = zAVLDelete(ztest_tree, z6.name);
222 CuAssertTrue(tc, 0 == result);
223 ptr = zAVLSearch(ztest_tree, z6.name);
224 CuAssertTrue(tc, NULL == ptr);
225
226 result = zAVLDelete(ztest_tree, z7.name);
227 CuAssertTrue(tc, 0 == result);
228 ptr = zAVLSearch(ztest_tree, z7.name);
229 CuAssertTrue(tc, NULL == ptr);
230
231 result = zAVLDelete(ztest_tree, z8.name);
232 CuAssertTrue(tc, 0 == result);
233 ptr = zAVLSearch(ztest_tree, z8.name);
234 CuAssertTrue(tc, NULL == ptr);
235
236} while (counter < 100);
237
238 result = zAVLInsert(ztest_tree, &z1);
239 CuAssertTrue(tc, 0 == result);
240 result = zAVLInsert(ztest_tree, &z2);
241 CuAssertTrue(tc, 0 == result);
242 result = zAVLInsert(ztest_tree, &z3);
243 CuAssertTrue(tc, 0 == result);
244 result = zAVLInsert(ztest_tree, &z4);
245 CuAssertTrue(tc, 0 == result);
246 result = zAVLInsert(ztest_tree, &z5);
247 CuAssertTrue(tc, 0 == result);
248 result = zAVLInsert(ztest_tree, &z6);
249 CuAssertTrue(tc, 0 == result);
250 result = zAVLInsert(ztest_tree, &z7);
251 CuAssertTrue(tc, 0 == result);
252 result = zAVLInsert(ztest_tree, &z8);
253 CuAssertTrue(tc, 0 == result);
254
255 zAVLFreeTree (ztest_tree, free_node);
256 CuAssertTrue (tc, z1.name[0] == '\0');
257 CuAssertTrue (tc, z2.name[0] == '\0');
258 CuAssertTrue (tc, z3.name[0] == '\0');
259 CuAssertTrue (tc, z4.name[0] == '\0');
260 CuAssertTrue (tc, z5.name[0] == '\0');
261 CuAssertTrue (tc, z6.name[0] == '\0');
262 CuAssertTrue (tc, z7.name[0] == '\0');
263 CuAssertTrue (tc, z8.name[0] == '\0');
264
265
266 /* Numeric key here */
267
268 counter = 0;
269 ztest_tree = NULL;
270
271 ptr = zAVLFirst(&cursor, ztest_tree);
272 CuAssertTrue(tc, NULL == ptr);
273
274 ztest_tree = zAVLAllocTree (ztest_intkey, zAVL_KEY_INT);
275 CuAssertPtrNotNull(tc, ztest_tree);
276
277 do {
278
279 ++counter;
280
281 result = zAVLInsert(ztest_tree, &iz1);
282 CuAssertTrue(tc, 0 == result);
283 result = zAVLInsert(ztest_tree, &iz2);
284 CuAssertTrue(tc, 0 == result);
285 result = zAVLInsert(ztest_tree, &iz3);
286 CuAssertTrue(tc, 0 == result);
287 result = zAVLInsert(ztest_tree, &iz4);
288 CuAssertTrue(tc, 0 == result);
289 result = zAVLInsert(ztest_tree, &iz5);
290 CuAssertTrue(tc, 0 == result);
291 result = zAVLInsert(ztest_tree, &iz6);
292 CuAssertTrue(tc, 0 == result);
293 result = zAVLInsert(ztest_tree, &iz7);
294 CuAssertTrue(tc, 0 == result);
295 result = zAVLInsert(ztest_tree, &iz8);
296 CuAssertTrue(tc, 0 == result);
297
298 ptr = zAVLFirst(&cursor, ztest_tree);
299 CuAssertStrEquals(tc, ptr->name, iz3.name);
300 ptr = zAVLNext(&cursor);
301 CuAssertStrEquals(tc, ptr->name, iz5.name);
302 ptr = zAVLNext(&cursor);
303 CuAssertStrEquals(tc, ptr->name, iz4.name);
304 ptr = zAVLNext(&cursor);
305 CuAssertStrEquals(tc, ptr->name, iz8.name);
306 ptr = zAVLNext(&cursor);
307 CuAssertStrEquals(tc, ptr->name, iz7.name);
308 ptr = zAVLNext(&cursor);
309 CuAssertStrEquals(tc, ptr->name, iz6.name);
310 ptr = zAVLNext(&cursor);
311 CuAssertStrEquals(tc, ptr->name, iz2.name);
312 ptr = zAVLNext(&cursor);
313 CuAssertStrEquals(tc, ptr->name, iz1.name);
314 ptr = zAVLNext(&cursor);
315 CuAssertTrue(tc, NULL == ptr);
316
317 result = zAVLInsert(ztest_tree, &iz8);
318 CuAssertTrue(tc, 0 != result);
319 result = zAVLInsert(ztest_tree, &iz7);
320 CuAssertTrue(tc, 0 != result);
321 result = zAVLInsert(ztest_tree, &iz6);
322 CuAssertTrue(tc, 0 != result);
323 result = zAVLInsert(ztest_tree, &iz5);
324 CuAssertTrue(tc, 0 != result);
325
326 ptr = zAVLSearch(ztest_tree, &(iz1.iname));
327 CuAssertIntEquals(tc, ptr->iname, iz1.iname);
328 ptr = zAVLSearch(ztest_tree, &(iz2.iname));
329 CuAssertIntEquals(tc, ptr->iname, iz2.iname);
330 ptr = zAVLSearch(ztest_tree, &(iz3.iname));
331 CuAssertIntEquals(tc, ptr->iname, iz3.iname);
332 ptr = zAVLSearch(ztest_tree, &(iz6.iname));
333 CuAssertIntEquals(tc, ptr->iname, iz6.iname);
334 ptr = zAVLSearch(ztest_tree, &(iz4.iname));
335 CuAssertIntEquals(tc, ptr->iname, iz4.iname);
336
337 ptr = zAVLSearch(ztest_tree, &(iz2.iname));
338 CuAssertIntEquals(tc, ptr->iname, iz2.iname);
339 ptr = zAVLSearch(ztest_tree, &(iz3.iname));
340 CuAssertIntEquals(tc, ptr->iname, iz3.iname);
341 ptr = zAVLSearch(ztest_tree, &(iz7.iname));
342 CuAssertIntEquals(tc, ptr->iname, iz7.iname);
343
344 ptr = zAVLFirst(&cursor, ztest_tree);
345 CuAssertStrEquals(tc, ptr->name, iz3.name);
346 ptr = zAVLNext(&cursor);
347 CuAssertStrEquals(tc, ptr->name, iz5.name);
348 ptr = zAVLNext(&cursor);
349 CuAssertStrEquals(tc, ptr->name, iz4.name);
350 ptr = zAVLNext(&cursor);
351 CuAssertStrEquals(tc, ptr->name, iz8.name);
352 ptr = zAVLNext(&cursor);
353 CuAssertStrEquals(tc, ptr->name, iz7.name);
354 ptr = zAVLNext(&cursor);
355 CuAssertStrEquals(tc, ptr->name, iz6.name);
356 ptr = zAVLNext(&cursor);
357 CuAssertStrEquals(tc, ptr->name, iz2.name);
358 ptr = zAVLNext(&cursor);
359 CuAssertStrEquals(tc, ptr->name, iz1.name);
360 ptr = zAVLNext(&cursor);
361 CuAssertTrue(tc, NULL == ptr);
362
363
364 ptr = zAVLSearch(ztest_tree, &(iz5.iname));
365 CuAssertStrEquals(tc, ptr->name, iz5.name);
366 ptr = zAVLSearch(ztest_tree, &(iz6.iname));
367 CuAssertStrEquals(tc, ptr->name, iz6.name);
368 ptr = zAVLSearch(ztest_tree, &(iz7.iname));
369 CuAssertStrEquals(tc, ptr->name, iz7.name);
370 ptr = zAVLSearch(ztest_tree, &(iz8.iname));
371 CuAssertStrEquals(tc, ptr->name, iz8.name);
372 ptr = zAVLSearch(ztest_tree, &(z1.iname)); /* been set to 0 */
373 CuAssertTrue(tc, NULL == ptr);
374
375 result = zAVLDelete(ztest_tree, &(iz8.iname));
376 CuAssertTrue(tc, 0 == result);
377 ptr = zAVLSearch(ztest_tree, &(iz8.iname));
378 CuAssertTrue(tc, NULL == ptr);
379
380 result = zAVLDelete(ztest_tree, &(iz3.iname));
381 CuAssertTrue(tc, 0 == result);
382 ptr = zAVLSearch(ztest_tree, &(iz3.iname));
383 CuAssertTrue(tc, NULL == ptr);
384
385 result = zAVLDelete(ztest_tree, &(iz1.iname));
386 CuAssertTrue(tc, 0 == result);
387 ptr = zAVLSearch(ztest_tree, &(iz1.iname));
388 CuAssertTrue(tc, NULL == ptr);
389
390 result = zAVLInsert(ztest_tree, &iz1);
391 CuAssertTrue(tc, 0 == result);
392 result = zAVLInsert(ztest_tree, &iz8);
393 CuAssertTrue(tc, 0 == result);
394 result = zAVLInsert(ztest_tree, &iz3);
395 CuAssertTrue(tc, 0 == result);
396
397 ptr = zAVLFirst(&cursor, ztest_tree);
398 CuAssertIntEquals(tc, ptr->iname, iz3.iname);
399 ptr = zAVLNext(&cursor);
400 CuAssertStrEquals(tc, ptr->name, iz5.name);
401 ptr = zAVLNext(&cursor);
402 CuAssertStrEquals(tc, ptr->name, iz4.name);
403 ptr = zAVLNext(&cursor);
404 CuAssertIntEquals(tc, ptr->iname, iz8.iname);
405 ptr = zAVLNext(&cursor);
406 CuAssertStrEquals(tc, ptr->name, iz7.name);
407 ptr = zAVLNext(&cursor);
408 CuAssertStrEquals(tc, ptr->name, iz6.name);
409 ptr = zAVLNext(&cursor);
410 CuAssertIntEquals(tc, ptr->iname, iz2.iname);
411 ptr = zAVLNext(&cursor);
412 CuAssertStrEquals(tc, ptr->name, iz1.name);
413 ptr = zAVLNext(&cursor);
414 CuAssertTrue(tc, NULL == ptr);
415
416 result = zAVLDelete(ztest_tree, &(iz1.iname));
417 CuAssertTrue(tc, 0 == result);
418 ptr = zAVLSearch(ztest_tree, &(iz1.iname));
419 CuAssertTrue(tc, NULL == ptr);
420
421 result = zAVLDelete(ztest_tree, &(iz2.iname));
422 CuAssertTrue(tc, 0 == result);
423 ptr = zAVLSearch(ztest_tree, &(iz2.iname));
424 CuAssertTrue(tc, NULL == ptr);
425
426 result = zAVLDelete(ztest_tree, &(iz3.iname));
427 CuAssertTrue(tc, 0 == result);
428 ptr = zAVLSearch(ztest_tree, &(iz3.iname));
429 CuAssertTrue(tc, NULL == ptr);
430
431 result = zAVLDelete(ztest_tree, &(iz4.iname));
432 CuAssertTrue(tc, 0 == result);
433 ptr = zAVLSearch(ztest_tree, &(iz4.iname));
434 CuAssertTrue(tc, NULL == ptr);
435
436 result = zAVLDelete(ztest_tree, &(iz5.iname));
437 CuAssertTrue(tc, 0 == result);
438 ptr = zAVLSearch(ztest_tree, &(iz5.iname));
439 CuAssertTrue(tc, NULL == ptr);
440
441 result = zAVLDelete(ztest_tree, &(iz6.iname));
442 CuAssertTrue(tc, 0 == result);
443 ptr = zAVLSearch(ztest_tree, &(iz6.iname));
444 CuAssertTrue(tc, NULL == ptr);
445
446 result = zAVLDelete(ztest_tree, &(iz7.iname));
447 CuAssertTrue(tc, 0 == result);
448 ptr = zAVLSearch(ztest_tree, &(iz7.iname));
449 CuAssertTrue(tc, NULL == ptr);
450
451 result = zAVLDelete(ztest_tree, &(iz8.iname));
452 CuAssertTrue(tc, 0 == result);
453 ptr = zAVLSearch(ztest_tree, &(iz8.iname));
454 CuAssertTrue(tc, NULL == ptr);
455
456} while (counter < 100);
457
458 result = zAVLInsert(ztest_tree, &iz1);
459 CuAssertTrue(tc, 0 == result);
460 result = zAVLInsert(ztest_tree, &iz2);
461 CuAssertTrue(tc, 0 == result);
462 result = zAVLInsert(ztest_tree, &iz3);
463 CuAssertTrue(tc, 0 == result);
464 result = zAVLInsert(ztest_tree, &iz4);
465 CuAssertTrue(tc, 0 == result);
466 result = zAVLInsert(ztest_tree, &iz5);
467 CuAssertTrue(tc, 0 == result);
468 result = zAVLInsert(ztest_tree, &iz6);
469 CuAssertTrue(tc, 0 == result);
470 result = zAVLInsert(ztest_tree, &iz7);
471 CuAssertTrue(tc, 0 == result);
472 result = zAVLInsert(ztest_tree, &iz8);
473 CuAssertTrue(tc, 0 == result);
474
475 zAVLFreeTree (ztest_tree, free_node);
476 CuAssertTrue (tc, iz1.iname == 0);
477 CuAssertTrue (tc, iz2.iname == 0);
478 CuAssertTrue (tc, iz3.iname == 0);
479 CuAssertTrue (tc, iz4.iname == 0);
480 CuAssertTrue (tc, iz5.iname == 0);
481 CuAssertTrue (tc, iz6.iname == 0);
482 CuAssertTrue (tc, iz7.iname == 0);
483 CuAssertTrue (tc, iz8.iname == 0);
484
485
486}
Note: See TracBrowser for help on using the repository browser.