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