hashmap.h
1.0.0
Une implémentation simple de hashmap à un en-tête pour C/C++.
#include "hashmap.h" dans votre code !
Les compilateurs actuellement pris en charge sont gcc, clang et msvc.
Les plates-formes actuellement prises en charge sont Linux, macOS et Windows.
Le hashmap est conçu pour fonctionner avec n'importe quelle clé de données arbitraire - vous fournissez simplement un pointeur et une taille, et il hachera ces données. Le hachage par défaut est une variante de crc32 utilisant si possible des éléments matériels intrinsèques, et le comparateur par défaut utilise simplement memcmp , il est donc conseillé de mettre à zéro tout remplissage dans les clés de structure.
Pour créer un hashmap, appelez la fonction hashmap_create :
const unsigned initial_size = 2 ;
struct hashmap_s hashmap ;
if ( 0 != hashmap_create ( initial_size , & hashmap )) {
// error!
} Le paramètre initial_size définit uniquement la taille initiale du hashmap - qui peut augmenter si plusieurs clés atteignent la même entrée de hachage. La taille du hashmap est arrondie à la puissance de deux la plus proche au-dessus de la initial_size fournie.
Il existe également une fonction de création étendue hashmap_create_ex :
struct hashmap_s hashmap ;
struct hashmap_create_options_s options ;
memset ( & options , 0 , sizeof ( options ));
// You can set a custom hasher that the hashmap should use.
options . hasher = & my_hasher ;
// You can set a custom comparer that the hashmap should for comparing keys.
options . comparer = & my_comparer ;
// You can also specify the initial capacity of the hashmap.
options . initial_capacity = 42 ;
if ( 0 != hashmap_create_ex ( options , & hashmap )) {
// error!
} Pour mettre un élément dans le hashmap, utilisez la fonction hashmap_put :
int meaning_of_life = 42 ;
char question = 6 * 8 ;
if ( 0 != hashmap_put ( & hashmap , "life" , strlen ( "life" ), & meaning_of_life )) {
// error!
}
if ( 0 != hashmap_put ( & hashmap , "?" , strlen ( "?" ), & question )) {
// error!
} Notez que plusieurs entrées de types différents peuvent exister dans la même hashmap. Le hashmap n'est pas typé - il peut stocker n'importe quelle donnée void* comme valeur d'une clé.
Pour obtenir une entrée d'un hashmap, utilisez la fonction hashmap_get :
void * const element = hashmap_get ( & hashmap , "x" , strlen ( "x" ));
if ( NULL == element ) {
// error!
} La fonction retournera NULL si l'élément n'est pas trouvé. Notez que la clé utilisée pour obtenir un élément ne doit pas nécessairement être le même pointeur que celui utilisé pour placer un élément dans la table de hachage - mais la tranche de chaîne doit correspondre pour qu'un accès se produise.
Pour supprimer une entrée d'un hashmap, utilisez la fonction hashmap_remove :
if ( 0 != hashmap_remove ( & hashmap , "x" , strlen ( "x" ))) {
// error!
}La fonction retournera une valeur différente de zéro si l'élément n'est pas trouvé. Notez que la clé utilisée pour obtenir un élément ne doit pas nécessairement être le même pointeur que celui utilisé pour placer un élément dans la table de hachage - mais la tranche de chaîne doit correspondre pour qu'un accès se produise.
Vous pouvez parcourir tous les éléments stockés dans le hashmap avec la fonction hashmap_iterate :
static int iterate ( void * const context , void * const value ) {
// If the value is 42...
if ( 42 == * ( int * ) value ) {
// Store into our user-provided context the value.
* ( void * * ) context = value ;
// Return 0 to tell the iteration to stop here.
return 0 ;
}
// Otherwise tell the iteration to keep going.
return 1 ;
}
int * value ;
if ( 0 != hashmap_iterate ( & hashmap , iterate , & value )) {
if ( * value != 42 ) {
// error!
}
} else {
// if we got here it means we never found 42 in the hashmap
}Vous pouvez quitter plus tôt l'itération du hashmap en renvoyant une valeur différente de zéro à partir de votre fonction de rappel - peut-être souhaitez-vous traiter et supprimer tous les éléments du hashmap ou rechercher uniquement une valeur spécifique. Sinon, si zéro est renvoyé par votre rappel, l'itération englobera l'intégralité de la table de hachage.
Dans certaines applications, comme la nécessité d'imprimer le contenu d'une hashmap, vous devez avoir accès à la clé et à la longueur de la clé en plus de la valeur. A cet effet, un deuxième itérateur a été ajouté appelé hashmap_iterate_pairs .
De plus, renvoyer un -1 à partir de la fonction de rappel permet la suppression automatique de l'élément actuel. Ceci est particulièrement pratique lors du stockage d'objets alloués dynamiquement à la carte et lorsque vous devez libérer de la mémoire lors de la destruction de la carte.
int log_and_free_all ( void * const context , struct hashmap_element_s * const e ) {
int counter ;
for ( counter = 0 ; counter < e -> key_len ; counter ++ ) {
fputc ( e -> key [ counter ], ( FILE ) context );
}
fprintf (( FILE ) context , "=%s pair has been freedn" , ( char * ) e -> data );
free ( e -> data );
return -1 ;
}
void shut_down () {
if ( 0 != hashmap_iterate_pairs ( & hash , log_and_free_all , ( void * ) log )) {
fprintf ( stderr , "failed to deallocate hashmap entriesn" );
}
fclose ( log );
hashmap_destroy ( & hash );
} Pour obtenir le nombre d'entrées qui ont été placées dans un hashmap, utilisez la fonction hashmap_num_entries :
unsigned num_entries = hashmap_num_entries ( & hashmap ); Pour obtenir le nombre réel de buckets alloués dans le hashmap (la capacité), utilisez la fonction hashmap_capacity :
unsigned num_entries = hashmap_capacity ( & hashmap ); Pour détruire un hashmap lorsque vous en avez terminé, utilisez la fonction hashmap_destroy :
hashmap_destroy ( & hashmap );Ce code a été presque entièrement écrit par le génial Pete Warden, sur la base d'un article de blog aujourd'hui disparu d'Elliott Back. Les auteurs ont appliqué les modifications supplémentaires suivantes :
Il s'agit d'un logiciel gratuit et sans contrainte publié dans le domaine public.
N'importe qui est libre de copier, modifier, publier, utiliser, compiler, vendre ou distribuer ce logiciel, soit sous forme de code source, soit sous forme de binaire compilé, à toute fin, commerciale ou non commerciale, et par tout moyen.
Dans les juridictions qui reconnaissent les lois sur le droit d'auteur, l'auteur ou les auteurs de ce logiciel consacrent tous les droits d'auteur sur le logiciel au domaine public. Nous effectuons cette dédicace au bénéfice du grand public et au détriment de nos héritiers et successeurs. Nous souhaitons que cette dédicace soit un acte manifeste d'abandon à perpétuité de tous les droits présents et futurs sur ce logiciel en vertu de la loi sur le droit d'auteur.
LE LOGICIEL EST FOURNI « EN L'ÉTAT », SANS GARANTIE D'AUCUNE SORTE, EXPRESSE OU IMPLICITE, Y COMPRIS MAIS SANS LIMITATION LES GARANTIES DE QUALITÉ MARCHANDE, D'ADAPTATION À UN USAGE PARTICULIER ET DE NON-VIOLATION. EN AUCUN CAS LES AUTEURS NE SERONT RESPONSABLES DE TOUTE RÉCLAMATION, DOMMAGES OU AUTRE RESPONSABILITÉ, QUE CE SOIT DANS UNE ACTION CONTRACTUELLE, DÉLIT OU AUTRE, DÉCOULANT DE, HORS OU EN RELATION AVEC LE LOGICIEL OU L'UTILISATION OU AUTRES AFFAIRES DANS LE LOGICIEL.
Pour plus d'informations, veuillez vous référer à http://unlicense.org/
