diff options
| -rw-r--r-- | README.md | 6 | ||||
| -rw-r--r-- | cheesemap.c | 18 | ||||
| -rw-r--r-- | cheesemap.h | 17 |
3 files changed, 29 insertions, 12 deletions
@@ -45,10 +45,10 @@ bool compare_string(const cm_u8* key1, const cm_u8* key2, cm_u8* user) { return strcmp(*(const char**)key1, *(const char**)key2) == 0; } -// Default allocator (uses malloc) -void* default_alloc(cm_usize size, cm_u8* user) { +// Default allocator (uses aligned_alloc) +void* default_alloc(cm_usize size, cm_usize align, cm_u8* user) { (void)user; - return malloc(size); + return aligned_alloc(align, size); } // Default deallocator (uses free) diff --git a/cheesemap.c b/cheesemap.c index c6e7077..d17ecf4 100644 --- a/cheesemap.c +++ b/cheesemap.c @@ -193,10 +193,15 @@ static inline cm_usize cm_capacity_to_buckets(cm_usize capacity) { return cm_max(buckets, CM_GROUP_SIZE); } +static inline cm_usize cm_alloc_align(const struct cm_type* type) { + return cm_max(type->entry_align, _Alignof(max_align_t)); +} + static inline cm_usize cm_ctrl_offset(cm_usize buckets, const struct cm_type* type) { cm_usize offset = type->entry_size * buckets; - return cm_align_up(offset, CM_GROUP_SIZE); + cm_usize ctrl_align = cm_max(type->entry_align, CM_GROUP_SIZE); + return cm_align_up(offset, ctrl_align); } static inline cm_u8* cm_raw_elem_at(const struct cheesemap_raw* map, @@ -375,9 +380,12 @@ bool cm_raw_init_with(struct cheesemap_raw* map, cm_alloc_fn alloc, cm_u8* user, cm_usize buckets = cm_capacity_to_buckets(initial_capacity); cm_usize ctrl_offset = cm_ctrl_offset(buckets, type); + + cm_usize align = cm_alloc_align(type); cm_usize size = ctrl_offset + buckets + CM_GROUP_SIZE; + size = cm_align_up(size, align); - cm_u8* ptr = alloc(size, user); + cm_u8* ptr = alloc(size, align, user); if (ptr == NULL) return false; cm_u8* ctrl = ptr + ctrl_offset; @@ -502,11 +510,11 @@ void cm_init(struct cheesemap* map, cm_usize key_size, cm_usize key_align, cm_assert(alloc != NULL && dealloc != NULL); cm_usize value_offset = cm_align_up(key_size, value_align); - cm_usize max_align = cm_max(key_align, value_align); - cm_usize entry_size = cm_align_up(value_offset + value_size, max_align); + cm_usize entry_align = cm_max(key_align, value_align); + cm_usize entry_size = cm_align_up(value_offset + value_size, entry_align); struct cm_type type = - cm_type_new(key_size, value_size, value_offset, entry_size); + cm_type_new(key_size, value_size, value_offset, entry_size, entry_align); *map = cm_init_inner(type, user, hash, compare, alloc, dealloc, cm_raw_new()); } diff --git a/cheesemap.h b/cheesemap.h index 338fd8a..3e307a3 100644 --- a/cheesemap.h +++ b/cheesemap.h @@ -65,14 +65,15 @@ typedef bool (*cm_compare_fn)(const cm_u8* key1, const cm_u8* key2, cm_u8* user); /* allocator methods */ -typedef cm_u8* (*cm_alloc_fn)(cm_usize size, cm_u8* user); +typedef cm_u8* (*cm_alloc_fn)(cm_usize size, cm_usize align, cm_u8* user); typedef void (*cm_dealloc_fn)(cm_u8* ptr, cm_u8* user); //////////////////////////////// // raw cheesemap implementation // // layout: -// [entries...][control bits...][mirror first CM_GROUP_SIZE bits] +// [padding][entry n-1...entry 1][entry 0][control bits...][mirror first +// CM_GROUP_SIZE bits] enum { // cheesemap config @@ -101,14 +102,22 @@ enum { extern const cm_u8 CM_CTRL_STATIC_EMPTY[CM_GROUP_SIZE]; struct cm_type { + // key size in bytes cm_usize key_size; + // value size in bytes cm_usize value_size; + // aligned value offset within an entry cm_usize value_offset; + // total entry size including padding cm_usize entry_size; + // required alignment for each entry + cm_usize entry_align; }; -#define cm_type_new(key_size, value_size, value_offset, entry_size) \ - ((struct cm_type){key_size, value_size, value_offset, entry_size}) +#define cm_type_new(key_size, value_size, value_offset, entry_size, \ + entry_align) \ + ((struct cm_type){key_size, value_size, value_offset, entry_size, \ + entry_align}) struct cheesemap_raw { // number of buckets as mask |