[fb-resolver] / lru_cache_test.c

#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);
}