lru cache implemention by asc c

• comment in my code also to litte,your can read my code no need to get problem about what will do in this function,because it is too simple,you just read code.

• first,we are also using in our project with lru cache.i implement it with asc c.that is too simple.using hash function and double list and hash tables to get or find a data.

• second,now i show detail about code for you

lru.h

/*************************************************************************
    > File Name: lru.h
    > Author: perrynzhou
    > Mail: perrynzhou@gmail.com
    > Created Time: Thu 01 Jun 2016 06:58:33 AM AKDT
 ************************************************************************/

#ifndef _LRU_H
#define _LRU_H
#include <stdint.h>
#include <stdbool.h>
typedef struct element_s element;
typedef struct lru_s lru;
/*-------call back function----------*/
typedef uint64_t (*key_size_function) (void *key);
typedef uint64_t (*key_hash_function) (void *key);
typedef void (*key_free_function) (void *key);
typedef void (*value_free_function) (void *value);
/*----------------*/
lru *lru_create (uint64_t max_size, key_size_function kz_fn, key_hash_function kh_fn);
void lru_function (lru * u, key_free_function kf_fn, value_free_function vf_fn);
bool lru_add (lru * u, void *key, void *value);
void lru_remove (lru *, void *key);
element *lru_get (lru * u, void *key);
void *element_key (element * e);
void *element_value (element * e);
#endif

lru.c

/*************************************************************************
    > File Name: lru.c
    > Author: perrynzhou
    > Mail: perrynzhou@gmail.com
    > Created Time: Thu 01 Jun 2017 07:21:05 AM AKDT
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "lru.h"
#define atomic_add(M,N) (__sync_add_and_fetch(&M,N))
#define atomic_sub(M,N) (__sync_sub_and_fetch(&M,N))
struct element_s
{
    void *key;
    void *value;
    struct element_s *next;
    struct element_s *prev;
};
struct lru_s
{
    uint64_t max_size;          //element max size 
    uint64_t cur_size;
    element **ht;
    element *head;
    element *tail;
    key_size_function kz_fn;
    key_hash_function kh_fn;

    // free callback
    key_free_function kf_fn;
    value_free_function vf_fn;
};
static element *element_create (void *key, void *value)
{
    if (!key || !value)
    {
        return NULL;
    }
    element *e = (element *) malloc (sizeof (*e));
    assert (e != NULL);
    e->key = key;
    e->value = value;
    e->prev = e->next = NULL;
    return e;
}

inline void lru_function (lru * u, key_free_function kf_fn, value_free_function vf_fn)
{
    if (u != NULL)
    {
        u->kf_fn = kf_fn;
        u->vf_fn = vf_fn;
    }
}

static inline void element_free (element * e)
{
    if (!e)
    {
        free (e);
    }
}

static uint64_t hash_fn (lru * u, void *key)
{
    return u->kh_fn (key) % (u->max_size);
}

static bool _lru_add_element (lru * u, element * e)
{
    if (!u || !e || u->cur_size >= u->max_size)
    {
        return false;
    }
    do
    {
        e->next = NULL;
        if (!u->head && !u->tail)
        {
            u->head = u->tail = e;
        }
        else
        {
            u->tail->next = e;
            e->prev = u->tail;
            u->tail = e;
        }
    }
    while (0);
    return true;
}

static void _lru_remove_element (lru * u, element * e)
{
    if (!u && !e)
    {
        do
        {
            if (e->next)
            {
                e->next->prev = e->prev;
            }
            else
            {
                u->tail = e->prev;
            }
            if (e->prev)
            {
                e->prev->next = e->next;
            }
            else
            {
                u->head = e->next;
            }
        }
        while (0);
    }
}

inline element *lru_head (lru * u)
{
    return u == NULL ? NULL : u->head;
}

inline element *lru_tail (lru * u)
{
    return u == NULL ? NULL : u->tail;
}

lru *lru_create (uint64_t max_size, key_size_function kz_fn, key_hash_function kh_fn)
{
    if (!kz_fn || !kh_fn)
    {
        return NULL;
    }
    lru *u = (lru *) malloc (sizeof (*u));
    assert (u != NULL);
    u->ht = (element **) malloc (sizeof (element *) * max_size);
    assert (u->ht != NULL);
    u->head = u->tail = NULL;
    u->cur_size = 0;
    u->max_size = max_size;
    u->kz_fn = kz_fn;
    u->kh_fn = kh_fn;
    return u;
}

void lru_destroy (lru * u)
{
    if (u != NULL)
    {
        element *e = u->head;
        while (e != NULL)
        {
            if (u->kf_fn != NULL)
            {
                u->kf_fn (e->key);
            }
            if (u->vf_fn != NULL)
            {
                u->vf_fn (e->value);
            }
            element_free (e);
            e = e->next;
        }
        free (u->ht);
        free (u);
    }
}

bool lru_add (lru * u, void *key, void *value)
{
    if (!u || !key || !value)
    {
        return false;
    }
    uint64_t index = hash_fn (u, key);
    element *e = u->ht[index];
    bool ret = false;
    if (e != NULL)
    {
        e->key = key;
        e->value = value;
        ret = _lru_add_element (u, e);
    }
    else
    {
        e = element_create (key, value);
        if (e != NULL)
        {
            ret = _lru_add_element (u, e);
            u->ht[index] = e;
            atomic_add (u->cur_size, 1);
        }
    }
    return ret;
}

void lru_remove (lru * u, void *key)
{
    if (u != NULL && key != NULL)
    {
        uint64_t index = hash_fn (u, key);
        element *e = u->ht[index];
        if (e != NULL)
        {
            _lru_remove_element (u, e);
            element_free (e);
            atomic_sub (u->cur_size, 1);
            u->ht[index] = NULL;
        }
    }
}

element *lru_get (lru * u, void *key)
{
    element *e = NULL;
    if (u != NULL && key != NULL)
    {
        uint64_t index = hash_fn (u, key);
        e = u->ht[index];
    }
    return e;
}

#ifdef TEST
uint64_t hash (void *key)
{
    uint32_t hash = 5381;
    uint64_t tmp;
    uint64_t key_size = u->kz_fn (key);
    while (key_size--)
    {
        tmp = (*(uint64_t *) key)++;
        hash = ((hash << 5) + hash) + tmp;
    }
    return;
}
#endif