hashmap.h

#️⃣ hashmap.h

Eine einfache Ein-Header-Hashmap-Implementierung für C/C++.

Verwendung

#include "hashmap.h" in Ihren Code ein!

Die aktuell unterstützten Compiler sind gcc, clang und msvc.

Die aktuell unterstützten Plattformen sind Linux, macOS und Windows.

Grundlegendes Design

Die Hashmap ist so konzipiert, dass sie mit beliebigen Datenschlüsseln funktioniert. Sie geben lediglich einen Zeiger und eine Größe an, und die Daten werden gehasht. Der Standard-Hasher ist eine crc32-Variante, die nach Möglichkeit Hardware-Intrinsics verwendet, und der Standard-Vergleicher verwendet nur memcmp , daher ist es ratsam, alle Auffüllungen in Strukturschlüsseln auf Null zu setzen.

Erstellen Sie eine Hashmap

Um eine Hashmap zu erstellen, rufen Sie die Funktion hashmap_create auf:

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

Der Parameter initial_size legt nur die Anfangsgröße der Hashmap fest – diese kann wachsen, wenn mehrere Schlüssel auf denselben Hash-Eintrag treffen. Die Größe der Hashmap wird auf die nächste Zweierpotenz über der angegebenen initial_size aufgerundet.

Es gibt auch eine erweiterte Erstellungsfunktion 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!
}

Fügen Sie etwas in eine Hashmap ein

Um ein Element in die Hashmap einzufügen, verwenden Sie die Funktion 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!
}

Beachten Sie, dass in derselben Hashmap mehrere Einträge unterschiedlichen Typs vorhanden sein können. Die Hashmap ist nicht typisiert – sie kann beliebige void* -Daten als Wert für einen Schlüssel speichern.

Holen Sie sich etwas aus einer Hashmap

Um einen Eintrag aus einer Hashmap abzurufen, verwenden Sie die Funktion hashmap_get :

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

Die Funktion gibt NULL zurück, wenn das Element nicht gefunden wird. Beachten Sie, dass der zum Abrufen eines Elements verwendete Schlüssel nicht derselbe Zeiger sein muss, der zum Einfügen eines Elements in die Hashmap verwendet wurde – das String-Slice muss jedoch übereinstimmen, damit ein Treffer erfolgt.

Etwas aus einer Hashmap entfernen

Um einen Eintrag aus einer Hashmap zu entfernen, verwenden Sie die Funktion hashmap_remove :

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

Die Funktion gibt einen Wert ungleich Null zurück, wenn das Element nicht gefunden wird. Beachten Sie, dass der zum Abrufen eines Elements verwendete Schlüssel nicht derselbe Zeiger sein muss, der zum Einfügen eines Elements in die Hashmap verwendet wurde – das String-Slice muss jedoch übereinstimmen, damit ein Treffer erfolgt.

Iterieren Sie über eine Hashmap

Mit der Funktion hashmap_iterate können Sie alle in der Hashmap gespeicherten Elemente durchlaufen:

 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
}

Sie können die Iteration der Hashmap vorzeitig beenden, indem Sie von Ihrer Rückruffunktion einen Wert ungleich Null zurückgeben. Vielleicht möchten Sie alle Elemente verarbeiten und aus der Hashmap entfernen oder nur nach einem bestimmten Wert suchen. Andernfalls umfasst die Iteration die gesamte Hashmap, wenn von Ihrem Rückruf Null zurückgegeben wird.

Alternativer Iterator für Schlüsselwertpaare

In einigen Anwendungen, beispielsweise wenn Sie den Inhalt einer Hashmap ausdrucken müssen, benötigen Sie zusätzlich zum Wert Zugriff auf den Schlüssel und die Schlüssellänge. Zu diesem Zweck wurde ein zweiter Iterator namens hashmap_iterate_pairs hinzugefügt.

Außerdem ermöglicht die Rückgabe einer -1 von der Rückruffunktion das automatische Entfernen des aktuellen Elements. Dies ist besonders praktisch, wenn dynamisch zugewiesene Objekte auf der Karte gespeichert werden und beim Zerstören der Karte Speicherplatz freigegeben werden muss.

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

Ermitteln Sie die Anzahl der Einträge in einer Hashmap

Um die Anzahl der Einträge zu ermitteln, die in eine Hashmap eingefügt wurden, verwenden Sie die Funktion hashmap_num_entries :

 unsigned num_entries = hashmap_num_entries ( & hashmap );

Holen Sie sich die Kapazität einer Hashmap

Um die tatsächliche Anzahl der in der Hashmap zugewiesenen Buckets (die Kapazität) zu erhalten, verwenden Sie die Funktion hashmap_capacity :

 unsigned num_entries = hashmap_capacity ( & hashmap );

Zerstöre eine Hashmap

Um eine Hashmap zu zerstören, wenn Sie damit fertig sind, verwenden Sie die Funktion hashmap_destroy :

 hashmap_destroy ( & hashmap );

Code-Eigentum

Dieser Code wurde fast vollständig vom großartigen Pete Warden geschrieben und basiert auf einem inzwischen nicht mehr existierenden Blogbeitrag von Elliott Back. Die Autoren haben folgende weitere Änderungen vorgenommen:

• .c / .h wurden zusammengeführt, um einen einzigen Header zu erstellen (was einfachere Integrationen mit externen Projekten bedeutet).
• Für den Code wurde eine explizit Public-Domain-Lizenz verwendet – die Unlicense.
• Die API wurde so geändert, dass sie beliebige Datenzeiger und Längen akzeptiert (ursprünglich war sie ausschließlich für UTF-8-String-Slices gedacht).
• Habe versucht, die Kommentare und Funktionssignaturen zu bereinigen.
• Zweiter Iterator, Tests und Dokumentation hinzugefügt. (Samuel D. Crow)

Lizenz

Hierbei handelt es sich um kostenlose und unbelastete Software, die der Öffentlichkeit zugänglich gemacht wird.

Es steht jedem frei, diese Software zu kopieren, zu ändern, zu veröffentlichen, zu verwenden, zu kompilieren, zu verkaufen oder zu verteilen, entweder in Quellcodeform oder als kompilierte Binärdatei, für jeden Zweck, kommerziell oder nichtkommerziell, und mit allen Mitteln.

In Gerichtsbarkeiten, die Urheberrechtsgesetze anerkennen, überlassen der Autor oder die Autoren dieser Software sämtliche Urheberrechtsansprüche an der Software der öffentlichen Domäne. Diese Widmung leisten wir zum Wohle der Allgemeinheit und zum Nachteil unserer Erben und Nachfolger. Wir beabsichtigen, dass diese Widmung ein offener Akt des dauerhaften Verzichts auf alle gegenwärtigen und zukünftigen Rechte an dieser Software gemäß dem Urheberrecht ist.

DIE SOFTWARE WIRD „WIE BESEHEN“ ZUR VERFÜGUNG GESTELLT, OHNE JEGLICHE AUSDRÜCKLICHE ODER STILLSCHWEIGENDE GEWÄHRLEISTUNG, EINSCHLIESSLICH, ABER NICHT BESCHRÄNKT AUF DIE GEWÄHRLEISTUNG DER MARKTGÄNGIGKEIT, EIGNUNG FÜR EINEN BESTIMMTEN ZWECK UND NICHTVERLETZUNG. IN KEINEM FALL SIND DIE AUTOREN HAFTBAR FÜR ANSPRÜCHE, SCHÄDEN ODER ANDERE HAFTUNG, WEDER AUS EINER VERTRAGSKlage, unerlaubter Handlung noch aus anderen Gründen, DIE AUS, AUS ODER IN VERBINDUNG MIT DER SOFTWARE ODER DER NUTZUNG ODER ANDEREN HANDELN MIT DER SOFTWARE ENTSTEHEN.

Weitere Informationen finden Sie unter http://unlicense.org/