/*-
 * Copyright (c) 2005 Michael Bushkov <bushman@rsu.ru>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 */

#include <sys/cdefs.h>
#include <sys/time.h>

#include <assert.h>
#include <stdlib.h>
#include <string.h>

#include "cacheplcs.h"
#include "debug.h"

static void cache_fifo_policy_update_item(struct cache_policy_ *,
        struct cache_policy_item_ *);
static void cache_lfu_policy_add_item(struct cache_policy_ *,
        struct cache_policy_item_ *);
static struct cache_policy_item_ * cache_lfu_policy_create_item(void);
static void cache_lfu_policy_destroy_item(struct cache_policy_item_ *);
static struct cache_policy_item_ *cache_lfu_policy_get_first_item(
        struct cache_policy_ *);
static struct cache_policy_item_ *cache_lfu_policy_get_last_item(
        struct cache_policy_ *);
static struct cache_policy_item_ *cache_lfu_policy_get_next_item(
        struct cache_policy_ *, struct cache_policy_item_ *);
static struct cache_policy_item_ *cache_lfu_policy_get_prev_item(
        struct cache_policy_ *, struct cache_policy_item_ *);
static void cache_lfu_policy_remove_item(struct cache_policy_ *,
        struct cache_policy_item_ *);
static void cache_lfu_policy_update_item(struct cache_policy_ *,
        struct cache_policy_item_ *);
static void cache_lru_policy_update_item(struct cache_policy_ *,
        struct cache_policy_item_ *);
static void cache_queue_policy_add_item(struct cache_policy_ *,
        struct cache_policy_item_ *);
static struct cache_policy_item_ * cache_queue_policy_create_item(void);
static void cache_queue_policy_destroy_item(struct cache_policy_item_ *);
static struct cache_policy_item_ *cache_queue_policy_get_first_item(
        struct cache_policy_ *);
static struct cache_policy_item_ *cache_queue_policy_get_last_item(
        struct cache_policy_ *);
static struct cache_policy_item_ *cache_queue_policy_get_next_item(
        struct cache_policy_ *, struct cache_policy_item_ *);
static struct cache_policy_item_ *cache_queue_policy_get_prev_item(
        struct cache_policy_ *, struct cache_policy_item_ *);
static void cache_queue_policy_remove_item(struct cache_policy_ *,
        struct cache_policy_item_ *);
static void destroy_cache_queue_policy(struct cache_queue_policy_ *);
static struct cache_queue_policy_ *init_cache_queue_policy(void);

/*
 * All cache_queue_policy_XXX functions below will be used to fill
 * the cache_queue_policy structure. They implement the most functionality of
 * LRU and FIFO policies. LRU and FIFO policies are actually the
 * cache_queue_policy_ with cache_update_item function changed.
 */
static struct cache_policy_item_ *
cache_queue_policy_create_item(void)
{
        struct cache_queue_policy_item_ *retval;

        TRACE_IN(cache_queue_policy_create_item);
        retval = calloc(1,
                sizeof(*retval));
        assert(retval != NULL);

        TRACE_OUT(cache_queue_policy_create_item);
        return ((struct cache_policy_item_ *)retval);
}

static void
cache_queue_policy_destroy_item(struct cache_policy_item_ *item)
{

        TRACE_IN(cache_queue_policy_destroy_item);
        assert(item != NULL);
        free(item);
        TRACE_OUT(cache_queue_policy_destroy_item);
}

static void
cache_queue_policy_add_item(struct cache_policy_ *policy,
        struct cache_policy_item_ *item)
{
        struct cache_queue_policy_ *queue_policy;
        struct cache_queue_policy_item_ *queue_item;

        TRACE_IN(cache_queue_policy_add_item);
        queue_policy = (struct cache_queue_policy_ *)policy;
        queue_item = (struct cache_queue_policy_item_ *)item;
        TAILQ_INSERT_TAIL(&queue_policy->head, queue_item, entries);
        TRACE_OUT(cache_queue_policy_add_item);
}

static void
cache_queue_policy_remove_item(struct cache_policy_ *policy,
        struct cache_policy_item_ *item)
{
        struct cache_queue_policy_ *queue_policy;
        struct cache_queue_policy_item_ *queue_item;

        TRACE_IN(cache_queue_policy_remove_item);
        queue_policy = (struct cache_queue_policy_ *)policy;
        queue_item = (struct cache_queue_policy_item_ *)item;
        TAILQ_REMOVE(&queue_policy->head, queue_item, entries);
        TRACE_OUT(cache_queue_policy_remove_item);
}

static struct cache_policy_item_ *
cache_queue_policy_get_first_item(struct cache_policy_ *policy)
{
        struct cache_queue_policy_ *queue_policy;

        TRACE_IN(cache_queue_policy_get_first_item);
        queue_policy = (struct cache_queue_policy_ *)policy;
        TRACE_OUT(cache_queue_policy_get_first_item);
        return ((struct cache_policy_item_ *)TAILQ_FIRST(&queue_policy->head));
}

static struct cache_policy_item_ *
cache_queue_policy_get_last_item(struct cache_policy_ *policy)
{
        struct cache_queue_policy_ *queue_policy;

        TRACE_IN(cache_queue_policy_get_last_item);
        queue_policy = (struct cache_queue_policy_ *)policy;
        TRACE_OUT(cache_queue_policy_get_last_item);
        return ((struct cache_policy_item_ *)TAILQ_LAST(&queue_policy->head,
                cache_queue_policy_head_));
}

static struct cache_policy_item_ *
cache_queue_policy_get_next_item(struct cache_policy_ *policy,
        struct cache_policy_item_ *item)
{
        struct cache_queue_policy_item_ *queue_item;

        TRACE_IN(cache_queue_policy_get_next_item);
        queue_item = (struct cache_queue_policy_item_ *)item;

        TRACE_OUT(cache_queue_policy_get_next_item);
        return ((struct cache_policy_item_ *)TAILQ_NEXT(queue_item, entries));
}

static struct cache_policy_item_ *
cache_queue_policy_get_prev_item(struct cache_policy_ *policy,
        struct cache_policy_item_ *item)
{
        struct cache_queue_policy_item_ *queue_item;

        TRACE_IN(cache_queue_policy_get_prev_item);
        queue_item = (struct cache_queue_policy_item_ *)item;

        TRACE_OUT(cache_queue_policy_get_prev_item);
        return ((struct cache_policy_item_ *)TAILQ_PREV(queue_item,
                cache_queue_policy_head_, entries));
}

/*
 * Initializes cache_queue_policy_ by filling the structure with the functions
 * pointers, defined above
 */
static struct cache_queue_policy_ *
init_cache_queue_policy(void)
{
        struct cache_queue_policy_      *retval;

        TRACE_IN(init_cache_queue_policy);
        retval = calloc(1,
                sizeof(*retval));
        assert(retval != NULL);

        retval->parent_data.create_item_func = cache_queue_policy_create_item;
        retval->parent_data.destroy_item_func = cache_queue_policy_destroy_item;

        retval->parent_data.add_item_func = cache_queue_policy_add_item;
        retval->parent_data.remove_item_func = cache_queue_policy_remove_item;

        retval->parent_data.get_first_item_func =
                cache_queue_policy_get_first_item;
        retval->parent_data.get_last_item_func =
                cache_queue_policy_get_last_item;
        retval->parent_data.get_next_item_func =
                cache_queue_policy_get_next_item;
        retval->parent_data.get_prev_item_func =
                cache_queue_policy_get_prev_item;

        TAILQ_INIT(&retval->head);
        TRACE_OUT(init_cache_queue_policy);
        return (retval);
}

static void
destroy_cache_queue_policy(struct cache_queue_policy_ *queue_policy)
{
        struct cache_queue_policy_item_ *queue_item;

        TRACE_IN(destroy_cache_queue_policy);
        while (!TAILQ_EMPTY(&queue_policy->head)) {
                queue_item = TAILQ_FIRST(&queue_policy->head);
                TAILQ_REMOVE(&queue_policy->head, queue_item, entries);
                cache_queue_policy_destroy_item(
                        (struct cache_policy_item_ *)queue_item);
        }
        free(queue_policy);
        TRACE_OUT(destroy_cache_queue_policy);
}

/*
 * Makes cache_queue_policy_ behave like FIFO policy - we don't do anything,
 * when the cache element is updated. So it always stays in its initial
 * position in the queue - that is exactly the FIFO functionality.
 */
static void
cache_fifo_policy_update_item(struct cache_policy_ *policy,
        struct cache_policy_item_ *item)
{

        TRACE_IN(cache_fifo_policy_update_item);
        /* policy and item arguments are ignored */
        TRACE_OUT(cache_fifo_policy_update_item);
}

struct cache_policy_ *
init_cache_fifo_policy(void)
{
        struct cache_queue_policy_ *retval;

        TRACE_IN(init_cache_fifo_policy);
        retval = init_cache_queue_policy();
        retval->parent_data.update_item_func = cache_fifo_policy_update_item;

        TRACE_OUT(init_cache_fifo_policy);
        return ((struct cache_policy_ *)retval);
}

void
destroy_cache_fifo_policy(struct cache_policy_ *policy)
{
        struct cache_queue_policy_      *queue_policy;

        TRACE_IN(destroy_cache_fifo_policy);
        queue_policy = (struct cache_queue_policy_ *)policy;
        destroy_cache_queue_policy(queue_policy);
        TRACE_OUT(destroy_cache_fifo_policy);
}

/*
 * Makes cache_queue_policy_ behave like LRU policy. On each update, cache
 * element is moved to the end of the queue - so it would be deleted in last
 * turn. That is exactly the LRU policy functionality.
 */
static void
cache_lru_policy_update_item(struct cache_policy_ *policy,
        struct cache_policy_item_ *item)
{
        struct cache_queue_policy_ *queue_policy;
        struct cache_queue_policy_item_ *queue_item;

        TRACE_IN(cache_lru_policy_update_item);
        queue_policy = (struct cache_queue_policy_ *)policy;
        queue_item = (struct cache_queue_policy_item_ *)item;

        TAILQ_REMOVE(&queue_policy->head, queue_item, entries);
        TAILQ_INSERT_TAIL(&queue_policy->head, queue_item, entries);
        TRACE_OUT(cache_lru_policy_update_item);
}

struct cache_policy_ *
init_cache_lru_policy(void)
{
        struct cache_queue_policy_ *retval;

        TRACE_IN(init_cache_lru_policy);
        retval = init_cache_queue_policy();
        retval->parent_data.update_item_func = cache_lru_policy_update_item;

        TRACE_OUT(init_cache_lru_policy);
        return ((struct cache_policy_ *)retval);
}

void
destroy_cache_lru_policy(struct cache_policy_ *policy)
{
        struct cache_queue_policy_      *queue_policy;

        TRACE_IN(destroy_cache_lru_policy);
        queue_policy = (struct cache_queue_policy_ *)policy;
        destroy_cache_queue_policy(queue_policy);
        TRACE_OUT(destroy_cache_lru_policy);
}

/*
 * LFU (least frequently used) policy implementation differs much from the
 * LRU and FIFO (both based on cache_queue_policy_). Almost all cache_policy_
 * functions are implemented specifically for this policy. The idea of this
 * policy is to represent frequency (real number) as the integer number and
 * use it as the index in the array. Each array's element is
 * the list of elements. For example, if we have the 100-elements
 * array for this policy, the elements with frequency 0.1 (calls per-second)
 * would be in 10th element of the array.
 */
static struct cache_policy_item_ *
cache_lfu_policy_create_item(void)
{
        struct cache_lfu_policy_item_ *retval;

        TRACE_IN(cache_lfu_policy_create_item);
        retval = calloc(1,
                sizeof(*retval));
        assert(retval != NULL);

        TRACE_OUT(cache_lfu_policy_create_item);
        return ((struct cache_policy_item_ *)retval);
}

static void
cache_lfu_policy_destroy_item(struct cache_policy_item_ *item)
{

        TRACE_IN(cache_lfu_policy_destroy_item);
        assert(item != NULL);
        free(item);
        TRACE_OUT(cache_lfu_policy_destroy_item);
}

/*
 * When placed in the LFU policy queue for the first time, the maximum
 * frequency is assigned to the element
 */
static void
cache_lfu_policy_add_item(struct cache_policy_ *policy,
        struct cache_policy_item_ *item)
{
        struct cache_lfu_policy_ *lfu_policy;
        struct cache_lfu_policy_item_ *lfu_item;

        TRACE_IN(cache_lfu_policy_add_item);
        lfu_policy = (struct cache_lfu_policy_ *)policy;
        lfu_item = (struct cache_lfu_policy_item_ *)item;

        lfu_item->frequency = CACHELIB_MAX_FREQUENCY - 1;
        TAILQ_INSERT_HEAD(&(lfu_policy->groups[CACHELIB_MAX_FREQUENCY - 1]),
                lfu_item, entries);
        TRACE_OUT(cache_lfu_policy_add_item);
}

/*
 * On each update the frequency of the element is recalculated and, if it
 * changed, the element would be moved to the another place in the array.
 */
static void
cache_lfu_policy_update_item(struct cache_policy_ *policy,
        struct cache_policy_item_ *item)
{
        struct cache_lfu_policy_ *lfu_policy;
        struct cache_lfu_policy_item_ *lfu_item;
        int index;

        TRACE_IN(cache_lfu_policy_update_item);
        lfu_policy = (struct cache_lfu_policy_ *)policy;
        lfu_item = (struct cache_lfu_policy_item_ *)item;

        /*
         * We calculate the square of the request_count to avoid grouping of
         * all elements at the start of the array (for example, if array size is
         * 100 and most of its elements has frequency below the 0.01, they
         * all would be grouped in the first array's position). Other
         * techniques should be used here later to ensure, that elements are
         * equally distributed  in the array and not grouped in its beginning.
         */
        if (lfu_item->parent_data.last_request_time.tv_sec !=
                lfu_item->parent_data.creation_time.tv_sec) {
                index = ((double)lfu_item->parent_data.request_count *
                        (double)lfu_item->parent_data.request_count /
                        (lfu_item->parent_data.last_request_time.tv_sec -
                            lfu_item->parent_data.creation_time.tv_sec + 1)) *
                            CACHELIB_MAX_FREQUENCY;
                if (index >= CACHELIB_MAX_FREQUENCY)
                        index = CACHELIB_MAX_FREQUENCY - 1;
        } else
                index = CACHELIB_MAX_FREQUENCY - 1;

        TAILQ_REMOVE(&(lfu_policy->groups[lfu_item->frequency]), lfu_item,
                entries);
        lfu_item->frequency = index;
        TAILQ_INSERT_HEAD(&(lfu_policy->groups[index]), lfu_item, entries);

        TRACE_OUT(cache_lfu_policy_update_item);
}

static void
cache_lfu_policy_remove_item(struct cache_policy_ *policy,
        struct cache_policy_item_ *item)
{
        struct cache_lfu_policy_ *lfu_policy;
        struct cache_lfu_policy_item_ *lfu_item;

        TRACE_IN(cache_lfu_policy_remove_item);
        lfu_policy = (struct cache_lfu_policy_ *)policy;
        lfu_item = (struct cache_lfu_policy_item_ *)item;

        TAILQ_REMOVE(&(lfu_policy->groups[lfu_item->frequency]), lfu_item,
                entries);
        TRACE_OUT(cache_lfu_policy_remove_item);
}

static struct cache_policy_item_ *
cache_lfu_policy_get_first_item(struct cache_policy_ *policy)
{
        struct cache_lfu_policy_ *lfu_policy;
        struct cache_lfu_policy_item_ *lfu_item;
        int i;

        TRACE_IN(cache_lfu_policy_get_first_item);
        lfu_item = NULL;
        lfu_policy = (struct cache_lfu_policy_ *)policy;
        for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i)
                if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) {
                        lfu_item = TAILQ_FIRST(&(lfu_policy->groups[i]));
                        break;
                }

        TRACE_OUT(cache_lfu_policy_get_first_item);
        return ((struct cache_policy_item_ *)lfu_item);
}

static struct cache_policy_item_ *
cache_lfu_policy_get_last_item(struct cache_policy_ *policy)
{
        struct cache_lfu_policy_ *lfu_policy;
        struct cache_lfu_policy_item_ *lfu_item;
        int i;

        TRACE_IN(cache_lfu_policy_get_last_item);
        lfu_item = NULL;
        lfu_policy = (struct cache_lfu_policy_ *)policy;
        for (i = CACHELIB_MAX_FREQUENCY - 1; i >= 0; --i)
                if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) {
                        lfu_item = TAILQ_LAST(&(lfu_policy->groups[i]),
                                cache_lfu_policy_group_);
                        break;
                }

        TRACE_OUT(cache_lfu_policy_get_last_item);
        return ((struct cache_policy_item_ *)lfu_item);
}

static struct cache_policy_item_ *
cache_lfu_policy_get_next_item(struct cache_policy_ *policy,
        struct cache_policy_item_ *item)
{
        struct cache_lfu_policy_ *lfu_policy;
        struct cache_lfu_policy_item_ *lfu_item;
        int i;

        TRACE_IN(cache_lfu_policy_get_next_item);
        lfu_policy = (struct cache_lfu_policy_ *)policy;
        lfu_item = TAILQ_NEXT((struct cache_lfu_policy_item_ *)item, entries);
        if (lfu_item == NULL)
        {
                for (i = ((struct cache_lfu_policy_item_ *)item)->frequency + 1;
                        i < CACHELIB_MAX_FREQUENCY; ++i) {
                        if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) {
                            lfu_item = TAILQ_FIRST(&(lfu_policy->groups[i]));
                            break;
                        }
                }
        }

        TRACE_OUT(cache_lfu_policy_get_next_item);
        return ((struct cache_policy_item_ *)lfu_item);
}

static struct cache_policy_item_ *
cache_lfu_policy_get_prev_item(struct cache_policy_ *policy,
        struct cache_policy_item_ *item)
{
        struct cache_lfu_policy_ *lfu_policy;
        struct cache_lfu_policy_item_ *lfu_item;
        int i;

        TRACE_IN(cache_lfu_policy_get_prev_item);
        lfu_policy = (struct cache_lfu_policy_ *)policy;
        lfu_item = TAILQ_PREV((struct cache_lfu_policy_item_ *)item,
                cache_lfu_policy_group_, entries);
        if (lfu_item == NULL)
        {
                for (i = ((struct cache_lfu_policy_item_ *)item)->frequency - 1;
                        i >= 0; --i)
                        if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) {
                                lfu_item = TAILQ_LAST(&(lfu_policy->groups[i]),
                                        cache_lfu_policy_group_);
                                break;
                }
        }

        TRACE_OUT(cache_lfu_policy_get_prev_item);
        return ((struct cache_policy_item_ *)lfu_item);
}

/*
 * Initializes the cache_policy_ structure by filling it with appropriate
 * functions pointers
 */
struct cache_policy_ *
init_cache_lfu_policy(void)
{
        int i;
        struct cache_lfu_policy_ *retval;

        TRACE_IN(init_cache_lfu_policy);
        retval = calloc(1,
                sizeof(*retval));
        assert(retval != NULL);

        retval->parent_data.create_item_func = cache_lfu_policy_create_item;
        retval->parent_data.destroy_item_func = cache_lfu_policy_destroy_item;

        retval->parent_data.add_item_func = cache_lfu_policy_add_item;
        retval->parent_data.update_item_func = cache_lfu_policy_update_item;
        retval->parent_data.remove_item_func = cache_lfu_policy_remove_item;

        retval->parent_data.get_first_item_func =
                cache_lfu_policy_get_first_item;
        retval->parent_data.get_last_item_func =
                cache_lfu_policy_get_last_item;
        retval->parent_data.get_next_item_func =
                cache_lfu_policy_get_next_item;
        retval->parent_data.get_prev_item_func =
                cache_lfu_policy_get_prev_item;

        for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i)
                TAILQ_INIT(&(retval->groups[i]));

        TRACE_OUT(init_cache_lfu_policy);
        return ((struct cache_policy_ *)retval);
}

void
destroy_cache_lfu_policy(struct cache_policy_ *policy)
{
        int i;
        struct cache_lfu_policy_ *lfu_policy;
        struct cache_lfu_policy_item_ *lfu_item;

        TRACE_IN(destroy_cache_lfu_policy);
        lfu_policy = (struct cache_lfu_policy_ *)policy;
        for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i) {
                while (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) {
                        lfu_item = TAILQ_FIRST(&(lfu_policy->groups[i]));
                        TAILQ_REMOVE(&(lfu_policy->groups[i]), lfu_item,
                                entries);
                        cache_lfu_policy_destroy_item(
                                (struct cache_policy_item_ *)lfu_item);
                }
        }
        free(policy);
        TRACE_OUT(destroy_cache_lfu_policy);
}