diff options
| -rw-r--r-- | cheesemap.c | 135 | ||||
| -rw-r--r-- | cheesemap.h | 39 | ||||
| -rw-r--r-- | cm-demo.c | 72 | ||||
| -rw-r--r-- | makefile | 11 |
4 files changed, 166 insertions, 91 deletions
diff --git a/cheesemap.c b/cheesemap.c index 9b8584e..a65b64e 100644 --- a/cheesemap.c +++ b/cheesemap.c @@ -209,9 +209,8 @@ static uintptr_t cm_raw_find_insert_index(const struct cheesemap_raw* map, static bool cm_raw_find_in_group(const struct cheesemap_raw* map, cm_compare_fn compare, uint8_t* user, group_t group, const struct sequence* seq, - uint8_t h2, uintptr_t key_size, - const uint8_t* key, uintptr_t value_size, - uintptr_t* out_index) { + 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); @@ -221,7 +220,7 @@ static bool cm_raw_find_in_group(const struct cheesemap_raw* map, uintptr_t bucket_offset = cm_bitmask_lowest_set_bit(mask); uintptr_t index = (seq->pos + bucket_offset) & map->bucket_mask; - uint8_t* elem = cm_raw_elem_at(map, index, key_size + value_size); + uint8_t* elem = cm_raw_elem_at(map, index, entry_size); if (compare(key, elem, user)) { *out_index = index; return true; @@ -234,9 +233,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 key_size, - const uint8_t* key, uintptr_t value_size, - uintptr_t* out_index) { + 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); @@ -247,8 +245,8 @@ static bool cm_raw_find(const struct cheesemap_raw* map, cm_compare_fn compare, uint8_t* ctrl = &map->ctrl[seq.pos]; group_t group = cm_group_load(ctrl); - if (cm_raw_find_in_group(map, compare, user, group, &seq, h2, key_size, key, - value_size, out_index)) + if (cm_raw_find_in_group(map, compare, user, group, &seq, h2, entry_size, + key, out_index)) return true; if (cm_group_match_empty(group) != 0) return false; @@ -258,8 +256,9 @@ static bool cm_raw_find(const struct cheesemap_raw* map, cm_compare_fn compare, } static void cm_raw_insert_at(struct cheesemap_raw* map, cm_hash_t hash, - uintptr_t index, uintptr_t key_size, - const uint8_t* key, uintptr_t value_size, + uintptr_t index, 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); assert(value != NULL); @@ -268,23 +267,19 @@ static void cm_raw_insert_at(struct cheesemap_raw* map, cm_hash_t hash, map->growth_left -= cm_ctrl_is_empty(old_ctrl); cm_raw_ctrl_set(map, index, cm_h2(hash)); - uint8_t* elem = cm_raw_elem_at(map, index, key_size + value_size); + uint8_t* elem = cm_raw_elem_at(map, index, entry_size); memcpy(elem, key, key_size); - elem += key_size; - memcpy(elem, value, value_size); + memcpy(elem + value_offset, value, value_size); map->count += 1; } static void cm_raw_rehash(struct cheesemap_raw* old_map, struct cheesemap_raw* new_map, cm_hash_fn hash, - uint8_t* user, uintptr_t key_size, - uintptr_t value_size) { + uint8_t* user, uintptr_t entry_size) { assert(old_map != NULL); assert(new_map != NULL && hash != NULL); - uintptr_t entry_size = key_size + value_size; - struct cheesemap_raw_iter iter; cm_raw_iter_init(&iter, old_map, entry_size, 0); @@ -306,29 +301,27 @@ 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 key_size, uintptr_t value_size, + uint8_t* user, uintptr_t entry_size, uintptr_t new_capacity) { assert(map != NULL && hash != NULL); struct cheesemap_raw new_map; - bool success = - cm_raw_new_with(&new_map, key_size, value_size, new_capacity); + bool success = cm_raw_new_with(&new_map, entry_size, new_capacity); if (!success) return false; - cm_raw_rehash(map, &new_map, hash, user, key_size, value_size); + cm_raw_rehash(map, &new_map, hash, user, entry_size); - cm_raw_drop(map, key_size, value_size); + cm_raw_drop(map, entry_size); *map = new_map; return true; } -bool cm_raw_new_with(struct cheesemap_raw* map, uintptr_t key_size, - uintptr_t value_size, uintptr_t initial_capacity) { +bool cm_raw_new_with(struct cheesemap_raw* map, uintptr_t entry_size, + uintptr_t initial_capacity) { assert(map != NULL); memset(map, 0, sizeof(*map)); uintptr_t buckets = cm_capacity_to_buckets(initial_capacity); - uintptr_t entry_size = key_size + value_size; uintptr_t ctrl_offset = cm_ctrl_offset(buckets, entry_size); uintptr_t size = ctrl_offset + buckets + CM_GROUP_SIZE; @@ -347,8 +340,7 @@ bool cm_raw_new_with(struct cheesemap_raw* map, uintptr_t key_size, } bool cm_raw_reserve(struct cheesemap_raw* map, cm_hash_fn hash, uint8_t* user, - uintptr_t key_size, uintptr_t value_size, - uintptr_t additional) { + uintptr_t entry_size, uintptr_t additional) { assert(map != NULL && hash != NULL); if (map->growth_left >= additional) return true; @@ -356,41 +348,43 @@ bool cm_raw_reserve(struct cheesemap_raw* map, cm_hash_fn hash, uint8_t* user, uintptr_t needed = map->count + additional; uintptr_t capacity = cm_buckets_to_capacity(map->bucket_mask); uintptr_t new_capacity = cm_max(needed, capacity + 1); - return cm_raw_resize(map, hash, user, key_size, value_size, new_capacity); + return cm_raw_resize(map, hash, user, entry_size, new_capacity); } bool cm_raw_lookup(struct cheesemap_raw* map, cm_hash_fn hash, - cm_compare_fn compare, uint8_t* user, uintptr_t key_size, - const uint8_t* key, uintptr_t value_size, uint8_t** out_value) { + 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_hash_t h = hash(key, user); uintptr_t index; - if (!cm_raw_find(map, compare, user, h, key_size, key, value_size, &index)) + if (!cm_raw_find(map, compare, user, h, entry_size, key, &index)) return false; - uint8_t* elem = cm_raw_elem_at(map, index, key_size + value_size); - *out_value = elem + key_size; + uint8_t* elem = cm_raw_elem_at(map, index, entry_size); + *out_value = elem + value_offset; return true; } bool cm_raw_remove(struct cheesemap_raw* map, cm_hash_fn hash, - cm_compare_fn compare, uint8_t* user, uintptr_t key_size, - const uint8_t* key, uintptr_t value_size, uint8_t* out_value) { + 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_hash_t h = hash(key, user); uintptr_t index; - if (!cm_raw_find(map, compare, user, h, key_size, key, value_size, &index)) + if (!cm_raw_find(map, compare, user, h, entry_size, key, &index)) return false; if (out_value != NULL) { - uint8_t* elem = cm_raw_elem_at(map, index, key_size + value_size); - memcpy(out_value, elem + key_size, value_size); + uint8_t* elem = cm_raw_elem_at(map, index, entry_size); + memcpy(out_value, elem + value_offset, value_size); } uintptr_t index_before = (index - CM_GROUP_SIZE) & map->bucket_mask; @@ -414,8 +408,9 @@ bool cm_raw_remove(struct cheesemap_raw* map, cm_hash_fn hash, } bool cm_raw_insert(struct cheesemap_raw* map, cm_hash_fn hash, uint8_t* user, - uintptr_t key_size, const uint8_t* key, uintptr_t value_size, - const uint8_t* value) { + 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); @@ -424,40 +419,45 @@ bool cm_raw_insert(struct cheesemap_raw* map, cm_hash_fn hash, uint8_t* user, uint8_t old_ctrl = map->ctrl[index]; if (map->growth_left == 0 && cm_ctrl_is_empty(old_ctrl)) { - bool success = cm_raw_reserve(map, hash, user, key_size, value_size, 1); + bool success = cm_raw_reserve(map, hash, user, entry_size, 1); if (!success) return success; index = cm_raw_find_insert_index(map, h); } - cm_raw_insert_at(map, h, index, key_size, key, value_size, value); + cm_raw_insert_at(map, h, index, entry_size, key_size, value_offset, + value_size, key, value); return true; } -void cm_raw_drop(struct cheesemap_raw* map, uintptr_t key_size, - uintptr_t value_size) { +void cm_raw_drop(struct cheesemap_raw* map, uintptr_t entry_size) { assert(map != NULL); if (map->ctrl == CM_CTRL_STATIC_EMPTY || map->ctrl == NULL) return; - uint8_t* origin = cm_raw_origin(map, key_size + value_size); + uint8_t* origin = cm_raw_origin(map, entry_size); free(origin); *map = cm_raw_new(); } -void cm_new(struct cheesemap* map, uintptr_t key_size, uintptr_t value_size, - uint8_t* user, cm_hash_fn hash, cm_compare_fn compare) { +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); - *map = (struct cheesemap){key_size, value_size, user, hash, compare, - cm_raw_new()}; + uintptr_t value_offset = cm_align_up(key_size, value_align); + uintptr_t max_align = cm_max(key_align, value_align); + uintptr_t entry_size = cm_align_up(value_offset + value_size, max_align); + + *map = (struct cheesemap){key_size, value_size, value_offset, entry_size, + user, hash, compare, cm_raw_new()}; } void cm_drop(struct cheesemap* map) { assert(map != NULL); - cm_raw_drop(&map->raw, map->key_size, map->value_size); + cm_raw_drop(&map->raw, map->entry_size); memset(map, 0, sizeof(*map)); } @@ -466,8 +466,9 @@ bool cm_insert(struct cheesemap* map, const uint8_t* key, assert(map != NULL); assert(key != NULL && value != NULL); - return cm_raw_insert(&map->raw, map->hash, map->user, map->key_size, key, - map->value_size, value); + return cm_raw_insert(&map->raw, map->hash, map->user, map->entry_size, + map->key_size, map->value_offset, map->value_size, key, + value); } bool cm_lookup(struct cheesemap* map, const uint8_t* key, uint8_t** out_value) { @@ -475,7 +476,7 @@ bool cm_lookup(struct cheesemap* map, const uint8_t* key, uint8_t** out_value) { assert(key != NULL && out_value != NULL); return cm_raw_lookup(&map->raw, map->hash, map->compare, map->user, - map->key_size, key, map->value_size, out_value); + map->entry_size, map->value_offset, key, out_value); } bool cm_remove(struct cheesemap* map, const uint8_t* key, uint8_t* out_value) { @@ -483,14 +484,15 @@ bool cm_remove(struct cheesemap* map, const uint8_t* key, uint8_t* out_value) { assert(key != NULL); return cm_raw_remove(&map->raw, map->hash, map->compare, map->user, - map->key_size, key, map->value_size, out_value); + map->entry_size, map->value_offset, map->value_size, key, + out_value); } bool cm_reserve(struct cheesemap* map, uintptr_t additional) { assert(map != NULL); - return cm_raw_reserve(&map->raw, map->hash, map->user, map->key_size, - map->value_size, additional); + return cm_raw_reserve(&map->raw, map->hash, map->user, map->entry_size, + additional); } /* iterator */ @@ -544,8 +546,8 @@ static inline uintptr_t cm_raw_iter_next_inner_fast( return iter->curr_index + bucket_offset; } -bool cm_raw_iter_next(struct cheesemap_raw_iter* iter, - uintptr_t entry_size, uintptr_t* out_index) { +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); @@ -565,9 +567,9 @@ bool cm_raw_iter_next(struct cheesemap_raw_iter* iter, void cm_iter_init(struct cheesemap_iter* iter, const struct cheesemap* map) { assert(iter != NULL && map != NULL); - iter->key_size = map->key_size; - iter->value_size = map->value_size; - cm_raw_iter_init(&iter->raw, &map->raw, map->key_size + map->value_size, 0); + iter->entry_size = map->entry_size; + iter->value_offset = map->value_offset; + cm_raw_iter_init(&iter->raw, &map->raw, map->entry_size, 0); } bool cm_iter_next(struct cheesemap_iter* iter, const struct cheesemap* map, @@ -576,13 +578,10 @@ bool cm_iter_next(struct cheesemap_iter* iter, const struct cheesemap* map, assert(out_key != NULL && out_value != NULL); uintptr_t index; - if (!cm_raw_iter_next(&iter->raw, iter->key_size + iter->value_size, - &index)) - return false; + if (!cm_raw_iter_next(&iter->raw, iter->entry_size, &index)) return false; - uint8_t* elem = - cm_raw_elem_at(&map->raw, index, iter->key_size + iter->value_size); + uint8_t* elem = cm_raw_elem_at(&map->raw, index, iter->entry_size); *out_key = elem; - *out_value = elem + iter->key_size; + *out_value = elem + iter->value_offset; return true; } diff --git a/cheesemap.h b/cheesemap.h index be4d584..27093db 100644 --- a/cheesemap.h +++ b/cheesemap.h @@ -91,22 +91,23 @@ struct cheesemap_raw { #define cm_raw_new() \ ((struct cheesemap_raw){.ctrl = (uint8_t*)CM_CTRL_STATIC_EMPTY}) -bool cm_raw_new_with(struct cheesemap_raw* map, uintptr_t key_size, - uintptr_t value_size, uintptr_t initial_capacity); -bool cm_raw_insert(struct cheesemap_raw* map, cm_hash_fn hash, uint8_t* user, - uintptr_t key_size, const uint8_t* key, uintptr_t value_size, - const uint8_t* value); +bool cm_raw_new_with(struct cheesemap_raw* map, uintptr_t entry_size, + uintptr_t initial_capacity); +void cm_raw_drop(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 key_size, uintptr_t value_size, - uintptr_t additional); + uintptr_t entry_size, uintptr_t additional); bool cm_raw_lookup(struct cheesemap_raw* map, cm_hash_fn hash, - cm_compare_fn compare, uint8_t* user, uintptr_t key_size, - const uint8_t* key, uintptr_t value_size, uint8_t** out_value); + cm_compare_fn compare, uint8_t* user, uintptr_t entry_size, + uintptr_t value_offset, const uint8_t* key, + uint8_t** out_value); bool cm_raw_remove(struct cheesemap_raw* map, cm_hash_fn hash, - cm_compare_fn compare, uint8_t* user, uintptr_t key_size, - const uint8_t* key, uintptr_t value_size, uint8_t* out_value); -void cm_raw_drop(struct cheesemap_raw* map, uintptr_t key_size, - uintptr_t value_size); + 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); +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); //////////////////////////////// // cheesemap implementation @@ -114,14 +115,16 @@ void cm_raw_drop(struct cheesemap_raw* map, uintptr_t key_size, struct cheesemap { uintptr_t key_size, value_size; + uintptr_t value_offset, entry_size; uint8_t* user; cm_hash_fn hash; cm_compare_fn compare; struct cheesemap_raw raw; }; -void cm_new(struct cheesemap* map, uintptr_t key_size, uintptr_t value_size, - uint8_t* user, cm_hash_fn hash, cm_compare_fn compare); +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); void cm_drop(struct cheesemap* map); bool cm_insert(struct cheesemap* map, const uint8_t* key, const uint8_t* value); bool cm_lookup(struct cheesemap* map, const uint8_t* key, uint8_t** out_value); @@ -143,11 +146,11 @@ struct cheesemap_raw_iter { void cm_raw_iter_init(struct cheesemap_raw_iter* iter, const struct cheesemap_raw* map, uintptr_t entry_size, uintptr_t start_index); -bool cm_raw_iter_next(struct cheesemap_raw_iter* iter, - uintptr_t entry_size, uintptr_t* out_index); +bool cm_raw_iter_next(struct cheesemap_raw_iter* iter, uintptr_t entry_size, + uintptr_t* out_index); struct cheesemap_iter { - uintptr_t key_size, value_size; + uintptr_t entry_size, value_offset; struct cheesemap_raw_iter raw; }; @@ -4,7 +4,7 @@ #include "cheesemap.h" -cm_hash_t cm_hash(const uint8_t* key, uint8_t* user) { +cm_hash_t hash_u64(const uint8_t* key, uint8_t* user) { (void)user; uint64_t k = *(const uint64_t*)key; k ^= k >> 33; @@ -15,14 +15,78 @@ cm_hash_t cm_hash(const uint8_t* key, uint8_t* user) { return k; } -bool cm_compare(const uint8_t* key1, const uint8_t* key2, uint8_t* user) { +bool compare_u64(const uint8_t* key1, const uint8_t* key2, uint8_t* user) { (void)user; return *(const uint64_t*)key1 == *(const uint64_t*)key2; } +cm_hash_t hash_u32(const uint8_t* key, uint8_t* user) { + (void)user; + uint64_t k = *(const uint32_t*)key; + k ^= k >> 33; + k *= 0xff51afd7ed558ccdULL; + k ^= k >> 33; + k *= 0xc4ceb9fe1a85ec53ULL; + k ^= k >> 33; + return k; +} + +bool compare_u32(const uint8_t* key1, const uint8_t* key2, uint8_t* user) { + (void)user; + return *(const uint32_t*)key1 == *(const uint32_t*)key2; +} + int main() { + printf("=== Alignment test (uint32 key, uint64 value) ===\n"); + { + struct cheesemap amap; + cm_new(&amap, sizeof(uint32_t), _Alignof(uint32_t), sizeof(uint64_t), + _Alignof(uint64_t), NULL, hash_u32, compare_u32); + + printf(" key_size=%lu, value_size=%lu\n", amap.key_size, amap.value_size); + printf(" value_offset=%lu (expected 8, padding=4)\n", amap.value_offset); + printf(" entry_size=%lu (expected 16)\n", amap.entry_size); + + if (amap.value_offset != 8 || amap.entry_size != 16) { + printf(" ERROR: alignment calculation wrong!\n"); + return 1; + } + + for (uint32_t i = 0; i < 1000; i++) { + uint32_t key = i; + uint64_t value = (uint64_t)i * 0x100000001ULL; + cm_insert(&amap, (uint8_t*)&key, (uint8_t*)&value); + } + + uint64_t errors = 0; + for (uint32_t i = 0; i < 1000; i++) { + uint32_t key = i; + uint8_t* value_ptr; + if (cm_lookup(&amap, (uint8_t*)&key, &value_ptr)) { + uint64_t value = *(uint64_t*)value_ptr; + uint64_t expected = (uint64_t)i * 0x100000001ULL; + if (value != expected) { + printf(" ERROR: key=%u value=%lu expected=%lu\n", i, value, + expected); + errors++; + } + } else { + printf(" ERROR: key=%u not found\n", i); + errors++; + } + } + + if (errors == 0) { + printf(" OK: all 1000 entries verified with correct alignment\n"); + } + + cm_drop(&amap); + } + printf("\n"); + struct cheesemap map; - cm_new(&map, sizeof(uint64_t), sizeof(uint64_t), NULL, cm_hash, cm_compare); + cm_new(&map, sizeof(uint64_t), _Alignof(uint64_t), sizeof(uint64_t), + _Alignof(uint64_t), NULL, hash_u64, compare_u64); const uint64_t num_entries = 1000000; printf("Stress test: inserting %lu entries...\n", num_entries); @@ -147,7 +211,7 @@ int main() { } // Calculate memory usage - uintptr_t entry_size = sizeof(uint64_t) + sizeof(uint64_t); + uintptr_t entry_size = map.entry_size; uintptr_t buckets = map.raw.bucket_mask + 1; uintptr_t data_size = entry_size * buckets; uintptr_t ctrl_size = buckets + 8; // buckets + mirror @@ -1,8 +1,9 @@ -# Header in which assert(x) is defined CM_OPT_RELEASE ?= 0 CM_OPT_CC_FLAGS ?= CM_OPT_ASSERT_PATH ?= <assert.h> CM_OPT_ENABLE_DEMO ?= 1 +CM_OPT_ENABLE_UBSAN ?= 0 +CM_OPT_ENABLE_ASAN ?= 0 CC ?= gcc @@ -29,6 +30,14 @@ endif CM_CC_FLAGS += $(CM_OPT_CC_FLAGS) CM_CC_FLAGS += -DCM_OPT_ASSERT_PATH='$(CM_OPT_ASSERT_PATH)' +ifeq ($(CM_OPT_ENABLE_UBSAN),1) + CM_CC_FLAGS += -fsanitize=undefined +endif + +ifeq ($(CM_OPT_ENABLE_ASAN),1) + CM_CC_FLAGS += -fsanitize=address +endif + .PHONY: all all:: $(CM_OBJECT) |
