template.h File Reference

#include "derive-c/container/map/swiss/utils.h"
#include "derive-c/core/panic.h"
#include <derive-c/core/includes/def.h>
#include "includes.h"
#include <derive-c/core/alloc/def.h>
#include <derive-c/core/self/def.h>
#include <derive-c/core/self/undef.h>
#include <derive-c/core/alloc/undef.h>
#include <derive-c/core/includes/undef.h>

Go to the source code of this file.

Data Structures
struct	value_t
struct	SLOT
struct	SELF
	An allocator that prints to stdout when it allocates or frees memory. More...
struct	ITER_CONST
struct	KV_PAIR_CONST
struct	ITER
struct	KV_PAIR

Macros
#define	KEY   map_key_t
	A simple swiss table implementation. See the abseil docs for swss table here.
#define	KEY_HASH   key_hash
#define	KEY_EQ   DC_MEM_EQ
#define	KEY_DELETE   DC_NO_DELETE
#define	KEY_CLONE   DC_COPY_CLONE
#define	KEY_DEBUG   DC_DEFAULT_DEBUG
#define	VALUE   value_t
#define	VALUE_DELETE   DC_NO_DELETE
#define	VALUE_CLONE   DC_COPY_CLONE
#define	VALUE_DEBUG   DC_DEFAULT_DEBUG
#define	SLOT   NS(SELF, slot_t)
#define	INVARIANT_CHECK(self)
#define	ITER_CONST   NS(SELF, iter_const)
#define	KV_PAIR_CONST   NS(ITER_CONST, item)
#define	ITER   NS(SELF, iter)
#define	KV_PAIR   NS(ITER, item)

Functions
static size_t	KEY_HASH (KEY const *key)
static SELF PRIV	new_with_exact_capacity (size_t capacity, ref alloc_ref)
static DC_PUBLIC SELF	new_with_capacity_for (size_t for_items, ref alloc_ref)
static DC_PUBLIC SELF	new (ref alloc_ref)
static DC_PUBLIC SELF	clone (SELF const *self)
static VALUE *PRIV	try_insert_no_extend_capacity (SELF *self, KEY key, VALUE value)
static void PRIV	rehash (SELF *self, size_t new_capacity)
static DC_PUBLIC void	extend_capacity_for (SELF *self, size_t expected_items)
static DC_PUBLIC VALUE *	try_insert (SELF *self, KEY key, VALUE value)
static DC_PUBLIC VALUE *	insert (SELF *self, KEY key, VALUE value)
static DC_PUBLIC VALUE const *	try_read (SELF const *self, KEY key)
static DC_PUBLIC VALUE const *	read (SELF const *self, KEY key)
static DC_PUBLIC VALUE *	try_write (SELF *self, KEY key)
static DC_PUBLIC VALUE *	write (SELF *self, KEY key)
static DC_PUBLIC bool	try_remove (SELF *self, KEY key, VALUE *destination)
static DC_PUBLIC VALUE	remove (SELF *self, KEY key)
static DC_PUBLIC void	delete_entry (SELF *self, KEY key)
static DC_PUBLIC size_t	size (SELF const *self)
static void PRIV	next_populated_index (SELF const *self, _dc_swiss_optional_index *index)
static DC_PUBLIC void	delete (SELF *self)
static DC_PUBLIC bool	empty_item (KV_PAIR_CONST const *item)
static DC_PUBLIC KV_PAIR_CONST	next (ITER_CONST *iter)
static DC_PUBLIC bool	empty (ITER_CONST const *iter)
static DC_PUBLIC ITER_CONST	get_iter_const (SELF const *self)
static DC_PUBLIC void	debug (SELF const *self, dc_debug_fmt fmt, FILE *stream)
static DC_PUBLIC bool	empty_item (KV_PAIR const *item)
static DC_PUBLIC KV_PAIR	next (ITER *iter)
static DC_PUBLIC bool	empty (ITER const *iter)
static DC_PUBLIC ITER	get_iter (SELF *self)
	DC_TRAIT_MAP (SELF)

Variables
DC_STATIC_CONSTANT size_t	max_capacity = _dc_swiss_index_capacity

Macro Definition Documentation

INVARIANT_CHECK

#define INVARIANT_CHECK

(

self

)

Value:

    DC_ASSUME(self);                                                                               \
    DC_ASSUME(DC_MATH_IS_POWER_OF_2((self)->capacity));                                            \
    DC_ASSUME((self)->slots);                                                                      \
    DC_ASSUME((self)->ctrl);                                                                       \
    DC_ASSUME((self)->count + (self)->tombstones <= (self)->capacity);

Definition at line 94 of file template.h.

#define INVARIANT_CHECK(self)                                                                      \
    DC_ASSUME(self);                                                                               \
    DC_ASSUME(DC_MATH_IS_POWER_OF_2((self)->capacity));                                            \
    DC_ASSUME((self)->slots);                                                                      \
    DC_ASSUME((self)->ctrl);                                                                       \
    DC_ASSUME((self)->count + (self)->tombstones <= (self)->capacity);

ITER

#define ITER   NS(SELF, iter)

Definition at line 539 of file template.h.

ITER_CONST

#define ITER_CONST   NS(SELF, iter_const)

Definition at line 435 of file template.h.

KEY

#define KEY   map_key_t

A simple swiss table implementation. See the abseil docs for swss table here.

Definition at line 18 of file template.h.

KEY_CLONE

#define KEY_CLONE   DC_COPY_CLONE

Definition at line 40 of file template.h.

KEY_DEBUG

#define KEY_DEBUG   DC_DEFAULT_DEBUG

Definition at line 44 of file template.h.

KEY_DELETE

#define KEY_DELETE   DC_NO_DELETE

Definition at line 36 of file template.h.

KEY_EQ

#define KEY_EQ   DC_MEM_EQ

Definition at line 32 of file template.h.

KEY_HASH

#define KEY_HASH   key_hash

Definition at line 27 of file template.h.

KV_PAIR

#define KV_PAIR   NS(ITER, item)

Definition at line 540 of file template.h.

KV_PAIR_CONST

#define KV_PAIR_CONST   NS(ITER_CONST, item)

Definition at line 436 of file template.h.

SLOT

#define SLOT   NS(SELF, slot_t)

Definition at line 73 of file template.h.

VALUE

#define VALUE   value_t

Definition at line 54 of file template.h.

VALUE_CLONE

#define VALUE_CLONE   DC_COPY_CLONE

Definition at line 62 of file template.h.

VALUE_DEBUG

#define VALUE_DEBUG   DC_DEFAULT_DEBUG

Definition at line 66 of file template.h.

VALUE_DELETE

#define VALUE_DELETE   DC_NO_DELETE

Definition at line 58 of file template.h.

Function Documentation

clone()

DC_PUBLIC SELF clone ( SELF const * self )

static

Definition at line 141 of file template.h.

                                                        {
    INVARIANT_CHECK(self);
 
    size_t ctrl_capacity = self->capacity + _DC_SWISS_SIMD_PROBE_SIZE;
 
    _dc_swiss_ctrl* ctrl = (_dc_swiss_ctrl*)NS(ALLOC, allocate_uninit)(
        self->alloc_ref, sizeof(_dc_swiss_ctrl) * ctrl_capacity);
    SLOT* slots = (SLOT*)NS(ALLOC, allocate_uninit)(self->alloc_ref, sizeof(SLOT) * self->capacity);
 
    memcpy(ctrl, self->ctrl, sizeof(_dc_swiss_ctrl) * ctrl_capacity);
 
    for (size_t i = 0; i < self->capacity; i++) {
        if (_dc_swiss_is_present(self->ctrl[i])) {
            slots[i].key = KEY_CLONE(&self->slots[i].key);
            slots[i].value = VALUE_CLONE(&self->slots[i].value);
        }
    }
 
    return (SELF){
        .capacity = self->capacity,
        .count = self->count,
        .tombstones = self->tombstones,
        .ctrl = ctrl,
        .slots = slots,
        .alloc_ref = self->alloc_ref,
        .derive_c_hashmap = dc_gdb_marker_new(),
        .iterator_invalidation_tracker = mutation_tracker_new(),
    };
}

DC_TRAIT_MAP()

DC_TRAIT_MAP

(

SELF

)

debug()

DC_PUBLIC void debug ( SELF const * self, dc_debug_fmt fmt, FILE * stream )

static

Definition at line 491 of file template.h.

                                                                                        {
    fprintf(stream, DC_EXPAND_STRING(SELF) "@%p {\n", (void*)self);
    fmt = dc_debug_fmt_scope_begin(fmt);
 
    dc_debug_fmt_print(fmt, stream, "capacity: %lu,\n", self->capacity);
    dc_debug_fmt_print(fmt, stream, "tombstones: %lu,\n", self->tombstones);
    dc_debug_fmt_print(fmt, stream, "count: %lu,\n", self->count);
 
    dc_debug_fmt_print(fmt, stream, "ctrl: @%p[%lu + simd probe size additional %lu],\n",
                       (void*)self->ctrl, self->capacity, (size_t)_DC_SWISS_SIMD_PROBE_SIZE);
    dc_debug_fmt_print(fmt, stream, "slots: @%p[%lu],\n", (void*)self->slots, self->capacity);
 
    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, "entries: [\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, "}");
}

delete()

DC_PUBLIC void delete ( SELF * self )

static

Definition at line 422 of file template.h.

                                                   {
    for (size_t i = 0; i < self->capacity; i++) {
        if (_dc_swiss_is_present(self->ctrl[i])) {
            KEY_DELETE(&self->slots[i].key);
            VALUE_DELETE(&self->slots[i].value);
        }
    }
 
    size_t ctrl_capacity = self->capacity + _DC_SWISS_SIMD_PROBE_SIZE;
    NS(ALLOC, deallocate)(self->alloc_ref, self->ctrl, sizeof(_dc_swiss_ctrl) * ctrl_capacity);
    NS(ALLOC, deallocate)(self->alloc_ref, self->slots, sizeof(SLOT) * self->capacity);
}

delete_entry()

DC_PUBLIC void delete_entry ( SELF * self, KEY key )

static

Definition at line 403 of file template.h.

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

empty() [1/2]

DC_PUBLIC bool empty ( ITER const * iter )

static

Definition at line 576 of file template.h.

                                                        {
    DC_ASSUME(iter);
    mutation_version_check(&iter->version);
    return iter->next_index == _DC_SWISS_NO_INDEX;
}

empty() [2/2]

DC_PUBLIC bool empty ( ITER_CONST const * iter )

static

Definition at line 472 of file template.h.

                                                                    {
    DC_ASSUME(iter);
    mutation_version_check(&iter->version);
    return iter->next_index == _DC_SWISS_NO_INDEX;
}

empty_item() [1/2]

DC_PUBLIC bool empty_item ( KV_PAIR const * item )

static

Definition at line 553 of file template.h.

                                                                {
    return item->key == NULL && item->value == NULL;
}

empty_item() [2/2]

DC_PUBLIC bool empty_item ( KV_PAIR_CONST const * item )

static

Definition at line 449 of file template.h.

                                                                            {
    return item->key == NULL && item->value == NULL;
}

extend_capacity_for()

DC_PUBLIC void extend_capacity_for ( SELF * self, size_t expected_items )

static

Definition at line 269 of file template.h.

                                                                                       {
    INVARIANT_CHECK(self);
    mutation_tracker_mutate(&self->iterator_invalidation_tracker);
 
    size_t new_capacity = dc_swiss_capacity(expected_items);
    if (new_capacity > self->capacity) {
        PRIV(NS(SELF, rehash))(self, new_capacity);
    }
}

get_iter()

DC_PUBLIC ITER get_iter ( SELF * self )

static

Definition at line 582 of file template.h.

                                                     {
    INVARIANT_CHECK(self);
 
    _dc_swiss_optional_index index = 0;
    PRIV(NS(SELF, next_populated_index))(self, &index);
 
    return (ITER){
        .map = self,
        .next_index = index,
        .version = mutation_tracker_get(&self->iterator_invalidation_tracker),
    };
}

get_iter_const()

DC_PUBLIC ITER_CONST get_iter_const ( SELF const * self )

static

Definition at line 478 of file template.h.

                                                                       {
    INVARIANT_CHECK(self);
 
    _dc_swiss_optional_index index = 0;
    PRIV(NS(SELF, next_populated_index))(self, &index);
 
    return (ITER_CONST){
        .map = self,
        .next_index = index,
        .version = mutation_tracker_get(&self->iterator_invalidation_tracker),
    };
}

insert()

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

static

Definition at line 300 of file template.h.

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

KEY_HASH()

size_t KEY_HASH ( KEY const * key )

static

Definition at line 28 of file template.h.

{ return *key; }

new()

DC_PUBLIC SELF new ( ref alloc_ref )

static

Definition at line 137 of file template.h.

                                                              {
    return NS(SELF, new_with_capacity_for)(DC_SWISS_INITIAL_CAPACITY, alloc_ref);
}

new_with_capacity_for()

DC_PUBLIC SELF new_with_capacity_for ( size_t for_items, ref alloc_ref )

static

Definition at line 130 of file template.h.

                                                                                                  {
    DC_ASSERT(for_items > 0, "Cannot create map with capacity for 0 items {for_items=%lu}",
              for_items);
 
    return PRIV(NS(SELF, new_with_exact_capacity))(dc_swiss_capacity(for_items), alloc_ref);
}

new_with_exact_capacity()

SELF PRIV new_with_exact_capacity ( size_t capacity, ref alloc_ref )

static

Definition at line 101 of file template.h.

                                                                                               {
    DC_ASSUME(capacity > _DC_SWISS_SIMD_PROBE_SIZE);
    DC_ASSUME(DC_MATH_IS_POWER_OF_2(capacity));
    size_t ctrl_capacity = capacity + _DC_SWISS_SIMD_PROBE_SIZE;
 
    _dc_swiss_ctrl* ctrl = (_dc_swiss_ctrl*)NS(ALLOC, allocate_zeroed)(
        alloc_ref, sizeof(_dc_swiss_ctrl) * ctrl_capacity);
    SLOT* slots = (SLOT*)NS(ALLOC, allocate_uninit)(alloc_ref, sizeof(SLOT) * capacity);
 
    for (size_t i = 0; i < capacity; i++) {
        ctrl[i] = DC_SWISS_VAL_EMPTY;
    }
    ctrl[capacity] = DC_SWISS_VAL_SENTINEL;
    for (size_t i = 1; i < _DC_SWISS_SIMD_PROBE_SIZE; i++) {
        ctrl[capacity + i] = ctrl[i - 1]; // currently empty
    }
 
    return (SELF){
        .capacity = capacity,
        .count = 0,
        .tombstones = 0,
        .ctrl = ctrl,
        .slots = slots,
        .alloc_ref = alloc_ref,
        .derive_c_hashmap = dc_gdb_marker_new(),
        .iterator_invalidation_tracker = mutation_tracker_new(),
    };
}

next() [1/2]

DC_PUBLIC KV_PAIR next ( ITER * iter )

static

Definition at line 557 of file template.h.

                                                    {
    mutation_version_check(&iter->version);
 
    _dc_swiss_optional_index index = iter->next_index;
    if (index == _DC_SWISS_NO_INDEX) {
        return (KV_PAIR){
            .key = NULL,
            .value = NULL,
        };
    }
 
    iter->next_index++;
    PRIV(NS(SELF, next_populated_index))(iter->map, &iter->next_index);
    return (KV_PAIR){
        .key = &iter->map->slots[index].key,
        .value = &iter->map->slots[index].value,
    };
}

next() [2/2]

DC_PUBLIC KV_PAIR_CONST next ( ITER_CONST * iter )

static

Definition at line 453 of file template.h.

                                                                      {
    mutation_version_check(&iter->version);
 
    _dc_swiss_optional_index index = iter->next_index;
    if (index == _DC_SWISS_NO_INDEX) {
        return (KV_PAIR_CONST){
            .key = NULL,
            .value = NULL,
        };
    }
 
    iter->next_index++;
    PRIV(NS(SELF, next_populated_index))(iter->map, &iter->next_index);
    return (KV_PAIR_CONST){
        .key = &iter->map->slots[index].key,
        .value = &iter->map->slots[index].value,
    };
}

next_populated_index()

void PRIV next_populated_index ( SELF const * self, _dc_swiss_optional_index * index )

static

Definition at line 413 of file template.h.

                                                                                  {
    size_t i = *index;
    while (i < self->capacity && !_dc_swiss_is_present(self->ctrl[i])) {
        ++i;
    }
    *index = (i == self->capacity) ? _DC_SWISS_NO_INDEX : i;
}

read()

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

static

Definition at line 340 of file template.h.

                                                                        {
    VALUE const* value = NS(SELF, try_read)(self, key);
    DC_ASSERT(value, "Cannot read item {key=%s}", DC_DEBUG(KEY_DEBUG, &key));
    return value;
}

rehash()

void PRIV rehash ( SELF * self, size_t new_capacity )

static

Definition at line 242 of file template.h.

                                                                    {
    INVARIANT_CHECK(self);
 
    // NOTE: This code also works for shrinking the hashmap
    //  - we never expect to do this, so are defensive.
    //  - We do expect to rehash with the same capacity (tombstone cleanup)
    DC_ASSUME(new_capacity >= self->capacity);
    mutation_tracker_mutate(&self->iterator_invalidation_tracker);
 
    SELF new_map = PRIV(NS(SELF, new_with_exact_capacity))(new_capacity, self->alloc_ref);
 
    for (size_t i = 0; i < self->capacity; i++) {
        if (_dc_swiss_is_present(self->ctrl[i])) {
            (void)PRIV(NS(SELF, try_insert_no_extend_capacity))(&new_map, self->slots[i].key,
                                                                self->slots[i].value);
        }
    }
 
    new_map.iterator_invalidation_tracker = self->iterator_invalidation_tracker;
 
    size_t ctrl_capacity = self->capacity + _DC_SWISS_SIMD_PROBE_SIZE;
    NS(ALLOC, deallocate)(self->alloc_ref, self->ctrl, sizeof(_dc_swiss_ctrl) * ctrl_capacity);
    NS(ALLOC, deallocate)(self->alloc_ref, self->slots, sizeof(SLOT) * self->capacity);
 
    *self = new_map;
}

remove()

DC_PUBLIC VALUE remove ( SELF * self, KEY key )

static

Definition at line 396 of file template.h.

                                                             {
    VALUE value;
    DC_ASSERT(NS(SELF, try_remove)(self, key, &value), "Failed to remove item {key=%s}",
              DC_DEBUG(KEY_DEBUG, &key));
    return value;
}

size()

DC_PUBLIC size_t size ( SELF const * self )

static

Definition at line 408 of file template.h.

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

try_insert()

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

static

Definition at line 279 of file template.h.

                                                                               {
    INVARIANT_CHECK(self);
 
    if (self->count >= NS(SELF, max_capacity)) {
        return NULL;
    }
 
    switch (_dc_swiss_heuristic_should_extend(self->tombstones, self->count, self->capacity)) {
    case DC_SWISS_DOUBLE_CAPACITY:
        PRIV(NS(SELF, rehash))(self, self->capacity * 2);
        break;
    case DC_SWISS_CLEANUP_TOMBSONES:
        PRIV(NS(SELF, rehash))(self, self->capacity);
        break;
    case DC_SWISS_DO_NOTHING:
        break;
    }
 
    return PRIV(NS(SELF, try_insert_no_extend_capacity))(self, key, value);
}

try_insert_no_extend_capacity()

VALUE *PRIV try_insert_no_extend_capacity ( SELF * self, KEY key, VALUE value )

static

Definition at line 171 of file template.h.

                                                                                              {
    INVARIANT_CHECK(self);
    DC_ASSUME(self->count + self->tombstones < self->capacity);
    mutation_tracker_mutate(&self->iterator_invalidation_tracker);
 
    const size_t mask = self->capacity - 1;
 
    const size_t hash = KEY_HASH(&key);
    const _dc_swiss_ctrl id = _dc_swiss_ctrl_from_hash(hash);
 
    _dc_swiss_optional_index first_deleted = _DC_SWISS_NO_INDEX;
 
    // `H1` - the bucket starting position
    size_t const start = hash & mask;
 
    for (size_t step = 0;; step += _DC_SWISS_SIMD_PROBE_SIZE) {
        const size_t group_start = (start + step) & mask;
 
        _dc_swiss_ctrl_group const group = _dc_swiss_group_load(&self->ctrl[group_start]);
        _dc_swiss_ctrl_group_bitmask const matches = _dc_swiss_group_match(group, id);
 
        _DC_SWISS_BITMASK_FOR_EACH(matches, group_offset) {
            size_t const index =
                _dc_swiss_group_index_to_slot(group_start, group_offset, self->capacity);
 
            // Sentinel value, skip over it.
            if (index == _DC_SWISS_NO_INDEX)
                continue;
 
            if (KEY_EQ(&self->slots[index].key, &key)) {
                return NULL;
            }
        }
 
        if (first_deleted == _DC_SWISS_NO_INDEX) {
            _dc_swiss_ctrl_group_bitmask const deleted =
                _dc_swiss_group_match(group, DC_SWISS_VAL_DELETED);
            if (deleted != 0) {
                size_t const slot = _dc_swiss_group_index_to_slot(
                    group_start, _dc_swiss_ctrl_group_bitmask_lowest(deleted), self->capacity);
                if (slot != _DC_SWISS_NO_INDEX) {
                    first_deleted = slot;
                }
            }
        }
 
        _dc_swiss_ctrl_group_bitmask const empty = _dc_swiss_group_match(group, DC_SWISS_VAL_EMPTY);
        if (empty != 0) {
            size_t const empty_idx = _dc_swiss_group_index_to_slot(
                group_start, _dc_swiss_ctrl_group_bitmask_lowest(empty), self->capacity);
            DC_ASSUME(empty_idx != _DC_SWISS_NO_INDEX, "Empty value cannot match the sentinel");
 
            bool const has_deleted = first_deleted != _DC_SWISS_NO_INDEX;
            size_t const insert_index = has_deleted ? first_deleted : empty_idx;
 
            if (has_deleted) {
                self->tombstones--;
            }
 
            self->slots[insert_index] = (SLOT){
                .value = value,
                .key = key,
            };
            _dc_swiss_ctrl_set_at(self->ctrl, self->capacity, insert_index, id);
 
            self->count++;
            return &self->slots[insert_index].value;
        }
    }
}

try_read()

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

static

Definition at line 307 of file template.h.

                                                                            {
    const size_t mask = self->capacity - 1;
 
    const size_t hash = KEY_HASH(&key);
    const _dc_swiss_ctrl id = _dc_swiss_ctrl_from_hash(hash);
 
    const size_t start = hash & mask;
 
    for (size_t step = 0;; step += _DC_SWISS_SIMD_PROBE_SIZE) {
        size_t const group_start = (start + step) & mask;
        _dc_swiss_ctrl_group const group = _dc_swiss_group_load(&self->ctrl[group_start]);
        _dc_swiss_ctrl_group_bitmask const matches = _dc_swiss_group_match(group, id);
 
        _DC_SWISS_BITMASK_FOR_EACH(matches, group_offset) {
            size_t const i =
                _dc_swiss_group_index_to_slot(group_start, group_offset, self->capacity);
 
            // Sentinel
            if (i == _DC_SWISS_NO_INDEX)
                continue;
 
            if (KEY_EQ(&self->slots[i].key, &key)) {
                return &self->slots[i].value;
            }
        }
 
        _dc_swiss_ctrl_group_bitmask const empty = _dc_swiss_group_match(group, DC_SWISS_VAL_EMPTY);
        if (empty != 0) {
            return NULL;
        }
    }
}

try_remove()

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

static

Definition at line 357 of file template.h.

                                                                                    {
    INVARIANT_CHECK(self);
    DC_ASSERT(destination != NULL, "Passed NULL destination pointer");
 
    const size_t mask = self->capacity - 1;
    const size_t hash = KEY_HASH(&key);
    const _dc_swiss_ctrl id = _dc_swiss_ctrl_from_hash(hash);
 
    const size_t start = hash & mask;
 
    for (size_t step = 0;; step += _DC_SWISS_SIMD_PROBE_SIZE) {
        const size_t group_start = (start + step) & mask;
 
        _dc_swiss_ctrl_group const group = _dc_swiss_group_load(&self->ctrl[group_start]);
        _dc_swiss_ctrl_group_bitmask const matches = _dc_swiss_group_match(group, id);
 
        _DC_SWISS_BITMASK_FOR_EACH(matches, group_offset) {
            size_t const index =
                _dc_swiss_group_index_to_slot(group_start, group_offset, self->capacity);
 
            if (index == _DC_SWISS_NO_INDEX)
                continue;
 
            if (KEY_EQ(&self->slots[index].key, &key)) {
                *destination = self->slots[index].value;
                _dc_swiss_ctrl_set_at(self->ctrl, self->capacity, index, DC_SWISS_VAL_DELETED);
                self->count--;
                self->tombstones++;
                return true;
            }
        }
 
        _dc_swiss_ctrl_group_bitmask const empty = _dc_swiss_group_match(group, DC_SWISS_VAL_EMPTY);
        if (empty != 0) {
            return false;
        }
    }
}

try_write()

DC_PUBLIC VALUE * try_write ( SELF * self, KEY key )

static

Definition at line 346 of file template.h.

                                                                 {
    INVARIANT_CHECK(self);
    return (VALUE*)NS(SELF, try_read)((SELF const*)self, key);
}

write()

DC_PUBLIC VALUE * write ( SELF * self, KEY key )

static

Definition at line 351 of file template.h.

                                                             {
    VALUE* value = NS(SELF, try_write)(self, key);
    DC_ASSERT(value, "Cannot write item {key=%s}", DC_DEBUG(KEY_DEBUG, &key));
    return value;
}

Variable Documentation

max_capacity

DC_STATIC_CONSTANT size_t max_capacity = _dc_swiss_index_capacity

Definition at line 92 of file template.h.