template.h File Reference

#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	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...
struct	ITER
struct	ITER_CONST

Macros
#define	ITEM   item_t
#define	ITEM_DELETE   item_delete
#define	ITEM_CLONE   item_clone
#define	ITEM_DEBUG   item_debug
#define	INVARIANT_CHECK(self)
#define	ITER   NS(SELF, iter)
#define	ITER_CONST   NS(SELF, iter_const)

Typedefs
typedef ITEM	item_t
typedef ITEM *	item

Functions
static void	ITEM_DELETE (item_t *)
static item_t	ITEM_CLONE (item_t const *self)
static void	ITEM_DEBUG (ITEM const *, dc_debug_fmt, FILE *)
static DC_PUBLIC SELF	new (ref alloc_ref)
static DC_PUBLIC SELF	new_with_capacity_for (size_t capacity_for, ref alloc_ref)
static DC_PUBLIC bool	empty (SELF const *self)
static DC_PUBLIC size_t	size (SELF const *self)
static void PRIV	set_inaccessible_memory_caps (SELF *self, dc_memory_tracker_capability cap)
static DC_PUBLIC void	reserve (SELF *self, size_t new_capacity_for)
static DC_PUBLIC void	push_back (SELF *self, ITEM item)
static DC_PUBLIC void	push_front (SELF *self, ITEM item)
static DC_PUBLIC ITEM	pop_front (SELF *self)
static DC_PUBLIC ITEM	pop_back (SELF *self)
static DC_PUBLIC ITEM const *	try_read_from_front (SELF const *self, size_t index)
static DC_PUBLIC ITEM const *	try_read_from_back (SELF const *self, size_t index)
static DC_PUBLIC ITEM *	try_write_from_front (SELF *self, size_t index)
static DC_PUBLIC ITEM *	try_write_from_back (SELF *self, size_t index)
static DC_PUBLIC bool	empty_item (ITEM *const *item)
static DC_PUBLIC bool	empty (ITER const *iter)
static DC_PUBLIC ITEM *	next (ITER *iter)
static DC_PUBLIC ITER	get_iter (SELF *self)
static DC_PUBLIC void	delete (SELF *self)
static DC_PUBLIC bool	empty_item (ITEM const *const *item)
static DC_PUBLIC bool	empty (ITER_CONST const *iter)
static DC_PUBLIC ITEM const *	next (ITER_CONST *iter)
static DC_PUBLIC ITER_CONST	get_iter_const (SELF const *self)
static DC_PUBLIC SELF	clone (SELF const *self)
static DC_PUBLIC void	debug (SELF const *self, dc_debug_fmt fmt, FILE *stream)
	DC_TRAIT_QUEUE (SELF)

Macro Definition Documentation

INVARIANT_CHECK

#define INVARIANT_CHECK

(

self

)

Value:

    DC_ASSUME(self);                                                                               \
    DC_ASSUME(DC_WHEN(!(self)->empty,                                                              \
                      (self)->head < (self)->capacity && (self)->tail < (self)->capacity));        \
    DC_ASSUME(DC_WHEN((self)->empty, (self)->head == (self)->tail));                               \
    DC_ASSUME(DC_WHEN(!(self)->data, (self)->head == 0 && (self)->tail == 0));

Definition at line 55 of file template.h.

#define INVARIANT_CHECK(self)                                                                      \
    DC_ASSUME(self);                                                                               \
    DC_ASSUME(DC_WHEN(!(self)->empty,                                                              \
                      (self)->head < (self)->capacity && (self)->tail < (self)->capacity));        \
    DC_ASSUME(DC_WHEN((self)->empty, (self)->head == (self)->tail));                               \
    DC_ASSUME(DC_WHEN(!(self)->data, (self)->head == 0 && (self)->tail == 0));

ITEM

#define ITEM   item_t

Definition at line 19 of file template.h.

ITEM_CLONE

#define ITEM_CLONE   item_clone

Definition at line 22 of file template.h.

ITEM_DEBUG

#define ITEM_DEBUG   item_debug

Definition at line 24 of file template.h.

ITEM_DELETE

#define ITEM_DELETE   item_delete

Definition at line 20 of file template.h.

ITER

#define ITER   NS(SELF, iter)

Definition at line 292 of file template.h.

ITER_CONST

#define ITER_CONST   NS(SELF, iter_const)

Definition at line 348 of file template.h.

Typedef Documentation

item

typedef ITEM const* item

Definition at line 293 of file template.h.

item_t

typedef ITEM item_t

Definition at line 40 of file template.h.

Function Documentation

clone()

DC_PUBLIC SELF clone ( SELF const * self )

static

Definition at line 385 of file template.h.

                                                        {
    INVARIANT_CHECK(self);
    ITEM* new_data = NULL;
    size_t tail = 0;
    size_t new_capacity = 0;
    size_t const old_size = self->size;
 
    if (old_size > 0) {
        new_capacity = dc_math_next_power_of_2(old_size);
        new_data = (ITEM*)NS(ALLOC, allocate_uninit)(self->alloc_ref, new_capacity * sizeof(ITEM));
 
        ITER_CONST iter = NS(SELF, get_iter_const)(self);
        ITEM const* item;
        while ((item = NS(ITER_CONST, next)(&iter))) {
            new_data[tail] = ITEM_CLONE(item);
            tail++;
        }
        tail--;
    }
    SELF new_self = {
        .data = new_data,
        .capacity = new_capacity,
        .size = old_size,
        .head = 0,
        .tail = tail,
        .empty = self->empty,
        .alloc_ref = self->alloc_ref,
        .derive_c_circular = dc_gdb_marker_new(),
        .iterator_invalidation_tracker = mutation_tracker_new(),
    };
    PRIV(NS(SELF, set_inaccessible_memory_caps))(&new_self, DC_MEMORY_TRACKER_CAP_NONE);
    return new_self;
}

DC_TRAIT_QUEUE()

DC_TRAIT_QUEUE

(

SELF

)

debug()

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

static

Definition at line 419 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, "size: %lu,\n", self->size);
    dc_debug_fmt_print(fmt, stream, "head: %lu,\n", self->head);
    dc_debug_fmt_print(fmt, stream, "tail: %lu,\n", self->tail);
 
    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, "queue: @%p [\n", (void*)self->data);
    fmt = dc_debug_fmt_scope_begin(fmt);
 
    ITER_CONST iter = NS(SELF, get_iter_const)(self);
    ITEM const* item;
    while ((item = NS(ITER_CONST, next)(&iter))) {
        dc_debug_fmt_print_indents(fmt, stream);
        ITEM_DEBUG(item, 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, "}");
}

delete()

DC_PUBLIC void delete ( SELF * self )

static

Definition at line 329 of file template.h.

                                                   {
    INVARIANT_CHECK(self);
    if (self->data) {
        ITER iter = NS(SELF, get_iter)(self);
        ITEM* item;
        while ((item = NS(ITER, next)(&iter))) {
            ITEM_DELETE(item);
            dc_memory_tracker_set(DC_MEMORY_TRACKER_LVL_CONTAINER, DC_MEMORY_TRACKER_CAP_NONE, item,
                                  sizeof(ITEM));
        }
        size_t const size = self->capacity * sizeof(ITEM);
        dc_memory_tracker_set(DC_MEMORY_TRACKER_LVL_CONTAINER, DC_MEMORY_TRACKER_CAP_WRITE,
                              self->data, size);
        NS(ALLOC, deallocate)(self->alloc_ref, self->data, size);
    }
}

empty() [1/3]

DC_PUBLIC bool empty ( ITER const * iter )

static

Definition at line 303 of file template.h.

                                                        {
    DC_ASSUME(iter);
    mutation_version_check(&iter->version);
    return !NS(SELF, try_read_from_front)(iter->circular, iter->position);
}

empty() [2/3]

DC_PUBLIC bool empty ( ITER_CONST const * iter )

static

Definition at line 359 of file template.h.

                                                                    {
    DC_ASSUME(iter);
    mutation_version_check(&iter->version);
    return !NS(SELF, try_read_from_front)(iter->circular, iter->position);
}

empty() [3/3]

DC_PUBLIC bool empty ( SELF const * self )

static

Definition at line 101 of file template.h.

                                                        {
    DC_ASSUME(self);
    if (self->empty) {
        DC_ASSUME(self->head == self->tail);
    }
    return self->empty;
}

empty_item() [1/2]

DC_PUBLIC bool empty_item ( ITEM *const * item )

static

Definition at line 295 of file template.h.

{ return *item == NULL; }

empty_item() [2/2]

DC_PUBLIC bool empty_item ( ITEM const *const * item )

static

Definition at line 351 of file template.h.

{ return *item == NULL; }

get_iter()

DC_PUBLIC ITER get_iter ( SELF * self )

static

Definition at line 320 of file template.h.

                                                     {
    INVARIANT_CHECK(self);
    return (ITER){
        .circular = self,
        .position = 0,
        .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 376 of file template.h.

                                                                       {
    INVARIANT_CHECK(self);
    return (ITER_CONST){
        .circular = self,
        .position = 0,
        .version = mutation_tracker_get(&self->iterator_invalidation_tracker),
    };
}

ITEM_CLONE()

item_t ITEM_CLONE ( item_t const * self )

static

Definition at line 23 of file template.h.

{ return *self; }

ITEM_DEBUG()

void ITEM_DEBUG ( ITEM const * , dc_debug_fmt , FILE *  )

static

Definition at line 25 of file template.h.

{}

ITEM_DELETE()

void ITEM_DELETE ( item_t * )

static

Definition at line 21 of file template.h.

{}

new()

DC_PUBLIC SELF new ( ref alloc_ref )

static

Definition at line 62 of file template.h.

                                                              {
    return (SELF){
        .data = NULL,
        .capacity = 0,
        .size = 0,
        .head = 0,
        .tail = 0,
        .empty = true,
        .alloc_ref = alloc_ref,
        .derive_c_circular = dc_gdb_marker_new(),
        .iterator_invalidation_tracker = mutation_tracker_new(),
    };
}

new_with_capacity_for()

DC_PUBLIC SELF new_with_capacity_for ( size_t capacity_for, ref alloc_ref )

static

Definition at line 76 of file template.h.

                                                                                {
    if (capacity_for == 0) {
        return NS(SELF, new)(alloc_ref);
    }
    size_t const capacity = dc_math_next_power_of_2(capacity_for);
    DC_ASSUME(DC_MATH_IS_POWER_OF_2(capacity));
    ITEM* data = (ITEM*)NS(ALLOC, allocate_uninit)(alloc_ref, capacity * sizeof(ITEM));
 
    dc_memory_tracker_set(DC_MEMORY_TRACKER_LVL_CONTAINER, DC_MEMORY_TRACKER_CAP_NONE, data,
                          capacity * sizeof(ITEM));
 
    return (SELF){
        .data = data,
        .capacity = capacity,
        .size = 0,
        .head = 0,
        .tail = 0,
        .empty = true,
        .alloc_ref = alloc_ref,
        .derive_c_circular = dc_gdb_marker_new(),
        .iterator_invalidation_tracker = mutation_tracker_new(),
    };
}

next() [1/2]

DC_PUBLIC ITEM * next ( ITER * iter )

static

Definition at line 309 of file template.h.

                                                  {
    DC_ASSUME(iter);
    mutation_version_check(&iter->version);
    ITEM* item = NS(SELF, try_write_from_front)(iter->circular, iter->position);
    if (!item) {
        return NULL;
    }
    iter->position++;
    return item;
}

next() [2/2]

DC_PUBLIC ITEM const * next ( ITER_CONST * iter )

static

Definition at line 365 of file template.h.

                                                                    {
    DC_ASSUME(iter);
    mutation_version_check(&iter->version);
    ITEM const* item = NS(SELF, try_read_from_front)(iter->circular, iter->position);
    if (!item) {
        return NULL;
    }
    iter->position++;
    return item;
}

pop_back()

DC_PUBLIC ITEM pop_back ( SELF * self )

static

Definition at line 240 of file template.h.

                                                     {
    INVARIANT_CHECK(self);
    mutation_tracker_mutate(&self->iterator_invalidation_tracker);
    DC_ASSERT(!NS(SELF, empty)(self), "Cannot pop back, already empty {size=%lu}",
              (size_t)self->size);
 
    ITEM value = self->data[self->tail];
    dc_memory_tracker_set(DC_MEMORY_TRACKER_LVL_CONTAINER, DC_MEMORY_TRACKER_CAP_NONE,
                          &self->data[self->tail], sizeof(ITEM));
    self->size--;
    if (self->head == self->tail) {
        self->empty = true;
    } else {
        if (self->tail == 0) {
            self->tail = self->capacity - 1;
        } else {
            self->tail--;
        }
    }
    return value;
}

pop_front()

DC_PUBLIC ITEM pop_front ( SELF * self )

static

Definition at line 219 of file template.h.

                                                      {
    INVARIANT_CHECK(self);
    mutation_tracker_mutate(&self->iterator_invalidation_tracker);
    DC_ASSERT(!NS(SELF, empty)(self), "Cannot pop front, already empty {size=%lu}",
              (size_t)self->size);
 
    ITEM value = self->data[self->head];
    dc_memory_tracker_set(DC_MEMORY_TRACKER_LVL_CONTAINER, DC_MEMORY_TRACKER_CAP_NONE,
                          &self->data[self->head], sizeof(ITEM));
    dc_memory_tracker_check(DC_MEMORY_TRACKER_LVL_CONTAINER, DC_MEMORY_TRACKER_CAP_NONE,
                            &self->data[self->head], sizeof(ITEM));
 
    self->size--;
    if (self->head == self->tail) {
        self->empty = true;
    } else {
        self->head = dc_math_modulus_power_of_2_capacity(self->head + 1, self->capacity);
    }
    return value;
}

push_back()

DC_PUBLIC void push_back ( SELF * self, ITEM item )

static

Definition at line 185 of file template.h.

                                                                 {
    INVARIANT_CHECK(self);
    mutation_tracker_mutate(&self->iterator_invalidation_tracker);
    NS(SELF, reserve)(self, self->size + 1);
 
    if (!self->empty) {
        self->tail = dc_math_modulus_power_of_2_capacity(self->tail + 1, self->capacity);
    }
    dc_memory_tracker_set(DC_MEMORY_TRACKER_LVL_CONTAINER, DC_MEMORY_TRACKER_CAP_WRITE,
                          &self->data[self->tail], sizeof(ITEM));
    self->data[self->tail] = item;
    self->empty = false;
    self->size++;
}

push_front()

DC_PUBLIC void push_front ( SELF * self, ITEM item )

static

Definition at line 200 of file template.h.

                                                                  {
    INVARIANT_CHECK(self);
    mutation_tracker_mutate(&self->iterator_invalidation_tracker);
    NS(SELF, reserve)(self, self->size + 1);
 
    if (!self->empty) {
        if (self->head == 0) {
            self->head = self->capacity - 1;
        } else {
            self->head--;
        }
    }
    dc_memory_tracker_set(DC_MEMORY_TRACKER_LVL_CONTAINER, DC_MEMORY_TRACKER_CAP_WRITE,
                          &self->data[self->head], sizeof(ITEM));
    self->data[self->head] = item;
    self->empty = false;
    self->size++;
}

reserve()

DC_PUBLIC void reserve ( SELF * self, size_t new_capacity_for )

static

Definition at line 130 of file template.h.

                                                                             {
    INVARIANT_CHECK(self);
    mutation_tracker_mutate(&self->iterator_invalidation_tracker);
 
    if (new_capacity_for > self->capacity) {
        size_t const new_capacity = dc_math_next_power_of_2(new_capacity_for * 2);
 
        // We set the capability to write for the allocator, and only touch the
        // state for memory that is inaccessible
        PRIV(NS(SELF, set_inaccessible_memory_caps))(self, DC_MEMORY_TRACKER_CAP_WRITE);
 
        ITEM* new_data;
        if (self->data == NULL) {
            new_data =
                (ITEM*)NS(ALLOC, allocate_uninit)(self->alloc_ref, new_capacity * sizeof(ITEM));
        } else {
            new_data = (ITEM*)NS(ALLOC, reallocate)(self->alloc_ref, self->data,
                                                    self->capacity * sizeof(ITEM),
                                                    new_capacity * sizeof(ITEM));
        }
 
        if (self->head > self->tail) {
            // The queue wraps at the old end, so we need to either:
            //  - shift elements of the tail around into the new area at the end of the buffer
            // - shift the head of the queue along to the new arena
            // need to move the wrapped around part to the end of the new buffer
            size_t const old_capacity = self->capacity;
            size_t const additional_capacity = new_capacity - old_capacity;
            size_t const front_tail_items = self->tail + 1;
            size_t const back_head_items = old_capacity - self->head;
 
            if (front_tail_items > back_head_items) {
                size_t const new_head = self->head + additional_capacity;
                memmove(&new_data[new_head], &new_data[self->head], back_head_items * sizeof(ITEM));
                self->head = new_head;
            } else {
                // as we go to the next power of 2 each time, the additional capacity is always >=
                // the number of items at the front. As a result, we never need to consider:
                // - Only copying the first n from the front
                // - Shifting some of the front items to the start of the buffer
                DC_ASSUME(front_tail_items <= additional_capacity);
 
                memcpy(&new_data[old_capacity], &new_data[0], front_tail_items * sizeof(ITEM));
                self->tail = old_capacity + front_tail_items - 1;
            }
        }
        self->capacity = new_capacity;
        self->data = new_data;
 
        // Set the new inaccessible memory
        PRIV(NS(SELF, set_inaccessible_memory_caps))(self, DC_MEMORY_TRACKER_CAP_NONE);
    }
    INVARIANT_CHECK(self);
}

set_inaccessible_memory_caps()

void PRIV set_inaccessible_memory_caps ( SELF * self, dc_memory_tracker_capability cap )

static

Definition at line 114 of file template.h.

                                                                                           {
    if (self->empty) {
        dc_memory_tracker_set(DC_MEMORY_TRACKER_LVL_CONTAINER, cap, self->data,
                              self->capacity * sizeof(ITEM));
    } else if (self->head <= self->tail) {
        dc_memory_tracker_set(DC_MEMORY_TRACKER_LVL_CONTAINER, cap, &self->data[self->tail + 1],
                              (self->capacity - (self->tail + 1)) * sizeof(ITEM));
        dc_memory_tracker_set(DC_MEMORY_TRACKER_LVL_CONTAINER, cap, self->data,
                              self->head * sizeof(ITEM));
    } else {
        dc_memory_tracker_set(DC_MEMORY_TRACKER_LVL_CONTAINER, cap, &self->data[self->tail + 1],
                              (self->head - (self->tail + 1)) * sizeof(ITEM));
    }
}

size()

DC_PUBLIC size_t size ( SELF const * self )

static

Definition at line 109 of file template.h.

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

try_read_from_back()

DC_PUBLIC ITEM const * try_read_from_back ( SELF const * self, size_t index )

static

Definition at line 272 of file template.h.

                                                                                          {
    INVARIANT_CHECK(self);
    if (index >= self->size) {
        return NULL;
    }
    if (index <= self->tail) {
        return &self->data[self->tail - index];
    }
    size_t const from_end = index - self->tail;
    return &self->data[self->capacity - from_end];
}

try_read_from_front()

DC_PUBLIC ITEM const * try_read_from_front ( SELF const * self, size_t index )

static

Definition at line 262 of file template.h.

                                                                                           {
    INVARIANT_CHECK(self);
    if (index < self->size) {
        size_t const real_index =
            dc_math_modulus_power_of_2_capacity(self->head + index, self->capacity);
        return &self->data[real_index];
    }
    return NULL;
}

try_write_from_back()

DC_PUBLIC ITEM * try_write_from_back ( SELF * self, size_t index )

static

Definition at line 288 of file template.h.

                                                                               {
    return (ITEM*)NS(SELF, try_read_from_back)(self, index);
}

try_write_from_front()

DC_PUBLIC ITEM * try_write_from_front ( SELF * self, size_t index )

static

Definition at line 284 of file template.h.

                                                                                {
    return (ITEM*)NS(SELF, try_read_from_front)(self, index);
}