Bardzo prosta implementacja mapy w C (na potrzeby buforowania)?

Question

Mam program, który odczytuje adresy URL w pliku i wykonuje gethostbyname() na każdym hostie URL. To połączenie jest dość pochłaniające. Chcę je buforować.

Czy istnieje bardzo prosty fragment kodu mapy w C, który mógłbym użyć do buforowania? (Po prostu nie chcę odkrywać koła na nowo).

To musi mieć następujące punkty:

• open-source z pozwalającej myśleć licencji (BSD lub public domain).
• Bardzo prosta: idealnie mniej niż 100 LOC
• Klucze char* i wartości void*. Nie trzeba ich kopiować.
• Nie ma potrzeby implementacji remove(), ale wymagana jest lub put() powinna zastąpić wartość.

PS: Oznaczyłem to jako zadanie domowe, ponieważ mogło być. Po prostu jestem leniwy i chcę uniknąć wszystkich typowych pułapek, które mogłem napotkać podczas reimplementacji.

Answer 1

Oto bardzo prosty i naiwny jeden

• Ustalony rozmiar wiadro
• No operacja usuwania
• wkładki zastępuje klucz i wartość, a ewentualnie może uwolnić ich

:

#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?

Brak fragmentu kodu, ale wysokowydajny rozproszony silnik buforowania.

Answer 3

Nie leniwy, głęboko rozsądny, aby uniknąć pisania tego.

Jak to jest library nigdy sam z siebie nie korzystałem, ale wydaje się, że robi to, o co prosisz.

Answer 4

Christoper Clark's hashtable implementation jest bardzo prosta. To ponad 100 linii, ale nie za dużo.

Kod Clarka prawdopodobnie pojawił się w Google's Conccurrency Library jako przykład równoległości.

Answer 5

std::map w C++ jest czerwono-czarnym drzewem pod maską; a co z używaniem an existing red-black tree implementation in C? Ten, który złączyłem, jest bardziej podobny do 700 LOC, ale jest dość dobrze skomentowany i wygląda na przyzwoitego z pobieżnego spojrzenia, które z niego zrobiłem. Prawdopodobnie znajdziesz innych; ten był pierwszym hitem w Google dla "C czerwono-czarnego drzewa".

Jeśli nie jesteś zbytnio wrażliwy na wydajność, możesz również użyć niezbalansowanego drzewa binarnego lub min-sterty lub czegoś w tym stylu. Dzięki zbalansowanemu drzewu binarnemu masz zagwarantowane wyszukiwanie O (log n); z niezrównoważonym drzewem najgorszym przypadkiem dla wyszukiwania jest O (n) (dla patologicznego przypadku, w którym węzły są wstawiane w kolejności, więc kończy się jednym naprawdę długim odgałęzieniem, które działa jak połączona lista), ale (jeśli mój zardzewiały pamięć jest poprawna) średnia wielkość liter nadal wynosi O (log n).

Answer 6

Znaleziono implementację tutaj: c plik i plik h, który jest dość blisko tego, o co prosiłeś.W3C licencja

Answer 7

Dave Hanson's C Interfaces and Implementations zawiera miły tabelę skrótów, a także wiele innych użytecznych modułów. Hash table zegary w 150 liniach, ale to w tym zarządzanie pamięcią, funkcja mapowania wyższego rzędu i konwersji do tablicy. Oprogramowanie jest bezpłatne, a książka jest warta zakupu.

Answer 8

Można spróbować użyć następujących implemntation

clib