diff options
| -rw-r--r-- | README.md | 16 | ||||
| -rw-r--r-- | cheesemap.c | 119 | ||||
| -rw-r--r-- | cheesemap.h | 11 | ||||
| -rw-r--r-- | cm-demo.c | 13 | ||||
| -rw-r--r-- | makefile | 6 |
5 files changed, 98 insertions, 67 deletions
@@ -8,11 +8,24 @@ is not yet production tested but fully working. * Example +#include <stdarg.h> #include <stdio.h> +#include <stdlib.h> #include <string.h> #include "cheesemap.h" +_Noreturn void panic_impl(const char* file, uint32_t line, const char* fmt, + ...) { + fprintf(stderr, "Panic at %s:%u: ", file, line); + va_list args; + va_start(args, fmt); + vfprintf(stderr, fmt, args); + va_end(args); + fprintf(stderr, "\n"); + abort(); +} + // Convenience macro for array length #define countof(arr) (sizeof(arr) / sizeof(*(arr))) @@ -79,6 +92,7 @@ int main(void) { cm_drop(&map); return 0; } -``` Copyright © 2026 Fabrice +``` + diff --git a/cheesemap.c b/cheesemap.c index 2068d35..8f96fc5 100644 --- a/cheesemap.c +++ b/cheesemap.c @@ -6,15 +6,10 @@ #include <stdlib.h> #include <string.h> -#include CM_OPT_ASSERT_PATH -#ifndef assert -#error "assert is not defined" -#endif - #define CM_ATTR(...) __attribute__((__VA_ARGS__)) CM_ATTR(hot) static inline uintptr_t cm_ctz(uintptr_t val) { - assert(val != 0); + cm_assert(val != 0); #if UINTPTR_MAX == UINT64_MAX return (uintptr_t)__builtin_ctzll(val); #elif UINTPTR_MAX == UINT32_MAX @@ -25,7 +20,7 @@ CM_ATTR(hot) static inline uintptr_t cm_ctz(uintptr_t val) { } CM_ATTR(hot) static inline uintptr_t cm_clz(uintptr_t val) { - assert(val != 0); + cm_assert(val != 0); #if UINTPTR_MAX == UINT64_MAX return (uintptr_t)__builtin_clzll(val); #elif UINTPTR_MAX == UINT32_MAX @@ -71,7 +66,7 @@ CM_ATTR(hot) static inline uintptr_t cm_bitmask_clz(bitmask_t mask) { #define cm_ispow2(x) (((x) & ((x) - 1)) == 0) static inline uintptr_t cm_align_up(uintptr_t value, uintptr_t alignment) { - assert(cm_ispow2(alignment)); + cm_assert(cm_ispow2(alignment)); return (value + alignment - 1) & ~(alignment - 1); } @@ -89,8 +84,8 @@ struct sequence { static inline void cm_sequence_next(struct sequence* sequence, uintptr_t bucket_mask) { - assert(sequence != NULL); - assert(sequence->stride <= bucket_mask); + cm_assert(sequence != NULL); + cm_assert(sequence->stride <= bucket_mask); sequence->stride += CM_GROUP_SIZE; sequence->pos += sequence->stride; @@ -101,7 +96,7 @@ static inline void cm_sequence_next(struct sequence* sequence, static inline bool cm_ctrl_is_special(uint8_t v) { return v & CM_CTRL_DELETED; } static inline bool cm_ctrl_is_empty(uint8_t v) { - assert(cm_ctrl_is_special(v) == true); + cm_assert(cm_ctrl_is_special(v) == true); return (v & CM_CTRL_END) != 0; } @@ -115,7 +110,7 @@ static inline bitmask_t cm_group_match_full(group_t group); /* sse2 implementation */ #ifdef CM_SSE2 static inline group_t cm_group_load(const uint8_t* ctrl) { - assert(ctrl != NULL); + cm_assert(ctrl != NULL); return _mm_loadu_si128((const group_t*)ctrl); } @@ -145,7 +140,7 @@ static inline group_t cm_group_repeat(uint8_t v) { } static inline group_t cm_group_load(const uint8_t* ctrl) { - assert(ctrl != NULL); + cm_assert(ctrl != NULL); group_t v; memcpy(&v, ctrl, sizeof(v)); @@ -207,15 +202,15 @@ static inline uintptr_t cm_ctrl_offset(uintptr_t buckets, static inline uint8_t* cm_raw_elem_at(const struct cheesemap_raw* map, uintptr_t index, uintptr_t entry_size) { - assert(map != NULL); - assert(map->bucket_mask + 1 > index); + cm_assert(map != NULL); + cm_assert(map->bucket_mask + 1 > index); return map->ctrl - entry_size * (index + 1); } static inline uint8_t* cm_raw_origin(const struct cheesemap_raw* map, uintptr_t entry_size) { - assert(map != NULL); + cm_assert(map != NULL); uintptr_t buckets = map->bucket_mask + 1; uintptr_t ctrl_offset = cm_ctrl_offset(buckets, entry_size); return map->ctrl - ctrl_offset; @@ -223,7 +218,7 @@ static inline uint8_t* cm_raw_origin(const struct cheesemap_raw* map, static inline void cm_raw_ctrl_set(struct cheesemap_raw* map, uintptr_t index, uint8_t ctrl) { - assert(map != NULL); + cm_assert(map != NULL); uintptr_t index2 = ((index - CM_GROUP_SIZE) & map->bucket_mask) + CM_GROUP_SIZE; @@ -235,9 +230,9 @@ static bool cm_raw_find_insert_index_in_group(const struct cheesemap_raw* map, const group_t* group, const struct sequence* seq, uintptr_t* out_index) { - assert(map != NULL); - assert(group != NULL && seq != NULL); - assert(out_index != NULL); + cm_assert(map != NULL); + cm_assert(group != NULL && seq != NULL); + cm_assert(out_index != NULL); bitmask_t mask = cm_group_match_empty_or_deleted(*group); if (mask == 0) return false; @@ -249,7 +244,7 @@ static bool cm_raw_find_insert_index_in_group(const struct cheesemap_raw* map, static uintptr_t cm_raw_find_insert_index(const struct cheesemap_raw* map, cm_hash_t hash) { - assert(map != NULL); + cm_assert(map != NULL); struct sequence seq = sequence_init(cm_h1(hash) & map->bucket_mask, 0); while (true) { @@ -268,9 +263,9 @@ static bool cm_raw_find_in_group(const struct cheesemap_raw* map, group_t group, const struct sequence* seq, uint8_t h2, uintptr_t entry_size, const uint8_t* key, uintptr_t* out_index) { - assert(map != NULL && compare != NULL); - assert(seq != NULL); - assert(key != NULL && out_index != NULL); + cm_assert(map != NULL && compare != NULL); + cm_assert(seq != NULL); + cm_assert(key != NULL && out_index != NULL); bitmask_t mask = cm_group_match_tag(group, h2); while (mask != 0) { @@ -292,8 +287,8 @@ static bool cm_raw_find_in_group(const struct cheesemap_raw* map, static bool cm_raw_find(const struct cheesemap_raw* map, cm_compare_fn compare, uint8_t* user, cm_hash_t hash, uintptr_t entry_size, const uint8_t* key, uintptr_t* out_index) { - assert(map != NULL && compare != NULL); - assert(key != NULL && out_index != NULL); + cm_assert(map != NULL && compare != NULL); + cm_assert(key != NULL && out_index != NULL); uint8_t h2 = cm_h2(hash); struct sequence seq = sequence_init(cm_h1(hash) & map->bucket_mask, 0); @@ -317,8 +312,8 @@ static void cm_raw_insert_at(struct cheesemap_raw* map, cm_hash_t hash, uintptr_t key_size, uintptr_t value_offset, uintptr_t value_size, const uint8_t* key, const uint8_t* value) { - assert(map != NULL); - assert(value != NULL); + cm_assert(map != NULL); + cm_assert(value != NULL); uint8_t old_ctrl = map->ctrl[index]; map->growth_left -= cm_ctrl_is_empty(old_ctrl); @@ -334,8 +329,8 @@ static void cm_raw_insert_at(struct cheesemap_raw* map, cm_hash_t hash, static void cm_raw_rehash(struct cheesemap_raw* old_map, struct cheesemap_raw* new_map, cm_hash_fn hash, uint8_t* user, uintptr_t entry_size) { - assert(old_map != NULL); - assert(new_map != NULL && hash != NULL); + cm_assert(old_map != NULL); + cm_assert(new_map != NULL && hash != NULL); struct cheesemap_raw_iter iter; cm_raw_iter_init(&iter, old_map, entry_size, 0); @@ -360,7 +355,7 @@ static void cm_raw_rehash(struct cheesemap_raw* old_map, static bool cm_raw_resize(struct cheesemap_raw* map, cm_hash_fn hash, uint8_t* user, uintptr_t entry_size, uintptr_t new_capacity) { - assert(map != NULL && hash != NULL); + cm_assert(map != NULL && hash != NULL); struct cheesemap_raw new_map; bool success = cm_raw_new_with(&new_map, entry_size, new_capacity); @@ -375,7 +370,7 @@ static bool cm_raw_resize(struct cheesemap_raw* map, cm_hash_fn hash, bool cm_raw_new_with(struct cheesemap_raw* map, uintptr_t entry_size, uintptr_t initial_capacity) { - assert(map != NULL); + cm_assert(map != NULL); memset(map, 0, sizeof(*map)); uintptr_t buckets = cm_capacity_to_buckets(initial_capacity); @@ -398,7 +393,7 @@ bool cm_raw_new_with(struct cheesemap_raw* map, uintptr_t entry_size, bool cm_raw_reserve(struct cheesemap_raw* map, cm_hash_fn hash, uint8_t* user, uintptr_t entry_size, uintptr_t additional) { - assert(map != NULL && hash != NULL); + cm_assert(map != NULL && hash != NULL); if (map->growth_left >= additional) return true; // TODO: inplace rehash @@ -412,8 +407,8 @@ bool cm_raw_lookup(const struct cheesemap_raw* map, cm_hash_fn hash, cm_compare_fn compare, uint8_t* user, uintptr_t entry_size, uintptr_t value_offset, const uint8_t* key, uint8_t** out_value) { - assert(map != NULL && hash != NULL); - assert(key != NULL && out_value != NULL); + cm_assert(map != NULL && hash != NULL); + cm_assert(key != NULL && out_value != NULL); cm_hash_t h = hash(key, user); uintptr_t index; @@ -430,8 +425,8 @@ bool cm_raw_remove(struct cheesemap_raw* map, cm_hash_fn hash, cm_compare_fn compare, uint8_t* user, uintptr_t entry_size, uintptr_t value_offset, uintptr_t value_size, const uint8_t* key, uint8_t* out_value) { - assert(map != NULL && hash != NULL); - assert(key != NULL); + cm_assert(map != NULL && hash != NULL); + cm_assert(key != NULL); cm_hash_t h = hash(key, user); uintptr_t index; @@ -468,8 +463,8 @@ bool cm_raw_insert(struct cheesemap_raw* map, cm_hash_fn hash, uint8_t* user, uintptr_t entry_size, uintptr_t key_size, uintptr_t value_offset, uintptr_t value_size, const uint8_t* key, const uint8_t* value) { - assert(map != NULL && hash != NULL); - assert(key != NULL && value != NULL); + cm_assert(map != NULL && hash != NULL); + cm_assert(key != NULL && value != NULL); cm_hash_t h = hash(key, user); uintptr_t index = cm_raw_find_insert_index(map, h); @@ -487,7 +482,7 @@ bool cm_raw_insert(struct cheesemap_raw* map, cm_hash_fn hash, uint8_t* user, } void cm_raw_drop(struct cheesemap_raw* map, uintptr_t entry_size) { - assert(map != NULL); + cm_assert(map != NULL); if (map->ctrl == CM_CTRL_STATIC_EMPTY || map->ctrl == NULL) return; @@ -500,8 +495,8 @@ void cm_raw_drop(struct cheesemap_raw* map, uintptr_t entry_size) { void cm_new(struct cheesemap* map, uintptr_t key_size, uintptr_t key_align, uintptr_t value_size, uintptr_t value_align, uint8_t* user, cm_hash_fn hash, cm_compare_fn compare) { - assert(map != NULL); - assert(hash != NULL && compare != NULL); + cm_assert(map != NULL); + cm_assert(hash != NULL && compare != NULL); uintptr_t value_offset = cm_align_up(key_size, value_align); uintptr_t max_align = cm_max(key_align, value_align); @@ -512,7 +507,7 @@ void cm_new(struct cheesemap* map, uintptr_t key_size, uintptr_t key_align, } void cm_drop(struct cheesemap* map) { - assert(map != NULL); + cm_assert(map != NULL); cm_raw_drop(&map->raw, map->entry_size); memset(map, 0, sizeof(*map)); @@ -520,8 +515,8 @@ void cm_drop(struct cheesemap* map) { bool cm_insert(struct cheesemap* map, const uint8_t* key, const uint8_t* value) { - assert(map != NULL); - assert(key != NULL && value != NULL); + cm_assert(map != NULL); + cm_assert(key != NULL && value != NULL); return cm_raw_insert(&map->raw, map->hash, map->user, map->entry_size, map->key_size, map->value_offset, map->value_size, key, @@ -530,16 +525,16 @@ bool cm_insert(struct cheesemap* map, const uint8_t* key, bool cm_lookup(const struct cheesemap* map, const uint8_t* key, uint8_t** out_value) { - assert(map != NULL); - assert(key != NULL && out_value != NULL); + cm_assert(map != NULL); + cm_assert(key != NULL && out_value != NULL); return cm_raw_lookup(&map->raw, map->hash, map->compare, map->user, map->entry_size, map->value_offset, key, out_value); } bool cm_remove(struct cheesemap* map, const uint8_t* key, uint8_t* out_value) { - assert(map != NULL); - assert(key != NULL); + cm_assert(map != NULL); + cm_assert(key != NULL); return cm_raw_remove(&map->raw, map->hash, map->compare, map->user, map->entry_size, map->value_offset, map->value_size, key, @@ -547,27 +542,27 @@ bool cm_remove(struct cheesemap* map, const uint8_t* key, uint8_t* out_value) { } bool cm_reserve(struct cheesemap* map, uintptr_t additional) { - assert(map != NULL); + cm_assert(map != NULL); return cm_raw_reserve(&map->raw, map->hash, map->user, map->entry_size, additional); } /* iterator */ -static inline uint8_t* cm_raw_iter_next_entry( - uint8_t* old_entry, uintptr_t entry_size) { +static inline uint8_t* cm_raw_iter_next_entry(uint8_t* old_entry, + uintptr_t entry_size) { return old_entry - entry_size * CM_GROUP_SIZE; } void cm_raw_iter_init(struct cheesemap_raw_iter* iter, const struct cheesemap_raw* map, uintptr_t entry_size, uintptr_t start_index) { - assert(map != NULL); - assert(start_index % CM_GROUP_SIZE == 0); + cm_assert(map != NULL); + cm_assert(start_index % CM_GROUP_SIZE == 0); memset(iter, 0, sizeof(*iter)); uintptr_t buckets = map->bucket_mask + 1; - assert(buckets > start_index); + cm_assert(buckets > start_index); uint8_t* ctrl = &map->ctrl[start_index]; uint8_t* entry = cm_raw_elem_at(map, start_index, entry_size); @@ -584,7 +579,7 @@ void cm_raw_iter_init(struct cheesemap_raw_iter* iter, static inline void cm_raw_iter_next_inner_slow( struct cheesemap_raw_iter* iter) { - assert(iter != NULL); + cm_assert(iter != NULL); group_t group = cm_group_load(iter->n_ctrl); iter->n_ctrl += CM_GROUP_SIZE; @@ -594,7 +589,7 @@ static inline void cm_raw_iter_next_inner_slow( static inline uintptr_t cm_raw_iter_next_inner_fast( struct cheesemap_raw_iter* iter) { - assert(iter != NULL); + cm_assert(iter != NULL); uintptr_t bucket_offset = cm_bitmask_lowest_set_bit(iter->curr_mask); iter->curr_mask &= iter->curr_mask - 1; @@ -604,8 +599,8 @@ static inline uintptr_t cm_raw_iter_next_inner_fast( bool cm_raw_iter_next(struct cheesemap_raw_iter* iter, uintptr_t entry_size, uintptr_t* out_index) { - assert(iter != NULL); - assert(out_index != NULL); + cm_assert(iter != NULL); + cm_assert(out_index != NULL); while (true) { if (iter->curr_mask != 0) { @@ -621,7 +616,7 @@ bool cm_raw_iter_next(struct cheesemap_raw_iter* iter, uintptr_t entry_size, } void cm_iter_init(struct cheesemap_iter* iter, const struct cheesemap* map) { - assert(iter != NULL && map != NULL); + cm_assert(iter != NULL && map != NULL); iter->entry_size = map->entry_size; iter->value_offset = map->value_offset; @@ -630,8 +625,8 @@ void cm_iter_init(struct cheesemap_iter* iter, const struct cheesemap* map) { bool cm_iter_next(struct cheesemap_iter* iter, const struct cheesemap* map, uint8_t** out_key, uint8_t** out_value) { - assert(iter != NULL && map != NULL); - assert(out_key != NULL && out_value != NULL); + cm_assert(iter != NULL && map != NULL); + cm_assert(out_key != NULL && out_value != NULL); uintptr_t index; if (!cm_raw_iter_next(&iter->raw, iter->entry_size, &index)) return false; diff --git a/cheesemap.h b/cheesemap.h index 5d87a6c..d17a8f5 100644 --- a/cheesemap.h +++ b/cheesemap.h @@ -13,7 +13,16 @@ extern "C" { #include <stdbool.h> #include <stdint.h> -#ifdef CM_SSE2 +_Noreturn void CM_OPT_PANIC_NAME(const char* file, uint32_t line, + const char* fmt, ...); + +#define cm_assert(cond) \ + do { \ + if (!(cond)) \ + CM_OPT_PANIC_NAME(__FILE__, __LINE__, "cm_assertion failed: %s", #cond); \ + } while (0) + +#ifdef CM_OPT_ENABLE_SSE2 #include <emmintrin.h> typedef __m128i group_t; @@ -1,8 +1,21 @@ +#include <stdarg.h> #include <stdio.h> +#include <stdlib.h> #include <string.h> #include "cheesemap.h" +_Noreturn void panic_impl(const char* file, uint32_t line, const char* fmt, + ...) { + fprintf(stderr, "Panic at %s:%u: ", file, line); + va_list args; + va_start(args, fmt); + vfprintf(stderr, fmt, args); + va_end(args); + fprintf(stderr, "\n"); + abort(); +} + // Convenience macro for array length #define countof(arr) (sizeof(arr) / sizeof(*(arr))) @@ -1,7 +1,7 @@ .SUFFIXES: CM_OPT_CC_FLAGS ?= -CM_OPT_ASSERT_PATH ?= <assert.h> +CM_OPT_PANIC_NAME ?= panic_impl CM_OPT_RELEASE ?= 1 CM_OPT_ENABLE_UBSAN ?= 0 CM_OPT_ENABLE_ASAN ?= 0 @@ -25,7 +25,7 @@ CM_CC_FLAGS := \ -MMD -MP -I$(CM_DIR) CM_CC_FLAGS += $(CM_OPT_CC_FLAGS) -CM_CC_FLAGS += -DCM_OPT_ASSERT_PATH='$(CM_OPT_ASSERT_PATH)' +CM_CC_FLAGS += -DCM_OPT_PANIC_NAME='$(CM_OPT_PANIC_NAME)' ifeq ($(CM_OPT_RELEASE),1) CM_CC_FLAGS += -O2 -fno-stack-protector @@ -42,7 +42,7 @@ ifeq ($(CM_OPT_ENABLE_ASAN),1) endif ifeq ($(CM_OPT_ENABLE_SSE2),1) - CM_CC_FLAGS += -DCM_SSE2=1 -msse2 + CM_CC_FLAGS += -DCM_OPT_ENABLE_SSE2=1 -msse2 endif ifeq ($(CM_OPT_STANDALONE),1) |