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