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