Repository files navigation

A simple one header hashmap implementation for C/C++.

Just#include "hashmap.h" in your code!

The current supported compilers are gcc, clang and msvc.

The current supported platforms are Linux, macOS and Windows.

The hashmap is made to work with any arbitrary data keys - you just provide apointer and size, and it'll hash that data. The default hasher is a crc32variant using hardware intrinsics if possible, and the default comparer justusesmemcmp, so zeroing out any padding in struct keys is advisable.

To create a hashmap call thehashmap_create function:

constunsignedinitial_size=2;structhashmap_shashmap;if (0!=hashmap_create(initial_size,&hashmap)) {// error!}

Theinitial_size parameter only sets the initial size of the hashmap - whichcan grow if multiple keys hit the same hash entry. The size of the hashmap isrounded up to the nearest power of two above the providedinitial_size.

There is also an extended creation functionhashmap_create_ex:

structhashmap_shashmap;structhashmap_create_options_soptions;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!}

To put an item in the hashmap use thehashmap_put function:

intmeaning_of_life=42;charquestion=6*8;if (0!=hashmap_put(&hashmap,"life",strlen("life"),&meaning_of_life)) {// error!}if (0!=hashmap_put(&hashmap,"?",strlen("?"),&question)) {// error!}

Notice that multiple entries ofdiffering types can exist in the same hashmap.The hashmap is not typed - it can store anyvoid* data as the value for a key.

To get an entry from a hashmap use thehashmap_get function:

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

The function will returnNULL if the element is not found. Note that the keyused to get an element does not have to be the same pointer used to put anelement in the hashmap - but the string slice must match for a hit to occur.

To remove an entry from a hashmap use thehashmap_remove function:

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

The function will return non-zero if the element is not found. Note that the keyused to get an element does not have to be the same pointer used to put anelement in the hashmap - but the string slice must match for a hit to occur.

You can iterate over all the elements stored in the hashmap with thehashmap_iterate function:

staticintiterate(void*constcontext,void*constvalue) {// 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.return0;  }// Otherwise tell the iteration to keep going.return1;}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}

You can early exit from the iteration of the hashmap by returning non-zero fromyour callback function - perhaps you want to process and remove all elementsfrom the hashmap or search for a specific value only. Otherwise if zero isreturned from your callback then the iteration will encompass the entirehashmap.

In some applications, such as needing to print out the contents of a hashmap,you need to have access to the key and key length in addition to the value.For that purpose a second iterator has been added calledhashmap_iterate_pairs.

Also, returning a -1 from the callback function allows automatic removal of thecurrent item. This is especially handy when storing dynamically allocatedobjects to the map and needing to free the memory when destroying the map.

intlog_and_free_all(void*constcontext,structhashmap_element_s*conste) {intcounter;for (counter=0;counter<e->key_len;counter++) {fputc(e->key[counter], (FILE)context);  }fprintf((FILE)context,"=%s pair has been freed\n", (char*)e->data);free(e->data);return-1;}voidshut_down() {if (0!=hashmap_iterate_pairs(&hash,log_and_free_all, (void*)log)) {fprintf(stderr,"failed to deallocate hashmap entries\n");  }fclose(log);hashmap_destroy(&hash);}

To get the number of entries that have been put into a hashmap use thehashmap_num_entries function:

unsignednum_entries=hashmap_num_entries(&hashmap);

To get the actual number of buckets allocated in the hashmap (the capacity) usethehashmap_capacity function:

unsignednum_entries=hashmap_capacity(&hashmap);

To destroy a hashmap when you are finished with it use thehashmap_destroyfunction:

hashmap_destroy(&hashmap);

This code was almost entirely written by the awesomePete Warden, based on a now defunctblog postby Elliott Back. The authors have applied the following further changes:

• Merged the .c / .h to create a single header (meaning easier integrations withexternal projects).
• Used an explicitly public domain license for the code - theunlicense.
• Changed the API to take arbitrary data pointers and length (it was originallysolely for UTF-8 string slices).
• Did a pass to clean up the comments and function signatures.
• Added second iterator, tests and documentation. (Samuel D. Crow)

This is free and unencumbered software released into the public domain.

Anyone is free to copy, modify, publish, use, compile, sell, ordistribute this software, either in source code form or as a compiledbinary, for any purpose, commercial or non-commercial, and by anymeans.

In jurisdictions that recognize copyright laws, the author or authorsof this software dedicate any and all copyright interest in thesoftware to the public domain. We make this dedication for the benefitof the public at large and to the detriment of our heirs andsuccessors. We intend this dedication to be an overt act ofrelinquishment in perpetuity of all present and future rights to thissoftware under copyright law.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OFMERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OROTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OROTHER DEALINGS IN THE SOFTWARE.

For more information, please refer tohttp://unlicense.org/