发布我的开源cache库ccache

yangsf5

下不动啊。。资源是 0/1。。

版主的博客在哪啊，想拜读。

另外能把你的cache发给我一份么？感激

[ 本帖最后由 yangsf5 于 2009-1-5 13:03 编辑 ]

yangsf5

挂迅雷挂了20分钟。。。终于下来了。。。

yangsf5

1.     while (0 <= index)
   
2. 
   
3.     {
   
4. 
   
5.         node = NODE(cache, index);
   
6. 
   
7.         nodekey = NODE_KEY(node);
   
8. 
   
9. 
   
10. 
    
11.         if (!cmp(key, nodekey))
    
12. 
    
13.         {
    
14. 
    
15.             break;
    
16. 
    
17.         }
    
18. 
    
19. 
    
20. 
    
21.         index = node->next;
    
22. 
    
23.     }

复制代码

版主的这个找节点是用遍历链表的阿？
我要维护一个1.5w节点的cache，这样会降低效率么？

如果设计成哈希表那样的，可以直接由数据的key找到对应节点的。。。但又会解决哈希冲突的开销和映射。。。

两种效率怎么取舍阿？

yangsf5

1. unsigned int hash(const void* key, ccache_t* cache)
   
2. 
   
3. {
   
4. 
   
5. #define mix(a,b,c) \
   
6. 
   
7.     { \
   
8. 
   
9.         a -= b; a -= c; a ^= (c >> 13); \
   
10. 
    
11.         b -= c; b -= a; b ^= (a << 8); \
    
12. 
    
13.         c -= a; c -= b; c ^= (b >> 13); \
    
14. 
    
15.         a -= b; a -= c; a ^= (c >> 12);  \
    
16. 
    
17.         b -= c; b -= a; b ^= (a << 16); \
    
18. 
    
19.         c -= a; c -= b; c ^= (b >> 5); \
    
20. 
    
21.         a -= b; a -= c; a ^= (c >> 3);  \
    
22. 
    
23.         b -= c; b -= a; b ^= (a << 10); \
    
24. 
    
25.         c -= a; c -= b; c ^= (b >> 15); \
    
26. 
    
27.     }
    
28. 
    
29. 
    
30. 
    
31.     char *k = (char *)key;
    
32. 
    
33.     unsigned int a, b, c, i, len;
    
34. 
    
35.     unsigned int length = cache->keysize;
    
36. 
    
37. 
    
38. 
    
39.     for (i = 0; i < length; i++)
    
40. 
    
41.         k[i] = tolower(k[i]);
    
42. 
    
43. 
    
44. 
    
45.     len = length;
    
46. 
    
47.     a = b = c = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
    
48. 
    
49. 
    
50. 
    
51.     while (12 <= len)
    
52. 
    
53.     {
    
54. 
    
55.         a += (k[0] +((unsigned int)k[1] << 8) +((unsigned int)k[2] << 16) +((unsigned int)k[3] << 24));
    
56. 
    
57.         b += (k[4] +((unsigned int)k[5] << 8) +((unsigned int)k[6] << 16) +((unsigned int)k[7] << 24));
    
58. 
    
59.         c += (k[8] +((unsigned int)k[9] << 8) +((unsigned int)k[10]<< 16)+((unsigned int)k[11] << 24));
    
60. 
    
61.         mix(a,b,c);
    
62. 
    
63.         k += 12;
    
64. 
    
65.         len -= 12;
    
66. 
    
67.     }
    
68. 
    
69. 
    
70. 
    
71.     c += length;
    
72. 
    
73.     switch(len)
    
74. 
    
75.     {
    
76. 
    
77.         case 11: c+=((unsigned int)k[10] << 24);
    
78. 
    
79.         case 10: c+=((unsigned int)k[9]  << 16);
    
80. 
    
81.         case 9 : c+=((unsigned int)k[8]  << 8);
    
82. 
    
83.         case 8 : b+=((unsigned int)k[7] << 24);
    
84. 
    
85.         case 7 : b+=((unsigned int)k[6] << 16);
    
86. 
    
87.         case 6 : b+=((unsigned int)k[5] << 8);
    
88. 
    
89.         case 5 : b+=k[4];
    
90. 
    
91.         case 4 : a+=((unsigned int)k[3] << 24);
    
92. 
    
93.         case 3 : a+=((unsigned int)k[2] << 16);
    
94. 
    
95.         case 2 : a+=((unsigned int)k[1] << 8);
    
96. 
    
97.         case 1 : a+=k[0];
    
98. 
    
99.     }
    
100. 
     
101.     mix(a,b,c);
     
102. 
     
103. 
     
104. 
     
105.     return c % cache->hashitemnum;
     
106. 
     
107. }

复制代码

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

yangsf5

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

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

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


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

yangsf5

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

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

yangsf5

原帖由 yangsf5 于 2008-4-3 11:16 发表
还没明白的地方：
这个cache里，可以有多张哈希表。。
建多张表的用意是：可以多张表并行的处理同时要求处理的太多的结点吗？

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

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

yangsf5

1. 
   
2. int find_data(const void* key, void* data, ccache_t* cache, cmpfun cmp)
   
3. {
   
4.     int hashindex = hash(key, cache), ret;
   
5.     void *nodedata;
   
6.     node_t *node;
   
7. 
   
8.     if (0 > lock(&(cache->mutex)))
   
9.     {
   
10.         return -1;
    
11.     }
    
12. 
    
13.     ret = FIND_NODE(hashindex, key, cache, cmp);
    
14. 
    
15.     if (0 <= ret)
    
16.     {
    
17.         if (NULL != data)
    
18.         {
    
19.             node = NODE(cache, ret);
    
20.             nodedata = NODE_DATA(node);
    
21.             memcpy(data, nodedata, node->datasize);
    
22.         }
    
23.         linktolrulisthead(ret, cache);
    
24.     }
    
25. 
    
26.     if (0 > unlock(&(cache->mutex)) || 0 > ret)
    
27.     {
    
28.         return -1;
    
29.     }
    
30.     return ret;
    
31. }
    

复制代码

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

1. 
   
2. int list_findnode(int hashindex, const void* key, ccache_t* cache, cmpfun cmp)
   
3. {
   
4.     hashitem_t *hashitem = HASH_ITEM(cache, hashindex);
   
5.     int index = hashitem->first;
   
6.     node_t *node;
   
7.     void* nodekey;
   
8. 
   
9.     while (0 <= index)
   
10.     {
    
11.         node = NODE(cache, index);
    
12.         nodekey = NODE_KEY(node);
    
13.         if (!cmp(key, nodekey))
    
14.         {
    
15.             break;
    
16.         }
    
17. 
    
18.         index = node->next;
    
19.     }
    
20. 
    
21.     return index;
    
22. }
    

复制代码

[ 本帖最后由 yangsf5 于 2009-1-5 13:06 编辑 ]