C中非常简单的地图实现(用于缓存目的)？

Question

我有一个程序,它读取文件中的gethostbyname()URL 并在每个URL主机上执行.这个电话很费劲.我想缓存它们.

C中是否有一个非常简单的基于地图的代码片段,我可以用来进行缓存？(我只是不想重新发明轮子).

它必须具有以下几点:

• 具有许可许可的开源(想想BSD或公共域).
• 非常简单:理想情况下不到100 LOC
• 键是char*和值void*.无需复制它们.
• 没有实际需要实现remove(),但是contains()需要或者put()应该替换价值.

PS:我标记了它的作业,因为它可能.我只是非常懒惰,并且想要避免在重新实现时遇到的所有常见陷阱.

Answer 1

Christoper Clark的哈希表实现非常简单.它超过100行,但不是很多.

Clark的代码似乎作为并行化示例进入了Google的Conccurrency Library.

Answer 2

这是一个非常简单和天真的

• 固定铲斗尺寸
• 没有删除操作
• 插入替换键和值,并可以选择释放它们

:

#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;
}