# 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

```c
#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

```c
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

```c
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

```c
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.

```c
/* 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.

```c
/* 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:

```c
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)

```c
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:**

```c
#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

```c
/* 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

```c
/* 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:

```c
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)

```c
#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)

```c
#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)

```c
#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:

```c
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)