[原创] 发布我的开源cache库ccache

    while (0 <= index)



    {



        node = NODE(cache, index);



        nodekey = NODE_KEY(node);







        if (!cmp(key, nodekey))



        {



            break;



        }







        index = node->next;



    }

unsigned int hash(const void* key, ccache_t* cache)



{



#define mix(a,b,c) \



    { \



        a -= b; a -= c; a ^= (c >> 13); \



        b -= c; b -= a; b ^= (a << 8); \



        c -= a; c -= b; c ^= (b >> 13); \



        a -= b; a -= c; a ^= (c >> 12);  \



        b -= c; b -= a; b ^= (a << 16); \



        c -= a; c -= b; c ^= (b >> 5); \



        a -= b; a -= c; a ^= (c >> 3);  \



        b -= c; b -= a; b ^= (a << 10); \



        c -= a; c -= b; c ^= (b >> 15); \



    }







    char *k = (char *)key;



    unsigned int a, b, c, i, len;



    unsigned int length = cache->keysize;







    for (i = 0; i < length; i++)



        k = tolower(k);







    len = length;



    a = b = c = 0x9e3779b9;  /* the golden ratio; an arbitrary value */







    while (12 <= len)



    {



        a += (k[0] +((unsigned int)k[1] << 8) +((unsigned int)k[2] << 16) +((unsigned int)k[3] << 24));



        b += (k[4] +((unsigned int)k[5] << 8) +((unsigned int)k[6] << 16) +((unsigned int)k[7] << 24));



        c += (k[8] +((unsigned int)k[9] << 8) +((unsigned int)k[10]<< 16)+((unsigned int)k[11] << 24));



        mix(a,b,c);



        k += 12; 



        len -= 12;



    }







    c += length;



    switch(len) 



    {



        case 11: c+=((unsigned int)k[10] << 24);



        case 10: c+=((unsigned int)k[9]  << 16);



        case 9 : c+=((unsigned int)k[8]  << 8);



        case 8 : b+=((unsigned int)k[7] << 24);



        case 7 : b+=((unsigned int)k[6] << 16);



        case 6 : b+=((unsigned int)k[5] << 8);



        case 5 : b+=k[4];



        case 4 : a+=((unsigned int)k[3] << 24);



        case 3 : a+=((unsigned int)k[2] << 16);



        case 2 : a+=((unsigned int)k[1] << 8);



        case 1 : a+=k[0];



    }



    mix(a,b,c);







    return c % cache->hashitemnum;



}

这段代码看不懂啊。。版主能粗略的讲解一下么？
是寻找节点所在的hash表的索引吗？

---

 converse 回复于：2008-04-03 09:30:53

你的理解是对的.

---

 yangsf5 回复于：2008-04-03 09:59:09

哈哈，关于本函数用途的理解是因为你代码里有上下逻辑。。。

但是，你的这个算法我看不懂阿，晕糊糊的。。

我是个unix编程初学者，要是版主能有时间详讲一下这段代码，那该多好阿。。


晕的我都不知道为啥要建多个哈希表了。。:sad:

---

 converse 回复于：2008-04-03 10:51:13

这个hash算法我也不懂,抄的,能用就是.
一个好的hash算法有一个标准,就是要求hash出来的index能够尽可能的平均分布.

---

 yangsf5 回复于：2008-04-03 11:16:38

还没明白的地方：
这个cache里，可以有多张哈希表。。
建多张表的用意是：可以多张表并行的处理同时要求处理的太多的结点吗？

如果是这样，那个算法是否处理了同个结点的位置唯一性？

---

 hantangwang 回复于：2008-04-03 15:35:26

拥有我们，这一切就不再是梦想！
汉唐咨询就是伴随您的企业从成立到发展的合作好伙伴！
选择汉唐，选择品牌服务！
:) 
联系方式：010-84466445   或   010-64611785转612    王小姐
OICQ： 648680710                MSN：[email]wyp_zhuce@hotmail.com[/email]
公司网站：http://www.zhucestar.com/

---

 鸡鸡歪歪 回复于：2008-04-03 17:13:32

*** 作者被禁止或删除 内容自动屏蔽 ***

---

 xulei_ice 回复于：2008-04-03 21:00:07

建议参考一下开源的数据库berkeley db.  感觉你的思路跟berkeley db很像， 从中可以参考和借鉴一下。

预祝你的数据库越来越完善！

---

 mantiser 回复于：2008-04-04 03:54:30

不错。哈哈。。谁共享下。。块内存管理，链接管理的代码出来。。谢谢。

---

 mantiser 回复于：2008-04-04 04:01:47

看了下代码。哈。。

发现你也喜欢用自动生成API参考。。是doxgen吗。。。

到此下载：http://webscripts.softpedia.com/script/Development-Scripts-js/Complete-applications/Doxygen-15198.html

[ 本帖最后由 mantiser 于 2008-4-4 04:11 编辑 ]

---

 yangsf5 回复于：2008-04-04 13:10:36

引用：原帖由 yangsf5 于 2008-4-3 11:16 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8165888&ptid=1069566]
还没明白的地方：
这个cache里，可以有多张哈希表。。
建多张表的用意是：可以多张表并行的处理同时要求处理的太多的结点吗？

如果是这样，那个算法是否处理了同个结点的位置唯一性？ 



都那么强，就没人回答我的问题吗？

---

 converse 回复于：2008-04-04 16:37:34

插入节点的时候,首先会在所在HASH表中查找节点是否已经存在,如果存在报错退出,否则进行插入操作,在函数insert_data中.

有问题,Read The Fu**ing Source, pls.

---

 jamesr 回复于：2008-04-04 16:58:05

给楼主提几个建议：
1、建议所有文件都用LF结尾
2、建议所有文件都用统一的编码：UTF－8
3、建议建一个doc文件夹内放Doxygen生成的文档

以下就是楼主没有这样做后，我自己用doxygen生成的文档图（编码实在头疼哪！）：

---

 converse 回复于：2008-04-05 00:46:55

关于这个问题,我决定以后的版本注释一律采用英文注释.

---

 SupervisedBoy 回复于：2008-04-05 12:33:17

楼主用mmap文件存储数据，应该用的是文件锁吧。文件锁支持按偏移和大小加锁的，不用每次锁住全部。

---

 converse 回复于：2008-04-05 16:39:54

之所以要采用全局锁,是因为一直没有解决这样的问题:

进程A要对hash表a进行插入操作,此时锁住hash表a,但是发现当前已经没有空闲节点,要采用淘汰算法进行淘汰,假设需要淘汰hash表b上的一个节点,此时hash表b已经被另一个进程B锁住,而进程B要进行淘汰的节点又在hash表a上,如此情况,造成死锁.

因此,现在的折中策略是对全局进行加锁,减少锁粒度属于今后的优化,暂缓.

---

 iunknown 回复于：2008-04-05 20:20:41

引用：原帖由 converse 于 2008-4-2 11:51 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8159377&ptid=1069566]
同时还有unlock_cache api,因为某些使用C++的用户如果使用了C++的异常处理,在调用ccache中的API时抛出异常将导致ccache没有解锁
, 以后就不能再使用了, 提供这个API是为了在抛出异常的时候用户自己释放锁



对于这个问题，在 c++ 中倒是可以通过 RAII 来处理。
RAII英文意思：Resource acquisition is initialization，资源获取即初始化。该原则或技术用于对资源的管理。其核心思想，就是在对象的生命周期中，资源总是有效。而对象结束时，资源会自动释放。

典型的实现

class MutexGuard {

public:

    MutexGuard( Lock_t * lock ) {

        mLock = lock;

        lock->lock();

    }



    ~MutexGuard() {

        mLock->unlock();

    }



private:

    Lock_t * mLock;

};



void Cache :: put( ... )

{

    MutexGuard guard( mLock );



    ..........

}

[ 本帖最后由 iunknown 于 2008-4-5 20:23 编辑 ]

---

 lysde 回复于：2008-04-07 13:43:39

支持,有时间学学...

---

 yangsf5 回复于：2008-04-11 21:51:47

int find_data(const void* key, void* data, ccache_t* cache, cmpfun cmp)



{



    int hashindex = hash(key, cache), ret;



    void *nodedata;



    node_t *node;







    if (0 > lock(&(cache->mutex)))



    {



        return -1;



    }







    ret = FIND_NODE(hashindex, key, cache, cmp);







    if (0 <= ret)



    {



        if (NULL != data)



        {



            node = NODE(cache, ret);



            nodedata = NODE_DATA(node);



            memcpy(data, nodedata, node->datasize);



        }



        linktolrulisthead(ret, cache);



    }







    if (0 > unlock(&(cache->mutex)) || 0 > ret)



    {



        return -1;



    }







    return ret;



}

搂住这个函数有问题。。。
在调用这个函数时，对返回值进行判断。
>=0...说明节点存在。。
但是对于－1，就不能确定了：
可以是还没判断就因为锁出错返回－1；也可以是没有这个节点返回－1(因为链表里的最后一个节点的next是－1)。

int list_findnode(int hashindex, const void* key, ccache_t* cache, cmpfun cmp)



{



    hashitem_t *hashitem = HASH_ITEM(cache, hashindex);







    int index = hashitem->first;



    node_t *node;



    void* nodekey;



    while (0 <= index)



    {



        node = NODE(cache, index);



        nodekey = NODE_KEY(node);







        if (!cmp(key, nodekey))



        {



            break;



        }







        index = node->next;



    }







    return index;



}