base_map.h File Reference

Arena-backed hash map keyed by String8, with string interning support. More...

#include "base_macros.h"
#include "base_strings.h"
#include "base_types.h"
#include "memory/mem_allocator.h"

Include dependency graph for base_map.h:

Go to the source code of this file.

Classes
struct	BaseMapNode
struct	BaseMap
struct	BaseMapIter
	Iterator for walking all live entries in a map. More...

Typedefs
typedef enum BaseMapInsertResult	BaseMapInsertResult
	Result returned by base_map_insert() indicating whether the key was new or already present.
typedef struct BaseMapNode	BaseMapNode
	A single key-value node in a bucket chain.
typedef struct BaseMap	BaseMap
	An arena-backed hash map with a fixed bucket array.
typedef struct BaseMapIter	BaseMapIter
	Iterator for walking all live entries in a map.

Enumerations
enum	BaseMapInsertResult { BASE_MAP_INSERTED = 0 , BASE_MAP_UPDATED = 1 }
	Result returned by base_map_insert() indicating whether the key was new or already present. More...

Functions
BaseMap	base_map_create (MemAllocator *alloc, usize bucket_count)
	Creates and returns an initialized BaseMap.
BaseMapInsertResult	base_map_insert (MemAllocator *alloc, BaseMap *map, String8 key, void *val)
	Inserts or updates a key-value pair.
void *	base_map_lookup (BaseMap *map, String8 key)
	Looks up a value by key.
b32	base_map_unlink (BaseMap *map, String8 key)
	Logically removes a key by unlinking its node from the bucket chain.
BaseMapIter	base_map_iter_begin (BaseMap *map)
	Initializes an iterator positioned before the first entry.
BaseMapNode *	base_map_iter_next (BaseMapIter *it)
	Advances the iterator and returns the next live node.
String8	base_map_intern (MemAllocator *alloc, BaseMap *map, String8 str)
	Interns a string, returning a stable canonical copy.
u64	base_hash_str8 (String8 str)
	Hashes a String8 using the FNV-1a (64-bit) algorithm.

Detailed Description

Arena-backed hash map keyed by String8, with string interning support.

Implements a hash map using separate chaining (linked list per bucket). Designed specifically for arena allocators - nodes are bump-allocated and never individually freed. The bucket array is fixed at creation time.

Design

The map uses FNV-1a hashing to distribute keys across a fixed bucket array. Collisions are resolved by a singly-linked chain per bucket. Because the backing arena never shrinks, removal is a logical unlink only - the node memory remains in the arena until the arena is cleared.

This design is optimal for:

• Symbol tables and intern pools (build once, query many times).
• Per-frame lookup tables that are cleared along with their arena.
• Any map where the total number of entries is bounded and known ahead of time.

Bucket Count

The bucket_count MUST be a power of 2. This is enforced with ASSERT in base_map_create(). The map uses hash & (bucket_count - 1) for indexing, which is only a valid modulo when bucket_count is a power of 2. Typical values: 256, 1024, 4096. Choose based on expected entry count - aim for a load factor below 0.75 to keep chains short.

String Interning

base_map_intern() turns the map into a string pool. Interned strings are deduplicated: the first call copies the string into the arena and returns a canonical String8; subsequent calls with the same bytes return the same pointer without allocating. This is useful for identifier tables in parsers and compilers.

Usage

MemAllocator alloc = mem_allocator_create(ARENA, MB(4));
BaseMap map = base_map_create(&alloc, 1024);
 
// Insert a value (int cast to void*).
base_map_insert(&alloc, &map, STR8("width"), (void *)(uintptr_t)1920);
 
// Look it up.
void *val = base_map_lookup(&map, STR8("width"));
int width = (int)(uintptr_t)val; // 1920
 
// String interning.
String8 a = base_map_intern(&alloc, &map, STR8("hello"));
String8 b = base_map_intern(&alloc, &map, STR8("hello"));
// a.str == b.str  (same pointer - only one copy exists)

Copyright

2026 Alfred Jijo (MIT License)

Definition in file base_map.h.