git.squeep.com Git - fb-resolver/blob - lru_cache_test.c

   1 #include <stdlib.h>
   2 #include <unistd.h>
   3 #include <stdio.h>
   4 #include <assert.h>
   5
   6 /* wrap the whole module */
   7 #include "lru_cache.c"
   8
   9 static unsigned int g_verbose_ = 0;
  10
  11 struct test_kv_cache_entry {
  12         struct lru_cache_entry lru_;
  13
  14         char key[128];
  15         char value[128];
  16 };
  17 typedef struct test_kv_cache_entry kve_t;
  18
  19 static
  20 void
  21 test_kv_hash_feed(lru_entry_t *entry, char **bufp, size_t *szp)
  22 {
  23         struct test_kv_cache_entry *e = (struct test_kv_cache_entry *)entry;
  24         *bufp = e->key;
  25         *szp = sizeof e->key;
  26 }
  27
  28 static
  29 int
  30 test_kv_cmp(lru_entry_t *a, lru_entry_t *b)
  31 {
  32         kve_t *kv_a = (kve_t *)a,
  33               *kv_b = (kve_t *)b;
  34
  35         return strcmp(kv_a->key, kv_b->key);
  36 }
  37
  38 static
  39 void
  40 kv_dump(struct lru_cache *c)
  41 {
  42         struct test_kv_cache_entry *kve;
  43         lru_entry_t *e;
  44         size_t i;
  45
  46         fprintf(stderr, "\nLRU, %zu entries\n", c->num_entries);
  47
  48         if (g_verbose_ == 0)
  49                 return;
  50
  51         fprintf(stderr, "-- hash --\n");
  52         for (i = 0; i < c->hash_sz; i++) {
  53                 int s;
  54                 for (s = 0, e = c->hash[i].entry; e; e = e->hash_next, s++) {
  55                         kve = (struct test_kv_cache_entry *)e;
  56                         if (e != NULL) {
  57                                 if (e->hash_slot != i)
  58                                         fprintf(stderr, "!!! sanity failure, entry has hash slot %zu, but is in slot %zu !!!\n", e->hash_slot, i);
  59                                 fprintf(stderr, "%*s[%zu]: (%p) '%s':'%s'\n", s, "", i, kve, kve->key, kve->value);
  60                         }
  61                 }
  62         }
  63
  64         fprintf(stderr, "-- queue --\n");
  65         for (e = c->newest; e; e = e->next) {
  66                 kve = (struct test_kv_cache_entry *)e;
  67                 fprintf(stderr, "(%p) '%s':'%s'\n", kve, kve->key, kve->value);
  68         }
  69
  70         fprintf(stderr, "\n");
  71 }
  72
  73 void
  74 kv_genstats(lru_entry_t *e, size_t i, void *data)
  75 {
  76         struct test_kv_cache_entry *kve = (struct test_kv_cache_entry *)e;
  77         size_t *hash_depth = (size_t *)data;
  78         (void)i, (void)kve;
  79
  80         hash_depth[e->hash_slot]++;
  81 }
  82 void
  83 kv_dumpstats(struct lru_cache *c, size_t *stats, size_t sz)
  84 {
  85         size_t i;
  86
  87         for (i = 0; i < sz; i++)
  88                 fprintf(stderr, "slot %04zu: %zu (expect: %zu)\n", i, stats[i], c->hash[i].tally);
  89 }
  90
  91 int
  92 main(int argc, char *argv[])
  93 {
  94         const size_t hash_sz = 31;
  95         const size_t capacity = 256;
  96
  97         struct lru_cache *cache;
  98         struct test_kv_cache_entry *e, *r, m;
  99         int i;
 100
 101         size_t *stats;
 102
 103         while ( (i = getopt(argc, argv, "vh")) != EOF ) {
 104                 switch (i) {
 105                         case 'v':
 106                                 g_verbose_++;
 107                                 break;
 108
 109                         case 'h':
 110                         default:
 111                                 exit(EXIT_FAILURE);
 112                 }
 113         }
 114
 115         stats = malloc(hash_sz * sizeof *stats);
 116         memset(stats, 0, hash_sz * sizeof *stats);
 117
 118         cache = lru_cache_new(hash_sz, capacity, test_kv_hash_feed, test_kv_cmp);
 119         assert(cache != NULL);
 120
 121         kv_dump(cache);
 122
 123         e = malloc(sizeof *e);
 124         assert(e != NULL);
 125
 126         strncpy(e->key, "key", sizeof e->key);
 127         strncpy(e->value, "value", sizeof e->value);
 128
 129         lru_cache_insert(cache, (lru_entry_t *)e, (lru_entry_t **)&r);
 130         assert(r == NULL);
 131
 132         kv_dump(cache);
 133
 134         memset(&m, 0, sizeof m);
 135         strncpy(m.key, "key", sizeof e->key);
 136         e = (struct test_kv_cache_entry *)lru_cache_locate(cache, (lru_entry_t *)&m);
 137         assert(e != NULL);
 138
 139         lru_cache_extract(cache, (lru_entry_t *)e);
 140         free(e);
 141
 142         kv_dump(cache);
 143
 144         for (i = 0; i < 500; i++) {
 145                 r = NULL;
 146                 e = malloc(sizeof *e);
 147                 assert(e != NULL);
 148                 memset(e, 0, sizeof *e);
 149                 snprintf(e->key, sizeof e->key, "test %d key", i);
 150                 snprintf(e->value, sizeof e->value, "some %d value", i);
 151                 lru_cache_insert(cache, (lru_entry_t *)e, (lru_entry_t **)&r);
 152                 if (r) {
 153                         if (g_verbose_)
 154                                 fprintf(stderr, "freeing (%p) '%s':'%s'\n", r, r->key, r->value);
 155                         free(r);
 156                 }
 157         }
 158
 159         kv_dump(cache);
 160
 161         for (i = 0; i < 500; i += 3) {
 162                 memset(&m, 0, sizeof m);
 163                 snprintf(m.key, sizeof m.key, "test %d key", i);
 164                 e = (struct test_kv_cache_entry *)lru_cache_locate(cache, (lru_entry_t *)&m);
 165                 if (e == NULL) {
 166                         if (g_verbose_)
 167                                 fprintf(stderr, "key %d was not cached\n", i);
 168                         continue;
 169                 }
 170                 lru_cache_extract(cache, (lru_entry_t *)e);
 171                 if (g_verbose_)
 172                         fprintf(stderr, "extracted '%s'\n", e->key);
 173                 free(e);
 174         }
 175
 176         kv_dump(cache);
 177
 178         for (i = 0; i < 10; i += 2) {
 179                 e = malloc(sizeof *e);
 180                 assert(e != NULL);
 181                 memset(e, 0, sizeof *e);
 182                 snprintf(e->key, sizeof e->key, "new key %d", i);
 183                 snprintf(e->value, sizeof e->value, "new value %d", i);
 184                 lru_cache_insert(cache, (lru_entry_t *)e, (lru_entry_t **)&r);
 185                 if (r) {
 186                         if (g_verbose_)
 187                                 fprintf(stderr, "freeing (%p) '%s':'%s'\n", r, r->key, r->value);
 188                         free(r);
 189                 }
 190         }
 191
 192         kv_dump(cache);
 193
 194         lru_cache_foreach(cache, kv_genstats, stats);
 195         kv_dumpstats(cache, stats, hash_sz);
 196
 197         exit(EXIT_SUCCESS);
 198 }