非常简单的地图实施在C(为缓存的目的)?
https://stackoverflow.com/questions/1234514
-
22-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我有一个程序，读取的网址在一个文件，而不一 gethostbyname() 在每个网址的主机。这一呼吁是非常耗时。我想缓。
是有一个非常简单的地图-基码段C在那里，我能用来做缓存？(我只是不想要重新发明轮子)。
它必须要有以下几点：
- 开放源码的一个 许可证 (觉得BSD或公共域中)。
- 非常 简单：理想的情况少于100LOC
- 钥匙是
char*和价值观void*.不需要复制他们。 - 没有真正需要实现
remove(), 但contains()要么需要或者put()应该替换价值。
PS:我标记它 家庭作业, ，因为它可能是。我只是被 非常 懒惰和想要避免所有常见的陷阱我可能会遇到同时重新实现.
解决方案
这是一个非常简单的和一个幼稚
- 固定桶大小的
- 没有删除操作
- 插入替代关键的和价值，并且可以选择他们自由
:
#include <string.h>
#include <stdlib.h>
#define NR_BUCKETS 1024
struct StrHashNode {
char *key;
void *value;
struct StrHashNode *next;
};
struct StrHashTable {
struct StrHashNode *buckets[NR_BUCKETS];
void (*free_key)(char *);
void (*free_value)(void*);
unsigned int (*hash)(const char *key);
int (*cmp)(const char *first,const char *second);
};
void *get(struct StrHashTable *table,const char *key)
{
unsigned int bucket = table->hash(key)%NR_BUCKETS;
struct StrHashNode *node;
node = table->buckets[bucket];
while(node) {
if(table->cmp(key,node->key) == 0)
return node->value;
node = node->next;
}
return NULL;
}
int insert(struct StrHashTable *table,char *key,void *value)
{
unsigned int bucket = table->hash(key)%NR_BUCKETS;
struct StrHashNode **tmp;
struct StrHashNode *node ;
tmp = &table->buckets[bucket];
while(*tmp) {
if(table->cmp(key,(*tmp)->key) == 0)
break;
tmp = &(*tmp)->next;
}
if(*tmp) {
if(table->free_key != NULL)
table->free_key((*tmp)->key);
if(table->free_value != NULL)
table->free_value((*tmp)->value);
node = *tmp;
} else {
node = malloc(sizeof *node);
if(node == NULL)
return -1;
node->next = NULL;
*tmp = node;
}
node->key = key;
node->value = value;
return 0;
}
unsigned int foo_strhash(const char *str)
{
unsigned int hash = 0;
for(; *str; str++)
hash = 31*hash + *str;
return hash;
}
#include <stdio.h>
int main(int argc,char *argv[])
{
struct StrHashTable tbl = {{0},NULL,NULL,foo_strhash,strcmp};
insert(&tbl,"Test","TestValue");
insert(&tbl,"Test2","TestValue2");
puts(get(&tbl,"Test"));
insert(&tbl,"Test","TestValueReplaced");
puts(get(&tbl,"Test"));
return 0;
}
其他提示
Christoper克拉克的hashtable执行情况 非常简单。这是100多条线，但是不多。
克拉克的代码似乎已经作出了它的方式进入 谷歌的Conccurrency库 作为一个并行的例子。
std::map C++是一个红黑色树下罩；什么使用 现有的红黑色树执行在C?一个我相联系的更像700LOC，但这是很好的注释，看上去理智，从粗略地看一眼我把它。你也许可以找到其他人；这个是第一个打击在谷歌"C红黑色树"。
如果你不挑剔的表现，你也可以使用一种不平衡的二进制树或分钟-堆或者类似的东西。有一个平衡的二进制树，你保证O(日志n)查询;与一个不平衡的树上最糟糕的是查找是O(n)(用于病理情况下的节点是插在了，所以你结束了一个很长的分支，就像链接表)，但是(如果我的生锈的记忆是正确的)的平均的情况仍然是O(日志n)。
你可以尝试使用以下implemntation
缓存?
不代码段，而是一个高性能的分布高速缓存引擎。
不懒惰的，深深的理智避免写这东西。
这个怎么样的 图书馆 从来没有使用过它自己，但它似乎要求去做你要求。
戴维*汉森的 C接口和实现 包括一个很好的散列表，以及其他许多有用的模块。哈希表时钟在150线，但这是包括存储管理、更高的阶映功能，以及转换到阵列。该软件是免费的，这本书是值得购买。
