diff options
| -rw-r--r-- | cheesemap.c | 89 | ||||
| -rw-r--r-- | cheesemap.h | 7 | ||||
| -rw-r--r-- | cm-demo.c | 84 |
3 files changed, 160 insertions, 20 deletions
diff --git a/cheesemap.c b/cheesemap.c index 58d1b53..69b8212 100644 --- a/cheesemap.c +++ b/cheesemap.c @@ -20,6 +20,10 @@ static inline uintptr_t cm_ctz(uintptr_t val) { #endif } +static inline uintptr_t cm_bitmask_to_index(bitmask_t mask) { + return cm_ctz(mask) / CHAR_BIT; +} + static inline uintptr_t cm_clz(uintptr_t val) { assert(val != 0); #if defined(__GNUC__) || defined(__clang__) @@ -96,7 +100,7 @@ static inline bitmask_t cm_group_empty_or_deleted(group_t group) { } static inline bitmask_t cm_group_full(group_t group) { - return ~cm_group_empty_or_deleted(group); + return cm_group_empty_or_deleted(group) ^ cm_group_repeat(CM_CTRL_DELETED); } /* static ctrl's */ @@ -127,7 +131,7 @@ static inline uint8_t* cm_raw_elem_at(const struct cheesemap_raw* map, assert(map != NULL); assert(map->bucket_mask + 1 > index); - return map->ctrl - entry_size * index; + return map->ctrl - entry_size * (index + 1); } static inline uint8_t* cm_raw_origin(const struct cheesemap_raw* map, @@ -159,7 +163,7 @@ static bool cm_raw_find_insert_index_in_group(const struct cheesemap_raw* map, bitmask_t mask = cm_group_empty_or_deleted(*group); if (mask == 0) return false; - uintptr_t bit = cm_ctz(mask); + uintptr_t bit = cm_bitmask_to_index(mask); *out_index = (seq->pos + bit) & map->bucket_mask; return true; } @@ -199,6 +203,35 @@ static void cm_raw_insert_at(struct cheesemap_raw* map, cm_hash_t hash, map->count += 1; } +static void cm_raw_rehash(struct cheesemap_raw* old_map, + struct cheesemap_raw* new_map, + const struct cheesemap_fns* fns, uintptr_t key_size, + uintptr_t value_size) { + assert(old_map != NULL); + assert(new_map != NULL && fns != NULL); + + uintptr_t entry_size = key_size + value_size; + + struct cheesemap_raw_iter iter; + cm_raw_iter_init(&iter, old_map, entry_size, 0); + + uintptr_t index; + while (cheesemap_raw_iter_next(&iter, entry_size, &index)) { + uint8_t* elem = cm_raw_elem_at(old_map, index, entry_size); + cm_hash_t hash = fns->hash(elem, fns->map_usr); + + uintptr_t new_index = cm_raw_find_insert_index(new_map, hash); + cm_raw_ctrl_set(new_map, new_index, cm_h2(hash)); + + uint8_t* new_elem = cm_raw_elem_at(new_map, new_index, entry_size); + memcpy(new_elem, elem, entry_size); + } + + new_map->count = old_map->count; + new_map->growth_left = + cm_buckets_to_capacity(new_map->bucket_mask) - new_map->count; +} + static bool cm_raw_resize(struct cheesemap_raw* map, const struct cheesemap_fns* fns, uintptr_t key_size, uintptr_t value_size, uintptr_t new_capacity) { @@ -207,9 +240,12 @@ static bool cm_raw_resize(struct cheesemap_raw* map, struct cheesemap_raw new_map; bool success = cm_raw_new_with(&new_map, fns, key_size, value_size, new_capacity); - if (!success) return success; + if (!success) return false; + cm_raw_rehash(map, &new_map, fns, key_size, value_size); + cm_raw_drop(map, key_size, value_size, fns); + *map = new_map; return true; } @@ -307,12 +343,16 @@ void cm_drop(struct cheesemap* map) { } /* iterator */ -static inline uint8_t* cm_raw_iter_next_entry(const struct cheesemap_raw_iter* iter, uint8_t* old_entry, uintptr_t entry_size) { +static inline uint8_t* cm_raw_iter_next_entry( + const struct cheesemap_raw_iter* iter, uint8_t* old_entry, + uintptr_t entry_size) { assert(iter != NULL); 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){ +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); memset(iter, 0, sizeof(*iter)); @@ -322,7 +362,7 @@ void cm_raw_iter_init(struct cheesemap_raw_iter* iter,const struct cheesemap_raw uint8_t* ctrl = &map->ctrl[start_index]; uint8_t* entry = cm_raw_elem_at(map, start_index, entry_size); - + group_t group = cm_group_load(ctrl); bitmask_t mask = cm_group_full(group); @@ -333,25 +373,40 @@ void cm_raw_iter_init(struct cheesemap_raw_iter* iter,const struct cheesemap_raw iter->end = map->ctrl + buckets; } -bool cheesemap_raw_iter_next(struct cheesemap_raw_iter* iter, uintptr_t entry_size, uintptr_t* out_index) { +static inline void cm_raw_iter_next_inner_slow( + struct cheesemap_raw_iter* iter) { + assert(iter != NULL); + + group_t group = cm_group_load(iter->n_ctrl); + iter->n_ctrl += CM_GROUP_SIZE; + iter->curr_mask = cm_group_full(group); + iter->curr_index += CM_GROUP_SIZE; +} + +static inline uintptr_t cm_raw_iter_next_inner_fast( + struct cheesemap_raw_iter* iter) { + assert(iter != NULL); + + uintptr_t bit = cm_bitmask_to_index(iter->curr_mask); + iter->curr_mask &= iter->curr_mask - 1; + + return iter->curr_index + bit; +} + +bool cheesemap_raw_iter_next(struct cheesemap_raw_iter* iter, + uintptr_t entry_size, uintptr_t* out_index) { assert(iter != NULL); assert(out_index != NULL); while (true) { if (iter->curr_mask != 0) { - uintptr_t bit = cm_ctz(iter->curr_mask); - *out_index = iter->curr_index + bit; - iter->curr_mask &= iter->curr_mask - 1; + *out_index = cm_raw_iter_next_inner_fast(iter); return true; } - if (iter->n_ctrl >= iter->end) - return false; + if (iter->n_ctrl >= iter->end) return false; - group_t group = cm_group_load(iter->n_ctrl); - iter->curr_mask = cm_group_full(group); - iter->curr_index += CM_GROUP_SIZE; - iter->n_ctrl += CM_GROUP_SIZE; + cm_raw_iter_next_inner_slow(iter); iter->n_entry = cm_raw_iter_next_entry(iter, iter->n_entry, entry_size); } } diff --git a/cheesemap.h b/cheesemap.h index f8991b1..17a1d42 100644 --- a/cheesemap.h +++ b/cheesemap.h @@ -143,7 +143,10 @@ struct cheesemap_raw_iter { uint8_t* end; }; -void cm_raw_iter_init(struct cheesemap_raw_iter* iter,const struct cheesemap_raw* map, uintptr_t entry_size, uintptr_t start_index); -bool cheesemap_raw_iter_next(struct cheesemap_raw_iter* iter, uintptr_t entry_size, uintptr_t* out_index); +void cm_raw_iter_init(struct cheesemap_raw_iter* iter, + const struct cheesemap_raw* map, uintptr_t entry_size, + uintptr_t start_index); +bool cheesemap_raw_iter_next(struct cheesemap_raw_iter* iter, + uintptr_t entry_size, uintptr_t* out_index); #endif @@ -1,3 +1,85 @@ #include "cheesemap.h" +#include <stdio.h> +#include <stdlib.h> +#include <stdint.h> -int main() {} +void* cm_malloc(uintptr_t size, uint8_t* user) { + (void)user; + return malloc(size); +} + +void cm_free(void* ptr, uint8_t* user) { + (void)user; + free(ptr); +} + +cm_hash_t cm_hash(const uint8_t* key, uint8_t* user) { + (void)user; + uint64_t k = *(const uint64_t*)key; + k ^= k >> 33; + k *= 0xff51afd7ed558ccdULL; + k ^= k >> 33; + k *= 0xc4ceb9fe1a85ec53ULL; + k ^= k >> 33; + return k; +} + +bool cm_compare(const uint8_t* key1, const uint8_t* key2, uint8_t* user) { + (void)user; + return *(const uint64_t*)key1 == *(const uint64_t*)key2; +} + +int main() { + struct cheesemap map; + cm_new(&map, sizeof(uint64_t), sizeof(uint64_t), + NULL, cm_malloc, cm_free, + NULL, cm_hash, cm_compare); + + const uint64_t num_entries = 1000000; + printf("Stress test: inserting %lu entries...\n", num_entries); + + for (uint64_t i = 0; i < num_entries; i++) { + uint64_t key = i; + uint64_t value = i * 2; + bool success = cm_raw_insert(&map.raw, &map.fns, + sizeof(uint64_t), (uint8_t*)&key, + sizeof(uint64_t), (uint8_t*)&value); + if (!success) { + printf("Insert failed at i=%lu\n", i); + cm_drop(&map); + return 1; + } + + if ((i + 1) % 100000 == 0) { + printf(" Progress: %lu entries, %lu buckets, %lu growth_left\n", + map.raw.count, map.raw.bucket_mask + 1, map.raw.growth_left); + } + } + + printf("\nSuccessfully inserted %lu entries!\n", num_entries); + printf("Map count: %lu\n", map.raw.count); + printf("Map buckets: %lu\n", map.raw.bucket_mask + 1); + printf("Growth left: %lu\n", map.raw.growth_left); + + // Calculate memory usage + uintptr_t entry_size = sizeof(uint64_t) + sizeof(uint64_t); + uintptr_t buckets = map.raw.bucket_mask + 1; + uintptr_t data_size = entry_size * buckets; + uintptr_t ctrl_size = buckets + 8; // buckets + mirror + uintptr_t total_size = data_size + ctrl_size; + + printf("\nMemory usage:\n"); + printf(" Entries: %lu x %lu bytes = %lu bytes\n", + buckets, entry_size, data_size); + printf(" Control: %lu bytes\n", ctrl_size); + printf(" Total: %lu bytes (%.2f MB)\n", + total_size, total_size / (1024.0 * 1024.0)); + printf(" Load factor: %.2f%% (%lu / %lu)\n", + (map.raw.count * 100.0) / buckets, map.raw.count, buckets); + printf(" Overhead: %.2f%% ((total - actual) / actual)\n", + ((total_size - (num_entries * entry_size)) * 100.0) / (num_entries * entry_size)); + + cm_drop(&map); + printf("\nDone!\n"); + return 0; +} |