source: trunk/src/cutest_zAVLTree.c @ 366

Last change on this file since 366 was 366, checked in by katerina, 10 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.