/*

 * Copyright (c) 2014-2016 DeNA Co., Ltd., Kazuho Oku

 *

 * Permission is hereby granted, free of charge, to any person obtaining a copy

 * of this software and associated documentation files (the "Software"), to

 * deal in the Software without restriction, including without limitation the

 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or

 * sell copies of the Software, and to permit persons to whom the Software is

 * furnished to do so, subject to the following conditions:

 *

 * The above copyright notice and this permission notice shall be included in

 * all copies or substantial portions of the Software.

 *

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE

 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING

 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS

 * IN THE SOFTWARE.

 */

#include <assert.h>

#include <pthread.h>

#include "khash.h"

#include "h2o/cache.h"

#include "h2o/linklist.h"

#include "h2o/memory.h"

#include "h2o/string_.h"

static h2o_cache_hashcode_t get_keyhash(h2o_cache_ref_t *ref);

static int is_equal(h2o_cache_ref_t *x, h2o_cache_ref_t *y);

KHASH_INIT(cache, h2o_cache_ref_t *, char, 0, get_keyhash, is_equal)

struct st_h2o_cache_t {

    int flags;

    khash_t(cache) * table;

    size_t size;

    size_t capacity;

    h2o_linklist_t lru;

    h2o_linklist_t age;

    uint64_t duration;

    void (*destroy_cb)(h2o_iovec_t value);

    pthread_mutex_t mutex; /* only used if (flags & H2O_CACHE_FLAG_MULTITHREADED) != 0 */

};

static h2o_cache_hashcode_t get_keyhash(h2o_cache_ref_t *ref)

{

    return ref->keyhash;

}

static int is_equal(h2o_cache_ref_t *x, h2o_cache_ref_t *y)

{

    return x->key.len == y->key.len && memcmp(x->key.base, y->key.base, x->key.len) == 0;

}

static void lock_cache(h2o_cache_t *cache)

{

    if ((cache->flags & H2O_CACHE_FLAG_MULTITHREADED) != 0)

        pthread_mutex_lock(&cache->mutex);

}

static void unlock_cache(h2o_cache_t *cache)

{

    if ((cache->flags & H2O_CACHE_FLAG_MULTITHREADED) != 0)

        pthread_mutex_unlock(&cache->mutex);

}

static void erase_ref(h2o_cache_t *cache, khiter_t iter, int reuse)

{

    h2o_cache_ref_t *ref = kh_key(cache->table, iter);

    if (!reuse)

        kh_del(cache, cache->table, iter);

    h2o_linklist_unlink(&ref->_lru_link);

    h2o_linklist_unlink(&ref->_age_link);

    cache->size -= ref->value.len;

    h2o_cache_release(cache, ref);

}

static int64_t get_timeleft(h2o_cache_t *cache, h2o_cache_ref_t *ref, uint64_t now)

{

    return (int64_t)(ref->at + cache->duration) - now;

}

static void purge(h2o_cache_t *cache, uint64_t now)

{

    /* by cache size */

    while (cache->capacity < cache->size) {

        h2o_cache_ref_t *last;

        assert(!h2o_linklist_is_empty(&cache->lru));

        last = H2O_STRUCT_FROM_MEMBER(h2o_cache_ref_t, _lru_link, cache->lru.next);

        erase_ref(cache, kh_get(cache, cache->table, last), 0);

    }

    /* by TTL */

    while (!h2o_linklist_is_empty(&cache->age)) {

        h2o_cache_ref_t *oldest = H2O_STRUCT_FROM_MEMBER(h2o_cache_ref_t, _age_link, cache->age.next);

        if (get_timeleft(cache, oldest, now) >= 0)

            break;

        erase_ref(cache, kh_get(cache, cache->table, oldest), 0);

    }

}

h2o_cache_hashcode_t h2o_cache_calchash(const char *s, size_t l)

{

    h2o_cache_hashcode_t h = 0;

    for (; l != 0; --l)

        h = (h << 5) - h + ((unsigned char *)s)[l - 1];

    return h;

}

h2o_cache_t *h2o_cache_create(int flags, size_t capacity, uint64_t duration, void (*destroy_cb)(h2o_iovec_t value))

{

    h2o_cache_t *cache = h2o_mem_alloc(sizeof(*cache));

    cache->flags = flags;

    cache->table = kh_init(cache);

    cache->size = 0;

    cache->capacity = capacity;

    h2o_linklist_init_anchor(&cache->lru);

    h2o_linklist_init_anchor(&cache->age);

    cache->duration = duration;

    cache->destroy_cb = destroy_cb;

    if ((cache->flags & H2O_CACHE_FLAG_MULTITHREADED) != 0)

        pthread_mutex_init(&cache->mutex, NULL);

    return cache;

}

void h2o_cache_destroy(h2o_cache_t *cache)

{

    h2o_cache_clear(cache);

    kh_destroy(cache, cache->table);

    if ((cache->flags & H2O_CACHE_FLAG_MULTITHREADED) != 0)

        pthread_mutex_destroy(&cache->mutex);

    free(cache);

}

void h2o_cache_clear(h2o_cache_t *cache)

{

    lock_cache(cache);

    while (!h2o_linklist_is_empty(&cache->lru)) {

        h2o_cache_ref_t *ref = H2O_STRUCT_FROM_MEMBER(h2o_cache_ref_t, _lru_link, cache->lru.next);

        erase_ref(cache, kh_get(cache, cache->table, ref), 0);

    }

    assert(h2o_linklist_is_linked(&cache->age));

    assert(kh_size(cache->table) == 0);

    assert(cache->size == 0);

    unlock_cache(cache);

}

h2o_cache_ref_t *h2o_cache_fetch(h2o_cache_t *cache, uint64_t now, h2o_iovec_t key, h2o_cache_hashcode_t keyhash)

{

    h2o_cache_ref_t search_key, *ref;

    khiter_t iter;

    int64_t timeleft;

    if (keyhash == 0)

        keyhash = h2o_cache_calchash(key.base, key.len);

    search_key.key = key;

    search_key.keyhash = keyhash;

    lock_cache(cache);

    purge(cache, now);

    if ((iter = kh_get(cache, cache->table, &search_key)) == kh_end(cache->table))

        goto NotFound;

    /* found */

    ref = kh_key(cache->table, iter);

    timeleft = get_timeleft(cache, ref, now);

    if (timeleft < 0)

        goto NotFound;

    if ((cache->flags & H2O_CACHE_FLAG_EARLY_UPDATE) != 0 && timeleft < 10 && !ref->_requested_early_update) {

        ref->_requested_early_update = 1;

        goto NotFound;

    }

    /* move the entry to the top of LRU */

    h2o_linklist_unlink(&ref->_lru_link);

    h2o_linklist_insert(&cache->lru, &ref->_lru_link);

    __sync_fetch_and_add(&ref->_refcnt, 1);

    /* unlock and return the found entry */

    unlock_cache(cache);

    return ref;

NotFound:

    unlock_cache(cache);

    return NULL;

}

void h2o_cache_release(h2o_cache_t *cache, h2o_cache_ref_t *ref)

{

    if (__sync_fetch_and_sub(&ref->_refcnt, 1) == 1) {

        assert(!h2o_linklist_is_linked(&ref->_lru_link));

        assert(!h2o_linklist_is_linked(&ref->_age_link));

        if (cache->destroy_cb != NULL)

            cache->destroy_cb(ref->value);

        free(ref->key.base);

        free(ref);

    }

}

int h2o_cache_set(h2o_cache_t *cache, uint64_t now, h2o_iovec_t key, h2o_cache_hashcode_t keyhash, h2o_iovec_t value)

{

    h2o_cache_ref_t *newref;

    khiter_t iter;

    int existed;

    if (keyhash == 0)

        keyhash = h2o_cache_calchash(key.base, key.len);

    /* create newref */

    newref = h2o_mem_alloc(sizeof(*newref));

    *newref = (h2o_cache_ref_t){h2o_strdup(NULL, key.base, key.len), keyhash, now, value, 0, {NULL}, {NULL}, 1};

    lock_cache(cache);

    /* set or replace the named value */

    iter = kh_get(cache, cache->table, newref);

    if (iter != kh_end(cache->table)) {

        erase_ref(cache, iter, 1);

        kh_key(cache->table, iter) = newref;

        existed = 1;

    } else {

        int unused;

        kh_put(cache, cache->table, newref, &unused);

        existed = 0;

    }

    h2o_linklist_insert(&cache->lru, &newref->_lru_link);

    h2o_linklist_insert(&cache->age, &newref->_age_link);

    cache->size += newref->value.len;

    purge(cache, now);

    unlock_cache(cache);

    return existed;

}

void h2o_cache_delete(h2o_cache_t *cache, uint64_t now, h2o_iovec_t key, h2o_cache_hashcode_t keyhash)

{

    h2o_cache_ref_t search_key;

    khiter_t iter;

    if (keyhash == 0)

        keyhash = h2o_cache_calchash(key.base, key.len);

    search_key.key = key;

    search_key.keyhash = keyhash;

    lock_cache(cache);

    purge(cache, now);

    if ((iter = kh_get(cache, cache->table, &search_key)) != kh_end(cache->table))

        erase_ref(cache, iter, 0);

    unlock_cache(cache);

}

size_t h2o_cache_get_capacity(h2o_cache_t *cache)

{

    return cache->capacity;

}

uint64_t h2o_cache_get_duration(h2o_cache_t *cache)

{

    return cache->duration;

}