template.h

Go to the documentation of this file.

 
#include <derive-c/core/includes/def.h>
#if !defined(SKIP_INCLUDES)
    #include "includes.h"
#endif
 
#include <derive-c/core/alloc/def.h>
#include <derive-c/core/self/def.h>
 
#if !defined KEY
    #if !defined DC_PLACEHOLDERS
TEMPLATE_ERROR("No KEY")
    #endif
    #define KEY map_key_t
typedef size_t KEY;
#endif
 
#if !defined KEY_HASH
    #if !defined DC_PLACEHOLDERS
TEMPLATE_ERROR("No KEY_HASH")
    #endif
 
    #define KEY_HASH key_hash
static size_t KEY_HASH(KEY const* key) { return *key; }
#endif
 
#if !defined KEY_EQ
    #define KEY_EQ DC_MEM_EQ
#endif
 
#if !defined KEY_DELETE
    #define KEY_DELETE DC_NO_DELETE
#endif
 
#if !defined KEY_CLONE
    #define KEY_CLONE DC_COPY_CLONE
#endif
 
#if !defined KEY_DEBUG
    #define KEY_DEBUG DC_DEFAULT_DEBUG
#endif
 
#if !defined VALUE
    #if !defined DC_PLACEHOLDERS
TEMPLATE_ERROR("No VALUE")
    #endif
typedef struct {
    int x;
} value_t;
    #define VALUE value_t
#endif
 
#if !defined VALUE_DELETE
    #define VALUE_DELETE DC_NO_DELETE
#endif
 
#if !defined VALUE_CLONE
    #define VALUE_CLONE DC_COPY_CLONE
#endif
 
#if !defined VALUE_DEBUG
    #define VALUE_DEBUG DC_DEFAULT_DEBUG
#endif
 
typedef KEY NS(SELF, key_t);
typedef VALUE NS(SELF, value_t);
typedef ALLOC NS(SELF, alloc_t);
 
#define KEY_ENTRY NS(SELF, key_entry)
typedef struct {
    bool present;
    uint16_t distance_from_desired;
    KEY key;
} KEY_ENTRY;
 
typedef struct {
    size_t capacity; // INVARIANT: A power of 2
    size_t items;
    KEY_ENTRY* keys;
    VALUE* values;
    NS(ALLOC, ref) alloc_ref;
    dc_gdb_marker derive_c_hashmap;
    mutation_tracker iterator_invalidation_tracker;
} SELF;
 
#define INVARIANT_CHECK(self)                                                                      \
    DC_ASSUME(self);                                                                               \
    DC_ASSUME(DC_MATH_IS_POWER_OF_2((self)->capacity));                                            \
    DC_ASSUME((self)->keys);                                                                       \
    DC_ASSUME((self)->values);
 
DC_STATIC_CONSTANT size_t NS(SELF, max_capacity) = SIZE_MAX;
 
DC_PUBLIC static SELF NS(SELF, new_with_capacity_for)(size_t capacity, NS(ALLOC, ref) alloc_ref) {
    DC_ASSERT(capacity > 0, "Cannot create map with capacity for 0 items {capacity=%lu}", capacity);
    size_t const real_capacity = dc_apply_capacity_policy(capacity);
    DC_ASSUME(real_capacity > 0);
 
    // JUSTIFY: calloc of keys
    //  - A cheap way to get all precense flags as zeroed (os & allocater supported get zeroed page)
    //  - for the values, we do not need this (no precense checks are done on values)
    KEY_ENTRY* keys =
        (KEY_ENTRY*)NS(ALLOC, allocate_zeroed)(alloc_ref, sizeof(KEY_ENTRY) * real_capacity);
    VALUE* values = (VALUE*)NS(ALLOC, allocate_uninit)(alloc_ref, sizeof(VALUE) * real_capacity);
 
    // JUSTIFY: no access for values & but keys are fine
    // - Keys are calloced/zeroed as we use this for item lookup, therefore it is valid to read
    // them.
    // - Values are only accessed when the corresponding key is present, so we can mark them as
    // deleted.
    dc_memory_tracker_set(DC_MEMORY_TRACKER_LVL_CONTAINER, DC_MEMORY_TRACKER_CAP_NONE, values,
                          sizeof(VALUE) * real_capacity);
 
    return (SELF){
        .capacity = real_capacity,
        .items = 0,
        .keys = keys,
        .values = values,
        .alloc_ref = alloc_ref,
        .derive_c_hashmap = dc_gdb_marker_new(),
        .iterator_invalidation_tracker = mutation_tracker_new(),
    };
}
 
DC_PUBLIC static SELF NS(SELF, new)(NS(ALLOC, ref) alloc_ref) {
    return NS(SELF, new_with_capacity_for)(DC_INITIAL_CAPACITY, alloc_ref);
}
 
DC_PUBLIC static SELF NS(SELF, clone)(SELF const* self) {
    INVARIANT_CHECK(self);
 
    // JUSTIFY: Naive copy
    //           - We could resize (potentially a smaller map) and rehash
    //           - Not confident it would be any better than just a copy.
    // JUSTIFY: Individually copy keys
    //           - Many entries are zeroed, no need to copy uninit data
 
    KEY_ENTRY* keys =
        (KEY_ENTRY*)NS(ALLOC, allocate_zeroed)(self->alloc_ref, sizeof(KEY_ENTRY) * self->capacity);
    VALUE* values =
        (VALUE*)NS(ALLOC, allocate_uninit)(self->alloc_ref, sizeof(VALUE) * self->capacity);
 
    for (size_t i = 0; i < self->capacity; i++) {
        if (self->keys[i].present) {
            KEY_ENTRY const* old_entry = &self->keys[i];
            keys[i] = (KEY_ENTRY){
                .present = true,
                .distance_from_desired = old_entry->distance_from_desired,
                .key = KEY_CLONE(&old_entry->key),
            };
            values[i] = VALUE_CLONE(&self->values[i]);
        } else {
            dc_memory_tracker_set(DC_MEMORY_TRACKER_LVL_CONTAINER, DC_MEMORY_TRACKER_CAP_NONE,
                                  &values[i], sizeof(VALUE));
        }
    }
 
    return (SELF){
        .capacity = self->capacity,
        .items = self->items,
        .keys = keys,
        .values = values,
        .alloc_ref = self->alloc_ref,
        .derive_c_hashmap = dc_gdb_marker_new(),
        .iterator_invalidation_tracker = mutation_tracker_new(),
    };
}
 
static VALUE* PRIV(NS(SELF, try_insert_no_extend_capacity))(SELF* self, KEY key, VALUE value) {
    uint16_t distance_from_desired = 0;
    size_t const hash = KEY_HASH(&key);
    size_t index = dc_math_modulus_power_of_2_capacity(hash, self->capacity);
 
    VALUE* inserted_to_entry = NULL;
 
    for (;;) {
        KEY_ENTRY* entry = &self->keys[index];
        DC_ASSUME(distance_from_desired < self->capacity);
 
        if (entry->present) {
            if (KEY_EQ(&entry->key, &key)) {
                return NULL;
            }
 
            if (entry->distance_from_desired < distance_from_desired) {
                KEY const switch_key = entry->key;
                uint16_t const switch_distance_from_desired = entry->distance_from_desired;
                VALUE const switch_value = self->values[index];
 
                entry->key = key;
                entry->distance_from_desired = distance_from_desired;
                self->values[index] = value;
 
                key = switch_key;
                distance_from_desired = switch_distance_from_desired;
                value = switch_value;
 
                if (!inserted_to_entry) {
                    inserted_to_entry = &self->values[index];
                }
            }
 
            distance_from_desired++;
            index = dc_math_modulus_power_of_2_capacity(index + 1, self->capacity);
        } else {
            entry->present = true;
            entry->distance_from_desired = distance_from_desired;
            entry->key = key;
 
            dc_memory_tracker_set(DC_MEMORY_TRACKER_LVL_CONTAINER, DC_MEMORY_TRACKER_CAP_WRITE,
                                  &self->values[index], sizeof(VALUE));
 
            self->values[index] = value;
 
            if (!inserted_to_entry) {
                inserted_to_entry = &self->values[index];
            }
 
            self->items++;
            return inserted_to_entry;
        }
    }
}
 
DC_PUBLIC static void NS(SELF, extend_capacity_for)(SELF* self, size_t expected_items) {
    INVARIANT_CHECK(self);
 
    mutation_tracker_mutate(&self->iterator_invalidation_tracker);
    size_t const target_capacity = dc_apply_capacity_policy(expected_items);
    if (target_capacity > self->capacity) {
        SELF new_map = NS(SELF, new_with_capacity_for)(expected_items, self->alloc_ref);
        for (size_t index = 0; index < self->capacity; index++) {
            KEY_ENTRY* entry = &self->keys[index];
            if (entry->present) {
                PRIV(NS(SELF, try_insert_no_extend_capacity))(&new_map, entry->key,
                                                              self->values[index]);
            }
        }
        NS(ALLOC, deallocate)(self->alloc_ref, (void*)self->keys,
                              self->capacity * sizeof(KEY_ENTRY));
        NS(ALLOC, deallocate)(self->alloc_ref, (void*)self->values, self->capacity * sizeof(VALUE));
 
        INVARIANT_CHECK(&new_map);
        *self = new_map;
    }
}
 
DC_PUBLIC static VALUE* NS(SELF, try_insert)(SELF* self, KEY key, VALUE value) {
    INVARIANT_CHECK(self);
    mutation_tracker_mutate(&self->iterator_invalidation_tracker);
 
    if (self->items >= NS(SELF, max_capacity)) {
        return NULL;
    }
 
    if (dc_apply_capacity_policy(self->items) > self->capacity / 2) {
        NS(SELF, extend_capacity_for)(self, self->items * 2);
    }
 
    return PRIV(NS(SELF, try_insert_no_extend_capacity))(self, key, value);
}
 
DC_PUBLIC static VALUE* NS(SELF, insert)(SELF* self, KEY key, VALUE value) {
    VALUE* value_ptr = NS(SELF, try_insert)(self, key, value);
    DC_ASSERT(value_ptr, "Failed to insert item {key=%s, value=%s}", DC_DEBUG(KEY_DEBUG, &key),
              DC_DEBUG(VALUE_DEBUG, &value));
    return value_ptr;
}
 
DC_PUBLIC static VALUE* NS(SELF, try_write)(SELF* self, KEY key) {
    INVARIANT_CHECK(self);
    size_t const hash = KEY_HASH(&key);
    size_t index = dc_math_modulus_power_of_2_capacity(hash, self->capacity);
 
    for (;;) {
        KEY_ENTRY* entry = &self->keys[index];
        if (entry->present) {
            if (KEY_EQ(&entry->key, &key)) {
                return &self->values[index];
            }
            index = dc_math_modulus_power_of_2_capacity(index + 1, self->capacity);
        } else {
            return NULL;
        }
    }
}
 
DC_PUBLIC static VALUE* NS(SELF, write)(SELF* self, KEY key) {
    VALUE* value = NS(SELF, try_write)(self, key);
    DC_ASSERT(value, "Cannot write item {key=%s}", DC_DEBUG(KEY_DEBUG, &key));
    return value;
}
 
DC_PUBLIC static VALUE const* NS(SELF, try_read)(SELF const* self, KEY key) {
    INVARIANT_CHECK(self);
    size_t const hash = KEY_HASH(&key);
    size_t index = dc_math_modulus_power_of_2_capacity(hash, self->capacity);
 
    for (;;) {
        KEY_ENTRY* entry = &self->keys[index];
        if (entry->present) {
            if (KEY_EQ(&entry->key, &key)) {
                return &self->values[index];
            }
            index = dc_math_modulus_power_of_2_capacity(index + 1, self->capacity);
        } else {
            return NULL;
        }
    }
}
 
DC_PUBLIC static VALUE const* NS(SELF, read)(SELF const* self, KEY key) {
    VALUE const* value = NS(SELF, try_read)(self, key);
    DC_ASSERT(value, "Cannot read item {key=%s}", DC_DEBUG(KEY_DEBUG, &key));
    return value;
}
 
DC_PUBLIC static bool NS(SELF, try_remove)(SELF* self, KEY key, VALUE* destination) {
    INVARIANT_CHECK(self);
    mutation_tracker_mutate(&self->iterator_invalidation_tracker);
    size_t const hash = KEY_HASH(&key);
    size_t index = dc_math_modulus_power_of_2_capacity(hash, self->capacity);
 
    for (;;) {
        KEY_ENTRY* entry = &self->keys[index];
        if (entry->present) {
            if (KEY_EQ(&entry->key, &key)) {
                self->items--;
 
                *destination = self->values[index];
                KEY_DELETE(&entry->key);
 
                // NOTE: For robin hood hashing, we need probe chains to be unbroken
                //        - Need to find the entries that might use this chain (
                //          distance_to_desired > 0 until the next not-present or
                //          distance_to_desired=0 slot)
                //        hence we shift entries the left (being careful with modulus index)
 
                size_t free_index = index;
                KEY_ENTRY* free_entry = entry;
 
                size_t check_index =
                    dc_math_modulus_power_of_2_capacity(free_index + 1, self->capacity);
                KEY_ENTRY* check_entry = &self->keys[check_index];
 
                while (check_entry->present && (check_entry->distance_from_desired > 0)) {
                    free_entry->key = check_entry->key;
                    free_entry->distance_from_desired = check_entry->distance_from_desired - 1;
                    self->values[free_index] = self->values[check_index];
 
                    free_index = check_index;
                    free_entry = check_entry;
 
                    check_index =
                        dc_math_modulus_power_of_2_capacity(free_index + 1, self->capacity);
                    check_entry = &self->keys[check_index];
                }
 
                // JUSTIFY: Only setting free entry to false
                //           - We remove, then shift down an index
                //           - The removed entry already has the flag set
                //           - the free entry was the last one removed/moved down an index, so it
                //             should be false.
 
                free_entry->present = false;
                dc_memory_tracker_set(DC_MEMORY_TRACKER_LVL_CONTAINER, DC_MEMORY_TRACKER_CAP_NONE,
                                      &self->values[free_index], sizeof(VALUE));
 
                return true;
            }
            index = dc_math_modulus_power_of_2_capacity(index + 1, self->capacity);
        } else {
            return false;
        }
    }
}
 
DC_PUBLIC static VALUE NS(SELF, remove)(SELF* self, KEY key) {
    VALUE value;
    DC_ASSERT(NS(SELF, try_remove)(self, key, &value), "Failed to remove item {key=%s}",
              DC_DEBUG(KEY_DEBUG, &key));
    return value;
}
 
DC_PUBLIC static void NS(SELF, delete_entry)(SELF* self, KEY key) {
    VALUE value = NS(SELF, remove)(self, key);
    VALUE_DELETE(&value);
}
 
DC_PUBLIC static size_t NS(SELF, size)(SELF const* self) {
    INVARIANT_CHECK(self);
    return self->items;
}
 
#define KV_PAIR NS(SELF, kv)
 
typedef struct {
    KEY const* key;
    VALUE* value;
} KV_PAIR;
 
#define ITER NS(SELF, iter)
typedef KV_PAIR NS(ITER, item);
 
DC_PUBLIC static bool NS(ITER, empty_item)(KV_PAIR const* item) {
    return item->key == NULL && item->value == NULL;
}
 
typedef struct {
    SELF* map;
    size_t index;
    KV_PAIR curr;
    mutation_version version;
} ITER;
 
DC_PUBLIC static KV_PAIR NS(ITER, next)(ITER* iter) {
    DC_ASSUME(iter);
    mutation_version_check(&iter->version);
    if (iter->index < iter->map->capacity) {
        iter->curr = (KV_PAIR){.key = &iter->map->keys[iter->index].key,
                               .value = &iter->map->values[iter->index]};
        iter->index++;
        while (iter->index < iter->map->capacity && !iter->map->keys[iter->index].present) {
            iter->index++;
        }
        return iter->curr;
    }
    return (KV_PAIR){.key = NULL, .value = NULL};
}
 
DC_PUBLIC static bool NS(ITER, empty)(ITER const* iter) {
    DC_ASSUME(iter);
    mutation_version_check(&iter->version);
    return iter->index >= iter->map->capacity;
}
 
DC_PUBLIC static ITER NS(SELF, get_iter)(SELF* self) {
    DC_ASSUME(self);
    size_t first_index = 0;
    while (first_index < self->capacity && !self->keys[first_index].present) {
        first_index++;
    }
    return (ITER){
        .map = self,
        .index = first_index,
        .curr = (KV_PAIR){.key = NULL, .value = NULL},
        .version = mutation_tracker_get(&self->iterator_invalidation_tracker),
    };
}
 
DC_PUBLIC static void NS(SELF, delete)(SELF* self) {
    DC_ASSUME(self);
 
    for (size_t i = 0; i < self->capacity; i++) {
        if (self->keys[i].present) {
            KEY_DELETE(&self->keys[i].key);
            VALUE_DELETE(&self->values[i]);
        }
    }
 
    NS(ALLOC, deallocate)(self->alloc_ref, (void*)self->keys, self->capacity * sizeof(KEY_ENTRY));
    NS(ALLOC, deallocate)(self->alloc_ref, (void*)self->values, self->capacity * sizeof(VALUE));
}
 
#undef ITER
#undef KV_PAIR
 
#define KV_PAIR_CONST NS(SELF, kv_const)
 
typedef struct {
    KEY const* key;
    VALUE const* value;
} KV_PAIR_CONST;
 
#define ITER_CONST NS(SELF, iter_const)
typedef KV_PAIR_CONST NS(ITER_CONST, item);
 
DC_PUBLIC static bool NS(ITER_CONST, empty_item)(KV_PAIR_CONST const* item) {
    return item->key == NULL && item->value == NULL;
}
 
typedef struct {
    SELF const* map;
    size_t index;
    KV_PAIR_CONST curr;
    mutation_version version;
} ITER_CONST;
 
DC_PUBLIC static KV_PAIR_CONST NS(ITER_CONST, next)(ITER_CONST* iter) {
    DC_ASSUME(iter);
    mutation_version_check(&iter->version);
    if (iter->index < iter->map->capacity) {
        iter->curr = (KV_PAIR_CONST){.key = &iter->map->keys[iter->index].key,
                                     .value = &iter->map->values[iter->index]};
        iter->index++;
        while (iter->index < iter->map->capacity && !iter->map->keys[iter->index].present) {
            iter->index++;
        }
        return iter->curr;
    }
    return (KV_PAIR_CONST){.key = NULL, .value = NULL};
}
 
DC_PUBLIC static bool NS(ITER_CONST, empty)(ITER_CONST const* iter) {
    DC_ASSUME(iter);
    mutation_version_check(&iter->version);
    return iter->index >= iter->map->capacity;
}
 
DC_PUBLIC static ITER_CONST NS(SELF, get_iter_const)(SELF const* self) {
    DC_ASSUME(self);
    size_t first_index = 0;
    while (first_index < self->capacity && !self->keys[first_index].present) {
        first_index++;
    }
    return (ITER_CONST){
        .map = self,
        .index = first_index,
        .curr = (KV_PAIR_CONST){.key = NULL, .value = NULL},
        .version = mutation_tracker_get(&self->iterator_invalidation_tracker),
    };
}
 
DC_PUBLIC static void NS(SELF, debug)(SELF const* self, dc_debug_fmt fmt, FILE* stream) {
    fprintf(stream, DC_EXPAND_STRING(SELF) "@%p {\n", (void*)self);
    fmt = dc_debug_fmt_scope_begin(fmt);
 
    dc_debug_fmt_print(fmt, stream, "capacity: %zu,\n", self->capacity);
    dc_debug_fmt_print(fmt, stream, "size: %zu,\n", NS(SELF, size)(self));
 
    dc_debug_fmt_print(fmt, stream, "keys: @%p,\n", (void*)self->keys);
    dc_debug_fmt_print(fmt, stream, "values: @%p,\n", (void*)self->values);
 
    dc_debug_fmt_print(fmt, stream, "alloc: ");
    NS(ALLOC, debug)(NS(NS(ALLOC, ref), deref)(self->alloc_ref), fmt, stream);
    fprintf(stream, ",\n");
 
    dc_debug_fmt_print(fmt, stream, "items: [\n");
    fmt = dc_debug_fmt_scope_begin(fmt);
 
    ITER_CONST iter = NS(SELF, get_iter_const)(self);
    for (KV_PAIR_CONST item = NS(ITER_CONST, next)(&iter); !NS(ITER_CONST, empty_item)(&item);
         item = NS(ITER_CONST, next)(&iter)) {
        dc_debug_fmt_print(fmt, stream, "{\n");
        fmt = dc_debug_fmt_scope_begin(fmt);
 
        dc_debug_fmt_print(fmt, stream, "key: ");
        KEY_DEBUG(item.key, fmt, stream);
        fprintf(stream, ",\n");
 
        dc_debug_fmt_print(fmt, stream, "value: ");
        VALUE_DEBUG(item.value, fmt, stream);
        fprintf(stream, ",\n");
 
        fmt = dc_debug_fmt_scope_end(fmt);
        dc_debug_fmt_print(fmt, stream, "},\n");
    }
 
    fmt = dc_debug_fmt_scope_end(fmt);
    dc_debug_fmt_print(fmt, stream, "],\n");
    fmt = dc_debug_fmt_scope_end(fmt);
    dc_debug_fmt_print(fmt, stream, "}");
}
 
#undef ITER_CONST
#undef KV_PAIR_CONST
 
#undef INVARIANT_CHECK
#undef KEY_ENTRY
 
#undef VALUE_DEBUG
#undef VALUE_CLONE
#undef VALUE_DELETE
#undef VALUE
 
#undef KEY_DEBUG
#undef KEY_CLONE
#undef KEY_DELETE
#undef KEY_EQ
#undef KEY_HASH
#undef KEY
 
DC_TRAIT_MAP(SELF);
 
#include <derive-c/core/self/undef.h>
#include <derive-c/core/alloc/undef.h>
#include <derive-c/core/includes/undef.h>