Очень простая реализация карты в C (для целей кэширования)?

Question

У меня есть программа, которая читает urls в файле и делает gethostbyname() на каждом хосте URL. Этот вызов довольно много. Я хочу их кэшировать.

Есть ли очень простой фрагмент кода на карте в C, который я мог бы использовать для кеширования? (Я просто не хочу изобретать велосипед).

Он должен иметь следующие пункты:

• с открытым исходным кодом с разрешительной лицензией (думает, BSD или общественное достояние).
• Очень просто: в идеале менее 100 LOC
• Ключи char* и значения void*. Нет необходимости копировать их.
• Нет необходимости в реализации remove(), но либо необходим, либо put() должен заменить значение.

PS: Я отметил домашнее задание, так как это может быть. Я просто являюсь очень ленивый и хочу избежать всех распространенных ошибок, с которыми я мог столкнуться при повторном выполнении.

Answer 1

Вот очень простой и наивный один

• размер Fixed ведро
• Нет операции удаления
• вставки заменяет ключ и значение, и может при необходимости освободить их

:

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

Answer 2

memcached?

Не фрагмент кода, а мощный механизм кеширования с высокой производительностью.

Answer 3

Не ленивый, глубоко разумный, чтобы избежать написания этого материала.

Как это library никогда не использовал его сам, но он, кажется, претендует на то, что вы просите.

Answer 4

Christoper Clark's hashtable implementation очень прост. Это более 100 строк, но не намного.

Код Кларка, кажется, пробился в Google's Conccurrency Library как пример параллелизации.

Answer 5

std::map в C++ - это красно-черное дерево под капотом; как насчет использования an existing red-black tree implementation in C? Тот, с которым я связан, больше похож на 700 LOC, но он довольно хорошо прокомментирован и выглядит здравомыслящим от беглого взгляда, который я взял на него. Вероятно, вы можете найти других; этот был первым хитом в Google для «C красно-черного дерева».

Если вы не придирчивы к производительности, вы также можете использовать несбалансированное двоичное дерево или мини-кучу или что-то в этом роде. Со сбалансированным двоичным деревом вам гарантируется O (log n) поиск; с неуравновешенным деревом наихудшим случаем поиска является O (n) (для патологического случая, когда узлы вставлены в порядке, поэтому вы получаете одну очень длинную ветвь, которая действует как связанный список), но (если мой ржавый память правильная), средний случай по-прежнему равен O (log n).

Answer 6

Обнаружена реализация здесь: c файл и h файл, который довольно близок к тому, что вы просили.W3C лицензия

Answer 7

Dave Hanson's C Interfaces and Implementations содержит приятный хеш-стол, а также множество других полезных модулей. Хэш-таблица синхронизируется в 150 строках, но это включает управление памятью, функцию сопоставления более высокого порядка и преобразование в массив. Программное обеспечение бесплатно, и книга стоит покупать.

Answer 8

Вы можете попробовать использовать следующие implemntation

clib