template.h File Reference

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include "utils.h"
#include <derive-c/core/debug/gdb_marker.h>
#include <derive-c/core/debug/memory_tracker.h>
#include <derive-c/core/debug/mutation_tracker.h>
#include <derive-c/core/prelude.h>
#include <derive-c/core/alloc/def.h>
#include <derive-c/core/self/def.h>
#include <derive-c/core/alloc/undef.h>
#include <derive-c/container/map/trait.h>
#include <derive-c/core/self/undef.h>

Include dependency graph for template.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	value_t
struct	KEY_ENTRY
struct	SELF
	An allocator that prints to stdout when it allocates or frees memory. More...
struct	KV_PAIR
struct	KV_PAIR_CONST

Macros
#define	KEY   map_key_t
	A simple open-addressed hashmap using robin-hood hashing.
#define	KEY_HASH   key_hash
#define	KEY_EQ   NS(SELF, key_eq_default)
#define	KEY_DELETE   NS(SELF, key_delete_default)
#define	KEY_CLONE   NS(SELF, key_clone_default)
#define	VALUE   value_t
#define	VALUE_DELETE   NS(SELF, value_delete_default)
#define	VALUE_CLONE   NS(SELF, value_clone_default)
#define	KEY_ENTRY   NS(SELF, key_entry)
#define	INVARIANT_CHECK(self)
#define	KV_PAIR   NS(SELF, kv)
#define	KV_PAIR_CONST   NS(SELF, kv_const)

Typedefs
typedef int	KEY
typedef KEY	key_t
typedef KV_PAIR const *	item

Functions
static size_t	KEY_HASH (KEY const *key)
static bool	KEY_EQ (KEY const *key_1, KEY const *key_2)
static void	KEY_DELETE (KEY *key)
static KEY	KEY_CLONE (KEY const *key)
static void	VALUE_DELETE (VALUE *value)
static VALUE	VALUE_CLONE (VALUE const *value)
static SELF	new_with_capacity_for (size_t capacity, ALLOC *alloc)
static SELF	new (ALLOC *alloc)
static SELF	clone (SELF const *self)
static void	delete (SELF *self)
static VALUE *	insert (SELF *self, KEY key, VALUE value)
static void	extend_capacity_for (SELF *self, size_t expected_items)
static VALUE *	try_insert (SELF *self, KEY key, VALUE value)
static VALUE *	try_write (SELF *self, KEY key)
static VALUE *	write (SELF *self, KEY key)
static VALUE const *	try_read (SELF const *self, KEY key)
static VALUE const *	read (SELF const *self, KEY key)
static bool	try_remove (SELF *self, KEY key, VALUE *destination)
static VALUE	remove (SELF *self, KEY key)
static void	delete_entry (SELF *self, KEY key)
static size_t	size (SELF const *self)
static bool	empty_item (KV_PAIR const *const *item)
static KV_PAIR const *	next (ITER *iter)
static bool	empty (ITER const *iter)
static ITER	get_iter (SELF *self)
static bool	empty_item (KV_PAIR_CONST const *const *item)
static KV_PAIR_CONST const *	next (ITER_CONST *iter)
static bool	empty (ITER_CONST const *iter)
static ITER_CONST	get_iter_const (SELF const *self)
	TRAIT_MAP (SELF)

Macro Definition Documentation

INVARIANT_CHECK

#define INVARIANT_CHECK

(

self

)

Value:

    ASSUME(self);                                                                                  \
    ASSUME(is_power_of_2((self)->capacity));                                                       \
    ASSUME((self)->keys);                                                                          \
    ASSUME((self)->values);                                                                        \
    ASSUME((self)->alloc);

Definition at line 91 of file template.h.

#define INVARIANT_CHECK(self)                                                                      \
    ASSUME(self);                                                                                  \
    ASSUME(is_power_of_2((self)->capacity));                                                       \
    ASSUME((self)->keys);                                                                          \
    ASSUME((self)->values);                                                                        \
    ASSUME((self)->alloc);

KEY

#define KEY   map_key_t

A simple open-addressed hashmap using robin-hood hashing.

Definition at line 22 of file template.h.

KEY_CLONE

#define KEY_CLONE   NS(SELF, key_clone_default)

Definition at line 46 of file template.h.

KEY_DELETE

#define KEY_DELETE   NS(SELF, key_delete_default)

Definition at line 41 of file template.h.

KEY_ENTRY

#define KEY_ENTRY   NS(SELF, key_entry)

Definition at line 74 of file template.h.

KEY_EQ

#define KEY_EQ   NS(SELF, key_eq_default)

Definition at line 36 of file template.h.

KEY_HASH

#define KEY_HASH   key_hash

Definition at line 31 of file template.h.

KV_PAIR

#define KV_PAIR   NS(SELF, kv)

Definition at line 386 of file template.h.

KV_PAIR_CONST

#define KV_PAIR_CONST   NS(SELF, kv_const)

Definition at line 457 of file template.h.

VALUE

#define VALUE   value_t

Definition at line 57 of file template.h.

VALUE_CLONE

#define VALUE_CLONE   NS(SELF, value_clone_default)

Definition at line 66 of file template.h.

VALUE_DELETE

#define VALUE_DELETE   NS(SELF, value_delete_default)

Definition at line 61 of file template.h.

Typedef Documentation

item

typedef KV_PAIR_CONST const* item

Definition at line 394 of file template.h.

KEY

typedef int KEY

Definition at line 23 of file template.h.

key_t

typedef KEY key_t

Definition at line 70 of file template.h.

Function Documentation

clone()

SELF clone ( SELF const * self )

static

Definition at line 132 of file template.h.

                                              {
    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, calloc)(self->alloc, sizeof(KEY_ENTRY), self->capacity);
    VALUE* values = (VALUE*)NS(ALLOC, malloc)(self->alloc, sizeof(VALUE) * self->capacity);
    ASSERT(keys && values);
 
    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 {
            memory_tracker_set(MEMORY_TRACKER_LVL_CONTAINER, MEMORY_TRACKER_CAP_NONE, &values[i],
                               sizeof(VALUE));
        }
    }
 
    return (SELF){
        .capacity = self->capacity,
        .items = self->items,
        .keys = keys,
        .values = values,
        .alloc = self->alloc,
        .derive_c_hashmap = gdb_marker_new(),
        .iterator_invalidation_tracker = mutation_tracker_new(),
    };
}

Here is the call graph for this function:

delete()

void delete ( SELF * self )

static

Definition at line 440 of file template.h.

                                         {
    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, free)(self->alloc, (void*)self->keys);
    NS(ALLOC, free)(self->alloc, (void*)self->values);
}

Here is the call graph for this function:

delete_entry()

void delete_entry ( SELF * self, KEY key )

static

Definition at line 376 of file template.h.

                                                        {
    VALUE value = NS(SELF, remove)(self, key);
    VALUE_DELETE(&value);
}

Here is the call graph for this function:

empty() [1/2]

bool empty ( ITER const * iter )

static

Definition at line 420 of file template.h.

                                              {
    ASSUME(iter);
    mutation_version_check(&iter->version);
    return iter->index >= iter->map->capacity;
}

Here is the call graph for this function:

empty() [2/2]

bool empty ( ITER_CONST const * iter )

static

Definition at line 491 of file template.h.

                                                          {
    ASSUME(iter);
    mutation_version_check(&iter->version);
    return iter->index >= iter->map->capacity;
}

Here is the call graph for this function:

empty_item() [1/2]

bool empty_item ( KV_PAIR const *const * item )

static

Definition at line 396 of file template.h.

{ return *item == NULL; }

Here is the call graph for this function:

empty_item() [2/2]

bool empty_item ( KV_PAIR_CONST const *const * item )

static

Definition at line 467 of file template.h.

{ return *item == NULL; }

Here is the call graph for this function:

extend_capacity_for()

void extend_capacity_for ( SELF * self, size_t expected_items )

static

Definition at line 175 of file template.h.

                                                                             {
    INVARIANT_CHECK(self);
 
    mutation_tracker_mutate(&self->iterator_invalidation_tracker);
    size_t const target_capacity = apply_capacity_policy(expected_items);
    if (target_capacity > self->capacity) {
        SELF new_map = NS(SELF, new_with_capacity_for)(expected_items, self->alloc);
        for (size_t index = 0; index < self->capacity; index++) {
            KEY_ENTRY* entry = &self->keys[index];
            if (entry->present) {
                NS(SELF, insert)(&new_map, entry->key, self->values[index]);
            }
        }
        NS(ALLOC, free)(self->alloc, (void*)self->keys);
        NS(ALLOC, free)(self->alloc, (void*)self->values);
 
        INVARIANT_CHECK(&new_map);
        *self = new_map;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

get_iter()

ITER get_iter ( SELF * self )

static

Definition at line 426 of file template.h.

                                           {
    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),
    };
}

Here is the call graph for this function:

get_iter_const()

ITER_CONST get_iter_const ( SELF const * self )

static

Definition at line 497 of file template.h.

                                                             {
    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),
    };
}

Here is the call graph for this function:

insert()

VALUE * insert ( SELF * self, KEY key, VALUE value )

static

Definition at line 258 of file template.h.

                                                                 {
    VALUE* value_ptr = NS(SELF, try_insert)(self, key, value);
    ASSERT(value_ptr);
    return value_ptr;
}

Here is the call graph for this function:

KEY_CLONE()

KEY KEY_CLONE ( KEY const * key )

static

Definition at line 47 of file template.h.

{ return *key; }

KEY_DELETE()

void KEY_DELETE ( KEY * key )

static

Definition at line 42 of file template.h.

{ (void)key; }

KEY_EQ()

bool KEY_EQ ( KEY const * key_1, KEY const * key_2 )

static

Definition at line 37 of file template.h.

{ return *key_1 == *key_2; }

KEY_HASH()

size_t KEY_HASH ( KEY const * key )

static

new()

SELF new ( ALLOC * alloc )

static

Definition at line 128 of file template.h.

                                        {
    return NS(SELF, new_with_capacity_for)(INITIAL_CAPACITY, alloc);
}

Here is the call graph for this function:

new_with_capacity_for()

SELF new_with_capacity_for ( size_t capacity, ALLOC * alloc )

static

Definition at line 98 of file template.h.

                                                                           {
    ASSERT(capacity > 0);
    size_t const real_capacity = apply_capacity_policy(capacity);
    ASSERT(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, calloc)(alloc, sizeof(KEY_ENTRY), real_capacity);
    VALUE* values = (VALUE*)NS(ALLOC, malloc)(alloc, sizeof(VALUE) * real_capacity);
    ASSERT(keys && values);
 
    // 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.
    memory_tracker_set(MEMORY_TRACKER_LVL_CONTAINER, MEMORY_TRACKER_CAP_NONE, values,
                       sizeof(VALUE) * real_capacity);
 
    return (SELF){
        .capacity = real_capacity,
        .items = 0,
        .keys = keys,
        .values = values,
        .alloc = alloc,
        .derive_c_hashmap = gdb_marker_new(),
        .iterator_invalidation_tracker = mutation_tracker_new(),
    };
}

Here is the call graph for this function:

next() [1/2]

KV_PAIR const * next ( ITER * iter )

static

Definition at line 405 of file template.h.

                                                 {
    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 NULL;
}

Here is the call graph for this function:

next() [2/2]

KV_PAIR_CONST const * next ( ITER_CONST * iter )

static

Definition at line 476 of file template.h.

                                                                   {
    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 NULL;
}

Here is the call graph for this function:

read()

VALUE const * read ( SELF const * self, KEY key )

static

Definition at line 306 of file template.h.

                                                              {
    VALUE const* value = NS(SELF, try_read)(self, key);
    ASSERT(value);
    return value;
}

Here is the call graph for this function:

remove()

VALUE remove ( SELF * self, KEY key )

static

Definition at line 370 of file template.h.

                                                   {
    VALUE value;
    ASSERT(NS(SELF, try_remove)(self, key, &value));
    return value;
}

Here is the call graph for this function:

size()

size_t size ( SELF const * self )

static

Definition at line 381 of file template.h.

                                               {
    INVARIANT_CHECK(self);
    return self->items;
}

Here is the call graph for this function:

TRAIT_MAP()

TRAIT_MAP

(

SELF

)

try_insert()

VALUE * try_insert ( SELF * self, KEY key, VALUE value )

static

Definition at line 196 of file template.h.

                                                                     {
    INVARIANT_CHECK(self);
    mutation_tracker_mutate(&self->iterator_invalidation_tracker);
    if (apply_capacity_policy(self->items) > self->capacity / 2) {
        NS(SELF, extend_capacity_for)(self, self->items * 2);
    }
 
    uint16_t distance_from_desired = 0;
    size_t const hash = KEY_HASH(&key);
    size_t index = modulus_power_of_2_capacity(hash, self->capacity);
 
    VALUE* inserted_to_entry = NULL;
 
    for (;;) {
        KEY_ENTRY* entry = &self->keys[index];
        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 = modulus_power_of_2_capacity(index + 1, self->capacity);
        } else {
            entry->present = true;
            entry->distance_from_desired = distance_from_desired;
            entry->key = key;
 
            memory_tracker_set(MEMORY_TRACKER_LVL_CONTAINER, 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;
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

try_read()

VALUE const * try_read ( SELF const * self, KEY key )

static

Definition at line 288 of file template.h.

                                                                  {
    INVARIANT_CHECK(self);
    size_t const hash = KEY_HASH(&key);
    size_t index = 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 = modulus_power_of_2_capacity(index + 1, self->capacity);
        } else {
            return NULL;
        }
    }
}

Here is the call graph for this function:

try_remove()

bool try_remove ( SELF * self, KEY key, VALUE * destination )

static

Definition at line 312 of file template.h.

                                                                          {
    INVARIANT_CHECK(self);
    mutation_tracker_mutate(&self->iterator_invalidation_tracker);
    size_t const hash = KEY_HASH(&key);
    size_t index = 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 = 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 = 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;
                memory_tracker_set(MEMORY_TRACKER_LVL_CONTAINER, MEMORY_TRACKER_CAP_NONE,
                                   &self->values[free_index], sizeof(VALUE));
 
                return true;
            }
            index = modulus_power_of_2_capacity(index + 1, self->capacity);
        } else {
            return false;
        }
    }
}

Here is the call graph for this function:

try_write()

VALUE * try_write ( SELF * self, KEY key )

static

Definition at line 264 of file template.h.

                                                       {
    INVARIANT_CHECK(self);
    size_t const hash = KEY_HASH(&key);
    size_t index = 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 = modulus_power_of_2_capacity(index + 1, self->capacity);
        } else {
            return NULL;
        }
    }
}

Here is the call graph for this function:

VALUE_CLONE()

VALUE VALUE_CLONE ( VALUE const * value )

static

Definition at line 67 of file template.h.

{ return *value; }

VALUE_DELETE()

void VALUE_DELETE ( VALUE * value )

static

Definition at line 62 of file template.h.

{ (void)value; }

write()

VALUE * write ( SELF * self, KEY key )

static

Definition at line 282 of file template.h.

                                                   {
    VALUE* value = NS(SELF, try_write)(self, key);
    ASSERT(value);
    return value;
}

Here is the call graph for this function: