hashmap.h

#️⃣ hashmap.h

Una implementación simple de un mapa hash de encabezado para C/C++.

Uso

¡Simplemente #include "hashmap.h" en tu código!

Los compiladores soportados actualmente son gcc, clang y msvc.

Las plataformas soportadas actualmente son Linux, macOS y Windows.

Diseño fundamental

El hashmap está diseñado para funcionar con cualquier clave de datos arbitraria: simplemente proporcione un puntero y un tamaño, y procesará esos datos. El hasher predeterminado es una variante crc32 que utiliza hardware intrínseco si es posible, y el comparador predeterminado solo usa memcmp , por lo que es recomendable poner a cero cualquier relleno en las claves de estructura.

Crear un mapa hash

Para crear un hashmap llame a la función hashmap_create :

 const unsigned initial_size = 2 ;
struct hashmap_s hashmap ;
if ( 0 != hashmap_create ( initial_size , & hashmap )) {
  // error!
}

El parámetro initial_size solo establece el tamaño inicial del mapa hash, que puede crecer si varias claves presionan la misma entrada hash. El tamaño del mapa hash se redondea a la potencia de dos más cercana por encima del initial_size proporcionado.

También hay una función de creación extendida 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!
}

Poner algo en un mapa hash

Para poner un elemento en el hashmap use la función 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!
}

Tenga en cuenta que pueden existir varias entradas de diferentes tipos en el mismo mapa hash. El mapa hash no está escrito; puede almacenar cualquier dato void* como valor de una clave.

Obtener algo de un Hashmap

Para obtener una entrada de un hashmap use la función hashmap_get :

 void * const element = hashmap_get ( & hashmap , "x" , strlen ( "x" ));
if ( NULL == element ) {
  // error!
}

La función devolverá NULL si no se encuentra el elemento. Tenga en cuenta que la clave utilizada para obtener un elemento no tiene que ser el mismo puntero utilizado para colocar un elemento en el mapa hash, pero el segmento de cadena debe coincidir para que se produzca un acierto.

Eliminar algo de un Hashmap

Para eliminar una entrada de un hashmap use la función hashmap_remove :

 if ( 0 != hashmap_remove ( & hashmap , "x" , strlen ( "x" ))) {
  // error!
}

La función devolverá un valor distinto de cero si no se encuentra el elemento. Tenga en cuenta que la clave utilizada para obtener un elemento no tiene que ser el mismo puntero utilizado para colocar un elemento en el mapa hash, pero el segmento de cadena debe coincidir para que se produzca un acierto.

Iterar sobre un mapa hash

Puede iterar sobre todos los elementos almacenados en el hashmap con la función 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
}

Puede salir anticipadamente de la iteración del mapa hash al devolver un valor distinto de cero desde su función de devolución de llamada; tal vez desee procesar y eliminar todos los elementos del mapa hash o buscar solo un valor específico. De lo contrario, si su devolución de llamada devuelve cero, la iteración abarcará todo el mapa hash.

Iterador alternativo para pares clave-valor

En algunas aplicaciones, como la necesidad de imprimir el contenido de un mapa hash, es necesario tener acceso a la clave y a la longitud de la clave además del valor. Para ello se ha agregado un segundo iterador llamado hashmap_iterate_pairs .

Además, devolver un -1 desde la función de devolución de llamada permite la eliminación automática del elemento actual. Esto es especialmente útil cuando se almacenan objetos asignados dinámicamente en el mapa y se necesita liberar memoria al destruir el mapa.

 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 );
}

Obtener el número de entradas en un Hashmap

Para obtener la cantidad de entradas que se han colocado en un hashmap, use la función hashmap_num_entries :

 unsigned num_entries = hashmap_num_entries ( & hashmap );

Obtenga la capacidad de un Hashmap

Para obtener la cantidad real de depósitos asignados en el hashmap (la capacidad), use la función hashmap_capacity :

 unsigned num_entries = hashmap_capacity ( & hashmap );

Destruir un mapa hash

Para destruir un hashmap cuando haya terminado con él, use la función hashmap_destroy :

 hashmap_destroy ( & hashmap );

Propiedad del código

Este código fue escrito casi en su totalidad por el increíble Pete Warden, basado en una publicación de blog ahora desaparecida de Elliott Back. Los autores han aplicado los siguientes cambios adicionales:

• Se fusionó .c/.h para crear un encabezado único (lo que significa integraciones más fáciles con proyectos externos).
• Usó una licencia de dominio público explícitamente para el código: la deslicencia.
• Se cambió la API para aceptar longitudes y punteros de datos arbitrarios (originalmente era únicamente para segmentos de cadena UTF-8).
• Hice una pasada para limpiar los comentarios y las firmas de funciones.
• Se agregó un segundo iterador, pruebas y documentación. (Samuel D. Cuervo)

Licencia

Este es un software gratuito y sin trabas lanzado al dominio público.

Cualquier persona es libre de copiar, modificar, publicar, usar, compilar, vender o distribuir este software, ya sea en forma de código fuente o como binario compilado, para cualquier propósito, comercial o no comercial, y por cualquier medio.

En jurisdicciones que reconocen las leyes de derechos de autor, el autor o autores de este software dedican todos y cada uno de los derechos de autor del software al dominio público. Hacemos esta dedicación en beneficio del público en general y en perjuicio de nuestros herederos y sucesores. Pretendemos que esta dedicación sea un acto abierto de renuncia a perpetuidad de todos los derechos presentes y futuros de este software según la ley de derechos de autor.

EL SOFTWARE SE PROPORCIONA "TAL CUAL", SIN GARANTÍA DE NINGÚN TIPO, EXPRESA O IMPLÍCITA, INCLUYENDO, PERO NO LIMITADO A, LAS GARANTÍAS DE COMERCIABILIDAD, IDONEIDAD PARA UN PROPÓSITO PARTICULAR Y NO INFRACCIÓN. EN NINGÚN CASO LOS AUTORES SERÁN RESPONSABLES DE NINGÚN RECLAMO, DAÑO U OTRA RESPONSABILIDAD, YA SEA EN UNA ACCIÓN CONTRACTUAL, AGRAVIO O DE OTRA MANERA, QUE SURJA DE, FUERA DE O EN RELACIÓN CON EL SOFTWARE O EL USO U OTRAS NEGOCIOS EN EL SOFTWARE.

Para obtener más información, consulte http://unlicense.org/