git.ozlabs.org Git - ccan/blob - ccan/stringmap/test/run.c

   1 #include <ccan/stringmap/stringmap.h>
   2 #include <ccan/stringmap/stringmap.c>
   3
   4 #include <ccan/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 = 0;
 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 }