template.h File Reference

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <derive-c/container/arena/trait.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/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	INDEX
struct	SLOT
struct	SELF
	An allocator that prints to stdout when it allocates or frees memory. More...
struct	IV_PAIR
struct	IV_PAIR_CONST

Macros
#define	INDEX_BITS   32
	A vector-backed arena, with support for small indices.
#define	VALUE   value_t
#define	VALUE_DELETE   value_delete
#define	VALUE_CLONE   value_clone
#define	SLOT   NS(SELF, slot)
#define	CHECK_ACCESS_INDEX(self, index)
#define	RESIZE_FACTOR   2
#define	INDEX   NS(SELF, index_t)
#define	INVARIANT_CHECK(self)
#define	IV_PAIR   NS(SELF, iv)
#define	IV_PAIR_CONST   NS(SELF, iv_const)

Typedefs
typedef VALUE	value_t
typedef ALLOC	alloc_t
typedef IV_PAIR const *	item

Functions
static void	value_delete (value_t *self)
static value_t	value_clone (value_t const *self)
	STATIC_ASSERT (sizeof(VALUE), "VALUE must be a non-zero sized type")
static void	memory_tracker_empty (SLOT const *slot)
static void	memory_tracker_present (SLOT const *slot)
static SELF	new_with_capacity_for (INDEX_TYPE items, ALLOC *alloc)
static INDEX	insert (SELF *self, VALUE value)
static VALUE *	try_write (SELF *self, INDEX index)
static VALUE *	write (SELF *self, INDEX index)
static VALUE const *	try_read (SELF const *self, INDEX index)
static VALUE const *	read (SELF const *self, INDEX index)
static SELF	clone (SELF const *self)
static INDEX_TYPE	size (SELF const *self)
static bool	full (SELF const *self)
static bool	try_remove (SELF *self, INDEX index, VALUE *destination)
static VALUE	remove (SELF *self, INDEX index)
static bool	delete_entry (SELF *self, INDEX index)
static bool	empty_item (IV_PAIR const *const *item)
static bool	empty (ITER const *iter)
static IV_PAIR const *	next (ITER *iter)
static ITER	get_iter (SELF *self)
static void	delete (SELF *self)
static bool	empty_item (IV_PAIR_CONST const *const *item)
static bool	empty (ITER_CONST const *iter)
static IV_PAIR_CONST const *	next (ITER_CONST *iter)
static ITER_CONST	get_iter_const (SELF const *self)
	TRAIT_ARENA (SELF)

Variables
static size_t	max_entries = MAX_INDEX
static IV_PAIR_CONST	iv_const_empty

Macro Definition Documentation

CHECK_ACCESS_INDEX

#define CHECK_ACCESS_INDEX	(		self,
			index )

Value:

((index).index < (self)->exclusive_end)

Definition at line 75 of file template.h.

INDEX

#define INDEX   NS(SELF, index_t)

Definition at line 82 of file template.h.

INDEX_BITS

#define INDEX_BITS   32

A vector-backed arena, with support for small indices.

Definition at line 23 of file template.h.

INVARIANT_CHECK

#define INVARIANT_CHECK

(

self

)

Value:

    ASSUME(self);                                                                                  \
    ASSUME((self)->count <= (self)->capacity);                                                     \
    ASSUME((self)->exclusive_end >= (self)->count);                                                \
    ASSUME((self)->count <= MAX_INDEX);

Definition at line 142 of file template.h.

#define INVARIANT_CHECK(self)                                                                      \
    ASSUME(self);                                                                                  \
    ASSUME((self)->count <= (self)->capacity);                                                     \
    ASSUME((self)->exclusive_end >= (self)->count);                                                \
    ASSUME((self)->count <= MAX_INDEX);

IV_PAIR

#define IV_PAIR   NS(SELF, iv)

Definition at line 343 of file template.h.

IV_PAIR_CONST

#define IV_PAIR_CONST   NS(SELF, iv_const)

Definition at line 417 of file template.h.

RESIZE_FACTOR

#define RESIZE_FACTOR   2

Definition at line 79 of file template.h.

SLOT

#define SLOT   NS(SELF, slot)

Definition at line 73 of file template.h.

VALUE

#define VALUE   value_t

Definition at line 33 of file template.h.

VALUE_CLONE

#define VALUE_CLONE   value_clone

Definition at line 37 of file template.h.

VALUE_DELETE

#define VALUE_DELETE   value_delete

Definition at line 35 of file template.h.

Typedef Documentation

alloc_t

typedef ALLOC alloc_t

Definition at line 85 of file template.h.

item

typedef ITEM const * item

Examples

container/vector/dynamic.c, and container/vector/static.c.

Definition at line 350 of file template.h.

value_t

typedef VALUE value_t

Definition at line 84 of file template.h.

Function Documentation

clone()

SELF clone ( SELF const * self )

static

Definition at line 246 of file template.h.

                                              {
    INVARIANT_CHECK(self);
    SLOT* slots = (SLOT*)NS(ALLOC, calloc)(self->alloc, self->capacity, sizeof(SLOT));
    ASSERT(slots);
 
    for (INDEX_TYPE index = 0; index < self->exclusive_end; index++) {
        if (self->slots[index].present) {
            NS(SLOT, memory_tracker_present)(&slots[index]);
            slots[index].present = true;
            slots[index].value = VALUE_CLONE(&self->slots[index].value);
        } else {
            NS(SLOT, memory_tracker_empty)(&slots[index]);
            slots[index].present = false;
            slots[index].next_free = self->slots[index].next_free;
        }
    }
 
    return (SELF){
        .slots = slots,
        .capacity = self->capacity,
        .free_list = self->free_list,
        .exclusive_end = self->exclusive_end,
        .count = self->count,
        .alloc = self->alloc,
        .derive_c_arena_basic = gdb_marker_new(),
        .iterator_invalidation_tracker = mutation_tracker_new(),
    };
}

Here is the call graph for this function:

Here is the caller graph for this function:

delete()

void delete ( SELF * self )

static

Definition at line 403 of file template.h.

                                         {
    INVARIANT_CHECK(self);
    ITER iter = NS(SELF, get_iter)(self);
    IV_PAIR const* entry;
    while ((entry = NS(ITER, next)(&iter))) {
        VALUE_DELETE(entry->value);
    }
 
    NS(ALLOC, free)(self->alloc, self->slots);
}

Here is the call graph for this function:

delete_entry()

bool delete_entry ( SELF * self, INDEX index )

static

Definition at line 322 of file template.h.

                                                            {
    INVARIANT_CHECK(self);
    mutation_tracker_mutate(&self->iterator_invalidation_tracker);
 
    if (!CHECK_ACCESS_INDEX(self, index)) {
        return false;
    }
 
    SLOT* entry = &self->slots[index.index];
    if (entry->present) {
        VALUE_DELETE(&entry->value);
        entry->present = false;
        NS(SLOT, memory_tracker_empty)(entry);
        entry->next_free = self->free_list;
        self->free_list = index.index;
        self->count--;
        return true;
    }
    return false;
}

Here is the call graph for this function:

Here is the caller graph for this function:

empty() [1/2]

bool empty ( ITER const * iter )

static

Definition at line 361 of file template.h.

                                              {
    ASSUME(iter);
    mutation_version_check(&iter->version);
    // JUSTIFY: If no entries are left, then the previous '.._next' call moved
    //          the index to the exclusive end
    // NOTE: `index + 1 > exclusive_end` implies `index >= exclusive_end`
    return iter->next_index == INDEX_NONE || iter->next_index >= iter->arena->exclusive_end;
}

Here is the call graph for this function:

Here is the caller graph for this function:

empty() [2/2]

bool empty ( ITER_CONST const * iter )

static

Definition at line 440 of file template.h.

                                                          {
    ASSUME(iter);
    mutation_version_check(&iter->version);
    return iter->next_index == INDEX_NONE || iter->next_index >= iter->arena->exclusive_end;
}

Here is the call graph for this function:

empty_item() [1/2]

bool empty_item ( IV_PAIR const *const * item )

static

Definition at line 352 of file template.h.

{ return *item == NULL; }

Here is the call graph for this function:

Here is the caller graph for this function:

empty_item() [2/2]

bool empty_item ( IV_PAIR_CONST const *const * item )

static

Definition at line 431 of file template.h.

{ return *item == NULL; }

Here is the call graph for this function:

full()

bool full ( SELF const * self )

static

Definition at line 280 of file template.h.

                                             {
    INVARIANT_CHECK(self);
    if (self->capacity == CAPACITY_EXCLUSIVE_UPPER) {
        if (self->free_list == INDEX_NONE) {
            return true;
        }
    }
    return false;
}

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 388 of file template.h.

                                           {
    INVARIANT_CHECK(self);
    INDEX_TYPE index = 0;
    while (index < INDEX_NONE && index < self->exclusive_end && !self->slots[index].present) {
        index++;
    }
 
    return (ITER){
        .arena = self,
        .next_index = index,
        .curr = (IV_PAIR){.index = (INDEX){.index = INDEX_NONE}, .value = NULL},
        .version = mutation_tracker_get(&self->iterator_invalidation_tracker),
    };
}

Here is the call graph for this function:

Here is the caller graph for this function:

get_iter_const()

ITER_CONST get_iter_const ( SELF const * self )

static

Definition at line 465 of file template.h.

                                                             {
    INVARIANT_CHECK(self);
    INDEX_TYPE index = 0;
    while (index < INDEX_NONE && index < self->exclusive_end && !self->slots[index].present) {
        index++;
    }
 
    return (ITER_CONST){
        .arena = self,
        .next_index = index,
        .curr = (IV_PAIR_CONST){.index = (INDEX){.index = INDEX_NONE}, .value = NULL},
        .version = mutation_tracker_get(&self->iterator_invalidation_tracker),
    };
}

Here is the call graph for this function:

Here is the caller graph for this function:

insert()

INDEX insert ( SELF * self, VALUE value )

static

Definition at line 171 of file template.h.

                                                       {
    INVARIANT_CHECK(self);
    ASSERT(self->count < MAX_INDEX);
 
    mutation_tracker_mutate(&self->iterator_invalidation_tracker);
    if (self->free_list != INDEX_NONE) {
        INDEX_TYPE free_index = self->free_list;
        SLOT* slot = &self->slots[free_index];
        ASSUME(!slot->present);
        self->free_list = slot->next_free;
        slot->present = true;
        NS(SLOT, memory_tracker_present)(slot);
        slot->value = value;
        self->count++;
        return (INDEX){.index = free_index};
    }
 
    if (self->exclusive_end == self->capacity) {
        ASSERT(self->capacity <= (CAPACITY_EXCLUSIVE_UPPER / RESIZE_FACTOR));
        self->capacity *= RESIZE_FACTOR;
        SLOT* new_alloc = (SLOT*)realloc(self->slots, self->capacity * sizeof(SLOT));
        ASSERT(new_alloc);
        self->slots = new_alloc;
 
        for (size_t index = self->exclusive_end; index < self->capacity; index++) {
            NS(SLOT, memory_tracker_empty)(&self->slots[index]);
        }
    }
 
    INDEX_TYPE new_index = self->exclusive_end;
    SLOT* slot = &self->slots[new_index];
    slot->present = true;
    NS(SLOT, memory_tracker_present)(slot);
    slot->value = value;
    self->count++;
    self->exclusive_end++;
    return (INDEX){.index = new_index};
}

Here is the call graph for this function:

Here is the caller graph for this function:

memory_tracker_empty()

void memory_tracker_empty ( SLOT const * slot )

static

Definition at line 104 of file template.h.

                                                             {
    memory_tracker_set(MEMORY_TRACKER_LVL_CONTAINER, MEMORY_TRACKER_CAP_NONE, &slot->value,
                       sizeof(VALUE));
    memory_tracker_set(MEMORY_TRACKER_LVL_CONTAINER, MEMORY_TRACKER_CAP_WRITE, &slot->next_free,
                       sizeof(INDEX_TYPE));
    memory_tracker_set(MEMORY_TRACKER_LVL_CONTAINER, MEMORY_TRACKER_CAP_READ_WRITE, &slot->present,
                       sizeof(bool));
}

Here is the call graph for this function:

Here is the caller graph for this function:

memory_tracker_present()

void memory_tracker_present ( SLOT const * slot )

static

Definition at line 113 of file template.h.

                                                               {
    memory_tracker_set(MEMORY_TRACKER_LVL_CONTAINER, MEMORY_TRACKER_CAP_NONE, &slot->next_free,
                       sizeof(INDEX_TYPE));
    memory_tracker_set(MEMORY_TRACKER_LVL_CONTAINER, MEMORY_TRACKER_CAP_WRITE, &slot->value,
                       sizeof(VALUE));
    memory_tracker_set(MEMORY_TRACKER_LVL_CONTAINER, MEMORY_TRACKER_CAP_READ_WRITE, &slot->present,
                       sizeof(bool));
}

Here is the call graph for this function:

Here is the caller graph for this function:

new_with_capacity_for()

SELF new_with_capacity_for ( INDEX_TYPE items, ALLOC * alloc )

static

Definition at line 148 of file template.h.

                                                                            {
    ASSERT(items > 0);
    size_t capacity = next_power_of_2(items);
    ASSERT(capacity <= CAPACITY_EXCLUSIVE_UPPER);
    SLOT* slots = (SLOT*)NS(ALLOC, calloc)(alloc, capacity, sizeof(SLOT));
    ASSERT(slots);
 
    for (INDEX_TYPE index = 0; index < capacity; index++) {
        NS(SLOT, memory_tracker_empty)(&slots[index]);
    }
 
    return (SELF){
        .slots = slots,
        .capacity = (INDEX_TYPE)capacity,
        .free_list = INDEX_NONE,
        .exclusive_end = 0,
        .count = 0,
        .alloc = alloc,
        .derive_c_arena_basic = gdb_marker_new(),
        .iterator_invalidation_tracker = mutation_tracker_new(),
    };
}

Here is the call graph for this function:

Here is the caller graph for this function:

next() [1/2]

IV_PAIR const * next ( ITER * iter )

static

Definition at line 370 of file template.h.

                                                 {
    ASSUME(iter);
    mutation_version_check(&iter->version);
 
    if (NS(ITER, empty)(iter)) {
        return NULL;
    }
    iter->curr = (IV_PAIR){.index = (INDEX){.index = iter->next_index},
                           .value = &iter->arena->slots[iter->next_index].value};
    iter->next_index++;
    while (iter->next_index < INDEX_NONE && iter->next_index < iter->arena->exclusive_end &&
           !iter->arena->slots[iter->next_index].present) {
        iter->next_index++;
    }
 
    return &iter->curr;
}

Here is the call graph for this function:

Here is the caller graph for this function:

next() [2/2]

IV_PAIR_CONST const * next ( ITER_CONST * iter )

static

Definition at line 446 of file template.h.

                                                                   {
    ASSUME(iter);
    mutation_version_check(&iter->version);
 
    if (NS(ITER_CONST, empty)(iter)) {
        return NULL;
    }
 
    iter->curr = (IV_PAIR_CONST){.index = (INDEX){.index = iter->next_index},
                                 .value = &iter->arena->slots[iter->next_index].value};
    iter->next_index++;
    while (iter->next_index != INDEX_NONE && iter->next_index < iter->arena->exclusive_end &&
           !iter->arena->slots[iter->next_index].present) {
        iter->next_index++;
    }
 
    return &iter->curr;
}

Here is the call graph for this function:

read()

VALUE const * read ( SELF const * self, INDEX index )

static

Definition at line 240 of file template.h.

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

Here is the call graph for this function:

Here is the caller graph for this function:

remove()

VALUE remove ( SELF * self, INDEX index )

static

Definition at line 313 of file template.h.

                                                       {
    INVARIANT_CHECK(self);
    mutation_tracker_mutate(&self->iterator_invalidation_tracker);
 
    VALUE value;
    ASSERT(NS(SELF, try_remove)(self, index, &value));
    return value;
}

Here is the call graph for this function:

Here is the caller graph for this function:

size()

INDEX_TYPE size ( SELF const * self )

static

Examples

complex/prime_sieve.c.

Definition at line 275 of file template.h.

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

Here is the call graph for this function:

Here is the caller graph for this function:

STATIC_ASSERT()

STATIC_ASSERT	(	sizeof(VALUE)	,
		"VALUE must be a non-zero sized type"	)

TRAIT_ARENA()

TRAIT_ARENA

(

SELF

)

try_read()

VALUE const * try_read ( SELF const * self, INDEX index )

static

Definition at line 228 of file template.h.

                                                                      {
    INVARIANT_CHECK(self);
    if (!CHECK_ACCESS_INDEX(self, index)) {
        return NULL;
    }
    SLOT* slot = &self->slots[index.index];
    if (!slot->present) {
        return NULL;
    }
    return &slot->value;
}

Here is the call graph for this function:

Here is the caller graph for this function:

try_remove()

bool try_remove ( SELF * self, INDEX index, VALUE * destination )

static

Definition at line 292 of file template.h.

                                                                              {
    INVARIANT_CHECK(self);
    mutation_tracker_mutate(&self->iterator_invalidation_tracker);
 
    if (!CHECK_ACCESS_INDEX(self, index)) {
        return false;
    }
 
    SLOT* entry = &self->slots[index.index];
    if (entry->present) {
        *destination = entry->value;
        entry->present = false;
        NS(SLOT, memory_tracker_empty)(entry);
        entry->next_free = self->free_list;
        self->free_list = index.index;
        self->count--;
        return true;
    }
    return false;
}

Here is the call graph for this function:

Here is the caller graph for this function:

try_write()

VALUE * try_write ( SELF * self, INDEX index )

static

Definition at line 210 of file template.h.

                                                           {
    INVARIANT_CHECK(self);
    if (!CHECK_ACCESS_INDEX(self, index)) {
        return NULL;
    }
    SLOT* slot = &self->slots[index.index];
    if (!slot->present) {
        return NULL;
    }
    return &slot->value;
}

Here is the call graph for this function:

Here is the caller graph for this function:

value_clone()

value_t value_clone ( value_t const * self )

static

Definition at line 36 of file template.h.

{ return *self; }

value_delete()

void value_delete ( value_t * self )

static

Definition at line 34 of file template.h.

{ (void)self; }

write()

VALUE * write ( SELF * self, INDEX index )

static

Definition at line 222 of file template.h.

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

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

iv_const_empty

IV_PAIR_CONST iv_const_empty

static

Initial value:

= {
    .index = {.index = INDEX_NONE},
    .value = NULL,
}

Definition at line 423 of file template.h.

                                                {
    .index = {.index = INDEX_NONE},
    .value = NULL,
};

max_entries

size_t max_entries = MAX_INDEX

static

Definition at line 290 of file template.h.