template.h File Reference

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <derive-c/core.h>
#include <derive-c/panic.h>
#include <derive-c/self.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	INDEX
struct	SLOT
struct	SELF
struct	IV_PAIR
struct	IV_PAIR_CONST

Macros
#define	INDEX_BITS   32
	A vector-backed arena, with support for small indices.
#define	V   derive_c_parameter_value
#define	V_DELETE   derive_c_parameter_value_delete
#define	SLOT   NAME(SELF, SLOT)
#define	CHECK_ACCESS_INDEX(self, index)
#define	RESIZE_FACTOR   2
#define	INDEX   NAME(SELF, index)
#define	IV_PAIR   NAME(SELF, iv)
#define	IV_PAIR_CONST   NAME(SELF, iv_const)

Functions
static SELF	new_with_capacity_for (INDEX_TYPE items)
static INDEX	insert (SELF *self, V value)
static V *	try_write (SELF *self, INDEX index)
static V *	write (SELF *self, INDEX index)
static V const *	try_read (SELF const *self, INDEX index)
static V const *	read (SELF const *self, INDEX index)
static SELF	shallow_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, V *destination)
static V	remove (SELF *self, INDEX index)
static bool	delete_entry (SELF *self, INDEX index)
static bool	empty (ITER const *iter)
static IV_PAIR	next (ITER *iter)
static size_t	position (ITER const *iter)
static ITER	get_iter (SELF *self)
static void	delete (SELF *self)
static bool	empty (ITER_CONST const *iter)
static IV_PAIR_CONST	next (ITER_CONST *iter)
static size_t	position (ITER_CONST const *iter)
static ITER_CONST	get_iter_const (SELF const *self)

Variables
static size_t	max_capacity = MAX_CAPACITY
static size_t	max_index = MAX_INDEX
static IV_PAIR	iv_empty
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 57 of file template.h.

INDEX

#define INDEX   NAME(SELF, index)

Definition at line 64 of file template.h.

INDEX_BITS

#define INDEX_BITS   32

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

Definition at line 15 of file template.h.

IV_PAIR

#define IV_PAIR   NAME(SELF, iv)

Definition at line 255 of file template.h.

IV_PAIR_CONST

#define IV_PAIR_CONST   NAME(SELF, iv_const)

Definition at line 335 of file template.h.

RESIZE_FACTOR

#define RESIZE_FACTOR   2

Definition at line 61 of file template.h.

SLOT

#define SLOT   NAME(SELF, SLOT)

Definition at line 55 of file template.h.

V

#define V   derive_c_parameter_value

Definition at line 23 of file template.h.

V_DELETE

#define V_DELETE   derive_c_parameter_value_delete

Definition at line 25 of file template.h.

Function Documentation

delete()

static void delete ( SELF * self )

static

Definition at line 319 of file template.h.

                                           {
    DEBUG_ASSERT(self);
    ITER iter = NAME(SELF, get_iter)(self);
    while (!NAME(ITER, empty)(&iter)) {
        IV_PAIR pair = NAME(ITER, next)(&iter);
        if (pair.value) {
            V_DELETE(pair.value);
        }
    }
 
    free(self->slots);
}

Here is the call graph for this function:

delete_entry()

static bool delete_entry ( SELF * self, INDEX index )

static

Definition at line 237 of file template.h.

                                                              {
    DEBUG_ASSERT(self);
    if (!CHECK_ACCESS_INDEX(self, index)) {
        return false;
    }
 
    SLOT* entry = &self->slots[index.index];
    if (entry->present) {
        V_DELETE(&entry->value);
        entry->present = false;
        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]

static bool empty ( ITER const * iter )

static

Definition at line 273 of file template.h.

                                                {
    DEBUG_ASSERT(iter);
    // 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]

static bool empty ( ITER_CONST const * iter )

static

Definition at line 353 of file template.h.

                                                            {
    DEBUG_ASSERT(iter);
    return iter->next_index == INDEX_NONE || iter->next_index >= iter->arena->exclusive_end;
}

Here is the call graph for this function:

full()

static bool full ( SELF const * self )

static

Definition at line 199 of file template.h.

                                               {
    DEBUG_ASSERT(self);
    if (self->capacity == MAX_CAPACITY) {
        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()

static ITER get_iter ( SELF * self )

static

Definition at line 305 of file template.h.

                                             {
    DEBUG_ASSERT(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,
        .pos = 0,
    };
}

Here is the call graph for this function:

Here is the caller graph for this function:

get_iter_const()

static ITER_CONST get_iter_const ( SELF const * self )

static

Definition at line 382 of file template.h.

                                                               {
    DEBUG_ASSERT(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,
        .pos = 0,
    };
}

Here is the call graph for this function:

Here is the caller graph for this function:

insert()

static INDEX insert ( SELF * self, V value )

static

Definition at line 114 of file template.h.

                                                     {
    DEBUG_ASSERT(self);
    if (self->free_list != INDEX_NONE) {
        INDEX_TYPE free_index = self->free_list;
        SLOT* slot = &self->slots[free_index];
        DEBUG_ASSERT(!SLOT->present);
        self->free_list = slot->next_free;
        slot->present = true;
        slot->value = value;
        self->count++;
        return (INDEX){.index = free_index};
    }
 
    if (self->exclusive_end == self->capacity) {
        ASSERT(self->capacity <= (MAX_CAPACITY / RESIZE_FACTOR));
        self->capacity *= RESIZE_FACTOR;
        SLOT* new_alloc = (SLOT*)realloc(self->slots, self->capacity * sizeof(SLOT));
        ASSERT(new_alloc);
        self->slots = new_alloc;
    }
 
    INDEX_TYPE new_index = self->exclusive_end;
    SLOT* slot = &self->slots[new_index];
    slot->present = true;
    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:

new_with_capacity_for()

static SELF new_with_capacity_for ( INDEX_TYPE items )

static

Definition at line 99 of file template.h.

                                                                {
    DEBUG_ASSERT(items > 0);
    size_t capacity = next_power_of_2(items);
    ASSERT(capacity <= MAX_CAPACITY);
    SLOT* slots = (SLOT*)calloc(capacity, sizeof(SLOT));
    ASSERT(slots);
    return (SELF){
        .slots = slots,
        .capacity = (INDEX_TYPE)capacity,
        .free_list = INDEX_NONE,
        .exclusive_end = 0,
        .count = 0,
    };
}

Here is the call graph for this function:

Here is the caller graph for this function:

next() [1/2]

static IV_PAIR next ( ITER * iter )

static

Definition at line 281 of file template.h.

                                            {
    DEBUG_ASSERT(iter);
 
    if (NAME(ITER, empty)(iter)) {
        return (IV_PAIR){.index = (INDEX){.index = INDEX_NONE}, .value = NULL};
    } else {
        IV_PAIR out = (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++;
        }
 
        iter->pos++;
        return out;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

next() [2/2]

static IV_PAIR_CONST next ( ITER_CONST * iter )

static

Definition at line 358 of file template.h.

                                                              {
    DEBUG_ASSERT(iter);
 
    if (NAME(ITER_CONST, empty)(iter)) {
        return (IV_PAIR_CONST){.index = (INDEX){.index = INDEX_NONE}, .value = NULL};
    } else {
        IV_PAIR_CONST out = (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++;
        }
 
        iter->pos++;
        return out;
    }
}

Here is the call graph for this function:

position() [1/2]

static size_t position ( ITER const * iter )

static

Definition at line 300 of file template.h.

                                                     {
    DEBUG_ASSERT(iter);
    return iter->pos;
}

Here is the call graph for this function:

Here is the caller graph for this function:

position() [2/2]

static size_t position ( ITER_CONST const * iter )

static

Definition at line 377 of file template.h.

                                                                 {
    DEBUG_ASSERT(iter);
    return iter->pos;
}

Here is the call graph for this function:

read()

static V const * read ( SELF const * self, INDEX index )

static

Definition at line 174 of file template.h.

                                                                {
    V const* value = NAME(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()

static V remove ( SELF * self, INDEX index )

static

Definition at line 231 of file template.h.

                                                     {
    V value;
    ASSERT(NAME(SELF, try_remove)(self, index, &value));
    return value;
}

Here is the call graph for this function:

Here is the caller graph for this function:

shallow_clone()

static SELF shallow_clone ( SELF const * self )

static

Definition at line 180 of file template.h.

                                                        {
    DEBUG_ASSERT(self);
    SLOT* slots = (SLOT*)malloc(self->capacity * sizeof(SLOT));
    ASSERT(slots);
    memcpy(slots, self->slots, self->exclusive_end * sizeof(SLOT));
    return (SELF){
        .slots = slots,
        .capacity = self->capacity,
        .free_list = self->free_list,
        .exclusive_end = self->exclusive_end,
        .count = self->count,
    };
}

Here is the call graph for this function:

Here is the caller graph for this function:

size()

static INDEX_TYPE size ( SELF const * self )

static

Definition at line 194 of file template.h.

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

Here is the call graph for this function:

Here is the caller graph for this function:

try_read()

static V const * try_read ( SELF const * self, INDEX index )

static

Definition at line 162 of file template.h.

                                                                    {
    DEBUG_ASSERT(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()

static bool try_remove ( SELF * self, INDEX index, V * destination )

static

Definition at line 212 of file template.h.

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

Here is the call graph for this function:

Here is the caller graph for this function:

try_write()

static V * try_write ( SELF * self, INDEX index )

static

Definition at line 144 of file template.h.

                                                         {
    DEBUG_ASSERT(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:

write()

static V * write ( SELF * self, INDEX index )

static

Definition at line 156 of file template.h.

                                                     {
    V* value = NAME(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 341 of file template.h.

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

iv_empty

IV_PAIR iv_empty

static

Initial value:

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

Definition at line 261 of file template.h.

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

max_capacity

size_t max_capacity = MAX_CAPACITY

static

Definition at line 209 of file template.h.

max_index

size_t max_index = MAX_INDEX

static

Definition at line 210 of file template.h.