9

gethostbyname()ファイル内の URL を読み取り、各 URL ホストで実行するプログラムがあります。この呼び出しはかなり消費します。それらをキャッシュしたい。

キャッシュを行うために使用できる C 言語の非常に単純なマップ ベースのコード スニペットはありますか? （私は車輪を再発明したくないだけです）。

次の点が必要です。

  • 寛大なライセンスを持つオープンソース(BSD またはパブリック ドメインを考えてください)。
  • 非常に単純: 理想的には 100 未満の LOC
  • キーはchar*と 値ですvoid*。それらをコピーする必要はありません。
  • を実装する必要はありませんが、必要であるか、値を置き換える必要remove()があります。contains()put()

PS:可能性があるので、宿題タグを付けました。私は非常に怠け者であり、再実装中に遭遇する可能性のある一般的な落とし穴をすべて回避したいと考えています。

4

8 に答える 8

9

これは非常にシンプルで素朴なものです

  • 固定バケットサイズ
  • 削除操作なし
  • 挿入はキーと値を置き換え、オプションでそれらを解放できます

：

#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;
}
于 2009-08-05T17:54:18.570 に答える
2

次の実装を使用して試すことができます

クリブ

于 2011-04-12T13:46:57.967 に答える
1

Dave HansonのCインターフェイスと実装には、優れたハッシュテーブルだけでなく、他の多くの便利なモジュールが含まれています。ハッシュテーブルは150行でクロックインしますが、これにはメモリ管理、高階マッピング関数、および配列への変換が含まれます。ソフトウェアは無料で、本は買う価値があります。

于 2009-08-05T19:50:34.543 に答える
1

memcached ?

コード スニペットではなく、高性能の分散キャッシュ エンジンです。

于 2009-08-05T17:08:34.963 に答える
1

このようなことを書くことを避けるために、怠け者ではなく、非常に賢明です。

このライブラリは自分で使用したことはありませんが、あなたが求めていることを行うと主張しているようです。

于 2009-08-05T17:09:45.803 に答える
0

ここで実装を見つけました：cファイルとhファイルは、あなたが求めたものにかなり近いです。W3C ライセンス

于 2009-08-05T17:21:24.300 に答える