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
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 211,194评论 6赞 490
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,058评论 2赞 385
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 156,780评论 0赞 346
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,388评论 1赞 283
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,430评论 5赞 384
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,764评论 1赞 290
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,907评论 3赞 406
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,679评论 0赞 266
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,122评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,459评论 2赞 325
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,605评论 1赞 340
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,270评论 4赞 329
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,867评论 3赞 312
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,734评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,961评论 1赞 265
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,297评论 2赞 360
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,472评论 2赞 348

推荐阅读更多精彩内容

  • 2003-2014考研真题
    **2014真题Directions:Read the following text. Choose the be...
    又是夜半惊坐起阅读 9,430评论 0赞 23
  • 家居厨房小妙招
    生活中，总有一下小烦恼 常常又费力又费事 小编今天就交大家一下生活的小妙招 分分钟，秒杀你的烦恼 厨房篇 倒饮料，...
    窗爸爸家居阅读 279评论 0赞 2
  • 当我老了
    坐在车上，听着音乐，不知怎么的，就想象到了自己老了会是怎样的。大致的老年生活会有这样几种:第一种是和儿女生活在一起...
    crystal101阅读 310评论 0赞 0
  • 实践－小细节 III
    1. 底部弹框无标题设置 Title:nil message:nil 标题和信息都设为 nil 不能设置...
    進无尽阅读 606评论 1赞 1