Map.h

Hasmap implementation in C.

License: GPL-3.0-or-later.

This map has rather interesting API and contains.

No resize

It does not resize on its own, but you can approximate usage by checking number of elements in each bucket and reallocate map when it will not create performance problems in your app. This can be done by just creating a new map and copying data from an old one (this is then only way to resize hasmap implemented like this).

Not a tree

It is implemented as a real hasmap and has O(1) access time (at least until most buckets have at most one element in them). If buckets are full performace start to degrade to O(n) where n is average number of elements in a bucket.

Managing data is user’s responsibility

It does not have set operation, only get and get_or_alloc. Because working with generic datatypes in C is pretty hard, this map does not rely on a type of key or data. User need to supply size of a key and full pair struct in bytes, and then key compared and hashed as byte array of specified size. Map functions always take key by pointer because of this. Elements is never written and get_or_alloc returns empty zero-initialized memory. You need to write key and value yourself there. You can treat this memory as either two byte arrays one after another or cast it to some struct.

Map can also use custom clear function for elements (because it can consist of any data, including pointers that “own” some external memory. While this function primary role is to clear element, it can also be used to properly free key that need some extra care to do that.

Support for C-strings as keys

For key one extra case is handled - if key size is declared as 0, then key is assumed to be const char* pointer to NULL-terminated string. This will be used only when hashing or comparing keys, so if key is not a constant string and may need to be freed, proper clear function should be provided.

Extensibility

If key has some specific properties, or is not stored inline in pair structure, then custom hash and keycmp functions can be provided.

If extra data need to be attached to a map, eg. key is an array, with size fixed per map object, structure like this can be defined:

typedef struct map_with_array_key_t {
    cbuild_map_t map;
    size_t key_element_count;
} map_with_array_key_t;

Then pointer to .map is passe to map function, but because C places struct fields in memory in a same way they are defined in code, this pointer can later be converted to pointer to outside structure by any of user-passed hook function. This will allow to access any additional data without using standard way of passing arguments to callback via void* parameter, thus simplifying API for a general use case.

cbuild_map_hash_t

typedef size_t (*cbuild_map_hash_t)(const void* map, const void* key);

Hash function for a key.

const void* map Pointer to map object. Can be used to retrieve extra data.
const void* key Pointer to a start of key (start of pair structure).

size_t Hash of this specific key. Will be truncated via % nbuckets.

cbuild_map_keycmp_t

typedef bool (*cbuild_map_keycmp_t)(const void* map, const void* k1,
const void* k2);

Key comparison function. Should return true if keys are the same.

This function should resolve hash collisions, so it can not rely on comparing hashes.

const void* map Pointer to map object. Can be used to retrieve extra data.
const void* k1 Pointer to a start of key 1 (start of pair structure).
const void* k2 Pointer to a start of key 2 (start of pair structure).

cbuild_map_clear_t

typedef void (*cbuild_map_clear_t)(const void* map, void* elem);

Element clear function.

const void* map Pointer to map object. Can be used to retrieve extra data.
void* elem Element that should be cleared. Pointer to a start of a pair structure.

cbuild_map_bucket_t

typedef struct cbuild_map_bucket_t {
void* vals;
size_t nvals;
} cbuild_map_bucket_t;

This structure is internal and should not be used outside of a map. It is docomented because it can be used to retrieve usage starts from a map.

void* vals Data of this bucket. Byte array of all pairs.
size_t nvals Number of values stored in this bucket.

cbuild_map_t

typedef struct cbuild_map_t {
cbuild_map_bucket_t* buckets;
size_t nbuckets;
cbuild_map_hash_t hash_func;
cbuild_map_keycmp_t keycmp_func;
cbuild_map_clear_t clear_func;
size_t key_size;
size_t elem_size;
size_t iter_buckets;
size_t iter_vals;
} cbuild_map_t;

Map structure. Some fields here are considered as configuration data, and should be modified by user by hand, while others are considered internal values and should not be modified (but still can be if you know what you are doing).

cbuild_map_bucket_t* buckets List of bucket this map has. Pre-allocated on by cbuild_map_init.
size_t nbuckets Number of buckets. Parameter to cbuild_map_init.
cbuild_map_hash_t hash_func Custom hash function, can be left as NULL if unused.
cbuild_map_keycmp_t keycmp_func Custom key comparison function, can be NULL if unused.
size_t key_size Size of key. Should be set manually before call to cbuild_map_init.
size_t elem_size Size of pair structure. Should be set manually before call to cbuild_map_init.
size_t iter_buckets Internal counter used by iterator functions.
size_t iter_vals Internal counter used by iterator functions.

cbuild_map_init

CBUILDDEF void cbuild_map_init(cbuild_map_t* map, size_t nbuckets);

Initialize a new map. Both key_size and elem_size must be valid at this point. If needed hash_func, keycmp_func and clear_func can be invalid, but it is better to init everything in one place, so it is a good practive to have them valid before call to init too.