#Hash Maps and Sets — Module 210

Type-safe hash maps and sets, generated from a name macro. One header covers both unordered and ordered (FIFO/LRU) variants.

See also: [← 200 types-overview.md](./200 types-overview.md)

#Setup

#define FIO_MAP_NAME my_map    /* required — sets the type and function prefix */
#define FIO_MAP_KEY  uint64_t  /* optional — key type; default is fio_str_info_s (bstr) */
#define FIO_MAP_VALUE void *   /* optional — omit for a Set instead of a Map */
#include "fio-stl.h"

This generates my_map_s and a full API prefixed my_map_*.

Throughout this document MAP stands for whatever name you chose. All examples use map as the name.

#Sets vs. Maps

Set: define only FIO_MAP_NAME (and optionally FIO_MAP_KEY). Each element is the key itself.
Hash Map: also define FIO_MAP_VALUE. Elements are key→value pairs.

If FIO_MAP_KEY is left undefined (or FIO_MAP_KEY_BSTR is defined), keys default to binary strings via fio_str_info_s / fio_bstr.

#Configuration Macros

Set these before #include, after FIO_MAP_NAME.

#Naming shortcuts

Macro	Effect
`FIO_MAP_NAME name`	Required. Sets the type and function prefix.
`FIO_OMAP_NAME name`	Shortcut: defines `FIO_MAP_NAME` and forces `FIO_MAP_ORDERED 1`.
`FIO_UMAP_NAME name`	Shortcut: defines `FIO_MAP_NAME` and forces `FIO_MAP_ORDERED 0`.

#Key configuration

Macro	Default	Effect
`FIO_MAP_KEY`	`fio_str_info_s`	External (API) key type.
`FIO_MAP_KEY_BSTR`	—	Shortcut: API keys are `fio_str_info_s`; internally stored as `fio_bstr` (heap-allocated, NUL-terminated). This is the default when `FIO_MAP_KEY` is not defined.
`FIO_MAP_KEY_KSTR`	—	Shortcut: API keys are `fio_str_info_s`; internally stored as `fio_keystr_s` with small-string optimisation (≤14 bytes inline on 64-bit). Better cache locality than `bstr`.
`FIO_MAP_KEY_INTERNAL`	`FIO_MAP_KEY`	Internal storage type (if different from the API type).
`FIO_MAP_KEY_FROM_INTERNAL(k)`	`k`	Converts internal storage → API type.
`FIO_MAP_KEY_COPY(dest, src)`	`(dest) = (src)`	Copies an API key into internal storage.
`FIO_MAP_KEY_CMP(a, b)`	`(a) == (b)`	Compares an internal key with an API key.
`FIO_MAP_KEY_DESTROY(key)`	(nothing)	Destroys a key in internal storage (free resources).
`FIO_MAP_KEY_DISCARD(key)`	(nothing)	Destroys an API key that was not inserted (e.g. if you pre-allocated or ref-counted it).

#Value configuration

Macro	Default	Effect
`FIO_MAP_VALUE`	(none — Set)	External (API) value type. Defining this makes the template a hash map.
`FIO_MAP_VALUE_BSTR`	—	Shortcut: binary-string values via `fio_bstr`.
`FIO_MAP_VALUE_INTERNAL`	`FIO_MAP_VALUE`	Internal storage type.
`FIO_MAP_VALUE_FROM_INTERNAL(v)`	`v`	Converts internal storage → API type.
`FIO_MAP_VALUE_COPY(dest, src)`	`(dest) = (src)`	Copies an API value into internal storage.
`FIO_MAP_VALUE_DESTROY(v)`	(nothing)	Destroys a value in internal storage.
`FIO_MAP_VALUE_DISCARD(v)`	(nothing)	Destroys an API value that was not stored.

#Hashing

Macro	Default	Effect
`FIO_MAP_HASH_FN(key)`	(not defined)	When defined, the map computes its own hash from the API key. Callers no longer pass a `hash` argument.
`FIO_MAP_RECALC_HASH`	`0`	Set to `1` to skip caching the hash per-node (saves 8 bytes/node). Requires `FIO_MAP_HASH_FN`.

When FIO_MAP_HASH_FN is not defined, every get/set/remove call takes an explicit uint64_t hash argument — letting you salt the hash per-map for defence against hash-flooding.

#Ordering

Macro	Default	Effect
`FIO_MAP_ORDERED`	`0`	Set to `1` (or define without a value) for insertion-order (FIFO) iteration and `evict`. Adds 8 bytes per node.
`FIO_MAP_LRU`	(not defined)	Implies `FIO_MAP_ORDERED 1` and keeps LRU-style iteration order. The value is ignored. Does not auto-evict; call `MAP_evict()` yourself to enforce a size limit.

#Limits

Macro	Default	Effect
`FIO_MAP_ATTACK_LIMIT`	`16`	Max full hash collisions before the map assumes a hash-flooding attack and starts overwriting stale entries.
`FIO_MAP_CAPA_BITS_LIMIT`	`31`	Max exponent for internal capacity (2^31 ≈ 2 billion elements). Cannot exceed 31 without rewriting internal code.

#Initialization

MAP_s m = FIO_MAP_INIT;      /* stack — zero-initialize */

MAP_s *p = MAP_new();        /* heap — allocate + zero-initialize */

FIO_MAP_INIT expands to {0}.

#Lifecycle

MAP_s *MAP_new(void);          /* allocate + initialize on the heap */
void   MAP_free(MAP_PTR map);  /* destroy elements + free the container */
void   MAP_destroy(MAP_PTR map); /* destroy elements, reset to empty (stack-safe) */

Use MAP_destroy for stack-allocated maps. Use MAP_new / MAP_free for heap.

#State

uint32_t MAP_count(MAP_PTR map);       /* number of stored elements */
uint32_t MAP_capa (MAP_PTR map);       /* theoretical capacity (always a power of 2) */
void     MAP_reserve(MAP_PTR map, size_t capa); /* ensure at least capa slots exist */
void     MAP_compact(MAP_PTR map);     /* shrink allocation to fit current count */

#Get, Set, Remove

The exact signature depends on whether FIO_MAP_HASH_FN is defined and whether FIO_MAP_VALUE is defined. Below [hash,] means the uint64_t hash argument is present only when FIO_MAP_HASH_FN is not defined.

/* Returns the stored value (or key for a Set). Zero-value if not found. */
MAP_GET_T MAP_get(MAP_PTR map, [uint64_t hash,] MAP_KEY key);

/* Insert or overwrite. Returns the resulting stored value/key.
   For hash maps: `old` (optional) receives the previous value before it is destroyed. */
MAP_GET_T MAP_set(MAP_PTR map, [uint64_t hash,]
                  MAP_KEY key [, MAP_VALUE val, MAP_VALUE_INTERNAL *old]);

/* Insert only if the key is absent. Returns current value/key. */
MAP_GET_T MAP_set_if_missing(MAP_PTR map, [uint64_t hash,]
                             MAP_KEY key [, MAP_VALUE val]);

/* Remove. Returns 0 on success, -1 if not found.
   `old` (optional): receives the removed value/key before it is destroyed. */
/* For hash maps: */
int MAP_remove(MAP_PTR map, [uint64_t hash,] MAP_KEY key,
               MAP_VALUE_INTERNAL *old);

/* For sets: */
int MAP_remove(MAP_PTR map, [uint64_t hash,] MAP_KEY key,
               MAP_KEY_INTERNAL *old);

/* Evict `n` elements. Order depends on FIO_MAP_LRU / FIO_MAP_ORDERED. */
void MAP_evict(MAP_PTR map, size_t n);

/* Remove all elements without freeing the internal buffer. */
void MAP_clear(MAP_PTR map);

#Low-Level Node Access

MAP_get_ptr and MAP_set_ptr return a pointer into internal storage. Use when you need to mutate a value in place or avoid a copy.

/* Returns internal node pointer, or NULL if missing. */
MAP_node_s *MAP_get_ptr(MAP_PTR map, [uint64_t hash,] MAP_KEY key);

/* Core insert/overwrite. `overwrite=1` replaces an existing value; `overwrite=0` keeps it.
   Returns internal node pointer, or NULL on error. */
MAP_node_s *MAP_set_ptr(MAP_PTR map, [uint64_t hash,]
                        MAP_KEY key [, MAP_VALUE val,
                        MAP_VALUE_INTERNAL *old, int overwrite]);

Accessors for node pointers:

MAP_KEY           MAP_node2key    (MAP_node_s *node); /* external key   */
MAP_VALUE         MAP_node2val    (MAP_node_s *node); /* external value (or key for Sets) */
uint64_t          MAP_node2hash   (MAP_node_s *node); /* hash value     */
MAP_KEY_INTERNAL  *MAP_node2key_ptr(MAP_node_s *node); /* pointer to internal key   */
MAP_VALUE_INTERNAL*MAP_node2val_ptr(MAP_node_s *node); /* pointer to internal value */

All return a zeroed/NULL result when node is NULL.

#Iteration

#`FIO_MAP_EACH` / `FIO_MAP_EACH_REVERSED` — for-loop macros (preferred)

FIO_MAP_EACH(map_name, map_ptr, i) {
  /* i.key   — current key  (API type) */
  /* i.value — current value (API type; absent for Sets) */
  /* i.hash  — current hash  (absent if FIO_MAP_RECALC_HASH is set) */
}

FIO_MAP_EACH_REVERSED(map_name, map_ptr, i) { /* same, backward */ }

i is declared inside the loop as a MAP_iterator_s.

Example:

#define FIO_MAP_NAME     wcount
#define FIO_MAP_KEY_KSTR         /* fio_str_info_s API keys, fio_keystr_s storage */
#define FIO_MAP_VALUE    size_t
#define FIO_MAP_HASH_FN(k) fio_risky_hash((k).buf, (k).len, (uintptr_t)wcount_destroy)
#include "fio-stl.h"

void print_counts(wcount_s *m) {
  FIO_MAP_EACH(wcount, m, it)
    printf("%.*s => %zu\n", (int)it.key.len, it.key.buf, it.value);
}

#Manual iterator API

/* Returns the first iterator (NULL current_pos) or the next one. */
MAP_iterator_s MAP_get_next(MAP_PTR map, MAP_iterator_s *current_pos);

/* Reverse: returns the last (NULL) or the previous one. */
MAP_iterator_s MAP_get_prev(MAP_PTR map, MAP_iterator_s *current_pos);

/* Returns 1 if valid, 0 if exhausted or invalidated. */
int MAP_iterator_is_valid(MAP_iterator_s *iter);

/* Returns the internal node pointer for an iterator. */
MAP_node_s *MAP_iterator2node(MAP_PTR map, MAP_iterator_s *iter);

Modifying the map (insert, rehash) between iterator steps is safe but may invalidate or reorder iterators for unordered maps.

#Callback API

/* Calls task(info) for each element starting at `start_at`.
   Returning -1 from the callback stops the loop.
   Returns the final position (items processed + start_at). */
uint32_t MAP_each(MAP_PTR map,
                  int (*task)(MAP_each_s *info),
                  void *udata,
                  ssize_t start_at);

The callback receives a MAP_each_s pointer with:

typedef struct {
  MAP_PTR const parent;   /* the map being iterated */
  uint64_t      index;    /* current element index  */
  int (*task)(MAP_each_s *); /* the callback (may be swapped mid-loop) */
  void         *udata;    /* opaque user data */
  MAP_VALUE     value;    /* current value (absent for Sets) */
  MAP_KEY       key;      /* current key  */
} MAP_each_s;

#Practical Examples

#String-key dictionary (default keys, bstr values)

#define FIO_MAP_NAME       dict
#define FIO_MAP_VALUE_BSTR        /* string values via fio_bstr */
#include "fio-stl.h"

/* Wrap set/get to salt the hash with the map pointer for security. */
static inline fio_str_info_s dict_put(dict_s *m, fio_str_info_s k, fio_str_info_s v) {
  return dict_set(m, fio_risky_hash(k.buf, k.len, (uint64_t)(uintptr_t)m), k, v, NULL);
}
static inline fio_str_info_s dict_fetch(dict_s *m, fio_str_info_s k) {
  return dict_get(m, fio_risky_hash(k.buf, k.len, (uint64_t)(uintptr_t)m), k);
}

void example(void) {
  dict_s d = FIO_MAP_INIT;
  dict_put(&d, FIO_STR_INFO1("hello"), FIO_STR_INFO1("world"));
  fio_str_info_s v = dict_fetch(&d, FIO_STR_INFO1("hello"));
  printf("%.*s\n", (int)v.len, v.buf);  /* "world" */
  dict_destroy(&d);
}

#Automatic hashing (FIO_MAP_HASH_FN)

#define FIO_MAP_NAME     imap
#define FIO_MAP_KEY      int
#define FIO_MAP_VALUE    float
#define FIO_MAP_HASH_FN(k) fio_risky_num((uint64_t)(k), 0)
#include "fio-stl.h"

void example(void) {
  imap_s m = FIO_MAP_INIT;
  imap_set(&m, 42, 3.14f, NULL);
  printf("%f\n", imap_get(&m, 42));  /* 3.14 */
  imap_destroy(&m);
}

#LRU cache (manual eviction)

#define FIO_MAP_NAME       cache
#define FIO_MAP_KEY_KSTR           /* efficient internal string storage */
#define FIO_MAP_VALUE      void *
#define FIO_MAP_LRU                       /* enables LRU ordering; value is ignored */
#define FIO_MAP_HASH_FN(k) fio_risky_hash((k).buf, (k).len, 0)
#include "fio-stl.h"

FIO_MAP_LRU only controls ordering. Enforce the size limit yourself after inserting:

static inline void cache_put(cache_s *c, fio_str_info_s k, void *v) {
  cache_set(c, k, v, NULL);
  if (cache_count(c) > (1ULL << 12))
    cache_evict(c, 1);
}

#Notes

210 map2.h is a legacy implementation. It is not documented here and should not be used in new code.
Pointer tagging (FIO_PTR_TAG) and reference counting (FIO_REF_NAME) are supported, same as all 200-range modules.
The map internally stores a compact 8-bit hash fingerprint alongside each node to speed up probing. Full hash is cached per-node unless FIO_MAP_RECALC_HASH 1 is set.
Against hash-flooding: after FIO_MAP_ATTACK_LIMIT full collisions the map falls back to overwriting stale entries. Always salt hashes with a per-map value (e.g., the map pointer) when keys come from untrusted input.

See also: [← 200 types-overview.md](./200 types-overview.md) · [201 string.md](./201 string.md) · [202 array.md](./202 array.md)