template.h File Reference

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <derive-c/container/vector/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	item_t
	A queue comprised of an extendable circular buffer. More...
struct	SELF
	An allocator that prints to stdout when it allocates or frees memory. More...

Macros
#define	ITEM   item_t
#define	ITEM_DELETE   item_delete
#define	ITEM_CLONE   item_clone
#define	INVARIANT_CHECK(self)

Typedefs
typedef size_t	index_t
typedef ITEM *	item

Functions
static void	item_delete (item_t *t)
static item_t	item_clone (item_t const *i)
static SELF	new (ALLOC *alloc)
static SELF	new_with_capacity (size_t capacity, ALLOC *alloc)
static SELF	new_with_defaults (size_t size, ITEM default_item, ALLOC *alloc)
static void	reserve (SELF *self, size_t new_capacity)
static SELF	clone (SELF const *self)
static ITEM const *	try_read (SELF const *self, size_t index)
static ITEM const *	read (SELF const *self, size_t index)
static ITEM *	try_write (SELF *self, size_t index)
static ITEM *	write (SELF *self, size_t index)
static void	insert_at (SELF *self, size_t at, ITEM const *items, size_t count)
static void	remove_at (SELF *self, size_t at, size_t count)
static ITEM *	push (SELF *self, ITEM item)
static bool	try_pop (SELF *self, ITEM *destination)
static ITEM *	data (SELF *self)
static ITEM	pop (SELF *self)
static ITEM	pop_front (SELF *self)
static size_t	size (SELF const *self)
static void	delete (SELF *self)
static void	transfer_reverse (SELF *source, SELF *target, size_t to_move)
static bool	empty_item (ITEM *const *item)
static ITEM *	next (ITER *iter)
static size_t	position (ITER const *iter)
static bool	empty (ITER const *iter)
static ITER	get_iter (SELF *self)
static bool	empty_item (ITEM const *const *item)
static ITEM const *	next (ITER_CONST *iter)
static size_t	position (ITER_CONST const *iter)
static bool	empty (ITER_CONST const *iter)
static ITER_CONST	get_iter_const (SELF const *self)
	TRAIT_VECTOR (SELF)

Macro Definition Documentation

INVARIANT_CHECK

#define INVARIANT_CHECK

(

self

)

Value:

    ASSUME(self);                                                                                  \
    ASSUME((self)->size <= (self)->capacity);                                                      \
    ASSUME((self->alloc));                                                                         \
    ASSUME(WHEN(!((self)->data), (self)->capacity == 0 && (self)->size == 0));

Definition at line 52 of file template.h.

#define INVARIANT_CHECK(self)                                                                      \
    ASSUME(self);                                                                                  \
    ASSUME((self)->size <= (self)->capacity);                                                      \
    ASSUME((self->alloc));                                                                         \
    ASSUME(WHEN(!((self)->data), (self)->capacity == 0 && (self)->size == 0));

ITEM

#define ITEM   item_t

Definition at line 25 of file template.h.

ITEM_CLONE

#define ITEM_CLONE   item_clone

Definition at line 29 of file template.h.

ITEM_DELETE

#define ITEM_DELETE   item_delete

Definition at line 27 of file template.h.

Typedef Documentation

index_t

typedef size_t index_t

Definition at line 40 of file template.h.

item

typedef ITEM const* item

Definition at line 344 of file template.h.

Function Documentation

clone()

SELF clone ( SELF const * self )

static

Definition at line 130 of file template.h.

                                              {
    INVARIANT_CHECK(self);
    ITEM* data = (ITEM*)NS(ALLOC, malloc)(self->alloc, self->capacity * sizeof(ITEM));
    ASSERT(data);
    for (size_t index = 0; index < self->size; index++) {
        data[index] = ITEM_CLONE(&self->data[index]);
    }
    memory_tracker_set(MEMORY_TRACKER_LVL_CONTAINER, MEMORY_TRACKER_CAP_NONE, &data[self->size],
                       (self->capacity - self->size) * sizeof(ITEM));
    return (SELF){
        .size = self->size,
        .capacity = self->capacity,
        .data = data,
        .alloc = self->alloc,
        .derive_c_vector_marker = gdb_marker_new(),
        .iterator_invalidation_tracker = mutation_tracker_new(),
    };
}

Here is the call graph for this function:

data()

ITEM * data ( SELF * self )

static

Examples

complex/employees.c.

Definition at line 259 of file template.h.

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

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

                                         {
    INVARIANT_CHECK(self);
    if (self->data) {
        for (size_t i = 0; i < self->size; i++) {
            ITEM_DELETE(&self->data[i]);
            // JUSTIFY: Setting items as inaccessible
            //  - Incase a destructor of one item accesses the memory of another.
            memory_tracker_set(MEMORY_TRACKER_LVL_CONTAINER, MEMORY_TRACKER_CAP_NONE,
                               &self->data[i], sizeof(ITEM));
        }
 
        // JUSTIFY: Return to write level before passing to allocator
        //  - Is uninitialised, but still valid memory
        memory_tracker_set(MEMORY_TRACKER_LVL_CONTAINER, MEMORY_TRACKER_CAP_WRITE, self->data,
                           self->capacity * sizeof(ITEM));
        NS(ALLOC, free)(self->alloc, self->data);
    }
}

Here is the call graph for this function:

empty() [1/2]

bool empty ( ITER const * iter )

static

Definition at line 372 of file template.h.

                                              {
    ASSUME(iter);
    mutation_version_check(&iter->version);
    return iter->pos >= iter->vec->size;
}

Here is the call graph for this function:

empty() [2/2]

bool empty ( ITER_CONST const * iter )

static

Definition at line 416 of file template.h.

                                                          {
    ASSUME(iter);
    mutation_version_check(&iter->vec_version);
    return iter->pos >= iter->vec->size;
}

Here is the call graph for this function:

empty_item() [1/2]

bool empty_item ( ITEM *const * item )

static

Definition at line 346 of file template.h.

{ return *item == NULL; }

Here is the call graph for this function:

empty_item() [2/2]

bool empty_item ( ITEM const *const * item )

static

Definition at line 391 of file template.h.

{ return *item == NULL; }

Here is the call graph for this function:

get_iter()

ITER get_iter ( SELF * self )

static

Definition at line 378 of file template.h.

                                           {
    ASSUME(self);
    return (ITER){
        .vec = self,
        .pos = 0,
        .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 422 of file template.h.

                                                             {
    ASSUME(self);
    return (ITER_CONST){
        .vec = self,
        .pos = 0,
        .vec_version = mutation_tracker_get(&self->iterator_invalidation_tracker),
    };
}

Here is the call graph for this function:

insert_at()

void insert_at ( SELF * self, size_t at, ITEM const * items, size_t count )

static

Definition at line 177 of file template.h.

                                                                                        {
    INVARIANT_CHECK(self);
    ASSUME(items);
    ASSERT(at <= self->size);
    mutation_tracker_mutate(&self->iterator_invalidation_tracker);
 
    if (count == 0) {
        return;
    }
 
    NS(SELF, reserve)(self, self->size + count);
    memory_tracker_set(MEMORY_TRACKER_LVL_CONTAINER, MEMORY_TRACKER_CAP_WRITE,
                       &self->data[self->size], count * sizeof(ITEM));
    memmove(&self->data[at + count], &self->data[at], (self->size - at) * sizeof(ITEM));
    memcpy(&self->data[at], items, count * sizeof(ITEM));
    self->size += count;
}

Here is the call graph for this function:

Here is the caller graph for this function:

item_clone()

item_t item_clone ( item_t const * i )

static

Definition at line 28 of file template.h.

{ return *i; }

item_delete()

void item_delete ( item_t * t )

static

Definition at line 26 of file template.h.

{ (void)t; }

new()

SELF new ( ALLOC * alloc )

static

Definition at line 58 of file template.h.

                                        {
    SELF self = (SELF){
        .size = 0,
        .capacity = 0,
        .data = NULL,
        .alloc = alloc,
        .derive_c_vector_marker = gdb_marker_new(),
        .iterator_invalidation_tracker = mutation_tracker_new(),
    };
    return self;
}

Here is the call graph for this function:

new_with_capacity()

SELF new_with_capacity ( size_t capacity, ALLOC * alloc )

static

Definition at line 70 of file template.h.

                                                                       {
    if (capacity == 0) {
        return NS(SELF, new)(alloc);
    }
 
    ITEM* data = (ITEM*)NS(ALLOC, malloc)(alloc, capacity * sizeof(ITEM));
    ASSERT(LIKELY(data));
    memory_tracker_set(MEMORY_TRACKER_LVL_CONTAINER, MEMORY_TRACKER_CAP_NONE, data,
                       capacity * sizeof(ITEM));
    return (SELF){
        .size = 0,
        .capacity = capacity,
        .data = data,
        .alloc = alloc,
        .derive_c_vector_marker = gdb_marker_new(),
        .iterator_invalidation_tracker = mutation_tracker_new(),
    };
}

Here is the call graph for this function:

new_with_defaults()

SELF new_with_defaults ( size_t size, ITEM default_item, ALLOC * alloc )

static

Definition at line 89 of file template.h.

                                                                                      {
    ITEM* data = (ITEM*)NS(ALLOC, malloc)(alloc, size * sizeof(ITEM));
    if (size > 0) {
        // JUSTIFY: We only need to copy size-1 entries - can move the first as default.
        data[0] = default_item;
        for (size_t i = 1; i < size; i++) {
            data[i] = ITEM_CLONE(&default_item);
        }
    }
    ASSERT(LIKELY(data));
    return (SELF){
        .size = size,
        .capacity = size,
        .data = data,
        .alloc = alloc,
        .derive_c_vector_marker = 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]

ITEM * next ( ITER * iter )

static

Definition at line 354 of file template.h.

                                        {
    ASSUME(iter);
    mutation_version_check(&iter->version);
 
    if (iter->pos < iter->vec->size) {
        ITEM* item = &iter->vec->data[iter->pos];
        iter->pos++;
        return item;
    }
    return NULL;
}

Here is the call graph for this function:

next() [2/2]

ITEM const * next ( ITER_CONST * iter )

static

Definition at line 399 of file template.h.

                                                          {
    ASSUME(iter);
    mutation_version_check(&iter->vec_version);
    if (iter->pos < iter->vec->size) {
        ITEM const* item = &iter->vec->data[iter->pos];
        iter->pos++;
        return item;
    }
    return NULL;
}

Here is the call graph for this function:

pop()

ITEM pop ( SELF * self )

static

Definition at line 264 of file template.h.

                                      {
    ITEM entry;
    ASSERT(NS(SELF, try_pop)(self, &entry));
    return entry;
}

Here is the call graph for this function:

Here is the caller graph for this function:

pop_front()

ITEM pop_front ( SELF * self )

static

Definition at line 270 of file template.h.

                                            {
    INVARIANT_CHECK(self);
    mutation_tracker_mutate(&self->iterator_invalidation_tracker);
    ASSERT(self->size > 0);
    ITEM entry = self->data[0];
    memmove(&self->data[0], &self->data[1], (self->size - 1) * sizeof(ITEM));
    self->size--;
    memory_tracker_set(MEMORY_TRACKER_LVL_CONTAINER, MEMORY_TRACKER_CAP_NONE,
                       &self->data[self->size], sizeof(ITEM));
    return entry;
}

Here is the call graph for this function:

position() [1/2]

size_t position ( ITER const * iter )

static

Definition at line 366 of file template.h.

                                                   {
    ASSUME(iter);
    mutation_version_check(&iter->version);
    return iter->pos;
}

Here is the call graph for this function:

Here is the caller graph for this function:

position() [2/2]

size_t position ( ITER_CONST const * iter )

static

Definition at line 410 of file template.h.

                                                               {
    ASSUME(iter);
    mutation_version_check(&iter->vec_version);
    return iter->pos;
}

Here is the call graph for this function:

push()

ITEM * push ( SELF * self, ITEM item )

static

Definition at line 214 of file template.h.

                                                   {
    INVARIANT_CHECK(self);
    mutation_tracker_mutate(&self->iterator_invalidation_tracker);
 
    if (self->size == self->capacity) {
        size_t new_capacity;
        if (self->data == NULL) {
            ASSUME(self->capacity == 0);
            // JUSTIFY: Allocating capacity of 4
            //           - Avoid repeat reallocations on growing a vector from
            //             size sero (from new)
            //           Otherwise an arbitrary choice (given we do not know the size of T)
            new_capacity = 8;
        } else {
            // JUSTIFY: Growth factor of 2
            //           - Simple arithmetic (for debugging)
            //           - Same as used by GCC's std::vector implementation
            new_capacity = self->capacity * 2;
        }
        NS(SELF, reserve)(self, new_capacity);
    }
 
    memory_tracker_set(MEMORY_TRACKER_LVL_CONTAINER, MEMORY_TRACKER_CAP_WRITE,
                       &self->data[self->size], sizeof(ITEM));
 
    ITEM* entry = &self->data[self->size];
    *entry = item;
    self->size++;
    return entry;
}

Here is the call graph for this function:

Here is the caller graph for this function:

read()

ITEM const * read ( SELF const * self, size_t index )

static

Definition at line 157 of file template.h.

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

Here is the call graph for this function:

remove_at()

void remove_at ( SELF * self, size_t at, size_t count )

static

Definition at line 195 of file template.h.

                                                                     {
    INVARIANT_CHECK(self);
    ASSERT(at + count <= self->size);
    mutation_tracker_mutate(&self->iterator_invalidation_tracker);
 
    if (count == 0) {
        return;
    }
 
    for (size_t i = at; i < at + count; i++) {
        ITEM_DELETE(&self->data[i]);
    }
 
    memmove(&self->data[at], &self->data[at + count], (self->size - (at + count)) * sizeof(ITEM));
    self->size -= count;
    memory_tracker_set(MEMORY_TRACKER_LVL_CONTAINER, MEMORY_TRACKER_CAP_NONE,
                       &self->data[self->size], count * sizeof(ITEM));
}

Here is the call graph for this function:

Here is the caller graph for this function:

reserve()

void reserve ( SELF * self, size_t new_capacity )

static

Definition at line 109 of file template.h.

                                                               {
    INVARIANT_CHECK(self);
    if (new_capacity > self->capacity) {
        const size_t capacity_increase = new_capacity - self->capacity;
        const size_t uninit_elements = self->capacity - self->size;
 
        // Set to writeable for allocator
        memory_tracker_set(MEMORY_TRACKER_LVL_CONTAINER, MEMORY_TRACKER_CAP_WRITE,
                           &self->data[self->size], uninit_elements * sizeof(ITEM));
 
        ITEM* new_data =
            (ITEM*)NS(ALLOC, realloc)(self->alloc, self->data, new_capacity * sizeof(ITEM));
        ASSERT(new_data);
        self->data = new_data;
        memory_tracker_set(MEMORY_TRACKER_LVL_CONTAINER, MEMORY_TRACKER_CAP_NONE,
                           &self->data[self->size],
                           (uninit_elements + capacity_increase) * sizeof(ITEM));
        self->capacity = new_capacity;
    }
}

Here is the call graph for this function:

size()

size_t size ( SELF const * self )

static

Definition at line 282 of file template.h.

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

Here is the call graph for this function:

TRAIT_VECTOR()

TRAIT_VECTOR

(

SELF

)

transfer_reverse()

void transfer_reverse ( SELF * source, SELF * target, size_t to_move )

static

Moves to_move items from the beginning of source, to the end of target, shuffling elements in source forward appropriately.

• Used for deque rebalancing

index:   0  1  2  3  4  5
source: [5, 4, 3, 2, 1, 0]
target: [6, 7, 8, 9]

Becomes:

index:   0  1  2  3  4  5
source: [3, 2, 1, 0]
target: [4, 5, 6, 7, 8, 9]

Definition at line 321 of file template.h.

                                                                                   {
    INVARIANT_CHECK(source);
    INVARIANT_CHECK(target);
 
    NS(SELF, reserve)(target, target->size + to_move);
 
    memory_tracker_set(MEMORY_TRACKER_LVL_CONTAINER, MEMORY_TRACKER_CAP_WRITE,
                       &target->data[target->size], to_move * sizeof(ITEM));
    memmove(&target->data[to_move], target->data, target->size * sizeof(ITEM));
 
    for (size_t i = 0; i < to_move; i++) {
        target->data[to_move - 1 - i] = source->data[i];
    }
 
    memmove(source->data, &source->data[to_move], (source->size - to_move) * sizeof(ITEM));
 
    source->size -= to_move;
    target->size += to_move;
    memory_tracker_set(MEMORY_TRACKER_LVL_CONTAINER, MEMORY_TRACKER_CAP_NONE,
                       &source->data[source->size], to_move * sizeof(ITEM));
}

Here is the call graph for this function:

Here is the caller graph for this function:

try_pop()

bool try_pop ( SELF * self, ITEM * destination )

static

Definition at line 245 of file template.h.

                                                             {
    INVARIANT_CHECK(self);
    mutation_tracker_mutate(&self->iterator_invalidation_tracker);
 
    if (LIKELY(self->size > 0)) {
        self->size--;
        *destination = self->data[self->size];
        memory_tracker_set(MEMORY_TRACKER_LVL_CONTAINER, MEMORY_TRACKER_CAP_NONE,
                           &self->data[self->size + 1], sizeof(ITEM));
        return true;
    }
    return false;
}

Here is the call graph for this function:

Here is the caller graph for this function:

try_read()

ITEM const * try_read ( SELF const * self, size_t index )

static

Definition at line 149 of file template.h.

                                                                      {
    INVARIANT_CHECK(self);
    if (LIKELY(index < self->size)) {
        return &self->data[index];
    }
    return NULL;
}

Here is the call graph for this function:

try_write()

ITEM * try_write ( SELF * self, size_t index )

static

Definition at line 163 of file template.h.

                                                           {
    INVARIANT_CHECK(self);
    if (LIKELY(index < self->size)) {
        return &self->data[index];
    }
    return NULL;
}

Here is the call graph for this function:

write()

ITEM * write ( SELF * self, size_t index )

static

Definition at line 171 of file template.h.

                                                       {
    ITEM* item = NS(SELF, try_write)(self, index);
    ASSERT(item);
    return item;
}

Here is the call graph for this function: