Sehr einfache Karte Implementierung in C (für Coaching Zweck)?

Question

Ich habe ein Programm, das Urls in einer Datei und macht einen gethostbyname() auf jeder URL-Host lesen. Dieser Aufruf ist recht aufwendig. Ich möchte, dass sie cachen.

Gibt es eine sehr einfache Kartenbank Code-Schnipsel in C gibt, dass ich das Caching zu tun verwenden könnte? (Ich will nur nicht, das Rad neu zu erfinden).

Es hat die folgenden Punkte haben:

• Open Source mit einer permissiven Lizenz (man denke BSD oder public domain).
• Sehr einfach: idealerweise weniger als 100 LOC
• Tasten sind char* und Werte void*. Keine Notwendigkeit zu kopieren.
• Keine wirkliche Notwendigkeit, remove() zu implementieren, aber contains() ist entweder erforderlich oder put() soll den Wert ersetzen.

PS: Ich getaggt es Hausaufgaben , da es sein könnte. Ich bin nur sehr faul und wollen alle Fallstricke zu vermeiden, ich begegnen konnte, während die Neuimplementierung.

Answer 1

Hier ist eine sehr einfache und naive ein

• Fixed Bucketgröße
• Kein Löschvorgang
• Einsätze ersetzt den Schlüssel und Wert, und kann sie gegebenenfalls frei

#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

Christ Clark hashtable Implementierung ist sehr einfach. Es ist mehr als 100 Zeilen, aber nicht viel.

Clark Code scheint seinen Weg in die gemacht zu haben: Google Conccurrency Bibliothek als Parallelisierung Beispiel.

Answer 3

std::map in C ++ ist ein rot-schwarz-Baum unter der Haube; was über die Verwendung von einer vorhandenen Rot-Schwarz-Baum-Implementierung in C ? Der, den ich verbunden ist mehr wie 700 LOC, aber es ist ziemlich gut kommentiert und sieht gesund aus dem flüchtigen Blick ich es nahm. Sie können sich wahrscheinlich andere finden; dieses war der erste Treffer bei Google für „C Rot-Schwarz-Baum“.

Wenn Sie nicht pingelig Leistung sind Sie auch einen unausgewogenen binären Baum oder einen min-Heap oder etwas ähnliches verwenden könnten. Mit einem ausgewogenen binären Baum, sind Sie O (log n) Lookup garantiert; mit einem unausgeglichenen Baum ist der schlimmste Fall für die Suche O (n) (für den pathologischen Fall, in dem Knoten in Ordnung eingefügt werden, so am Ende mit einem wirklich langen Zweig, die wie eine verknüpfte Liste handelt), aber (wenn mein rostigen Speicher korrekt ist) die durchschnittliche Fall ist immer noch O (log n).

Answer 4

Sie können folgende implemntation versuchen mit

clib

Answer 5

Memcached ?

Nicht ein Code-Schnipsel, aber ein hohe Leistung verteilt Caching-Engine.

Answer 6

Nicht faul, tief vernünftige Schreiben dieses Zeug zu vermeiden.

Wie ist das Bibliothek es mich nie verwendet, aber es scheint zu behaupten, was zu tun ist Sie fragen nach.

Answer 7

Dave Hanson C Schnittstellen und Realisierungen eine schöne Hash-Tabelle enthält, als auch wie viele andere nützliche Module. Die Hash-Tischuhren in 150 Zeilen, aber das ist mit einer Speicherverwaltung, eine übergeordnete Zuordnungsfunktion, und die Umwandlung in Array. Die Software ist kostenlos, und das Buch ist der Kauf wert.

Answer 8

Gefunden eine Implementierung hier: c Datei und h Datei, die ziemlich nahe ist, was Sie gefragt . W3C Lizenz