View on GitHub

hashmap

Templated type-safe hashmap implementation in C using open addressing and linear probing for collision resolution.

hashmap

ci

Templated type-safe hashmap implementation in C using open addressing and linear probing for collision resolution.

Summary

This project came into existence because there are a notable lack of flexible and easy to use data structures available in C. C data structures with efficient, type-safe interfaces are virtually non-existent. Higher level languages have built-in libraries and templated classes, but plenty of embedded projects or higher level libraries are implemented in C. When it is undesireable to depend on a bulky library like Glib or grapple with a restrictive license agreement, this is the library for you.

Goals

API Examples

Declaring a type-specific hashmap

Use the HASHMAP(key_type, value_type) macro to declare a hashmap state struct specific to your needs. Keys and values are always passed in by pointer. Keys are const.

/* Map with string key (const char *) and integer value (int *) */
HASHMAP(char, int) map1;

/* Map with uint64 key (const uint64_t *) and struct value (struct my_value *) */
HASHMAP(uint64_t, struct my_value) map2;

The structure defined by the HASHMAP() macro may be used directly, or named using typedef. For example:

typedef HASHMAP(char, struct my_value) value_map_t;

Initialization and cleanup

Maps must be initialized with a key hash function and a key comparator.

/* Initialize the map structure */
hashmap_init(&map, my_key_hash, my_key_compare);

/* Use the map... */

/* Free resources associated with the map */
hashmap_cleanup(&map);

This library provides some hash functions, so you may not have to write your own:

I recommend using these, unless you have very specific needs.

/* Initialize a map with case-sensitive string keys */
hashmap_init(&map, hashmap_hash_string, strcmp);

Note that memory associated with map keys and values is not managed by the map, so you may need to free this before calling hashmap_cleanup(). Keys are often stored in the same structure as the value, but it is possible to have the map manage key memory allocation internally, by calling hashmap_set_key_alloc_funcs().

Value insertion and access

/* Insert a my_value (fails and returns -EEXIST if the key already exists) */
int result = hashmap_put(&map, "KeyABC", val);

/* Access the value with a given key */
struct my_value *val = hashmap_get(&map, "KeyABC");

Value removal

/* Erase the entry with the given key */
struct my_value *val = hashmap_remove(&map, "KeyABC");

/* Erase all entries */
hashmap_clear(&map);

/* Erase all entries and reset the hash table to its initial size */
hashmap_reset(&map);

Iteration

Iteration may be accomplished using the “convenience” foreach macros, or by using the iterator interface directly. Generally, the foreach macros are the most intuitive and convenient.

const char *key;
struct my_value *val;

/* Iterate over all map entries and access both keys and values */
hashmap_foreach(key, val, &map) {
    /* Access each entry */
}

/* Iterate over all map entries and access just keys */
hashmap_foreach_key(key, &map) {
    /* Access each entry */
}

/* Iterate over all map entries and access just values */
hashmap_foreach_data(val, &map) {
    /* Access each entry */
}

The above iteration macros are only safe for read-only access. To safely remove the current element during iteration, use the macros with a _safe suffix. These require an additional pointer parameter. For example:

const char *key;
struct my_value *val;
void *temp;

/* Okay */
hashmap_foreach_key_safe(key, &map, temp) {
    hashmap_remove(&map, key);
}

Iteration using the iterator interface.

HASHMAP_ITER(map) it;

for (it = hashmap_iter(&map); hashmap_iter_valid(&it); hashmap_iter_next(&it) {
	/*
	 * Access entry using:
	 *   hashmap_iter_get_key()
	 *   hashmap_iter_get_data()
	 *   hashmap_iter_set_data()
	 */
}

Additional examples

Are located in the examples directory in the source tree.

How to Build and Install

This project uses CMake to orchestrate the build and installallation process. To build and install on your host system, follow these easy steps:

  1. git clone https://github.com/DavidLeeds/hashmap.git - download the source
  2. mkdir build-hashmap && cd build-hashmap - create a build directory outside the source tree
  3. cmake ../hashmap - run CMake to setup the build
  4. make - compile the code
  5. make test - run the unit tests (if enabled)
  6. sudo make install - OPTIONAL install the library on this system
CMake Options

Contibutions and Questions

I welcome all questions and contributions. Feel free to e-mail me, or put up a pull request. The core algorithm is stable, but I’m happy to consider CMake improvements, compiler compatibility fixes, or API additions.