/*
 * @lc app=leetcode.cn id=146 lang=c
 *
 * [146] LRU 缓存
 */

// @lc code=start

typedef struct
{
    int key;
    int val;
    UT_hash_handle hh;
} UTTable;

typedef struct
{
    UTTable *caches;
    int capacity;
} LRUCache;

LRUCache *lRUCacheCreate(int capacity)
{
    if (capacity > 3000)
    {
        return NULL;
    }
    LRUCache *obj = (LRUCache *)malloc(sizeof(LRUCache));
    if (obj == NULL)
    {
        return NULL;
    }
    obj->capacity = capacity;
    obj->caches = NULL;
    return obj;
}

int lRUCacheGet(LRUCache *obj, int key)
{
    UTTable *s = NULL;
    HASH_FIND_INT(obj->caches, &key, s);

    if (s)
    {
        // 先删除再添加
        HASH_DELETE(hh, obj->caches, s);
        HASH_ADD_INT(obj->caches, key, s);
    }
    return s ? s->val : -1;
}

void lRUCachePut(LRUCache *obj, int key, int value)
{
    UTTable *current_i = NULL;
    UTTable *tmp = NULL;

    HASH_FIND_INT(obj->caches, &key, current_i); /* id already in the hash? */
    if (current_i)
    {
        current_i->val = value;
        // 先删除再添加
        HASH_DELETE(hh, obj->caches, current_i);
        HASH_ADD_INT(obj->caches, key, current_i);
        return;
    }

    // prune the cache to MAX_CACHE_SIZE
    if (HASH_COUNT(obj->caches) >= obj->capacity)
    {
        HASH_ITER(hh, obj->caches, current_i, tmp)
        {
            // prune the first entry (loop is based on insertion order so this deletes the oldest item)
            HASH_DELETE(hh, obj->caches, current_i);
            free(current_i);
            break;
        }
    }
    current_i = malloc(sizeof(*current_i));
    current_i->key = key;
    current_i->val = value;
    HASH_ADD_INT(obj->caches, key, current_i);
}

void lRUCacheFree(LRUCache *obj)
{
    UTTable *current_i = NULL;
    UTTable *tmp = NULL;

    HASH_ITER(hh, obj->caches, current_i, tmp)
    {
        HASH_DEL(obj->caches, current_i);
        free(current_i);
    }
    free(obj);
}

/**
 * Your LRUCache struct will be instantiated and called as such:
 * LRUCache* obj = lRUCacheCreate(capacity);
 * int param_1 = lRUCacheGet(obj, key);

 * lRUCachePut(obj, key, value);

 * lRUCacheFree(obj);
*/
// @lc code=end