avl: new module
[ccan] / ccan / avl / test / run.c
1 /*
2  * Copyright (c) 2010 Joseph Adams <joeyadams3.14159@gmail.com>
3  *
4  * Permission to use, copy, modify, and/or distribute this software for any
5  * purpose with or without fee is hereby granted, provided that the above
6  * copyright notice and this permission notice appear in all copies.
7  *
8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15  */
16
17 #include <ccan/avl/avl.h>
18
19 #define remove remove_
20 #include <ccan/avl/avl.c>
21 #undef remove
22
23 #include <ccan/tap/tap.h>
24
25 #include <stdint.h>
26 #include <stdio.h>
27 #include <stdlib.h>
28 #include <string.h>
29
30 #define ANIMATE_RANDOM_ACCESS 0
31
32 #if ANIMATE_RANDOM_ACCESS
33
34 #include <sys/time.h>
35
36 typedef int64_t msec_t;
37
38 static msec_t time_ms(void)
39 {
40         struct timeval tv;
41         gettimeofday(&tv, NULL);
42         return (msec_t)tv.tv_sec * 1000 + tv.tv_usec / 1000;
43 }
44
45 #endif
46
47 uint32_t rand32_state = 0;
48
49 /*
50  * Finds a pseudorandom 32-bit number from 0 to 2^32-1 .
51  * Uses the BCPL linear congruential generator method.
52  *
53  * Note: this method (or maybe just this implementation) seems to
54  *       go back and forth between odd and even exactly, which can
55  *       affect low-cardinality testing if the cardinality given is even.
56  */
57 static uint32_t rand32(void)
58 {
59         rand32_state *= (uint32_t)0x7FF8A3ED;
60         rand32_state += (uint32_t)0x2AA01D31;
61         return rand32_state;
62 }
63
64 static void scramble(void *base, size_t nmemb, size_t size)
65 {
66         char *i = base;
67         char *o;
68         size_t sd;
69         for (;nmemb>1;nmemb--) {
70                 o = i + size*(rand32()%nmemb);
71                 for (sd=size;sd--;) {
72                         char tmp = *o;
73                         *o++ = *i;
74                         *i++ = tmp;
75                 }
76         }
77 }
78
79 static struct {
80         size_t success;
81         size_t passed_invariants_checks;
82         
83         size_t excess;
84         size_t duplicate;
85         size_t missing;
86         size_t incorrect;
87         size_t failed;
88         size_t failed_invariants_checks;
89 } stats;
90
91 static void clear_stats(void)
92 {
93         memset(&stats, 0, sizeof(stats));
94 }
95
96 static bool print_stats(const char *success_label, size_t expected_success)
97 {
98         int failed = 0;
99         
100         printf("      %s:  \t%zu\n", success_label, stats.success);
101         if (stats.success != expected_success)
102                 failed = 1;
103         
104         if (stats.passed_invariants_checks)
105                 printf("      Passed invariants checks: %zu\n", stats.passed_invariants_checks);
106         
107         if (stats.excess)
108                 failed = 1, printf("      Excess:     \t%zu\n", stats.excess);
109         if (stats.duplicate)
110                 failed = 1, printf("      Duplicate:  \t%zu\n", stats.duplicate);
111         if (stats.missing)
112                 failed = 1, printf("      Missing:    \t%zu\n", stats.missing);
113         if (stats.incorrect)
114                 failed = 1, printf("      Incorrect:  \t%zu\n", stats.incorrect);
115         if (stats.failed)
116                 failed = 1, printf("      Failed:     \t%zu\n", stats.failed);
117         if (stats.failed_invariants_checks)
118                 failed = 1, printf("      Failed invariants checks: %zu\n", stats.failed_invariants_checks);
119         
120         return !failed;
121 }
122
123 struct test_item {
124         uint32_t key;
125         uint32_t value;
126         size_t   insert_id; /* needed because qsort is not a stable sort */
127 };
128
129 static int compare_uint32_t(const void *ap, const void *bp)
130 {
131         uint32_t a = *(const uint32_t *)ap;
132         uint32_t b = *(const uint32_t *)bp;
133         
134         if (a < b)
135                 return -1;
136         if (a > b)
137                 return 1;
138         return 0;
139 }
140
141 static int compare_test_item(const void *ap, const void *bp)
142 {
143         const struct test_item *a = *(void**)ap, *b = *(void**)bp;
144         
145         if (a->key < b->key)
146                 return -1;
147         if (a->key > b->key)
148                 return 1;
149         
150         if (a->insert_id < b->insert_id)
151                 return -1;
152         if (a->insert_id > b->insert_id)
153                 return 1;
154         
155         return 0;
156 }
157
158 static bool test_insert_item(AVL *avl, struct test_item *item)
159 {
160         avl_insert(avl, &item->key, &item->value);
161         return true;
162 }
163
164 static bool test_lookup_item(const AVL *avl, const struct test_item *item)
165 {
166         return avl_member(avl, &item->key) && avl_lookup(avl, &item->key) == &item->value;
167 }
168
169 static bool test_remove_item(AVL *avl, struct test_item *item)
170 {
171         return avl_remove(avl, &item->key);
172 }
173
174 static void test_foreach(AVL *avl, struct test_item **test_items, int count)
175 {
176         AvlIter iter;
177         int     i;
178         
179         i = 0;
180         avl_foreach(iter, avl) {
181                 if (i >= count) {
182                         stats.excess++;
183                         continue;
184                 }
185                 if (iter.key == &test_items[i]->key && iter.value == &test_items[i]->value)
186                         stats.success++;
187                 else
188                         stats.incorrect++;
189                 i++;
190         }
191 }
192
193 static void test_foreach_reverse(AVL *avl, struct test_item **test_items, int count)
194 {
195         AvlIter iter;
196         int     i;
197         
198         i = count - 1;
199         avl_foreach_reverse(iter, avl) {
200                 if (i < 0) {
201                         stats.excess++;
202                         continue;
203                 }
204                 if (iter.key == &test_items[i]->key && iter.value == &test_items[i]->value)
205                         stats.success++;
206                 else
207                         stats.incorrect++;
208                 i--;
209         }
210 }
211
212 static void benchmark(size_t max_per_trial, size_t round_count, bool random_counts, int cardinality)
213 {
214         struct test_item **test_item;
215         struct test_item *test_item_array;
216         size_t i, o, count;
217         size_t round = 0;
218         
219         test_item = malloc(max_per_trial * sizeof(*test_item));
220         test_item_array = malloc(max_per_trial * sizeof(*test_item_array));
221         
222         if (!test_item || !test_item_array) {
223                 fail("Not enough memory for %zu keys per trial\n",
224                         max_per_trial);
225                 return;
226         }
227         
228         /* Initialize test_item pointers. */
229         for (i=0; i<max_per_trial; i++)
230                 test_item[i] = &test_item_array[i];
231         
232         /*
233          * If round_count is not zero, run round_count trials.
234          * Otherwise, run forever.
235          */
236         for (round = 1; round_count==0 || round <= round_count; round++) {
237                 AVL *avl;
238                 
239                 if (cardinality)
240                         printf("Round %zu (cardinality = %d)\n", round, cardinality);
241                 else
242                         printf("Round %zu\n", round);
243                 
244                 if (random_counts)
245                         count = rand32() % (max_per_trial+1);
246                 else
247                         count = max_per_trial;
248                 
249                 /*
250                  * Initialize test items by giving them sequential keys and
251                  * random values. Scramble them so the order of insertion
252                  * will be random.
253                  */
254                 for (i=0; i<count; i++) {
255                         test_item[i]->key   = rand32();
256                         test_item[i]->value = rand32();
257                         
258                         if (cardinality)
259                                 test_item[i]->key %= cardinality;
260                 }
261                 scramble(test_item, count, sizeof(*test_item));
262                 
263                 avl = avl_new(compare_uint32_t);
264                 
265                 clear_stats();
266                 printf("   Inserting %zu items...\n", count);
267                 for (i=0; i<count; i++) {
268                         if (test_insert_item(avl, test_item[i])) {
269                                 stats.success++;
270                                 test_item[i]->insert_id = i;
271                         } else {
272                                 printf("invariants check failed at insertion %zu\n", i);
273                                 stats.failed++;
274                         }
275                         
276                         /* Periodically do an invariants check */
277                         if (count / 10 > 0 && i % (count / 10) == 0) {
278                                 if (avl_check_invariants(avl))
279                                         stats.passed_invariants_checks++;
280                                 else
281                                         stats.failed_invariants_checks++;
282                         }
283                 }
284                 ok1(print_stats("Inserted", count));
285                 ok1(avl_check_invariants(avl));
286                 
287                 /* remove early duplicates, as they are shadowed in insertions. */
288                 qsort(test_item, count, sizeof(*test_item), compare_test_item);
289                 for (i = 0, o = 0; i < count;) {
290                         uint32_t k = test_item[i]->key;
291                         do i++; while (i < count && test_item[i]->key == k);
292                         test_item[o++] = test_item[i-1];
293                 }
294                 count = o;
295                 ok1(avl_count(avl) == count);
296                 
297                 scramble(test_item, count, sizeof(*test_item));
298                 
299                 printf("   Finding %zu items...\n", count);
300                 clear_stats();
301                 for (i=0; i<count; i++) {
302                         if (!test_lookup_item(avl, test_item[i]))
303                                 stats.missing++;
304                         else
305                                 stats.success++;
306                 }
307                 ok1(print_stats("Retrieved", count));
308                 
309                 qsort(test_item, count, sizeof(*test_item), compare_test_item);
310                 
311                 printf("   Traversing forward through %zu items...\n", count);
312                 clear_stats();
313                 test_foreach(avl, test_item, count);
314                 ok1(print_stats("Traversed", count));
315                 
316                 printf("   Traversing backward through %zu items...\n", count);
317                 clear_stats();
318                 test_foreach_reverse(avl, test_item, count);
319                 ok1(print_stats("Traversed", count));
320                 
321                 scramble(test_item, count, sizeof(*test_item));
322                 
323                 printf("   Deleting %zu items...\n", count);
324                 clear_stats();
325                 for (i=0; i<count; i++) {
326                         if (test_remove_item(avl, test_item[i]))
327                                 stats.success++;
328                         else
329                                 stats.missing++;
330                         
331                         /* Periodically do an invariants check */
332                         if (count / 10 > 0 && i % (count / 10) == 0) {
333                                 if (avl_check_invariants(avl))
334                                         stats.passed_invariants_checks++;
335                                 else
336                                         stats.failed_invariants_checks++;
337                         }
338                 }
339                 ok1(print_stats("Deleted", count));
340                 ok1(avl_count(avl) == 0);
341                 ok1(avl_check_invariants(avl));
342                 
343                 avl_free(avl);
344         }
345         
346         free(test_item);
347         free(test_item_array);
348 }
349
350 static int compare_ptr(const void *a, const void *b)
351 {
352         if (a < b)
353                 return -1;
354         if (a > b)
355                 return 1;
356         return 0;
357 }
358
359 struct fail_total {
360         int64_t fail;
361         int64_t total;
362 };
363
364 static bool print_pass_fail(struct fail_total *pf, const char *label)
365 {
366         long long fail  = pf->fail,
367                   total = pf->total;
368         
369         printf("%s:\t%lld / %lld\n", label, total - fail, total);
370         
371         return fail == 0;
372 }
373
374 static void test_random_access(uint32_t max, int64_t ops)
375 {
376         char       *in_tree;
377         AVL        *avl;
378         int64_t     i;
379         struct {
380                 struct fail_total
381                         inserts, lookups, removes, checks;
382         } s;
383         
384         #if ANIMATE_RANDOM_ACCESS
385         msec_t last_update, now;
386         msec_t interval = 100;
387         #endif
388         
389         memset(&s, 0, sizeof(s));
390         
391         in_tree = malloc(max);
392         memset(in_tree, 0, max);
393         
394         avl = avl_new(compare_ptr);
395         
396         #if ANIMATE_RANDOM_ACCESS
397         now = time_ms();
398         last_update = now - interval;
399         #endif
400         
401         for (i = 0; i < ops; i++) {
402                 char *item = &in_tree[rand32() % max];
403                 char *found;
404                 bool  inserted, removed;
405                 
406                 #if ANIMATE_RANDOM_ACCESS
407                 now = time_ms();
408                 if (now >= last_update + interval) {
409                         last_update = now;
410                         printf("\r%.2f%%\t%zu / %zu\033[K", (double)i * 100 / ops, avl_count(avl), max);
411                         fflush(stdout);
412                 }
413                 #endif
414                 
415                 switch (rand32() % 3) {
416                         case 0:
417                                 inserted = avl_insert(avl, item, item);
418                                 
419                                 if ((*item == 0 && !inserted) ||
420                                     (*item == 1 && inserted))
421                                         s.inserts.fail++;
422                                 
423                                 if (inserted)
424                                         *item = 1;
425                                 
426                                 s.inserts.total++;
427                                 break;
428                         
429                         case 1:
430                                 found = avl_lookup(avl, item);
431                                 
432                                 if ((*item == 0 && found != NULL) ||
433                                     (*item == 1 && found != item) ||
434                                     (avl_member(avl, item) != !!found))
435                                         s.lookups.fail++;
436                                 
437                                 s.lookups.total++;
438                                 break;
439                         
440                         case 2:
441                                 removed = avl_remove(avl, item);
442                                 
443                                 if ((*item == 0 && removed) ||
444                                     (*item == 1 && !removed))
445                                         s.removes.fail++;
446                                 
447                                 if (removed)
448                                         *item = 0;
449                                 
450                                 s.removes.total++;
451                                 break;
452                 }
453                 
454                 /* Periodically do an invariants check */
455                 if (ops / 10 > 0 && i % (ops / 10) == 0) {
456                         if (!avl_check_invariants(avl))
457                                 s.checks.fail++;
458                         s.checks.total++;
459                 }
460         }
461         
462         #if ANIMATE_RANDOM_ACCESS
463         printf("\r\033[K");
464         #endif
465         
466         avl_free(avl);
467         free(in_tree);
468         
469         ok1(print_pass_fail(&s.inserts, "Inserts"));
470         ok1(print_pass_fail(&s.lookups, "Lookups"));
471         ok1(print_pass_fail(&s.removes, "Removes"));
472         ok1(print_pass_fail(&s.checks,  "Invariants checks"));
473 }
474
475 int main(void)
476 {
477         plan_tests(18 * 3 + 4);
478         
479         benchmark(100000, 2, false, 0);
480         benchmark(100000, 2, false, 12345);
481         benchmark(100000, 2, false, 100001);
482         
483         printf("Running random access test\n");
484         test_random_access(12345, 1234567);
485         
486         return exit_status();
487 }