Map.h

Hasmap implementation in C.

License: GPL-3.0-or-later.

This implements open-addressing hashmap built on top of dynamic array. Below there is a few details about implementation.

No resize

Resize is complex and slow. User need to perform it manually, as map can overflow. Each append operation may report failure. Also, you may manually calculate map utilization (both high number of used elements and a lot of deleted elements are bad signals).

Creating your map

Underlying store is just a dynamic array with a few more fields:

typedef struct cbuild_map_t {
    cbuild_map_pair_t* data;
    size_t size;
    size_t capacity;
    cbuild_map_hash_t hash;
    cbuild_map_keycmp_t keycmp;
    cbuild_map_clear_t clear;
} cbuild_map_t;

You can init all function pointers to default values using one of cbuild_map_init_* functions.

Pair structure also need to have some fields:

typedef struct cbuild_map_pair_t {
    T key;
    cbuild_map_tombstone_t tombstone;
} cbuild_map_pair_t;

Key can be any value, but you need to use init function that support specific type of keys.

Removing memory

To emove memory you first need to get pair, and then set tombstone to CBUILD_MAP_DELETED. You can also run map->clear(map, pair) if you actually used clear function for this map instance. Or you can manually clear what is needed for this specific pair.

Backing memory

Backing memory is a dynamic array. It allows to do a few things for maps (like freeing it, iterating over all elements, accessing elements if you have index, etc). But you should set size to capacity after resize for this to properly work. Also, capacity must be power-of-2

cbuild_map_hash_t

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

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 & (map.capacity - 1).

cbuild_map_keycmp_t

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

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_tombstone_t

typedef enum cbuild_map_tombstone_t {
CBUILD_MAP_EMPTY = 0,
CBUILD_MAP_FULL,
CBUILD_MAP_DELETED,
} cbuild_map_tombstone_t;

Tombstones enum

cbuild_map_init_num

#define cbuild_map_init_num(map)

Initialize map which uses numbers as keys (number can be arbitrary in size and is more like “a random binary blob”).

cbuild_map_t* map Map object.

cbuild_map_init_cstr

#define cbuild_map_init_cstr(map)

Initialize map which uses c-strings as keys.

cbuild_map_t* map Map object.

cbuild_map_init_sv

#define cbuild_map_init_sv(map)

Initialize map which uses string views as keys.

cbuild_map_t* map Map object.

cbuild_map_init_sb

#define cbuild_map_init_sb(map)

Initialize map which uses string builders as keys.

cbuild_map_t* map Map object.

cbuild_map_find

#define cbuild_map_find(map, key_)

Find element in a map. This function is guaranteed to not modify map.

This function may return NULL if element is not in a map.

cbuild_map_t* map Map object.
typeof(map->data[0 key_.key)] Key.

typeof(map->data) Pointer to a pair.

cbuild_map_find_idx

#define cbuild_map_find_idx(map, key_)

Find element in a map. This function is guaranteed to not modify map.

This function may return (size_t)-1 if element is not in a map.

cbuild_map_t* map Map object.
typeof(map->data[0 key_.key)] Key.

size_t Pointer to a pair.

cbuild_map_append

#define cbuild_map_append(map, key_)

Set element in map. This will allocate new element (even if element with same key exists in map already). This function can be a little faster than cbuild_map_get as it returns on first EMPTY/DELETED slot found, and cbuild_map_get exits only on EMPTY slow or when key is found.

This function will copy key into new pair using memcpy.

This function may return NULL if map overflows.

cbuild_map_t* map Map object.
typeof(map->data[0 key_.key)] Key.

typeof(map->data) Pointer to a pair.

cbuild_map_get

#define cbuild_map_get(map, key_)

Set element in map. This will allocate new element if key is not already in map.

This function will copy key into new pair using memcpy.

This function may return NULL if map overflows.

cbuild_map_t* map Map object.
typeof(map->data[0 key_.key)] Key.

typeof(map->data) Pointer to a pair.

cbuild_map_rehash

#define cbuild_map_rehash(map1, map2)

Rehash elements from one map into another. New map is assumed to be larger than old one.

cbuild_map_t* map1 Source map object.
cbuild_map_t* map2 Destination map object.

cbuild_map_resize

#define cbuild_map_resize(map, new_elems)

Resizes the map, sets size and zero-inits memory. This will not rehash older elements into a new size!

This function will automatically round-up size to next power-of-2.

cbuild_map_t* map Map object.
size_t new_elems New size.

This library provides some default hash functions. You can configure

default one using macro CBUILD_MAP_DEFALT_HASH. DJB2 hash.

cbuild_map_hash_fnv1

CBUILDDEF size_t cbuild_map_hash_fnv1(const void* data, size_t len);

FNV1a.

cbuild_map_hash_fnv1a

CBUILDDEF size_t cbuild_map_hash_fnv1a(const void* data, size_t len);

FNV1.

cbuild_map_hash_sdbm

CBUILDDEF size_t cbuild_map_hash_sdbm(const void* data, size_t len);

SDBM.

Internal functions

cbuild-map-internal

__cbuild_map_cstr_hash

CBUILDDEF size_t __cbuild_map_cstr_hash(const void* map,
const void* key, size_t klen);

__cbuild_map_sv_hash

CBUILDDEF size_t __cbuild_map_sv_hash(const void* map,
const void* key, size_t klen);

__cbuild_map_sb_hash

CBUILDDEF size_t __cbuild_map_sb_hash(const void* map,
const void* key, size_t klen);

__cbuild_map_num_keycmp

CBUILDDEF bool __cbuild_map_num_keycmp(const void* map,
const void* k1, const void* k2, size_t klen);

__cbuild_map_cstr_keycmp

CBUILDDEF bool __cbuild_map_cstr_keycmp(const void* map,
const void* k1, const void* k2, size_t klen);

__cbuild_map_sv_keycmp

CBUILDDEF bool __cbuild_map_sv_keycmp(const void* map,
const void* k1, const void* k2, size_t klen);

__cbuild_map_sb_keycmp

CBUILDDEF bool __cbuild_map_sb_keycmp(const void* map,
const void* k1, const void* k2, size_t klen);

__cbuild_map_step

CBUILDDEF size_t __cbuild_map_step(size_t prev);

Implements Splitmix64.