template.h File Reference

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>
#include <derive-c/core/helpers.h>
#include <derive-c/core/panic.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:

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

Functions
static void	item_delete (item_t *UNUSED(self))
static item_t	item_clone (item_t const *self)
static SELF	new (ALLOC *alloc)
static SELF	new_with_capacity_for (size_t capacity_for, ALLOC *alloc)
static bool	empty (SELF const *self)
static size_t	size (SELF const *self)
static void	reserve (SELF *self, size_t new_capacity_for)
static void	push_back (SELF *self, ITEM item)
static void	push_front (SELF *self, ITEM item)
static ITEM	pop_front (SELF *self)
static ITEM	pop_back (SELF *self)
static ITEM const *	try_read_from_front (SELF const *self, size_t index)
static ITEM const *	read_from_front (SELF const *self, size_t index)
static ITEM *	try_write_from_front (SELF *self, size_t index)
static ITEM *	write_from_front (SELF *self, size_t index)
static bool	empty (ITER const *iter)
static ITEM *	next (ITER *iter)
static ITER	get_iter (SELF *self)
static void	delete (SELF *self)
static bool	empty (ITER_CONST const *iter)
static ITEM const *	next (ITER_CONST *iter)
static ITER_CONST	get_iter_const (SELF const *self)
static SELF	clone (SELF const *self)

Macro Definition Documentation

ITEM

#define ITEM   item_t

Definition at line 22 of file template.h.

ITEM_CLONE

#define ITEM_CLONE   item_clone

Definition at line 26 of file template.h.

ITEM_DELETE

#define ITEM_DELETE   item_delete

Definition at line 24 of file template.h.

Function Documentation

clone()

SELF clone ( SELF const * self )

static

Definition at line 295 of file template.h.

                                              {
    DEBUG_ASSERT(self);
    ITEM* new_data = NULL;
    size_t tail = 0;
    size_t new_capacity = 0;
    size_t old_size = NS(SELF, size)(self);
 
    if (old_size > 0) {
        new_capacity = next_power_of_2(old_size);
        new_data = (ITEM*)NS(ALLOC, malloc)(self->alloc, new_capacity * sizeof(ITEM));
        ASSERT(new_data);
 
        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--;
    }
    return (SELF){
        .data = new_data,
        .capacity = new_capacity,
        .head = 0,
        .tail = tail,
        .empty = self->empty,
        .alloc = self->alloc,
        .derive_c_circular = (gdb_marker){},
    };
}

Here is the call graph for this function:

delete()

void delete ( SELF * self )

static

Definition at line 252 of file template.h.

                                         {
    DEBUG_ASSERT(self);
    if (self->data) {
        ITER iter = NS(SELF, get_iter)(self);
        ITEM* item;
        while ((item = NS(ITER, next)(&iter))) {
            ITEM_DELETE(item);
        }
        NS(ALLOC, free)(self->alloc, self->data);
    }
}

Here is the call graph for this function:

empty() [1/3]

bool empty ( ITER const * iter )

static

Definition at line 229 of file template.h.

                                              {
    DEBUG_ASSERT(iter);
    return !NS(SELF, try_read_from_front)(iter->circular, iter->position);
}

Here is the call graph for this function:

empty() [2/3]

bool empty ( ITER_CONST const * iter )

static

Definition at line 272 of file template.h.

                                                          {
    DEBUG_ASSERT(iter);
    return !NS(SELF, try_read_from_front)(iter->circular, iter->position);
}

Here is the call graph for this function:

empty() [3/3]

bool empty ( SELF const * self )

static

Definition at line 76 of file template.h.

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

Here is the call graph for this function:

get_iter()

ITER get_iter ( SELF * self )

static

Definition at line 244 of file template.h.

                                           {
    DEBUG_ASSERT(self);
    return (ITER){
        .circular = self,
        .position = 0,
    };
}

Here is the call graph for this function:

get_iter_const()

ITER_CONST get_iter_const ( SELF const * self )

static

Definition at line 287 of file template.h.

                                                             {
    DEBUG_ASSERT(self);
    return (ITER_CONST){
        .circular = self,
        .position = 0,
    };
}

Here is the call graph for this function:

item_clone()

item_t item_clone ( item_t const * self )

static

Definition at line 25 of file template.h.

{ return *self; }

item_delete()

void item_delete ( item_t * UNUSEDself )

static

Definition at line 23 of file template.h.

{}

new()

SELF new ( ALLOC * alloc )

static

Definition at line 47 of file template.h.

                                        {
    return (SELF){.data = NULL,
                  .head = 0,
                  .tail = 0,
                  .empty = true,
                  .alloc = alloc,
                  .derive_c_circular = (gdb_marker){}};
}

new_with_capacity_for()

SELF new_with_capacity_for ( size_t capacity_for, ALLOC * alloc )

static

Definition at line 56 of file template.h.

                                                                               {
    if (capacity_for == 0) {
        return NS(SELF, new)(alloc);
    }
    size_t capacity = next_power_of_2(capacity_for);
    ASSERT(is_power_of_2(capacity));
    ITEM* data = (ITEM*)NS(ALLOC, malloc)(alloc, capacity * sizeof(ITEM));
    ASSERT(data);
 
    return (SELF){
        .data = data,
        .capacity = capacity,
        .head = 0,
        .tail = 0,
        .empty = true,
        .alloc = alloc,
        .derive_c_circular = (gdb_marker){},
    };
}

Here is the call graph for this function:

next() [1/2]

ITEM * next ( ITER * iter )

static

Definition at line 234 of file template.h.

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

Here is the call graph for this function:

next() [2/2]

ITEM const * next ( ITER_CONST * iter )

static

Definition at line 277 of file template.h.

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

Here is the call graph for this function:

pop_back()

ITEM pop_back ( SELF * self )

static

Definition at line 174 of file template.h.

                                           {
    DEBUG_ASSERT(self);
    ASSERT(!NS(SELF, empty)(self));
 
    ITEM value = self->data[self->tail];
    if (self->head == self->tail) {
        self->empty = true;
    } else {
        if (self->tail == 0) {
            self->tail = self->capacity - 1;
        } else {
            self->tail--;
        }
    }
    return value;
}

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

                                            {
    DEBUG_ASSERT(self);
    ASSERT(!NS(SELF, empty)(self));
 
    ITEM value = self->data[self->head];
    if (self->head == self->tail) {
        self->empty = true;
    } else {
        self->head = modulus_power_of_2_capacity(self->head + 1, self->capacity);
    }
    return value;
}

Here is the call graph for this function:

Here is the caller graph for this function:

push_back()

void push_back ( SELF * self, ITEM item )

static

Definition at line 135 of file template.h.

                                                       {
    DEBUG_ASSERT(self);
    NS(SELF, reserve)(self, NS(SELF, size)(self) + 1);
 
    if (!self->empty) {
        self->tail = modulus_power_of_2_capacity(self->tail + 1, self->capacity);
    }
    self->data[self->tail] = item;
    self->empty = false;
}

Here is the call graph for this function:

Here is the caller graph for this function:

push_front()

void push_front ( SELF * self, ITEM item )

static

Definition at line 146 of file template.h.

                                                        {
    DEBUG_ASSERT(self);
    NS(SELF, reserve)(self, NS(SELF, size)(self) + 1);
 
    if (!self->empty) {
        if (self->head == 0) {
            self->head = self->capacity - 1;
        } else {
            self->head--;
        }
    }
    self->data[self->head] = item;
    self->empty = false;
}

Here is the call graph for this function:

Here is the caller graph for this function:

read_from_front()

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

static

Definition at line 200 of file template.h.

                                                                             {
    DEBUG_ASSERT(self);
    ITEM const* item = NS(SELF, try_read_from_front)(self, index);
    ASSERT(item);
    return 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_for )

static

Definition at line 97 of file template.h.

                                                                   {
    DEBUG_ASSERT(self);
 
    if (new_capacity_for > self->capacity) {
        size_t new_capacity = next_power_of_2(new_capacity_for * 2);
        ITEM* new_data =
            (ITEM*)NS(ALLOC, realloc)(self->alloc, self->data, new_capacity * sizeof(ITEM));
        ASSERT(new_data);
        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 old_capacity = self->capacity;
            size_t additional_capacity = new_capacity - old_capacity;
            size_t front_tail_items = self->tail + 1;
            size_t back_head_items = old_capacity - self->head;
 
            if (front_tail_items > back_head_items) {
                size_t 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
                DEBUG_ASSERT(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;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

size()

size_t size ( SELF const * self )

static

Definition at line 84 of file template.h.

                                               {
    DEBUG_ASSERT(self);
    if (self->empty) {
        DEBUG_ASSERT(self->tail == self->head);
        return 0;
    }
 
    if (self->head <= self->tail) {
        return (self->tail - self->head) + 1;
    }
    return (self->capacity - self->head) + self->tail + 1;
}

Here is the call graph for this function:

try_read_from_front()

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

static

Definition at line 191 of file template.h.

                                                                                 {
    DEBUG_ASSERT(self);
    if (index < NS(SELF, size)(self)) {
        size_t real_index = modulus_power_of_2_capacity(self->head + index, self->capacity);
        return &self->data[real_index];
    }
    return NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

try_write_from_front()

ITEM * try_write_from_front ( SELF * self, size_t index )

static

Definition at line 207 of file template.h.

                                                                      {
    DEBUG_ASSERT(self);
    if (index < NS(SELF, size)(self)) {
        size_t real_index = modulus_power_of_2_capacity(self->head + index, self->capacity);
        return &self->data[real_index];
    }
    return NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

write_from_front()

ITEM * write_from_front ( SELF * self, size_t index )

static

Definition at line 216 of file template.h.

                                                                  {
    DEBUG_ASSERT(self);
    ITEM* value = NS(SELF, try_write_from_front)(self, index);
    ASSERT(value);
    return value;
}

Here is the call graph for this function:

Here is the caller graph for this function: