rune: avoid shadowing var in test/run.c
[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_test_item(const void *ap, const void *bp)
136 {
137         const struct test_item *a = *(void**)ap, *b = *(void**)bp;
138         
139         if (a->key < b->key)
140                 return -1;
141         if (a->key > b->key)
142                 return 1;
143         
144         if (a->insert_id < b->insert_id)
145                 return -1;
146         if (a->insert_id > b->insert_id)
147                 return 1;
148         
149         return 0;
150 }
151
152 static bool test_insert_item(AVL *avl, struct test_item *item)
153 {
154         avl_insert(avl, &item->key, &item->value);
155         return true;
156 }
157
158 static bool test_lookup_item(const AVL *avl, const struct test_item *item)
159 {
160         return avl_member(avl, &item->key) && avl_lookup(avl, &item->key) == &item->value;
161 }
162
163 static bool test_remove_item(AVL *avl, struct test_item *item)
164 {
165         return avl_remove(avl, &item->key);
166 }
167
168 static void test_foreach(AVL *avl, struct test_item **test_items, int count)
169 {
170         AvlIter iter;
171         int     i;
172         
173         i = 0;
174         avl_foreach(iter, avl) {
175                 if (i >= count) {
176                         stats.excess++;
177                         continue;
178                 }
179                 if (iter.key == &test_items[i]->key && iter.value == &test_items[i]->value)
180                         stats.success++;
181                 else
182                         stats.incorrect++;
183                 i++;
184         }
185 }
186
187 static void test_foreach_reverse(AVL *avl, struct test_item **test_items, int count)
188 {
189         AvlIter iter;
190         int     i;
191         
192         i = count - 1;
193         avl_foreach_reverse(iter, avl) {
194                 if (i < 0) {
195                         stats.excess++;
196                         continue;
197                 }
198                 if (iter.key == &test_items[i]->key && iter.value == &test_items[i]->value)
199                         stats.success++;
200                 else
201                         stats.incorrect++;
202                 i--;
203         }
204 }
205
206 static void benchmark(size_t max_per_trial, size_t round_count, bool random_counts, int cardinality)
207 {
208         struct test_item **test_item;
209         struct test_item *test_item_array;
210         size_t i, o, count;
211         size_t round = 0;
212         
213         test_item = malloc(max_per_trial * sizeof(*test_item));
214         test_item_array = malloc(max_per_trial * sizeof(*test_item_array));
215         
216         if (!test_item || !test_item_array) {
217                 fail("Not enough memory for %zu keys per trial\n",
218                         max_per_trial);
219                 return;
220         }
221         
222         /* Initialize test_item pointers. */
223         for (i=0; i<max_per_trial; i++)
224                 test_item[i] = &test_item_array[i];
225         
226         /*
227          * If round_count is not zero, run round_count trials.
228          * Otherwise, run forever.
229          */
230         for (round = 1; round_count==0 || round <= round_count; round++) {
231                 AVL *avl;
232                 
233                 if (cardinality)
234                         printf("Round %zu (cardinality = %d)\n", round, cardinality);
235                 else
236                         printf("Round %zu\n", round);
237                 
238                 if (random_counts)
239                         count = rand32() % (max_per_trial+1);
240                 else
241                         count = max_per_trial;
242                 
243                 /*
244                  * Initialize test items by giving them sequential keys and
245                  * random values. Scramble them so the order of insertion
246                  * will be random.
247                  */
248                 for (i=0; i<count; i++) {
249                         test_item[i]->key   = rand32();
250                         test_item[i]->value = rand32();
251                         
252                         if (cardinality)
253                                 test_item[i]->key %= cardinality;
254                 }
255                 scramble(test_item, count, sizeof(*test_item));
256                 
257                 avl = avl_new(order_u32_noctx);
258                 
259                 clear_stats();
260                 printf("   Inserting %zu items...\n", count);
261                 for (i=0; i<count; i++) {
262                         if (test_insert_item(avl, test_item[i])) {
263                                 stats.success++;
264                                 test_item[i]->insert_id = i;
265                         } else {
266                                 printf("invariants check failed at insertion %zu\n", i);
267                                 stats.failed++;
268                         }
269                         
270                         /* Periodically do an invariants check */
271                         if (count / 10 > 0 && i % (count / 10) == 0) {
272                                 if (avl_check_invariants(avl))
273                                         stats.passed_invariants_checks++;
274                                 else
275                                         stats.failed_invariants_checks++;
276                         }
277                 }
278                 ok1(print_stats("Inserted", count));
279                 ok1(avl_check_invariants(avl));
280                 
281                 /* remove early duplicates, as they are shadowed in insertions. */
282                 qsort(test_item, count, sizeof(*test_item), compare_test_item);
283                 for (i = 0, o = 0; i < count;) {
284                         uint32_t k = test_item[i]->key;
285                         do i++; while (i < count && test_item[i]->key == k);
286                         test_item[o++] = test_item[i-1];
287                 }
288                 count = o;
289                 ok1(avl_count(avl) == count);
290                 
291                 scramble(test_item, count, sizeof(*test_item));
292                 
293                 printf("   Finding %zu items...\n", count);
294                 clear_stats();
295                 for (i=0; i<count; i++) {
296                         if (!test_lookup_item(avl, test_item[i]))
297                                 stats.missing++;
298                         else
299                                 stats.success++;
300                 }
301                 ok1(print_stats("Retrieved", count));
302                 
303                 qsort(test_item, count, sizeof(*test_item), compare_test_item);
304                 
305                 printf("   Traversing forward through %zu items...\n", count);
306                 clear_stats();
307                 test_foreach(avl, test_item, count);
308                 ok1(print_stats("Traversed", count));
309                 
310                 printf("   Traversing backward through %zu items...\n", count);
311                 clear_stats();
312                 test_foreach_reverse(avl, test_item, count);
313                 ok1(print_stats("Traversed", count));
314                 
315                 scramble(test_item, count, sizeof(*test_item));
316                 
317                 printf("   Deleting %zu items...\n", count);
318                 clear_stats();
319                 for (i=0; i<count; i++) {
320                         if (test_remove_item(avl, test_item[i]))
321                                 stats.success++;
322                         else
323                                 stats.missing++;
324                         
325                         /* Periodically do an invariants check */
326                         if (count / 10 > 0 && i % (count / 10) == 0) {
327                                 if (avl_check_invariants(avl))
328                                         stats.passed_invariants_checks++;
329                                 else
330                                         stats.failed_invariants_checks++;
331                         }
332                 }
333                 ok1(print_stats("Deleted", count));
334                 ok1(avl_count(avl) == 0);
335                 ok1(avl_check_invariants(avl));
336                 
337                 avl_free(avl);
338         }
339         
340         free(test_item);
341         free(test_item_array);
342 }
343
344 static int compare_ptr(const void *a, const void *b)
345 {
346         if (a < b)
347                 return -1;
348         if (a > b)
349                 return 1;
350         return 0;
351 }
352
353 struct fail_total {
354         int64_t fail;
355         int64_t total;
356 };
357
358 static bool print_pass_fail(struct fail_total *pf, const char *label)
359 {
360         long long fail  = pf->fail,
361                   total = pf->total;
362         
363         printf("%s:\t%lld / %lld\n", label, total - fail, total);
364         
365         return fail == 0;
366 }
367
368 static void test_random_access(uint32_t max, int64_t ops)
369 {
370         char       *in_tree;
371         AVL        *avl;
372         int64_t     i;
373         struct {
374                 struct fail_total
375                         inserts, lookups, removes, checks;
376         } s;
377         
378         #if ANIMATE_RANDOM_ACCESS
379         msec_t last_update, now;
380         msec_t interval = 100;
381         #endif
382         
383         memset(&s, 0, sizeof(s));
384         
385         in_tree = malloc(max);
386         memset(in_tree, 0, max);
387         
388         avl = avl_new(compare_ptr);
389         
390         #if ANIMATE_RANDOM_ACCESS
391         now = time_ms();
392         last_update = now - interval;
393         #endif
394         
395         for (i = 0; i < ops; i++) {
396                 char *item = &in_tree[rand32() % max];
397                 char *found;
398                 bool  inserted, removed;
399                 
400                 #if ANIMATE_RANDOM_ACCESS
401                 now = time_ms();
402                 if (now >= last_update + interval) {
403                         last_update = now;
404                         printf("\r%.2f%%\t%zu / %zu\033[K", (double)i * 100 / ops, avl_count(avl), max);
405                         fflush(stdout);
406                 }
407                 #endif
408                 
409                 switch (rand32() % 3) {
410                         case 0:
411                                 inserted = avl_insert(avl, item, item);
412                                 
413                                 if ((*item == 0 && !inserted) ||
414                                     (*item == 1 && inserted))
415                                         s.inserts.fail++;
416                                 
417                                 if (inserted)
418                                         *item = 1;
419                                 
420                                 s.inserts.total++;
421                                 break;
422                         
423                         case 1:
424                                 found = avl_lookup(avl, item);
425                                 
426                                 if ((*item == 0 && found != NULL) ||
427                                     (*item == 1 && found != item) ||
428                                     (avl_member(avl, item) != !!found))
429                                         s.lookups.fail++;
430                                 
431                                 s.lookups.total++;
432                                 break;
433                         
434                         case 2:
435                                 removed = avl_remove(avl, item);
436                                 
437                                 if ((*item == 0 && removed) ||
438                                     (*item == 1 && !removed))
439                                         s.removes.fail++;
440                                 
441                                 if (removed)
442                                         *item = 0;
443                                 
444                                 s.removes.total++;
445                                 break;
446                 }
447                 
448                 /* Periodically do an invariants check */
449                 if (ops / 10 > 0 && i % (ops / 10) == 0) {
450                         if (!avl_check_invariants(avl))
451                                 s.checks.fail++;
452                         s.checks.total++;
453                 }
454         }
455         
456         #if ANIMATE_RANDOM_ACCESS
457         printf("\r\033[K");
458         #endif
459         
460         avl_free(avl);
461         free(in_tree);
462         
463         ok1(print_pass_fail(&s.inserts, "Inserts"));
464         ok1(print_pass_fail(&s.lookups, "Lookups"));
465         ok1(print_pass_fail(&s.removes, "Removes"));
466         ok1(print_pass_fail(&s.checks,  "Invariants checks"));
467 }
468
469 int main(void)
470 {
471         plan_tests(18 * 3 + 4);
472         
473         benchmark(100000, 2, false, 0);
474         benchmark(100000, 2, false, 12345);
475         benchmark(100000, 2, false, 100001);
476         
477         printf("Running random access test\n");
478         test_random_access(12345, 1234567);
479         
480         return exit_status();
481 }