我有一个程序可以读取文件中的 url 并gethostbyname()在每个 URL 主机上执行。这个电话很费劲。我想缓存它们。
C 中有一个非常简单的基于地图的代码片段，我可以用它来进行缓存吗？（我只是不想重新发明轮子）。
它必须具有以下几点：
char*和值void*。无需复制它们。remove()，但contains()需要或put()应该替换该值。PS：我把它标记为homework，因为它可能是。我只是非常懒惰，并且确实想避免在重新实现时可能遇到的所有常见陷阱。
这是一个非常简单和幼稚的
：
#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 Clark 的哈希表实现非常简单。它有 100 多行，但不是很多。
Clark 的代码似乎已经作为并行化示例进入了Google 的并发库。
std::map在 C++ 中是引擎盖下的红黑树；在 C 中使用现有的红黑树实现怎么样？我链接的那个更像是 700 LOC，但它的评论非常好，从我粗略的一瞥看来它看起来很理智。您可能可以找到其他人；这是“C 红黑树”在谷歌上的第一次点击。
如果您对性能不挑剔，您还可以使用不平衡二叉树或最小堆或类似的东西。使用平衡二叉树，可以保证 O(log n) 查找；对于不平衡的树，查找的最坏情况是 O(n) （对于按顺序插入节点的病态情况，所以你最终会得到一个非常长的分支，就像链表一样），但是（如果我生锈了记忆是正确的）平均情况仍然是O（log n）。
您可以尝试使用以下实现
内存缓存？
不是一个代码片段，而是一个高性能的分布式缓存引擎。
不懒惰，避免写这些东西是非常明智的。
这个库是如何自己从未使用过的，但它似乎声称可以满足您的要求。
Dave Hanson 的C 接口和实现包括一个很好的哈希表，以及许多其他有用的模块。哈希表有 150 行，但其中包括内存管理、高阶映射函数和数组转换。该软件是免费的，这本书值得购买。