¿Implementación de mapas muy simple en C (para fines de entrenamiento)?

Question

Tengo un programa que lee las URL en un archivo y hace un gethostbyname () en cada host de URL. Esta llamada consume bastante. Quiero guardarlos en caché.

¿Hay un fragmento de código base de mapa muy simple en C que pueda usar para hacer el almacenamiento en caché? (Simplemente no quiero reinventar la rueda).

Tiene que tener los siguientes puntos:

• Código abierto con una licencia permisiva (piense en BSD o dominio público).
• Muy simple: idealmente menos de 100 LOC
• Las claves son char * y los valores void * . No es necesario copiarlos.
• No es necesario implementar remove () , pero contiene () es necesario o put () debe reemplazar el valor.

PD: lo etiqueté como tarea , ya que podría ser. Solo estoy siendo muy vago y quiero evitar todos los escollos comunes que podría encontrar mientras se reimplementa.

Answer 1

Aquí hay una muy simple e ingenua

• Tamaño de cubo fijo
• Sin operación de eliminación
• inserta reemplaza la clave y el valor, y opcionalmente puede liberarlos

:

#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

Christoper Clark's la implementación de tabla hash es muy sencilla. Tiene más de 100 líneas, pero no mucho.

El código de Clark parece haber llegado a Biblioteca de concurrencia de Google como ejemplo de paralelización.

Answer 3

std :: map en C ++ es un árbol rojo-negro debajo del capó; ¿Qué pasa con el uso de una implementación de árbol rojo-negro existente en C ? El que vinculé es más como 700 LOC, pero está bastante bien comentado y parece cuerdo por la mirada superficial que le di. Probablemente puedas encontrar otros; este fue el primer éxito en Google para " C árbol rojo-negro " ;.

Si no eres exigente con el rendimiento, también puedes usar un árbol binario desequilibrado o un montón mínimo o algo así. Con un árbol binario equilibrado, tiene garantizada la búsqueda de O (log n); con un árbol desequilibrado, el peor caso para la búsqueda es O (n) (para el caso patológico donde los nodos se insertan en orden, por lo que terminas con una rama realmente larga que actúa como una lista enlazada), pero (si mi oxidado memoria es correcta) el caso promedio sigue siendo O (log n).

Answer 4

Puede intentar usar la siguiente implementación

clib

Answer 5

memcached ?

No es un fragmento de código, sino un motor de almacenamiento en caché distribuido de alto rendimiento.

Answer 6

No vago, muy sensato para evitar escribir estas cosas.

¿Cómo es que esta biblioteca nunca la usé yo mismo pero parece afirmar que hace lo que usted pide.

Answer 7

Dave Hanson C Interfaces e implementaciones también incluye una buena tabla hash como muchos otros módulos útiles. La tabla hash registra 150 líneas, pero eso incluye administración de memoria, una función de mapeo de orden superior y conversión a matriz. El software es gratuito y vale la pena comprar el libro.

Answer 8

Encontramos una implementación aquí: c file y h archivo que está bastante cerca de lo que solicitó . Licencia W3C