Skip to content

Instantly share code, notes, and snippets.

@jaburns

jaburns/containers.h

Created September 25, 2024 16:13
Show Gist options
  • Save jaburns/1fe6cedbaedf11300e1bd3e0e2652d1d to your computer and use it in GitHub Desktop.
Save jaburns/1fe6cedbaedf11300e1bd3e0e2652d1d to your computer and use it in GitHub Desktop.
Download ZIP
Type-safe monomorphized containers in C preprocessor (dynamic array, hashmap, generational index array)
Raw
containers.h
#pragma once
// ---------- Dynarray ------------------------------------------------------------------------------------------------
#define x_DEF_DYNARRAY_SHARED(Name, V, Capacity) \
internal V Name##_pop(Name* arr) { \
if (arr->count_ == 0) PANIC("Can't pop empty dynarray"); \
return arr->data[--arr->count_]; \
} \
\
internal void Name##_clear(Name* arr) { \
arr->count_ = 0; \
}
#define DEF_DYNARRAY(Name, V) \
typedef struct Name { \
size_t capacity_; \
size_t count_; \
V* data; \
} Name; \
\
x_DEF_DYNARRAY_SHARED(Name, V, arr->capacity_); \
\
internal void Name##_free(Name* arr) { \
free(arr->data); \
*arr = (Name){0}; \
} \
\
internal size_t Name##_push(Name* arr, V value) { \
if (arr->count_ == arr->capacity_) { \
if (arr->capacity_ == 0) { \
arr->capacity_ = 4; \
arr->data = calloc(arr->capacity_, sizeof(V)); \
} else { \
arr->capacity_ <<= 1; \
arr->data = realloc(arr->data, arr->capacity_ * sizeof(V)); \
} \
} \
size_t ret = arr->count_; \
arr->data[arr->count_++] = value; \
return ret; \
} \
\
internal V* Name##_push_zero(Name* arr) { \
if (arr->count_ == arr->capacity_) { \
if (arr->capacity_ == 0) { \
arr->capacity_ = 4; \
arr->data = calloc(arr->capacity_, sizeof(V)); \
} else { \
arr->capacity_ <<= 1; \
arr->data = realloc(arr->data, arr->capacity_ * sizeof(V)); \
} \
} \
ZERO_STRUCT(&arr->data[arr->count_]); \
return &arr->data[arr->count_++]; \
}
#define DEF_FIXED_DYNARRAY(Name, V, Capacity) \
typedef struct Name { \
size_t count_; \
V data[Capacity]; \
} Name; \
\
x_DEF_DYNARRAY_SHARED(Name, V, Capacity); \
\
internal size_t Name##_push(Name* arr, V value) { \
if (arr->count_ < Capacity) { \
size_t ret = arr->count_; \
arr->data[arr->count_++] = value; \
return ret; \
} else { \
PANIC("Can't push onto a full fixed-size dynarray"); \
} \
} \
\
internal V* Name##_push_zero(Name* arr) { \
if (arr->count_ < Capacity) { \
ZERO_STRUCT(&arr->data[arr->count_]); \
return &arr->data[arr->count_++]; \
} else { \
PANIC("Can't push onto a full fixed-size dynarray"); \
} \
}
// ---------- Hashmap -------------------------------------------------------------------------------------------------
#define HASHMAP_LOAD_FACTOR_PERCENT 70
#define x_DEF_HASHMAP_TYPES(Name, K, V) \
typedef struct Name Name; \
\
typedef struct { \
u32 hash_; /* 0: empty, 1: tombstone */ \
K key_; \
V value; \
} x_##Name##_Entry; \
\
typedef struct { \
bool done; \
Name* target; \
x_##Name##_Entry* item; \
} Name##_Iter;
#define x_DEF_HASHMAP_FUNCS(Name, K, V, Eq, Capacity) \
internal void Name##_iter_next(Name##_Iter* it) { \
if (it->item == NULL) { \
it->item = it->target->entries_; \
} else { \
it->item++; \
} \
x_##Name##_Entry* end = &it->target->entries_[Capacity]; \
for (;;) { \
if (it->item >= end) { \
it->done = true; \
return; \
} \
if (it->item->hash_ > 1) { \
return; \
} \
it->item++; \
} \
} \
\
internal Name##_Iter Name##_iter(Name* map) { \
Name##_Iter it = (Name##_Iter){.done = false, .target = map, .item = NULL}; \
Name##_iter_next(&it); \
return it; \
} \
\
internal int x_##Name##_get_idx(Name* map, K* key) { \
u32 hash = x_hashmap_hash(key, sizeof(K)); \
int start_idx = hash & (Capacity - 1); \
int i; \
for (i = start_idx; i < Capacity; ++i) { \
if (map->entries_[i].hash_ == 0) return -1; \
if (map->entries_[i].hash_ > 1 && Eq(key, &map->entries_[i].key_)) return i; \
} \
for (i = 0; i < start_idx; ++i) { \
if (map->entries_[i].hash_ == 0) return -1; \
if (map->entries_[i].hash_ > 1 && Eq(key, &map->entries_[i].key_)) return i; \
} \
return -1; \
} \
\
internal void x_##Name##_insert_with_hash(Name* map, u32 hash, K key, V value) { \
int start_idx = hash & (Capacity - 1); \
int i; \
for (i = start_idx; i < Capacity; ++i) { \
if (map->entries_[i].hash_ < 2) goto found; \
} \
for (i = 0; i < start_idx; ++i) { \
if (map->entries_[i].hash_ < 2) goto found; \
} \
PANIC("Failed to find an empty hashmap slot (should never happen!)"); \
found: \
map->count_++; \
map->entries_[i] = (x_##Name##_Entry){ \
.hash_ = hash, \
.key_ = key, \
.value = value}; \
} \
\
internal V* Name##_get(Name* map, K* key) { \
int i = x_##Name##_get_idx(map, key); \
return i >= 0 ? &map->entries_[i].value : NULL; \
} \
\
internal bool Name##_remove(Name* map, K* key) { \
int i = x_##Name##_get_idx(map, key); \
if (i >= 0) { \
map->count_--; \
map->entries_[i].hash_ = 1; /*tombstone*/ \
return true; \
} \
return false; \
} \
\
internal void Name##_clear(Name* map) { \
memset(map->entries_, 0, Capacity * sizeof(x_##Name##_Entry)); \
map->count_ = 0; \
}
#define DEF_HASHMAP(Name, K, V, Eq) \
x_DEF_HASHMAP_TYPES(Name, K, V); \
\
struct Name { \
size_t capacity_; \
size_t count_; \
x_##Name##_Entry* entries_; \
}; \
\
x_DEF_HASHMAP_FUNCS(Name, K, V, Eq, map->capacity_); \
\
internal void Name##_free(Name* map) { \
free(map->entries_); \
*map = (Name){0}; \
} \
\
internal void Name##_insert(Name* map, K key, V value) { \
if (map->count_ >= map->capacity_ * HASHMAP_LOAD_FACTOR_PERCENT / 100) { \
if (map->capacity_ == 0) { \
*map = (Name){ \
.capacity_ = 16, \
.count_ = 0, \
.entries_ = calloc(16, sizeof(x_##Name##_Entry)), \
}; \
} else { \
size_t new_capacity = map->capacity_ << 1; \
Name new_map = (Name){ \
.capacity_ = new_capacity, \
.count_ = 0, \
.entries_ = calloc(new_capacity, sizeof(x_##Name##_Entry))}; \
\
for (int i = 0; i < map->capacity_; ++i) { \
if (map->entries_[i].hash_ > 1) { \
x_##Name##_insert_with_hash( \
&new_map, map->entries_[i].hash_, map->entries_[i].key_, map->entries_[i].value); \
} \
} \
\
free(map->entries_); \
*map = new_map; \
} \
} \
\
u32 hash = x_hashmap_hash(&key, sizeof(K)); \
x_##Name##_insert_with_hash(map, hash, key, value); \
}
#define DEF_FIXED_HASHMAP(Name, K, V, LogCapacity) \
x_DEF_HASHMAP_TYPES(Name, K, V); \
\
struct Name { \
size_t count_; \
x_##Name##_Entry entries_[1 << LogCapacity]; \
}; \
\
global const size_t Name##_CAPACITY = 1 << LogCapacity; \
\
x_DEF_HASHMAP_FUNCS(Name, K, V, Eq, Name##_CAPACITY); \
\
internal void Name##_insert(Name* map, K key, V value) { \
if (map->count_ >= Name##_CAPACITY * HASHMAP_LOAD_FACTOR_PERCENT / 100) { \
PANIC("Fixed-size hashmap is full and cannot be resized"); \
} \
u32 hash = x_hashmap_hash(&key, sizeof(K)); \
x_##Name##_insert_with_hash(map, hash, key, value); \
}
internal u32 hash_murmur3_32(void* data, size_t len) {
u8* bytes = (u8*)data;
int nblocks = len / 4;
u32 h1 = 0x87c263d1; // seed
u32* blocks = (u32*)(bytes + nblocks * 4);
for (int i = -nblocks; i; i++) {
u32 k1 = blocks[i];
k1 *= 0xcc9e2d51;
k1 = (k1 << 15) | (k1 >> 17);
k1 *= 0x1b873593;
h1 ^= k1;
h1 = (h1 << 13) | (h1 >> 19);
h1 = h1 * 5 + 0xe6546b64;
}
u8* tail = bytes + nblocks * 4;
u32 k1 = 0;
switch (len & 3) {
case 3:
k1 ^= tail[2] << 16;
case 2:
k1 ^= tail[1] << 8;
case 1:
k1 ^= tail[0];
k1 *= 0xcc9e2d51;
k1 = (k1 << 15) | (k1 >> 17);
k1 *= 0x1b873593;
h1 ^= k1;
};
h1 ^= len;
h1 ^= h1 >> 16;
h1 *= 0x85ebca6b;
h1 ^= h1 >> 13;
h1 *= 0xc2b2ae35;
h1 ^= h1 >> 16;
return h1;
}
internal u32 x_hashmap_hash(void* data, size_t len) {
u32 result = hash_murmur3_32(data, len);
if (result < 2) result += 2;
return result;
}
// ---------- Slotmap / generational index array ----------------------------------------------------------------------
#define x_DEF_SLOTMAP_TYPES_0(Name, IdxName, V) \
typedef struct { \
i32 gen_; \
bool populated_; \
V item; \
} x_##Name##_Item;
#define x_DEF_SLOTMAP_TYPES_1(Name, IdxName, V) \
typedef struct Name { \
x_##Name##_FreeSlotList free_slot_list_; \
x_##Name##_ItemList item_list_; \
} Name; \
\
typedef struct Name##_Iter { \
bool done; \
Name* target; \
V* item; \
IdxName idx; \
} Name##_Iter;
#define x_DEF_SLOTMAP_FUNCS(Name, IdxName, V) \
internal void Name##_iter_next(Name##_Iter* it) { \
if (it->item != NULL) { \
it->idx.slot_++; \
} \
for (;;) { \
if (it->idx.slot_ >= it->target->item_list_.count_) { \
it->done = true; \
return; \
} \
if (it->target->item_list_.data[it->idx.slot_].populated_) { \
it->idx.gen_ = it->target->item_list_.data[it->idx.slot_].gen_; \
it->item = &it->target->item_list_.data[it->idx.slot_].item; \
return; \
} \
it->idx.slot_++; \
} \
} \
\
internal Name##_Iter Name##_iter(Name* map) { \
Name##_Iter it = (Name##_Iter){.done = false, .target = map, .item = NULL, .idx = {0}}; \
Name##_iter_next(&it); \
return it; \
} \
\
internal IdxName Name##_insert(Name* map) { \
if (map->free_slot_list_.count_) { \
u32 slot = x_##Name##_FreeSlotList_pop(&map->free_slot_list_); \
x_##Name##_Item* item = &map->item_list_.data[slot]; \
item->populated_ = true; \
item->gen_++; \
ZERO_STRUCT(&item->item); \
return (IdxName){item->gen_, slot}; \
} \
x_##Name##_Item new_item = (x_##Name##_Item){ \
.populated_ = true, \
.gen_ = 1, \
.item = (V){0}, \
}; \
x_##Name##_ItemList_push(&map->item_list_, new_item); \
return (IdxName){1, map->item_list_.count_ - 1}; \
} \
\
internal V* Name##_get(Name* map, IdxName idx) { \
if (idx.slot_ >= map->item_list_.count_) return NULL; \
x_##Name##_Item* item = &map->item_list_.data[idx.slot_]; \
if (!item->populated_ || item->gen_ != idx.gen_) return NULL; \
return &item->item; \
} \
\
internal bool Name##_remove(Name* map, IdxName idx) { \
if (idx.slot_ >= map->item_list_.count_) return false; \
x_##Name##_Item* item = &map->item_list_.data[idx.slot_]; \
if (!item->populated_ || item->gen_ != idx.gen_) return false; \
item->populated_ = false; \
x_##Name##_FreeSlotList_push(&map->free_slot_list_, idx.slot_); \
return true; \
} \
\
internal void Name##_clear(Name* map) { \
x_##Name##_FreeSlotList_clear(&map->free_slot_list_); \
x_##Name##_ItemList_clear(&map->item_list_); \
}
#define DEF_SLOTMAP_IDX(IdxName) \
typedef struct IdxName { \
u32 gen_; \
u32 slot_; \
} IdxName;
#define DEF_SLOTMAP(Name, IdxName, V) \
x_DEF_SLOTMAP_TYPES_0(Name, IdxName, V); \
DEF_DYNARRAY(x_##Name##_FreeSlotList, u32); \
DEF_DYNARRAY(x_##Name##_ItemList, x_##Name##_Item); \
x_DEF_SLOTMAP_TYPES_1(Name, IdxName, V); \
x_DEF_SLOTMAP_FUNCS(Name, IdxName, V); \
\
internal void Name##_free(Name* map) { \
x_##Name##_FreeSlotList_free(&map->free_slot_list_); \
x_##Name##_ItemList_free(&map->item_list_); \
*map = (Name){0}; \
}
#define DEF_FIXED_SLOTMAP(Name, IdxName, V, Capacity) \
x_DEF_SLOTMAP_TYPES_0(Name, IdxName, V); \
DEF_FIXED_DYNARRAY(x_##Name##_FreeSlotList, u32, Capacity); \
DEF_FIXED_DYNARRAY(x_##Name##_ItemList, x_##Name##_Item, Capacity); \
x_DEF_SLOTMAP_TYPES_1(Name, IdxName, V); \
x_DEF_SLOTMAP_FUNCS(Name, IdxName, V);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment