1 #include "stringmap/stringmap.h"
2 #include "stringmap/stringmap.c"
6 static void test_trivial(void) {
7 stringmap(int) map = stringmap_new(NULL);
9 ok1(stringmap_lookup(map, "") == NULL);
10 *stringmap_enter(map, "") = -1;
12 ok1(stringmap_lookup(map, "0") == NULL);
13 *stringmap_enter(map, "0") = 0;
15 ok1(stringmap_lookup(map, "one") == NULL);
16 *stringmap_enter(map, "one") = 1;
18 ok1(stringmap_lookup(map, "two") == NULL);
19 *stringmap_enter(map, "two") = 2;
21 ok1(stringmap_lookup(map, "three") == NULL);
22 *stringmap_enter(map, "three") = 3;
24 ok1(stringmap_lookup(map, "four") == NULL);
25 *stringmap_enter(map, "four") = 4;
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);
34 ok1(map.t.count == 6);
40 static void scramble(void *base, size_t nmemb, size_t size) {
44 for (;nmemb>1;nmemb--) {
45 o = i + size*(random()%nmemb);
54 //#define RANDOM_STRING_READABLE
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;
60 size_t len = random() % 10;
62 char *str = block_pool_alloc(bp, len);
67 for (i=str; len--; i++) {
68 #ifndef RANDOM_STRING_READABLE
72 //only generate characters a-z
73 char c = random()%26 + 'a';
82 //note: struct layout needs to match *stringmap(char*).last
87 /* value is not a string, but a pointer to char marking that
88 this key has been entered already. */
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;
98 return 0; //strings are the same
99 return -1; //a is shorter than b
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;
108 static int by_str(const void *a, const void *b) {
112 static void cull_duplicates(struct test_entry *entries, size_t *count) {
113 struct test_entry *i, *o, *e = entries + *count;
115 qsort(entries, *count, sizeof(*entries), by_str);
117 for (i=entries, o=entries; i<e;) {
118 //skip repeated strings
120 struct test_entry *last = &o[-1];
121 if (!tecmp(last, i)) {
122 do i++; while(i<e && !tecmp(last, i));
127 //write all entries with the same value (should also have same string)
129 char *value = i->value;
130 do *o++ = *i++; while(i<e && i->value == value);
137 #define print(tag, fmt, ...) do { \
139 fprintf(out, tag fmt "\n", ##__VA_ARGS__); \
141 #define err(...) do { \
142 print("error: ", __VA_ARGS__); \
145 //#define debug(...) print("debug: ", __VA_ARGS__)
146 #define debug(...) do {} while(0)
147 #define msg(...) print("info: ", __VA_ARGS__)
149 static int test_traverse(struct stringmap *map, struct test_entry *strings, size_t size, FILE *out) {
151 size_t stack_alloc = 16;
152 struct stringmap_node **stack = NULL;
153 struct stringmap_node *n;
155 #define check(lri) do { \
158 err("Fewer items in tree than counted"); \
159 if (tecmp(leaf, strings++)) \
160 err("%s leaf has incorrect string", lri ? "Left" : "Right"); \
162 #define check_left() check(0)
163 #define check_right() check(1)
165 if (map->count != size)
166 err("map->count != size");
171 if (map->count == 1) {
172 leaf = (struct test_entry*)map->root;
173 if (!tecmp(leaf, &strings[0]))
176 err("Only leaf in tree has incorrect value");
179 stack = malloc(sizeof(*stack) * stack_alloc);
184 while (!n->left_is_leaf) {
188 if (sp >= stack_alloc) {
189 stack_alloc += stack_alloc;
190 stack = realloc(stack, sizeof(*stack) * stack_alloc);
197 while (n->right_is_leaf) {
201 goto done; //we finished up the last entry
207 while (n->left_is_leaf) {
210 if (n->right_is_leaf) {
216 goto ascend_right; //sorry
224 err("More items in tree than counted");
239 static int test_stringmap(size_t count, FILE *out) {
240 stringmap(char*) map = stringmap_new(NULL);
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 = 0;
248 //we use value to track whether an entry has been added or not
249 memset(value, 0, count);
251 msg("Generating %zu test entries...", count);
253 for (i=entries; i<e; value++) {
255 char *str = random_string(bp, &len);
256 size_t same_count = (random()%5 ? random()%3 : random()%10) + 1;
258 for (;same_count-- && i<e; i++) {
265 cull_duplicates(entries, &count);
267 scramble(entries, count, sizeof(*entries));
269 msg("Inserting/looking up %zu entries...", count);
271 for (i=entries, o=entries; i<e; i++) {
274 debug("Looking up %s", i->str);
276 node = stringmap_lookup_n(map, i->str, i->len);
280 err("Previously inserted entry not found");
282 debug("Not found; entering %s", i->str);
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");
290 *i->value = 1; //mark that the entry is entered
292 //write this unique entry to the entry list to traverse later
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");
302 err("lookup returned bogus value");
306 unique_count = o-entries;
308 if (map.t.count != unique_count)
309 err("Map has incorrect count");
311 qsort(entries, unique_count, sizeof(*entries), by_str);
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");
317 printf("stringmap test passed after %zu inserts, %zu lookups (%zu total operations)\n",
318 unique_count, (i-entries)-unique_count, i-entries);
325 printf("stringmap test failed after %zu inserts, %zu lookups (%zu total operations)\n",
326 unique_count, (i-entries)-unique_count, i-entries);
343 ok1(test_stringmap(10000, stdout));
345 return exit_status();