hashmap.h

#️⃣ hashmap.h

Uma implementação simples de hashmap de um cabeçalho para C/C++.

Uso

Basta #include "hashmap.h" no seu código!

Os compiladores atualmente suportados são gcc, clang e msvc.

As plataformas atualmente suportadas são Linux, macOS e Windows.

Projeto Fundamental

O hashmap é feito para funcionar com qualquer chave de dados arbitrária - você apenas fornece um ponteiro e um tamanho, e ele fará o hash desses dados. O hasher padrão é uma variante crc32 usando intrínsecos de hardware, se possível, e o comparador padrão usa apenas memcmp , portanto, é aconselhável zerar qualquer preenchimento nas chaves de estrutura.

Crie um mapa hash

Para criar um hashmap, chame a função hashmap_create :

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

O parâmetro initial_size define apenas o tamanho inicial do hashmap - que pode aumentar se várias chaves atingirem a mesma entrada de hash. O tamanho do hashmap é arredondado para a potência de dois mais próxima acima do initial_size fornecido.

Há também uma função de criação estendida 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!
}

Coloque algo em um hashmap

Para colocar um item no hashmap use a função 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!
}

Observe que várias entradas de tipos diferentes podem existir no mesmo hashmap. O hashmap não é digitado - ele pode armazenar quaisquer dados void* como o valor de uma chave.

Obtenha algo de um Hashmap

Para obter uma entrada de um hashmap use a função hashmap_get :

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

A função retornará NULL se o elemento não for encontrado. Observe que a chave usada para obter um elemento não precisa ser o mesmo ponteiro usado para colocar um elemento no hashmap - mas a fatia da string deve corresponder para que ocorra um acerto.

Remover algo de um Hashmap

Para remover uma entrada de um hashmap use a função hashmap_remove :

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

A função retornará diferente de zero se o elemento não for encontrado. Observe que a chave usada para obter um elemento não precisa ser o mesmo ponteiro usado para colocar um elemento no hashmap - mas a fatia da string deve corresponder para que ocorra um acerto.

Iterar em um Hashmap

Você pode iterar todos os elementos armazenados no hashmap com a função 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
}

Você pode sair antecipadamente da iteração do hashmap retornando um valor diferente de zero da sua função de retorno de chamada - talvez você queira processar e remover todos os elementos do hashmap ou procurar apenas um valor específico. Caso contrário, se zero for retornado do seu retorno de chamada, a iteração abrangerá todo o hashmap.

Iterador alternativo para pares de valores-chave

Em algumas aplicações, como a necessidade de imprimir o conteúdo de um hashmap, você precisa ter acesso à chave e ao comprimento da chave, além do valor. Para esse propósito, um segundo iterador foi adicionado chamado hashmap_iterate_pairs .

Além disso, retornar -1 da função de retorno de chamada permite a remoção automática do item atual. Isso é especialmente útil ao armazenar objetos alocados dinamicamente no mapa e precisar liberar memória ao destruir o 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 );
}

Obtenha o número de entradas em um Hashmap

Para obter o número de entradas que foram colocadas em um hashmap, use a função hashmap_num_entries :

 unsigned num_entries = hashmap_num_entries ( & hashmap );

Obtenha a capacidade de um Hashmap

Para obter o número real de buckets alocados no hashmap (a capacidade), use a função hashmap_capacity :

 unsigned num_entries = hashmap_capacity ( & hashmap );

Destruir um Hashmap

Para destruir um hashmap quando terminar, use a função hashmap_destroy :

 hashmap_destroy ( & hashmap );

Propriedade do código

Este código foi quase inteiramente escrito pelo incrível Pete Warden, baseado em uma postagem de blog extinta de Elliott Back. Os autores aplicaram as seguintes alterações adicionais:

• Mesclamos o .c/.h para criar um único cabeçalho (o que significa integrações mais fáceis com projetos externos).
• Usou uma licença de domínio explicitamente público para o código - a não licença.
• A API foi alterada para obter ponteiros e comprimentos de dados arbitrários (originalmente era apenas para fatias de string UTF-8).
• Fiz uma tentativa de limpar os comentários e assinaturas de funções.
• Adicionado segundo iterador, testes e documentação. (Samuel D. Corvo)

Licença

Este é um software gratuito e desimpedido lançado em domínio público.

Qualquer pessoa é livre para copiar, modificar, publicar, usar, compilar, vender ou distribuir este software, seja na forma de código-fonte ou como binário compilado, para qualquer finalidade, comercial ou não comercial, e por qualquer meio.

Em jurisdições que reconhecem leis de direitos autorais, o autor ou autores deste software dedicam todo e qualquer direito autoral do software ao domínio público. Fazemos esta dedicação em benefício do público em geral e em detrimento dos nossos herdeiros e sucessores. Pretendemos que esta dedicação seja um ato aberto de renúncia perpétua de todos os direitos presentes e futuros a este software sob a lei de direitos autorais.

O SOFTWARE É FORNECIDO "COMO ESTÁ", SEM GARANTIA DE QUALQUER TIPO, EXPRESSA OU IMPLÍCITA, INCLUINDO, MAS NÃO SE LIMITANDO ÀS GARANTIAS DE COMERCIALIZAÇÃO, ADEQUAÇÃO A UM DETERMINADO FIM E NÃO VIOLAÇÃO. EM HIPÓTESE ALGUMA OS AUTORES SERÃO RESPONSÁVEIS POR QUALQUER RECLAMAÇÃO, DANOS OU OUTRA RESPONSABILIDADE, SEJA EM UMA AÇÃO DE CONTRATO, ATO ILÍCITO OU DE OUTRA FORMA, DECORRENTE DE, OU EM CONEXÃO COM O SOFTWARE OU O USO OU OUTRAS NEGOCIAÇÕES NO SOFTWARE.

Para obter mais informações, consulte http://unlicense.org/