Implémentation très simple de la carte en C (à des fins d’encadrement)?

Question

J'ai un programme qui lit les URL dans un fichier et effectue un gethostbyname () sur chaque hôte URL. Cet appel est assez consommateur. Je veux les cacher.

Existe-t-il un fragment de code de base de carte très simple en C que je pourrais utiliser pour effectuer la mise en cache? (Je ne veux tout simplement pas réinventer la roue).

Il doit comporter les points suivants:

• Open-source avec une licence permissive (pensez à BSD ou au domaine public).
• Très simple: idéalement, moins de 100 LOC
Les
• clés sont char * et les valeurs void * . Pas besoin de les copier.
• Pas vraiment besoin d'implémenter remove () , mais contient () est nécessaire ou put () devrait remplacer la valeur.

PS: je l'ai étiqueté devoir , puisqu'il pourrait l'être. Je suis juste très paresseux et veux éviter tous les pièges courants que je pourrais rencontrer lors de la réimplémentation.

Answer 1

En voici un très simple et naïf

• Taille de seau fixe
• Aucune opération de suppression
• insère remplace la clé et la valeur et peut éventuellement les libérer

:

#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

de Christoper Clark La mise en œuvre de hashtable est très simple. C'est plus de 100 lignes, mais pas beaucoup.

Le code de Clark semble être entré dans Bibliothèque de concurrence de Google comme exemple de parallélisation.

Answer 3

std :: map en C ++ est un arbre rouge-noir sous le capot; Qu'en est-il d'utiliser une implémentation existante de l'arbre rouge-noir en C ? Celui que j'ai lié ressemble plus à 700 LOC, mais il est assez bien commenté et semble sain d'esprit après le coup d'œil rapide que j'ai jeté. Vous pouvez probablement en trouver d'autres. celui-ci a été le premier succès sur Google pour "C arbre rouge-noir".

Si vous n’êtes pas pointilleux en matière de performances, vous pouvez également utiliser un arbre binaire non équilibré, un min-tas ou quelque chose du genre. Avec un arbre binaire équilibré, vous êtes assuré d'obtenir une recherche O (log n); avec un arbre déséquilibré, le cas le plus défavorable pour la recherche est O (n) (pour le cas pathologique où les noeuds sont insérés dans l’ordre, de sorte que vous obtenez une très longue branche qui agit comme une liste chaînée), mais la mémoire est correcte) la moyenne des cas est toujours O (log n).

Answer 4

Vous pouvez essayer d'utiliser l'implémentation suivante

clib

Answer 5

memcached ?

Ce n'est pas un extrait de code, mais un moteur de cache distribué hautes performances.

Answer 6

Pas paresseux, profondément sensible pour éviter d'écrire ce genre de choses.

Comment cette bibliothèque ne l'a-t-elle jamais utilisée mais elle semble prétendre faire quoi vous demandez.

Answer 7

Les Interfaces et implémentations C de Dave Hanson comprennent également une belle table de hachage. comme beaucoup d'autres modules utiles. La table de hachage compte 150 lignes, mais cela inclut la gestion de la mémoire, une fonction de mappage d'ordre supérieur et la conversion en tableau. Le logiciel est gratuit et le livre vaut la peine d'être acheté.

Answer 8

Vous avez trouvé une implémentation ici: c fichier et un h fichier assez proche de ce que vous avez demandé . Licence W3C