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

static int getHashKey(LruCache *lru , char key)
{
    //printf("%s : push -> %d\n" , __func__ , ((int)key % lru->CacheCapacity));
    return ((int)key % lru->CacheCapacity);
}

static void removeEntryFromHash(LruCache *lru , CacheEntry *entry)
{
    if(NULL == entry)
    {
        return ;
    }
    if(entry->HashPre != NULL)
    {
        entry->HashPre->HashNext = entry->HashNext;
    }
    else
    {
        int idx = getHashKey(lru , entry->key);
        lru->HashArray[idx] = entry->HashNext;
        if(NULL != entry->HashNext)
        {
            entry->HashNext->HashPre = lru->HashArray[idx];
        }
    }
}


static CacheEntry* newCacheEntry(char key , char value)
{
    CacheEntry *entry = (CacheEntry *)malloc(sizeof(CacheEntry));
    entry->key   = key;
    entry->value = value;

    entry->ListNext = entry->ListPre = NULL;
    entry->HashNext = entry->HashPre = NULL;

    return entry;
}

static void removeEntryFromLru(LruCache *lru , CacheEntry *entry)
{
    if(NULL == lru || NULL == entry)
    {
        return ;
    }
    removeEntryFromHash(lru , entry);
    if(NULL == entry->ListPre && NULL == entry->ListNext)
    {
        free(entry);
        entry = NULL;
        lru->ListBegin = lru->ListEnd = NULL;
    }
    else if(NULL == entry->ListPre)
    {
        lru->ListBegin = entry->ListNext;
        lru->ListBegin->ListPre = NULL;
        free(entry);
        entry = NULL;
    }
    else if(NULL == entry->ListNext)
    {
        lru->ListEnd = entry->ListPre;
        lru->ListEnd->ListNext = NULL;
        free(entry);
        entry = NULL;
    }
    else
    {
        entry->ListPre->ListNext = entry->ListNext;
        entry->ListNext->ListPre = entry->ListPre;
        free(entry);
        entry = NULL;
    }
    lru->NowCapacity -= 1;

    return ;
}

static void removeEndEntryFromLru(LruCache *lru)
{
    if(NULL != lru)
    {
        removeEntryFromLru(lru , lru->ListEnd);
    }
}


static void addEntryToHash(LruCache *lru , CacheEntry *entry)
{
    if(NULL == lru || NULL == entry)
    {
        return ;
    }
    CacheEntry* hashBegin = lru->HashArray[getHashKey(lru , entry->key)];
    if(NULL == hashBegin)
    {
        lru->HashArray[getHashKey(lru , entry->key)] = entry;
        entry->HashPre = lru->HashArray[getHashKey(lru , entry->key)];
    }
    else
    {
        entry->HashNext = hashBegin;
        hashBegin->HashPre = entry;

        lru->HashArray[getHashKey(lru , entry->key)] = entry;
    }
}

static void addEntryInLruBegin(LruCache *lru , CacheEntry *entry)
{
    if(NULL == lru || NULL == entry)
    {
        return ;
    }
    CacheEntry* lruBegin = lru->ListBegin;

    if(NULL == lruBegin)
    {
        lru->ListBegin = lru->ListEnd = entry;
    }
    else
    {
        lruBegin->ListPre = entry;
        entry->ListNext   = lruBegin;
        lru->ListBegin =  entry;
    }
    lru->NowCapacity += 1;
    addEntryToHash(lru , entry);
}
/*
 * 通过哈希寻找key
 */
CacheEntry* findKey(LruCache *lru , char key)
{
    static int a = 0;

    CacheEntry *listHead = lru->HashArray[getHashKey(lru , key)];

    if(NULL == listHead)
    {
        return NULL;
    }
    CacheEntry *ptr = listHead;
    while(NULL != ptr)
    {
        if(ptr->key == key)
            return ptr;
        ptr = ptr->HashNext;
    }
    return NULL;
}
/*
 * 新建LruCache并初始化
 */
LruCache* newLruCache(int capacity)
{
    LruCache *lru = (LruCache*)malloc(sizeof(LruCache));
    if(NULL == lru)
    {
        fprintf(stderr , "%s %d : malloc failed.\n" , __func__ , __LINE__);
    }
    lru->NowCapacity   = 0;
    lru->CacheCapacity = capacity;
    lru->ListBegin = lru->ListEnd = NULL;

    lru->HashArray = (Entrys**)malloc(sizeof(Entrys) * (capacity+1));
    for(int i = 0; i < capacity + 1; i++)
    {
        lru->HashArray[i] = NULL;
    }

    if(NULL == lru->HashArray)
    {
        fprintf(stderr , "%s %d : malloc failed.\n" , __func__ , __LINE__);
        exit(-1);
    }

    return lru;
}

/*
 *将(key ： value)压入lru。
 * 1.若lru容量已经满了，就将最后一个节点删除
 * 2.若lru中已经存在key，则将这个(key : value)删除
 * 3.将(key : value)压入到队首
 */
void cachePush(LruCache *lru , char key , char value)
{
    if(NULL == lru)
    {
        return ;
    }
    CacheEntry *entry = findKey(lru , key);
    if(NULL != entry)
    {
        printf("entry is not empty!\n");
        removeEntryFromLru(lru , entry);
    }
    entry = newCacheEntry(key , value);

    if(lru->NowCapacity + 1 > lru->CacheCapacity)
    {
        removeEndEntryFromLru(lru);
    }
    addEntryInLruBegin(lru , entry);
}

/*
 *查找key多代表的节点
 *1.若没有key则返回NULL
 *2.找到后将(key , value)放到队首
 */
CacheEntry* getValueThroughKey(LruCache *lru , char key)
{
    if(NULL == lru)
    {
        return NULL;
    }
    CacheEntry *entry = findKey(lru , key);
    if(NULL == entry) {
        return NULL;
    }
    CacheEntry *ptr = newCacheEntry(entry->key , entry->value);
    removeEntryFromLru(lru , entry);
    addEntryInLruBegin(lru , ptr);
    return ptr;
}

void printCache(LruCache *lru)
{
    CacheEntry *ptr = lru->ListBegin;
    while(ptr)
    {
        if(NULL != ptr->ListNext)
            fprintf(stdout , "%c %c -> " , ptr->key , ptr->value);
        else
            fprintf(stdout , "%c %c\n" , ptr->key , ptr->value);
        ptr = ptr->ListNext;
    }
    return ;
}

void LruCacheDestory(LruCache *lru)
{
    Entrys *ptr = lru->ListBegin;
    while(NULL != ptr)
    {
        Entrys *ptr2 = ptr->ListNext;
        free(ptr);

        ptr = ptr2;
    }
    if(lru->HashArray) {
        free(lru->HashArray);
    }
    return ;
}