git.ozlabs.org Git - ccan/blob - 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 }