initial overhaul of resolver

[fb-resolver] / lru_cache_test.c

diff --git a/lru_cache_test.c b/lru_cache_test.c
new file mode 100644 (file)
index 0000000..135ec34
--- /dev/null
+++ b/lru_cache_test.c
@@ -0,0 +1,198 @@
+#include <stdlib.h>
+#include <unistd.h>
+#include <stdio.h>
+#include <assert.h>
+
+/* wrap the whole module */
+#include "lru_cache.c"
+
+static unsigned int g_verbose_ = 0;
+
+struct test_kv_cache_entry {
+       struct lru_cache_entry lru_;
+
+       char key[128];
+       char value[128];
+};
+typedef struct test_kv_cache_entry kve_t;
+
+static
+void
+test_kv_hash_feed(lru_entry_t *entry, char **bufp, size_t *szp)
+{
+       struct test_kv_cache_entry *e = (struct test_kv_cache_entry *)entry;
+       *bufp = e->key;
+       *szp = sizeof e->key;
+}
+
+static
+int
+test_kv_cmp(lru_entry_t *a, lru_entry_t *b)
+{
+       kve_t *kv_a = (kve_t *)a,
+             *kv_b = (kve_t *)b;
+
+       return strcmp(kv_a->key, kv_b->key);
+}
+
+static
+void
+kv_dump(struct lru_cache *c)
+{
+       struct test_kv_cache_entry *kve;
+       lru_entry_t *e;
+       size_t i;
+
+       fprintf(stderr, "\nLRU, %zu entries\n", c->num_entries);
+
+       if (g_verbose_ == 0)
+               return;
+
+       fprintf(stderr, "-- hash --\n");
+       for (i = 0; i < c->hash_sz; i++) {
+               int s;
+               for (s = 0, e = c->hash[i].entry; e; e = e->hash_next, s++) {
+                       kve = (struct test_kv_cache_entry *)e;
+                       if (e != NULL) {
+                               if (e->hash_slot != i)
+                                       fprintf(stderr, "!!! sanity failure, entry has hash slot %zu, but is in slot %zu !!!\n", e->hash_slot, i);
+                               fprintf(stderr, "%*s[%zu]: (%p) '%s':'%s'\n", s, "", i, kve, kve->key, kve->value);
+                       }
+               }
+       }
+
+       fprintf(stderr, "-- queue --\n");
+       for (e = c->newest; e; e = e->next) {
+               kve = (struct test_kv_cache_entry *)e;
+               fprintf(stderr, "(%p) '%s':'%s'\n", kve, kve->key, kve->value);
+       }
+
+       fprintf(stderr, "\n");
+}
+
+void
+kv_genstats(lru_entry_t *e, size_t i, void *data)
+{
+       struct test_kv_cache_entry *kve = (struct test_kv_cache_entry *)e;
+       size_t *hash_depth = (size_t *)data;
+       (void)i, (void)kve;
+
+       hash_depth[e->hash_slot]++;
+}
+void
+kv_dumpstats(struct lru_cache *c, size_t *stats, size_t sz)
+{
+       size_t i;
+
+       for (i = 0; i < sz; i++)
+               fprintf(stderr, "slot %04zu: %zu (expect: %zu)\n", i, stats[i], c->hash[i].tally);
+}
+
+int
+main(int argc, char *argv[])
+{
+       const size_t hash_sz = 31;
+       const size_t capacity = 256;
+
+       struct lru_cache *cache;
+       struct test_kv_cache_entry *e, *r, m;
+       int i;
+
+       size_t *stats;
+
+       while ( (i = getopt(argc, argv, "vh")) != EOF ) {
+               switch (i) {
+                       case 'v':
+                               g_verbose_++;
+                               break;
+
+                       case 'h':
+                       default:
+                               exit(EXIT_FAILURE);
+               }
+       }
+
+       stats = malloc(hash_sz * sizeof *stats);
+       memset(stats, 0, hash_sz * sizeof *stats);
+
+       cache = lru_cache_new(hash_sz, capacity, test_kv_hash_feed, test_kv_cmp);
+       assert(cache != NULL);
+
+       kv_dump(cache);
+
+       e = malloc(sizeof *e);
+       assert(e != NULL);
+
+       strncpy(e->key, "key", sizeof e->key);
+       strncpy(e->value, "value", sizeof e->value);
+
+       lru_cache_insert(cache, (lru_entry_t *)e, (lru_entry_t **)&r);
+       assert(r == NULL);
+
+       kv_dump(cache);
+
+       memset(&m, 0, sizeof m);
+       strncpy(m.key, "key", sizeof e->key);
+       e = (struct test_kv_cache_entry *)lru_cache_locate(cache, (lru_entry_t *)&m);
+       assert(e != NULL);
+
+       lru_cache_extract(cache, (lru_entry_t *)e);
+       free(e);
+
+       kv_dump(cache);
+
+       for (i = 0; i < 500; i++) {
+               r = NULL;
+               e = malloc(sizeof *e);
+               assert(e != NULL);
+               memset(e, 0, sizeof *e);
+               snprintf(e->key, sizeof e->key, "test %d key", i);
+               snprintf(e->value, sizeof e->value, "some %d value", i);
+               lru_cache_insert(cache, (lru_entry_t *)e, (lru_entry_t **)&r);
+               if (r) {
+                       if (g_verbose_)
+                               fprintf(stderr, "freeing (%p) '%s':'%s'\n", r, r->key, r->value);
+                       free(r);
+               }
+       }
+
+       kv_dump(cache);
+
+       for (i = 0; i < 500; i += 3) {
+               memset(&m, 0, sizeof m);
+               snprintf(m.key, sizeof m.key, "test %d key", i);
+               e = (struct test_kv_cache_entry *)lru_cache_locate(cache, (lru_entry_t *)&m);
+               if (e == NULL) {
+                       if (g_verbose_)
+                               fprintf(stderr, "key %d was not cached\n", i);
+                       continue;
+               }
+               lru_cache_extract(cache, (lru_entry_t *)e);
+               if (g_verbose_)
+                       fprintf(stderr, "extracted '%s'\n", e->key);
+               free(e);
+       }
+
+       kv_dump(cache);
+
+       for (i = 0; i < 10; i += 2) {
+               e = malloc(sizeof *e);
+               assert(e != NULL);
+               memset(e, 0, sizeof *e);
+               snprintf(e->key, sizeof e->key, "new key %d", i);
+               snprintf(e->value, sizeof e->value, "new value %d", i);
+               lru_cache_insert(cache, (lru_entry_t *)e, (lru_entry_t **)&r);
+               if (r) {
+                       if (g_verbose_)
+                               fprintf(stderr, "freeing (%p) '%s':'%s'\n", r, r->key, r->value);
+                       free(r);
+               }
+       }
+
+       kv_dump(cache);
+
+       lru_cache_foreach(cache, kv_genstats, stats);
+       kv_dumpstats(cache, stats, hash_sz);
+
+       exit(EXIT_SUCCESS);
+}