template.h File Reference

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>
#include "utils.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/structures/vector/template.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
#define	ITEM_VECTORS   NS(NAME, item_vectors)
#define	INTERNAL_NAME   ITEM_VECTORS

Functions
static void	item_delete (item_t *UNUSED(a))
static item_t	item_clone (item_t const *a)
static SELF	new (ALLOC *alloc)
static SELF	new_with_capacity (size_t front_and_back_capacity, ALLOC *alloc)
static SELF	clone (SELF const *other)
static void	rebalance (SELF *self)
static ITEM const *	peek_front_read (SELF const *self)
static ITEM *	peek_front_write (SELF *self)
static ITEM const *	peek_back_read (SELF const *self)
static ITEM *	peek_back_write (SELF *self)
static void	push_front (SELF *self, ITEM item)
static void	push_back (SELF *self, ITEM item)
static ITEM	pop_front (SELF *self)
static ITEM	pop_back (SELF *self)
static size_t	size (SELF const *self)
static bool	empty (SELF const *self)
static ITEM *	next (ITER *iter)
static bool	empty (ITER const *iter)
static ITER	get_iter (SELF *self)
static ITEM const *	next (ITER_CONST *iter)
static bool	empty (ITER_CONST const *iter)
static ITER_CONST	get_iter_const (SELF const *self)
static void	delete (SELF *self)

Macro Definition Documentation

INTERNAL_NAME

#define INTERNAL_NAME   ITEM_VECTORS

Definition at line 48 of file template.h.

ITEM

#define ITEM   item_t

Definition at line 24 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.

ITEM_VECTORS

#define ITEM_VECTORS   NS(NAME, item_vectors)

Definition at line 40 of file template.h.

Function Documentation

clone()

SELF clone ( SELF const * other )

static

Definition at line 77 of file template.h.

                                               {
    DEBUG_ASSERT(other);
    return (SELF){.front = NS(ITEM_VECTORS, clone)(&other->front),
                  .back = NS(ITEM_VECTORS, clone)(&other->back),
                  .alloc = other->alloc,
                  .derive_c_deque = (gdb_marker){}};
}

Here is the call graph for this function:

delete()

void delete ( SELF * self )

static

Definition at line 309 of file template.h.

                                         {
    DEBUG_ASSERT(self);
    NS(ITEM_VECTORS, delete)(&self->front);
    NS(ITEM_VECTORS, delete)(&self->back);
}

empty() [1/3]

bool empty ( ITER const * iter )

static

Definition at line 251 of file template.h.

                                              {
    DEBUG_ASSERT(iter);
    return iter->pos >=
           NS(ITEM_VECTORS, size)(&iter->deque->front) + NS(ITEM_VECTORS, size)(&iter->deque->back);
}

Here is the call graph for this function:

empty() [2/3]

bool empty ( ITER_CONST const * iter )

static

Definition at line 293 of file template.h.

                                                          {
    DEBUG_ASSERT(iter);
    return iter->pos >=
           NS(ITEM_VECTORS, size)(&iter->deque->front) + NS(ITEM_VECTORS, size)(&iter->deque->back);
}

Here is the call graph for this function:

empty() [3/3]

bool empty ( SELF const * self )

static

Definition at line 220 of file template.h.

                                              {
    DEBUG_ASSERT(self);
    return NS(ITEM_VECTORS, size)(&self->front) == 0 && NS(ITEM_VECTORS, size)(&self->back) == 0;
}

Here is the call graph for this function:

get_iter()

ITER get_iter ( SELF * self )

static

Definition at line 257 of file template.h.

                                           {
    DEBUG_ASSERT(self);
    return (ITER){
        .deque = self,
        .pos = 0,
    };
}

Here is the call graph for this function:

get_iter_const()

ITER_CONST get_iter_const ( SELF const * self )

static

Definition at line 299 of file template.h.

                                                             {
    DEBUG_ASSERT(self);
    return (ITER_CONST){
        .deque = self,
        .pos = 0,
    };
}

Here is the call graph for this function:

item_clone()

item_t item_clone ( item_t const * a )

static

Definition at line 28 of file template.h.

{ return *a; }

item_delete()

void item_delete ( item_t * UNUSEDa )

static

Definition at line 26 of file template.h.

{}

new()

SELF new ( ALLOC * alloc )

static

Definition at line 63 of file template.h.

                                        {
    return (SELF){.front = NS(ITEM_VECTORS, new)(alloc),
                  .back = NS(ITEM_VECTORS, new)(alloc),
                  .alloc = alloc,
                  .derive_c_deque = (gdb_marker){}};
}

new_with_capacity()

SELF new_with_capacity ( size_t front_and_back_capacity, ALLOC * alloc )

static

Definition at line 70 of file template.h.

                                                                                      {
    return (SELF){.front = NS(ITEM_VECTORS, new_with_capacity)(front_and_back_capacity, alloc),
                  .back = NS(ITEM_VECTORS, new_with_capacity)(front_and_back_capacity, alloc),
                  .alloc = alloc,
                  .derive_c_deque = (gdb_marker){}};
}

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

                                        {
    DEBUG_ASSERT(iter);
    size_t front_size = NS(ITEM_VECTORS, size)(&iter->deque->front);
    size_t back_size = NS(ITEM_VECTORS, size)(&iter->deque->back);
    size_t total_size = front_size + back_size;
 
    if (iter->pos < total_size) {
        ITEM* item;
        if (iter->pos < front_size) {
            item = NS(ITEM_VECTORS, write)(&iter->deque->front, front_size - 1 - iter->pos);
        } else {
            item = NS(ITEM_VECTORS, write)(&iter->deque->back, iter->pos - front_size);
        }
        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 274 of file template.h.

                                                          {
    DEBUG_ASSERT(iter);
    size_t front_size = NS(ITEM_VECTORS, size)(&iter->deque->front);
    size_t back_size = NS(ITEM_VECTORS, size)(&iter->deque->back);
    size_t total_size = front_size + back_size;
 
    if (iter->pos < total_size) {
        ITEM const* item;
        if (iter->pos < front_size) {
            item = NS(ITEM_VECTORS, read)(&iter->deque->front, front_size - 1 - iter->pos);
        } else {
            item = NS(ITEM_VECTORS, read)(&iter->deque->back, iter->pos - front_size);
        }
        iter->pos++;
        return item;
    }
    return NULL;
}

Here is the call graph for this function:

peek_back_read()

ITEM const * peek_back_read ( SELF const * self )

static

Definition at line 155 of file template.h.

                                                              {
    DEBUG_ASSERT(self);
 
    size_t back_size = NS(ITEM_VECTORS, size)(&self->back);
    if (back_size > 0) {
        return NS(ITEM_VECTORS, read)(&self->back, back_size - 1);
    }
 
    return NS(ITEM_VECTORS, try_read)(&self->front, 0);
}

Here is the call graph for this function:

Here is the caller graph for this function:

peek_back_write()

ITEM * peek_back_write ( SELF * self )

static

Definition at line 166 of file template.h.

                                                   {
    DEBUG_ASSERT(self);
 
    size_t back_size = NS(ITEM_VECTORS, size)(&self->back);
    if (back_size > 0) {
        return NS(ITEM_VECTORS, write)(&self->back, back_size - 1);
    }
 
    return NS(ITEM_VECTORS, try_write)(&self->front, 0);
}

Here is the call graph for this function:

Here is the caller graph for this function:

peek_front_read()

ITEM const * peek_front_read ( SELF const * self )

static

Definition at line 133 of file template.h.

                                                               {
    DEBUG_ASSERT(self);
 
    size_t front_size = NS(ITEM_VECTORS, size)(&self->front);
    if (front_size > 0) {
        return NS(ITEM_VECTORS, read)(&self->front, front_size - 1);
    }
 
    return NS(ITEM_VECTORS, try_read)(&self->back, 0);
}

Here is the call graph for this function:

Here is the caller graph for this function:

peek_front_write()

ITEM * peek_front_write ( SELF * self )

static

Definition at line 144 of file template.h.

                                                    {
    DEBUG_ASSERT(self);
 
    size_t front_size = NS(ITEM_VECTORS, size)(&self->front);
    if (front_size > 0) {
        return NS(ITEM_VECTORS, write)(&self->front, front_size - 1);
    }
 
    return NS(ITEM_VECTORS, try_write)(&self->back, 0);
}

Here is the call graph for this function:

Here is the caller graph for this function:

pop_back()

ITEM pop_back ( SELF * self )

static

Definition at line 202 of file template.h.

                                           {
    DEBUG_ASSERT(self);
    if (NS(ITEM_VECTORS, size)(&self->back) > 0) {
        ITEM result = NS(ITEM_VECTORS, pop)(&self->back);
        NS(SELF, rebalance)(self);
        return result;
    }
 
    ITEM result = NS(ITEM_VECTORS, pop_front)(&self->front);
    NS(SELF, rebalance)(self);
    return result;
}

Here is the call graph for this function:

pop_front()

ITEM pop_front ( SELF * self )

static

Definition at line 189 of file template.h.

                                            {
    DEBUG_ASSERT(self);
    if (NS(ITEM_VECTORS, size)(&self->front) > 0) {
        ITEM result = NS(ITEM_VECTORS, pop)(&self->front);
        NS(SELF, rebalance)(self);
        return result;
    }
 
    ITEM result = NS(ITEM_VECTORS, pop_front)(&self->back);
    NS(SELF, rebalance)(self);
    return result;
}

Here is the call graph for this function:

push_back()

void push_back ( SELF * self, ITEM item )

static

Definition at line 183 of file template.h.

                                                       {
    DEBUG_ASSERT(self);
    NS(ITEM_VECTORS, push)(&self->back, item);
    NS(SELF, rebalance)(self);
}

Here is the call graph for this function:

push_front()

void push_front ( SELF * self, ITEM item )

static

Definition at line 177 of file template.h.

                                                        {
    DEBUG_ASSERT(self);
    NS(ITEM_VECTORS, push)(&self->front, item);
    NS(SELF, rebalance)(self);
}

Here is the call graph for this function:

rebalance()

void rebalance ( SELF * self )

static

Definition at line 85 of file template.h.

                                            {
    DEBUG_ASSERT(self);
 
    size_t front_size = NS(ITEM_VECTORS, size)(&self->front);
    size_t back_size = NS(ITEM_VECTORS, size)(&self->back);
    size_t total_size = front_size + back_size;
 
    if (!deque_rebalance_policy(total_size, front_size)) {
        return;
    }
 
    ITEM_VECTORS* source;
    ITEM_VECTORS* target;
    size_t source_size;
    size_t target_size;
 
    if (front_size > back_size + 1) {
        source = &self->front;
        target = &self->back;
        source_size = front_size;
        target_size = back_size;
    } else {
        DEBUG_ASSERT(back_size > front_size + 1)
        source = &self->back;
        target = &self->front;
        source_size = back_size;
        target_size = front_size;
    }
 
    size_t to_move = (source_size - target_size) / 2;
 
    NS(ITEM_VECTORS, reserve)(target, target_size + to_move);
 
    ITEM* source_data = NS(ITEM_VECTORS, data)(source);
    ITEM* target_data = NS(ITEM_VECTORS, data)(target);
 
    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));
 
    target->size += to_move;
    source->size -= to_move;
}

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

                                               {
    DEBUG_ASSERT(self);
    return NS(ITEM_VECTORS, size)(&self->front) + NS(ITEM_VECTORS, size)(&self->back);
}

Here is the call graph for this function: