merge
[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 *ap, const struct test_entry *bp) {
92         const unsigned char *a = (unsigned char*)ap->str, *ae = a+ap->len;
93         const unsigned char *b = (unsigned char*)bp->str, *be = b+bp->len;
94         
95         for (;;a++, b++) {
96                 if (a >= ae) {
97                         if (b >= be)
98                                 return 0; //strings are the same
99                         return -1; //a is shorter than b
100                 }
101                 if (b >= be)
102                         return 1; //b is shorter than a
103                 if (*a != *b) //there is a differing character
104                         return (unsigned int)*a - (unsigned int)*b;
105         }
106 }
107
108 static int by_str(const void *a, const void *b) {
109         return tecmp(a, b);
110 }
111
112 static void cull_duplicates(struct test_entry *entries, size_t *count) {
113         struct test_entry *i, *o, *e = entries + *count;
114         
115         qsort(entries, *count, sizeof(*entries), by_str);
116         
117         for (i=entries, o=entries; i<e;) {
118                 //skip repeated strings
119                 if (o>entries) {
120                         struct test_entry *last = &o[-1];
121                         if (!tecmp(last, i)) {
122                                 do i++; while(i<e && !tecmp(last, i));
123                                 continue;
124                         }
125                 }
126                 
127                 //write all entries with the same value (should also have same string)
128                 {
129                         char *value = i->value;
130                         do *o++ = *i++; while(i<e && i->value == value);
131                 }
132         }
133         
134         *count = o-entries;
135 }
136
137 #define print(tag, fmt, ...) do { \
138                 if (out) \
139                         fprintf(out, tag fmt "\n", ##__VA_ARGS__); \
140         } while(0)
141 #define err(...) do { \
142                 print("error: ", __VA_ARGS__); \
143                 goto fail; \
144         } while(0)
145 //#define debug(...) print("debug: ", __VA_ARGS__)
146 #define debug(...) do {} while(0)
147 #define msg(...) print("info: ", __VA_ARGS__)
148
149 static int test_traverse(struct stringmap *map, struct test_entry *strings, size_t size, FILE *out) {
150         size_t sp = 0;
151         size_t stack_alloc = 16;
152         struct stringmap_node **stack = NULL;
153         struct stringmap_node *n;
154         void *leaf;
155         #define check(lri) do { \
156                         leaf = n->lr[lri]; \
157                         if (!size--) \
158                                 err("Fewer items in tree than counted"); \
159                         if (tecmp(leaf, strings++)) \
160                                 err("%s leaf has incorrect string", lri ? "Left" : "Right"); \
161                 } while(0)
162         #define check_left() check(0)
163         #define check_right() check(1)
164         
165         if (map->count != size)
166                 err("map->count != size");
167         
168         if (map->count == 0)
169                 return 1;
170         
171         if (map->count == 1) {
172                 leaf = (struct test_entry*)map->root;
173                 if (!tecmp(leaf, &strings[0]))
174                         return 1;
175                 else
176                         err("Only leaf in tree has incorrect value");
177         }
178         
179         stack = malloc(sizeof(*stack) * stack_alloc);
180         n = map->root;
181         
182         for (;;) {
183                 //descend left
184                 while (!n->left_is_leaf) {
185                         stack[sp++] = n;
186                         n = n->lr[0];
187                         
188                         if (sp >= stack_alloc) {
189                                 stack_alloc += stack_alloc;
190                                 stack = realloc(stack, sizeof(*stack) * stack_alloc);
191                         }
192                 }
193                 
194                 check_left();
195                 
196         ascend_right:
197                 while (n->right_is_leaf) {
198                         check_right();
199                         
200                         if (!sp)
201                                 goto done; //we finished up the last entry
202                         n = stack[--sp];
203                 }
204                 
205                 //descend right
206                 n = n->lr[1];
207                 while (n->left_is_leaf) {
208                         check_left();
209                         
210                         if (n->right_is_leaf) {
211                                 check_right();
212                                 
213                                 if (!sp)
214                                         goto done;
215                                 n = stack[--sp];
216                                 goto ascend_right; //sorry
217                         }
218                         n = n->lr[1];
219                 }
220         }
221         
222 done:
223         if (size != 0)
224                 err("More items in tree than counted");
225         
226         free(stack);
227         return 1;
228         
229 fail:
230         if (stack)
231                 free(stack);
232         return 0;
233         
234         #undef check
235         #undef check_left
236         #undef check_right
237 }
238
239 static int test_stringmap(size_t count, FILE *out) {
240         stringmap(char*) map = stringmap_new(NULL);
241         
242         struct block_pool *bp = block_pool_new(NULL);
243         struct test_entry *entries = block_pool_alloc(bp, sizeof(*entries) * count);
244         struct test_entry *i, *e = entries+count, *o;
245         char *value_base = block_pool_alloc(bp, count), *value = value_base;
246         size_t unique_count;
247         
248         //we use value to track whether an entry has been added or not
249         memset(value, 0, count);
250         
251         msg("Generating %zu test entries...", count);
252         
253         for (i=entries; i<e; value++) {
254                 size_t len;
255                 char *str = random_string(bp, &len);
256                 size_t same_count = (random()%5 ? random()%3 : random()%10) + 1;
257                 
258                 for (;same_count-- && i<e; i++) {
259                         i->str = str;
260                         i->len = len;
261                         i->value = value;
262                 }
263         }
264         
265         cull_duplicates(entries, &count);
266         e = entries+count;
267         scramble(entries, count, sizeof(*entries));
268         
269         msg("Inserting/looking up %zu entries...", count);
270         
271         for (i=entries, o=entries; i<e; i++) {
272                 char **node;
273                 
274                 debug("Looking up %s", i->str);
275                 
276                 node = stringmap_lookup_n(map, i->str, i->len);
277                 
278                 if (!node) {
279                         if (*i->value)
280                                 err("Previously inserted entry not found");
281                         
282                         debug("Not found; entering %s", i->str);
283                         
284                         node = stringmap_enter_n(map, i->str, i->len);
285                         if (!node || tecmp(i, (void*)map.last))
286                                 err("Node not properly entered");
287                         if (map.last->str[map.last->len])
288                                 err("Entered string not zero-terminated");
289                         *node = i->value;
290                         *i->value = 1; //mark that the entry is entered
291                         
292                         //write this unique entry to the entry list to traverse later
293                         *o++ = *i;
294                 } else {
295                         if (tecmp(i, (void*)map.last))
296                                 err("lookup returned incorrect string");
297                         if (map.last->str[map.last->len])
298                                 err("Looked-up string not zero-terminated");
299                         if (i->value != *node)
300                                 err("lookup returned incorrect value");
301                         if (!*i->value)
302                                 err("lookup returned bogus value");
303                 }
304         }
305         
306         unique_count = o-entries;
307         
308         if (map.t.count != unique_count)
309                 err("Map has incorrect count");
310         
311         qsort(entries, unique_count, sizeof(*entries), by_str);
312         
313         msg("Traversing forward through %zu items", unique_count);      
314         if (!test_traverse(&map.t, entries, unique_count, out))
315                 err("Traversal does not produce the strings in order");
316         
317         printf("stringmap test passed after %zu inserts, %zu lookups (%zu total operations)\n",
318                 unique_count, (i-entries)-unique_count, i-entries);
319         
320         block_pool_free(bp);
321         stringmap_free(map);
322         return 1;
323
324 fail:
325         printf("stringmap test failed after %zu inserts, %zu lookups (%zu total operations)\n",
326                 unique_count, (i-entries)-unique_count, i-entries);
327         
328         block_pool_free(bp);
329         stringmap_free(map);
330         return 0;
331 }
332
333 #undef print
334 #undef err
335 #undef debug
336 #undef msg
337
338 int main(void)
339 {
340         plan_tests(14);
341         
342         test_trivial();
343         ok1(test_stringmap(10000, stdout));
344         
345         return exit_status();
346 }