代码之家 › 专栏 › 技术社区 › Steve Schnepp

在C中实现非常简单的映射(用于缓存)?

code-reuse code-snippets map c

Steve Schnepp · 技术社区 · 16 年前

我有一个程序可以读取文件中的URL并执行 gethostbyname() 在每个URL主机上。这个电话很费劲。我想把它们藏起来。

在C语言中有没有一个非常简单的映射基代码片段,我可以用它来进行缓存?(我只是不想重新发明轮子)。

它必须具备以下几点:

打开源代码 许可证 (想想BSD或公共领域)。
非常简单:理想情况下少于100个位置
钥匙是 char* 价值观 void* . 不需要复制它们。
不需要执行 remove() 但是 contains() 需要或 put() 应替换该值。

我把它贴上标签。作业因为它可能是。我只是在非常懒惰,并且确实想避免我在重新实现时遇到的所有常见陷阱。

8 回复 | 直到 10 年前

nos 16 年前

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

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

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

Sinan Ünür 10 年前

Christoper Clark's hashtable implementation 非常简单。它超过100行,但不多。

克拉克的密码似乎已经进入 Google's Conccurrency Library 作为一个并行化的例子。

Meredith L. Patterson 16 年前

std::map 在C++中,引擎盖下面是一棵红黑树。 an existing red-black tree implementation in C ?我链接的那个更像是700个loc,但它的评论很好,从我粗略的一瞥中看,它看起来很正常。你可能会找到其他人;这是谷歌第一次因为“C红黑树”而被点击。

如果您对性能不挑剔,也可以使用不平衡的二叉树、最小堆或类似的东西。对于平衡二叉树,您可以保证O(log n)查找;对于不平衡树,查找的最坏情况是O(n)(对于按顺序插入节点的病理情况,您最终得到一个相当长的分支,其作用类似于链表),但是(如果我的生锈内存是正确的)平均情况仍然是O(log n)。

Avinash 14 年前

你可以尝试使用以下的暗示

clib

Justin Niessner 16 年前

memcached ?

不是代码片段,而是高性能分布式缓存引擎。

djna 16 年前

不懒惰,很明智,避免写这些东西。

这是怎么回事? library 我从未使用过它,但它似乎声称要做你要求做的。

Norman Ramsey 16 年前

Dave Hanson C Interfaces and Implementations 包括一个很好的哈希表,以及许多其他有用的模块。哈希表的时钟是150行,但这包括内存管理、一个高阶映射函数以及到数组的转换。软件是免费的,这本书值得买。

zebrabox 16 年前

在此处找到一个实现: c 文件和 h 把你要求的文件归档。W3C许可证