Tiny fix to stringmap's run.c
[ccan] / ccan / stringmap / test / run.c
1 #include "stringmap/stringmap.h"
2 #include "stringmap/stringmap.c"
3
4 #include "tap/tap.h"
5
6 static void test_trivial(void) {
7         stringmap(int) map = stringmap_new(NULL);
8         
9         ok1(stringmap_lookup(map, "one") == NULL);
10         *stringmap_enter(map, "one") = 1;
11         
12         ok1(stringmap_lookup(map, "two") == NULL);
13         *stringmap_enter(map, "two") = 2;
14         
15         ok1(stringmap_lookup(map, "three") == NULL);
16         *stringmap_enter(map, "three") = 3;
17         
18         ok1(stringmap_lookup(map, "four") == NULL);
19         *stringmap_enter(map, "four") = 4;
20         
21         ok1(*stringmap_lookup(map, "three") == 3);
22         ok1(*stringmap_lookup(map, "one") == 1);
23         ok1(*stringmap_lookup(map, "four") == 4);
24         ok1(*stringmap_lookup(map, "two") == 2);
25         
26         ok1(map.t.count == 4);
27         
28         stringmap_free(map);
29 }
30
31
32 static void scramble(void *base, size_t nmemb, size_t size) {
33    char *i = base;
34    char *o;
35    size_t sd;
36    for (;nmemb>1;nmemb--) {
37       o = i + size*(random()%nmemb);
38       for (sd=size;sd--;) {
39          char tmp = *o;
40          *o++ = *i;
41          *i++ = tmp;
42       }
43    }
44 }
45
46 //#define RANDOM_STRING_READABLE
47
48 static char *random_string(struct block_pool *bp) {
49         size_t len = random() % 100;
50         char *str = block_pool_alloc(bp, len+1);
51         char *i;
52         
53         for (i=str; len--; i++) {
54                 #ifndef RANDOM_STRING_READABLE
55                 char c = random();
56                 *i = c ? c : ' ';
57                 #else
58                 //only generate characters [32,126]
59                 char c = random()%95 + 32;
60                 *i = c;
61                 #endif
62         }
63         *i = 0;
64         
65         return str;
66 }
67
68 struct test_entry {
69         const char *str;
70         char *value;
71                 /* value is not a string, but a pointer to char marking that
72                    this key has been entered already. */
73 };
74
75 static int by_str(const void *ap, const void *bp) {
76         return strcmp(((struct test_entry*)ap)->str, ((struct test_entry*)bp)->str);
77 }
78
79 static void cull_duplicates(struct test_entry *entries, size_t *count) {
80         struct test_entry *i, *o, *e = entries + *count;
81         
82         qsort(entries, *count, sizeof(*entries), by_str);
83         
84         for (i=entries, o=entries; i<e;) {
85                 //skip repeated strings
86                 if (i>entries) {
87                         const char *last = i[-1].str;
88                         if (!strcmp(last, i->str)) {
89                                 do i++; while(i<e && !strcmp(last, i->str));
90                                 continue;
91                         }
92                 }
93                 
94                 //write all entries with the same value (should also have same string)
95                 {
96                         char *value = i->value;
97                         do *o++ = *i++; while(i<e && i->value == value);
98                 }
99         }
100         
101         *count = o-entries;
102 }
103
104 static int test_stringmap(size_t count, FILE *out) {
105         stringmap(char*) map = stringmap_new(NULL);
106         
107         #define print(tag, fmt, ...) do { \
108                         if (out) \
109                                 fprintf(out, tag fmt "\n", ##__VA_ARGS__); \
110                 } while(0)
111         #define err(...) do { \
112                         print("error: ", __VA_ARGS__); \
113                         goto fail; \
114                 } while(0)
115         #define debug(...) print("debug: ", __VA_ARGS__)
116         #define msg(...) print("info: ", __VA_ARGS__)
117         
118         struct block_pool *bp = block_pool_new(NULL);
119         struct test_entry *entries = block_pool_alloc(bp, sizeof(*entries) * count);
120         struct test_entry *i, *e = entries+count;
121         char *value_base = block_pool_alloc(bp, count), *value = value_base;
122         size_t unique_count = 0;
123         
124         //we use value to track whether an entry has been added or not
125         memset(value, 0, count);
126         
127         msg("Generating %zu test entries...", count);
128         
129         for (i=entries; i<e; value++) {
130                 char *str = random_string(bp);
131                 size_t same_count = (random()%5 ? random()%3 : random()%10) + 1;
132                 
133                 for (;same_count-- && i<e; i++) {
134                         i->str = str;
135                         i->value = value;
136                 }
137         }
138         
139         cull_duplicates(entries, &count);
140         e = entries+count;
141         scramble(entries, count, sizeof(*entries));
142         
143         msg("Inserting/looking up %zu entries...", count);
144         
145         for (i=entries; i<e; i++) {
146                 char **node;
147                 
148                 debug("Looking up %s", i->str);
149                 
150                 node = stringmap_lookup(map, i->str);
151                 
152                 if (!node) {
153                         if (*i->value)
154                                 err("Previously inserted entry not found");
155                         
156                         debug("Not found; entering");
157                         
158                         node = stringmap_enter(map, i->str);
159                         if (!node || strcmp(i->str, map.last->str))
160                                 err("Node not properly entered");
161                         *node = i->value;
162                         *i->value = 1; //mark that the entry is entered
163                         
164                         unique_count++;
165                 } else {
166                         if (strcmp(i->str, map.last->str))
167                                 err("lookup returned incorrect string");
168                         if (i->value != *node)
169                                 err("lookup returned incorrect value");
170                         if (!*i->value)
171                                 err("lookup returned bogus value");
172                 }
173         }
174         
175         if (map.t.count != unique_count)
176                 err("Map has incorrect count");
177         
178         printf("stringmap test passed after %zu inserts, %zu lookups (%zu total operations)\n", unique_count, (i-entries)-unique_count, i-entries);
179         
180         block_pool_free(bp);
181         stringmap_free(map);
182         return 1;
183
184 fail:
185         printf("stringmap test failed after %zu inserts, %zu lookups (%zu total operations)\n", unique_count, (i-entries)-unique_count, i-entries);
186         
187         block_pool_free(bp);
188         stringmap_free(map);
189         return 0;
190         
191         #undef print
192         #undef err
193         #undef debug
194         #undef msg
195 }
196
197 int main(void)
198 {
199         plan_tests(10);
200         
201         test_trivial();
202         ok1(test_stringmap(10000, NULL));
203         
204         return exit_status();
205 }