String Hash Map

Arena-backed hash map from String8 keys to void* values. More...

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 from String8 keys to void* values.

Typedef Documentation

BaseMap

typedef struct BaseMap BaseMap

An arena-backed hash map with a fixed bucket array.

Initialize with base_map_create(). Zero-initialization is not sufficient — the bucket array must be allocated before use.

Definition at line 100 of file base_map.h.

BaseMapIter

typedef struct BaseMapIter BaseMapIter

Iterator for walking all live entries in a map.

Initialize with base_map_iter_begin(), advance with base_map_iter_next().

BaseMapIter it = base_map_iter_begin(&map);
for (BaseMapNode *n = base_map_iter_next(&it); n; n = base_map_iter_next(&it)) {
    printf("%.*s\n", STR8_FMT(n->key));
}

BaseMapNode

typedef struct BaseMapNode BaseMapNode

A single key-value node in a bucket chain.

Nodes are allocated from the arena passed to base_map_insert(). They are never individually freed - unlinking via base_map_unlink() is a logical delete only.

Definition at line 87 of file base_map.h.

Enumeration Type Documentation

BaseMapInsertResult

enum BaseMapInsertResult

Result returned by base_map_insert() indicating whether the key was new or already present.

Enumerator
BASE_MAP_INSERTED	The key did not exist; a new node was allocated.
BASE_MAP_UPDATED	The key already existed; its value was replaced.

Definition at line 75 of file base_map.h.

Function Documentation

base_hash_str8()

u64 base_hash_str8

(

String8

str

)

Hashes a String8 using the FNV-1a (64-bit) algorithm.

FNV-1a is a fast, non-cryptographic hash with good distribution for short strings. It is the right choice for hash table keying. Do NOT use this for any security or cryptographic purpose - it has no collision resistance guarantees and is trivially reversible.

Parameters

str	The string to hash.

Returns

A 64-bit hash value.

base_map_create()

BaseMap base_map_create	(	MemAllocator *	alloc,
		usize	bucket_count )

Creates and returns an initialized BaseMap.

Allocates the bucket array from arena. The bucket array is zeroed so all chains start empty.

Parameters

alloc	Allocator to allocate the bucket array from.
bucket_count	Number of hash buckets. MUST be a power of 2 (enforced by ASSERT). Recommended values: 256, 1024, 4096.

Returns

An initialized BaseMap ready for use.

base_map_insert()

BaseMapInsertResult base_map_insert	(	MemAllocator *	alloc,
		BaseMap *	map,
		String8	key,
		void *	val )

Inserts or updates a key-value pair.

If the key already exists its value is updated in-place and BASE_MAP_UPDATED is returned. If the key is new, a fresh node is allocated from arena and BASE_MAP_INSERTED is returned.

Parameters

alloc	Allocator to allocate the new node from (only used on insert).
map	The map to insert into.
key	The string key to hash and store.
val	The value to store. May be any pointer or an integer cast to void*.

Returns

BASE_MAP_INSERTED if a new key was added, BASE_MAP_UPDATED if existing.

base_map_intern()

String8 base_map_intern	(	MemAllocator *	alloc,
		BaseMap *	map,
		String8	str )

Interns a string, returning a stable canonical copy.

If str already exists in the map (byte-exact match), the existing canonical String8 is returned - no allocation occurs. If it is new, the string bytes are copied into arena, a node is allocated, and the new canonical String8 is returned.

Because the returned pointer is arena-backed, it is stable for the lifetime of the arena. Two interned strings with identical content are guaranteed to have the same .str pointer, making equality checks O(1) pointer comparisons.

Parameters

alloc	Arena to allocate the string copy and node from (only on first intern).
map	The map acting as the intern pool.
str	The transient string to intern (does not need to outlive this call).

Returns

The canonical, allocator-backed String8 for this string value.

base_map_iter_begin()

BaseMapIter base_map_iter_begin

(

BaseMap *

map

)

Initializes an iterator positioned before the first entry.

Parameters

map	The map to iterate over.

Returns

An iterator ready to be advanced with base_map_iter_next().

base_map_iter_next()

BaseMapNode * base_map_iter_next

(

BaseMapIter *

it

)

Advances the iterator and returns the next live node.

Returns NULL when iteration is complete. Unlinked nodes are skipped automatically. Do not insert or unlink entries while iterating.

Parameters

it	Pointer to the iterator to advance.

Returns

The next BaseMapNode, or NULL if there are no more entries.

base_map_lookup()

void * base_map_lookup	(	BaseMap *	map,
		String8	key )

Looks up a value by key.

Parameters

map	The map to search.
key	The string key to look up.

Returns

The stored value pointer, or NULL if the key is not present.

base_map_unlink()

b32 base_map_unlink	(	BaseMap *	map,
		String8	key )

Logically removes a key by unlinking its node from the bucket chain.

Note

This is a logical delete only. Because the map is arena-backed, the node memory remains allocated in the arena until the arena is cleared. Re-inserting the same key after unlinking allocates a new node.

Parameters

map	The map to remove from.
key	The string key to remove.

Returns

1 if the key was found and unlinked, 0 if not found.