template.h File Reference

#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/container/vector/dynamic/template.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(NAME, slot_t)
#define	SLOT_VECTOR   NS(NAME, item_vectors)
#define	ITEM   SLOT
#define	ITEM_DELETE   PRIV(NS(SLOT, delete))
#define	ITEM_CLONE   PRIV(NS(SLOT, clone))
#define	ITEM_DEBUG   PRIV(NS(SLOT, debug))
#define	INTERNAL_NAME   SLOT_VECTOR
#define	BUCKET   _dc_ankerl_bucket
#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)

Typedefs
typedef size_t	KEY
typedef KEY	key_t

Functions
static size_t	KEY_HASH (KEY const *key)
static DC_INTERNAL SLOT PRIV	clone (SLOT const *slot)
static DC_INTERNAL void PRIV	debug (SLOT const *slot, dc_debug_fmt fmt, FILE *stream)
static DC_INTERNAL void PRIV	delete (SLOT *slot)
static DC_INTERNAL 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 DC_INTERNAL VALUE *PRIV	try_insert_no_extend_capacity (SELF *self, KEY key, VALUE value)
static DC_INTERNAL 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_INTERNAL bool PRIV	try_find (SELF const *self, KEY const *key, size_t *out_bucket_pos, size_t *out_dense_index)
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 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 = max_index_exclusive

Macro Definition Documentation

BUCKET

#define BUCKET   _dc_ankerl_bucket

Definition at line 127 of file template.h.

INTERNAL_NAME

#define INTERNAL_NAME   SLOT_VECTOR

Definition at line 118 of file template.h.

INVARIANT_CHECK

#define INVARIANT_CHECK

(

self

)

Value:

    DC_ASSUME(self);                                                                               \
    DC_ASSUME(DC_MATH_IS_POWER_OF_2((self)->buckets_capacity));                                    \
    DC_ASSUME((self)->buckets);

Definition at line 143 of file template.h.

#define INVARIANT_CHECK(self)                                                                      \
    DC_ASSUME(self);                                                                               \
    DC_ASSUME(DC_MATH_IS_POWER_OF_2((self)->buckets_capacity));                                    \
    DC_ASSUME((self)->buckets);

ITEM

#define ITEM   SLOT

Definition at line 114 of file template.h.

ITEM_CLONE

#define ITEM_CLONE   PRIV(NS(SLOT, clone))

Definition at line 116 of file template.h.

ITEM_DEBUG

#define ITEM_DEBUG   PRIV(NS(SLOT, debug))

Definition at line 117 of file template.h.

ITEM_DELETE

#define ITEM_DELETE   PRIV(NS(SLOT, delete))

Definition at line 115 of file template.h.

ITER

#define ITER   NS(SELF, iter)

Definition at line 584 of file template.h.

ITER_CONST

#define ITER_CONST   NS(SELF, iter_const)

Definition at line 521 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 17 of file template.h.

KEY_CLONE

#define KEY_CLONE   DC_COPY_CLONE

Definition at line 39 of file template.h.

KEY_DEBUG

#define KEY_DEBUG   DC_DEFAULT_DEBUG

Definition at line 43 of file template.h.

KEY_DELETE

#define KEY_DELETE   DC_NO_DELETE

Definition at line 35 of file template.h.

KEY_EQ

#define KEY_EQ   DC_MEM_EQ

Definition at line 31 of file template.h.

KEY_HASH

#define KEY_HASH   key_hash

Definition at line 26 of file template.h.

KV_PAIR

#define KV_PAIR   NS(ITER, item)

Definition at line 585 of file template.h.

KV_PAIR_CONST

#define KV_PAIR_CONST   NS(ITER_CONST, item)

Definition at line 522 of file template.h.

SLOT

#define SLOT   NS(NAME, slot_t)

Definition at line 75 of file template.h.

SLOT_VECTOR

#define SLOT_VECTOR   NS(NAME, item_vectors)

Definition at line 109 of file template.h.

VALUE

#define VALUE   value_t

Definition at line 53 of file template.h.

VALUE_CLONE

#define VALUE_CLONE   DC_COPY_CLONE

Definition at line 61 of file template.h.

VALUE_DEBUG

#define VALUE_DEBUG   DC_DEFAULT_DEBUG

Definition at line 65 of file template.h.

VALUE_DELETE

#define VALUE_DELETE   DC_NO_DELETE

Definition at line 57 of file template.h.

Typedef Documentation

KEY

typedef size_t KEY

Definition at line 18 of file template.h.

key_t

typedef KEY key_t

Definition at line 68 of file template.h.

Function Documentation

clone() [1/2]

DC_PUBLIC SELF clone ( SELF const * self )

static

Definition at line 174 of file template.h.

                                                        {
    INVARIANT_CHECK(self);
 
    BUCKET* new_buckets = (BUCKET*)NS(ALLOC, allocate_uninit)(
        self->alloc_ref, self->buckets_capacity * sizeof(BUCKET));
    memcpy(new_buckets, self->buckets, self->buckets_capacity * sizeof(BUCKET));
 
    return (SELF){
        .buckets_capacity = self->buckets_capacity,
        .buckets = new_buckets,
        .slots = NS(SLOT_VECTOR, clone)(&self->slots),
        .alloc_ref = self->alloc_ref,
        .derive_c_hashmap = dc_gdb_marker_new(),
    };
}

clone() [2/2]

DC_INTERNAL SLOT PRIV clone ( SLOT const * slot )

static

Definition at line 81 of file template.h.

                                                                {
    return (SLOT){
        .key = KEY_CLONE(&slot->key),
        .value = VALUE_CLONE(&slot->value),
    };
}

DC_TRAIT_MAP()

DC_TRAIT_MAP

(

SELF

)

debug() [1/2]

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

static

Definition at line 563 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, "bucket capacity: %lu,\n", self->buckets_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, "slots: ");
    NS(SLOT_VECTOR, debug)(&self->slots, fmt, stream);
    fprintf(stream, ",\n");
 
    fmt = dc_debug_fmt_scope_end(fmt);
    dc_debug_fmt_print(fmt, stream, "}");
}

debug() [2/2]

DC_INTERNAL void PRIV debug ( SLOT const * slot, dc_debug_fmt fmt, FILE * stream )

static

Definition at line 88 of file template.h.

                                                                                                {
    fprintf(stream, DC_EXPAND_STRING(SLOT) "@%p {\n", slot);
    fmt = dc_debug_fmt_scope_begin(fmt);
 
    dc_debug_fmt_print(fmt, stream, "key: ");
    KEY_DEBUG(&slot->key, fmt, stream);
    fprintf(stream, ",\n");
 
    dc_debug_fmt_print(fmt, stream, "value: ");
    VALUE_DEBUG(&slot->value, fmt, stream);
    fprintf(stream, ",\n");
 
    fmt = dc_debug_fmt_scope_end(fmt);
    dc_debug_fmt_print(fmt, stream, "}");
}

delete() [1/2]

DC_PUBLIC void delete ( SELF * self )

static

Definition at line 514 of file template.h.

                                                   {
    INVARIANT_CHECK(self);
 
    NS(ALLOC, deallocate)(self->alloc_ref, self->buckets, self->buckets_capacity * sizeof(BUCKET));
    NS(SLOT_VECTOR, delete)(&self->slots);
}

delete() [2/2]

DC_INTERNAL void PRIV delete ( SLOT * slot )

static

Definition at line 104 of file template.h.

                                                           {
    KEY_DELETE(&slot->key);
    VALUE_DELETE(&slot->value);
}

delete_entry()

DC_PUBLIC void delete_entry ( SELF * self, KEY key )

static

Definition at line 504 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 614 of file template.h.

                                                        {
    DC_ASSUME(iter);
    return NS(NS(SLOT_VECTOR, iter), empty)(&iter->iter);
}

empty() [2/2]

DC_PUBLIC bool empty ( ITER_CONST const * iter )

static

Definition at line 551 of file template.h.

                                                                    {
    DC_ASSUME(iter);
    return NS(NS(SLOT_VECTOR, iter_const), empty)(&iter->iter);
}

empty_item() [1/2]

DC_PUBLIC bool empty_item ( KV_PAIR const * item )

static

Definition at line 596 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 533 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 307 of file template.h.

                                                                                       {
    INVARIANT_CHECK(self);
 
    const size_t required = _dc_ankerl_buckets_capacity(expected_items);
    if (required <= self->buckets_capacity) {
        return;
    }
 
    PRIV(NS(SELF, rehash))(self, required);
}

get_iter()

DC_PUBLIC ITER get_iter ( SELF * self )

static

Definition at line 619 of file template.h.

                                                     {
    INVARIANT_CHECK(self);
    return (ITER){
        .iter = NS(SLOT_VECTOR, get_iter)(&self->slots),
    };
}

get_iter_const()

DC_PUBLIC ITER_CONST get_iter_const ( SELF const * self )

static

Definition at line 556 of file template.h.

                                                                       {
    INVARIANT_CHECK(self);
    return (ITER_CONST){
        .iter = NS(SLOT_VECTOR, get_iter_const)(&self->slots),
    };
}

insert()

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

static

Definition at line 333 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 27 of file template.h.

{ return *key; }

new()

DC_PUBLIC SELF new ( ref alloc_ref )

static

Definition at line 170 of file template.h.

                                                              {
    return PRIV(NS(SELF, new_with_exact_capacity))(dc_ankerl_initial_items, alloc_ref);
}

new_with_capacity_for()

DC_PUBLIC SELF new_with_capacity_for ( size_t for_items, ref alloc_ref )

static

Definition at line 163 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_ankerl_buckets_capacity(for_items),
                                                   alloc_ref);
}

new_with_exact_capacity()

DC_INTERNAL SELF PRIV new_with_exact_capacity ( size_t capacity, ref alloc_ref )

static

Definition at line 148 of file template.h.

                                                                                          {
    DC_ASSUME(capacity > 0);
    DC_ASSUME(DC_MATH_IS_POWER_OF_2(capacity));
 
    BUCKET* buckets = (BUCKET*)NS(ALLOC, allocate_zeroed)(alloc_ref, capacity * sizeof(BUCKET));
 
    return (SELF){
        .buckets_capacity = capacity,
        .buckets = buckets,
        .slots = NS(SLOT_VECTOR, new_with_capacity)(capacity, alloc_ref),
        .alloc_ref = alloc_ref,
    };
}

next() [1/2]

DC_PUBLIC KV_PAIR next ( ITER * iter )

static

Definition at line 600 of file template.h.

                                                    {
    SLOT* next_item = NS(NS(SLOT_VECTOR, iter), next)(&iter->iter);
    if (!next_item) {
        return (KV_PAIR){
            .key = NULL,
            .value = NULL,
        };
    }
    return (KV_PAIR){
        .key = &next_item->key,
        .value = &next_item->value,
    };
}

next() [2/2]

DC_PUBLIC KV_PAIR_CONST next ( ITER_CONST * iter )

static

Definition at line 537 of file template.h.

                                                                      {
    SLOT const* next_item = NS(NS(SLOT_VECTOR, iter_const), next)(&iter->iter);
    if (!next_item) {
        return (KV_PAIR_CONST){
            .key = NULL,
            .value = NULL,
        };
    }
    return (KV_PAIR_CONST){
        .key = &next_item->key,
        .value = &next_item->value,
    };
}

read()

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

static

Definition at line 391 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()

DC_INTERNAL void PRIV rehash ( SELF * self, size_t new_capacity )

static

Definition at line 260 of file template.h.

                                                                                {
    INVARIANT_CHECK(self);
    DC_ASSUME(DC_MATH_IS_POWER_OF_2(new_capacity));
 
    BUCKET* new_buckets =
        (BUCKET*)NS(ALLOC, allocate_zeroed)(self->alloc_ref, new_capacity * sizeof(BUCKET));
 
    const size_t new_mask = new_capacity - 1;
    const size_t n = NS(SLOT_VECTOR, size)(&self->slots);
 
    for (size_t dense_index = 0; dense_index < n; ++dense_index) {
        SLOT const* slot = NS(SLOT_VECTOR, read)(&self->slots, dense_index);
 
        const size_t hash = KEY_HASH(&slot->key);
        const uint8_t fp = _dc_ankerl_fingerprint_from_hash(hash);
        const size_t desired = hash & new_mask;
 
        BUCKET cur = NS(BUCKET, new)(
            (_dc_ankerl_mdata){
                .fingerprint = fp,
                .dfd = _dc_ankerl_dfd_new(0),
            },
            dense_index);
 
        for (size_t pos = desired;; pos = (pos + 1) & new_mask) {
            BUCKET* b = &new_buckets[pos];
 
            if (!_dc_ankerl_mdata_present(&b->mdata)) {
                *b = cur;
                break;
            }
 
            if (b->mdata.dfd < cur.mdata.dfd) {
                BUCKET tmp = *b;
                *b = cur;
                cur = tmp;
            }
 
            cur.mdata.dfd = _dc_ankerl_dfd_increment(cur.mdata.dfd);
        }
    }
 
    NS(ALLOC, deallocate)(self->alloc_ref, self->buckets, self->buckets_capacity * sizeof(BUCKET));
    self->buckets = new_buckets;
    self->buckets_capacity = new_capacity;
}

remove()

DC_PUBLIC VALUE remove ( SELF * self, KEY key )

static

Definition at line 497 of file template.h.

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

size()

DC_PUBLIC size_t size ( SELF const * self )

static

Definition at line 509 of file template.h.

                                                         {
    INVARIANT_CHECK(self);
    return NS(SLOT_VECTOR, size)(&self->slots);
}

try_find()

DC_INTERNAL bool PRIV try_find ( SELF const * self, KEY const * key, size_t * out_bucket_pos, size_t * out_dense_index )

static

Definition at line 340 of file template.h.

                                                                                                  {
    INVARIANT_CHECK(self);
    DC_ASSUME(key);
    DC_ASSUME(out_bucket_pos);
    DC_ASSUME(out_dense_index);
 
    const size_t mask = self->buckets_capacity - 1;
 
    const size_t hash = KEY_HASH(key);
    const uint8_t fp = _dc_ankerl_fingerprint_from_hash(hash);
    const size_t desired = hash & mask;
 
    _dc_ankerl_dfd dfd = _dc_ankerl_dfd_new(0);
    for (size_t pos = desired;; pos = (pos + 1) & mask) {
        BUCKET const* b = &self->buckets[pos];
 
        if (!_dc_ankerl_mdata_present(&b->mdata)) {
            return false;
        }
 
        // NOTE: capped/saturating dfd: early-out only valid while dfd not saturated.
        if (dfd != _dc_ankerl_dfd_max && b->mdata.dfd < dfd) {
            return false;
        }
 
        if (b->mdata.fingerprint == fp) {
            const size_t di = NS(BUCKET, get_index)(b);
            SLOT const* slot = NS(SLOT_VECTOR, read)(&self->slots, di);
            if (KEY_EQ(&slot->key, key)) {
                *out_bucket_pos = pos;
                *out_dense_index = di;
                return true;
            }
        }
 
        dfd = _dc_ankerl_dfd_increment(dfd);
    }
}

try_insert()

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

static

Definition at line 318 of file template.h.

                                                                               {
    INVARIANT_CHECK(self);
 
    if (NS(SLOT_VECTOR, size)(&self->slots) >= NS(SELF, max_capacity)) {
        return NULL;
    }
 
    const size_t size = NS(SLOT_VECTOR, size)(&self->slots);
    if (size >= self->buckets_capacity) {
        NS(SELF, extend_capacity_for)(self, size * 2);
    }
 
    return PRIV(NS(SELF, try_insert_no_extend_capacity))(self, key, value);
}

try_insert_no_extend_capacity()

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

static

Definition at line 190 of file template.h.

                                                                                     {
    INVARIANT_CHECK(self);
    DC_DEBUG_ASSERT(NS(SLOT_VECTOR, size)(&self->slots) < self->buckets_capacity);
    const size_t mask = self->buckets_capacity - 1;
 
    const size_t hash = KEY_HASH(&key);
    const uint8_t fp = _dc_ankerl_fingerprint_from_hash(hash);
    const size_t desired = hash & mask;
 
    {
        _dc_ankerl_dfd dfd = _dc_ankerl_dfd_new(0);
        for (size_t pos = desired;; pos = (pos + 1) & mask) {
            BUCKET const* b = &self->buckets[pos];
 
            if (!_dc_ankerl_mdata_present(&b->mdata)) {
                break;
            }
 
            // JUSTIFY: Checking for the maximum DFD
            //  - dfd (distance-from-desired) uses saturating arithmetic.
            //  - Once dfd reaches dc_ankerl_dfd_max it no longer encodes a strict ordering,
            //    so the usual Robin Hood early-out (b->dfd < dfd) is only valid while dfd
            //    is not saturated. After saturation we must continue probing until EMPTY.
            if (dfd != _dc_ankerl_dfd_max && b->mdata.dfd < dfd) {
                break;
            }
 
            if (b->mdata.fingerprint == fp) {
                const size_t di = NS(BUCKET, get_index)(b);
                SLOT const* slot = NS(SLOT_VECTOR, read)(&self->slots, di);
                if (KEY_EQ(&slot->key, &key)) {
                    return NULL;
                }
            }
 
            dfd = _dc_ankerl_dfd_increment(dfd);
        }
    }
 
    const size_t dense_index = NS(SLOT_VECTOR, size)(&self->slots);
    NS(SLOT_VECTOR, push)(&self->slots, (SLOT){
                                            .key = key,
                                            .value = value,
                                        });
    BUCKET cur = NS(BUCKET, new)(
        (_dc_ankerl_mdata){
            .fingerprint = fp,
            .dfd = _dc_ankerl_dfd_new(0),
        },
        dense_index);
 
    for (size_t pos = desired;; pos = (pos + 1) & mask) {
        BUCKET* b = &self->buckets[pos];
 
        if (!_dc_ankerl_mdata_present(&b->mdata)) {
            *b = cur;
            return &NS(SLOT_VECTOR, write)(&self->slots, dense_index)->value;
        }
 
        if (b->mdata.dfd < cur.mdata.dfd) {
            BUCKET tmp = *b;
            *b = cur;
            cur = tmp;
        }
 
        cur.mdata.dfd = _dc_ankerl_dfd_increment(cur.mdata.dfd);
    }
}

try_read()

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

static

Definition at line 380 of file template.h.

                                                                            {
    INVARIANT_CHECK(self);
    size_t pos;
    size_t di;
    if (!PRIV(NS(SELF, try_find))(self, &key, &pos, &di)) {
        return NULL;
    }
 
    return &NS(SLOT_VECTOR, read)(&self->slots, di)->value;
}

try_remove()

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

static

Definition at line 408 of file template.h.

                                                                                    {
    INVARIANT_CHECK(self);
 
    size_t found_pos;
    size_t removed_dense_index;
    if (!PRIV(NS(SELF, try_find))((SELF const*)self, &key, &found_pos, &removed_dense_index)) {
        return false; // unchanged
    }
 
    const size_t mask = self->buckets_capacity - 1;
 
    // Move out value (or delete if destination is NULL) and delete key.
    {
        SLOT* slot = NS(SLOT_VECTOR, write)(&self->slots, removed_dense_index);
 
        if (destination) {
            *destination = slot->value;
        } else {
            VALUE_DELETE(&slot->value);
        }
 
        KEY_DELETE(&slot->key);
    }
 
    // Backshift delete from buckets starting at found_pos.
    {
        size_t hole = found_pos;
 
        for (;;) {
            const size_t next = (hole + 1) & mask;
            BUCKET* nb = &self->buckets[next];
 
            if (!_dc_ankerl_mdata_present(&nb->mdata) || nb->mdata.dfd == _dc_ankerl_dfd_new(0)) {
                self->buckets[hole].mdata.dfd = _dc_ankerl_dfd_none;
                break;
            }
 
            self->buckets[hole] = *nb;
            self->buckets[hole].mdata.dfd =
                _dc_ankerl_dfd_decrement_for_backshift(self->buckets[hole].mdata.dfd);
            hole = next;
        }
    }
 
    // Dense swap-remove + update moved element’s bucket (if swap occurred).
    {
        const size_t size = NS(SLOT_VECTOR, size)(&self->slots);
        const size_t last = size - 1;
 
        if (removed_dense_index != last) {
            SLOT* dst = NS(SLOT_VECTOR, write)(&self->slots, removed_dense_index);
            SLOT* src = NS(SLOT_VECTOR, write)(&self->slots, last);
            *dst = *src;
 
            // Find moved key's bucket and patch its dense index to removed_dense_index.
            // (One extra probe only when we swapped.)
            const size_t moved_hash = KEY_HASH(&dst->key);
            const uint8_t moved_fp = _dc_ankerl_fingerprint_from_hash(moved_hash);
            const size_t desired = moved_hash & mask;
 
            _dc_ankerl_dfd dfd = _dc_ankerl_dfd_new(0);
            for (size_t pos = desired;; pos = (pos + 1) & mask) {
                BUCKET* b = &self->buckets[pos];
 
                DC_DEBUG_ASSERT(_dc_ankerl_mdata_present(&b->mdata));
 
                if (dfd != _dc_ankerl_dfd_max && b->mdata.dfd < dfd) {
                    DC_UNREACHABLE();
                }
 
                if (b->mdata.fingerprint == moved_fp) {
                    const size_t di = NS(BUCKET, get_index)(b);
                    SLOT const* slot = NS(SLOT_VECTOR, read)(&self->slots, di);
                    if (KEY_EQ(&slot->key, &dst->key)) {
                        *b = NS(BUCKET, new)(b->mdata, removed_dense_index);
                        break;
                    }
                }
 
                dfd = _dc_ankerl_dfd_increment(dfd);
            }
        }
 
        (void)NS(SLOT_VECTOR, pop)(&self->slots);
    }
 
    return true;
}

try_write()

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

static

Definition at line 397 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 402 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 = max_index_exclusive

Definition at line 130 of file template.h.