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

typedef struct LRUCacheMember LRUCacheMember;

struct LRUCacheMember
{
    LRUCacheMember *next;
    LRUCacheMember *prev;
    int key;
    int value;
};

typedef struct LRUCache
{
    int capacity;
    int count;
    int hash_size;
    LRUCacheMember *head;
    LRUCacheMember *hash;
} LRUCache;

LRUCache *lRUCacheCreate(int capacity)
{
    LRUCache *cache = (LRUCache *)malloc(sizeof(LRUCache));
    cache->capacity = capacity;
    cache->count = 0;
    cache->head = NULL;
    cache->hash_size = 2 * capacity;
    cache->hash = (LRUCacheMember *)
        calloc(cache->hash_size, sizeof(LRUCacheMember));
    return cache;
}

/*
 ******************************************************************************
 */

static void
l2c_insert_before(LRUCacheMember *curr, LRUCacheMember *new)
{
    new->next = curr;
    new->prev = curr->prev;
    curr->prev->next = new;
    curr->prev = new;
}

static void
l2c_delete(LRUCacheMember *curr)
{
    curr->prev->next = curr->next;
    curr->next->prev = curr->prev;
}

/*
 ******************************************************************************
 */

static LRUCacheMember *
hash_enter(LRUCache *obj, int key, int value, int *found)
{
    int offset = key % obj->hash_size;

    while (obj->hash[offset].value != 0 &&
           obj->hash[offset].key != key)
    {
        offset++;
        offset %= obj->hash_size;
    }

    *found = obj->hash[offset].key == key;
    obj->hash[offset].key = key;
    obj->hash[offset].value = value;
    return (obj->hash + offset);
}

static LRUCacheMember *
hash_search(LRUCache *obj, int key)
{
    int offset = key % obj->hash_size;

    while (obj->hash[offset].value != 0 &&
           obj->hash[offset].key != key)
    {
        offset++;
        offset %= obj->hash_size;
    }

    if (obj->hash[offset].key == key && obj->hash[offset].value)
        return (obj->hash + offset);
    else
        return NULL;
}

/*
 ******************************************************************************
 */

int lRUCacheGet(LRUCache *obj, int key)
{
    LRUCacheMember *curr;

    if (obj->capacity == 0)
        return -1;

    curr = hash_search(obj, key);
    if (curr)
    {
        // retop
        if (curr != obj->head && obj->head)
        {
            l2c_delete(curr);
            l2c_insert_before(obj->head, curr);
            obj->head = curr;
        }
        return curr->value;
    }
    else
        return -1;
}

void lRUCachePut(LRUCache *obj, int key, int value)
{
    LRUCacheMember *member;
    int found = 0;

    if (obj->capacity == 0)
        return;

    member = hash_enter(obj, key, value, &found);

    // create if not found
    if (!found)
    {
        obj->count++;

        // put on top
        if (obj->head == NULL)
        {
            obj->head = member;
            member->next = member;
            member->prev = member;
        }
        else
        {
            l2c_insert_before(obj->head, member);
            obj->head = member;
        }

        // evict old if needed
        if (obj->count > obj->capacity)
        {
            LRUCacheMember *least = obj->head->prev;
            l2c_delete(least);
            least->value = 0;
            least->key = 0;
            obj->count--;
        }
    }
    else
    {
        member->value = value;
        // retop
        // if (member != obj->head)
        if (member != obj->head && obj->head)
        {
            l2c_delete(member);
            l2c_insert_before(obj->head, member);
            obj->head = member;
        }
    }
}

void lRUCacheFree(LRUCache *obj)
{
    free(obj->hash);
    free(obj);
}