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/container/vector/dynamic/template.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	ITEM_VECTORS   NS(NAME, item_vectors)
#define	INTERNAL_NAME   ITEM_VECTORS
#define	INVARIANT_CHECK(self)
#define	ITER   NS(SELF, iter)
#define	ITER_CONST   NS(SELF, iter_const)

Typedefs
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 (size_t front_and_back_capacity, ref alloc_ref)
static DC_PUBLIC SELF	clone (SELF const *other)
static DC_PUBLIC size_t	size (SELF const *self)
static DC_PUBLIC bool	empty (SELF const *self)
static DC_PUBLIC void	rebalance (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 void	push_front (SELF *self, ITEM item)
static DC_PUBLIC void	push_back (SELF *self, ITEM item)
static DC_PUBLIC ITEM	pop_front (SELF *self)
static DC_PUBLIC ITEM	pop_back (SELF *self)
static DC_PUBLIC bool	empty_item (ITEM *const *item)
static DC_PUBLIC ITEM *	next (ITER *iter)
static DC_PUBLIC bool	empty (ITER const *iter)
static DC_PUBLIC ITER	get_iter (SELF *self)
static DC_PUBLIC bool	empty_item (ITEM const *const *item)
static DC_PUBLIC ITEM const *	next (ITER_CONST *iter)
static DC_PUBLIC bool	empty (ITER_CONST const *iter)
static DC_PUBLIC ITER_CONST	get_iter_const (SELF const *self)
static DC_PUBLIC void	delete (SELF *self)
static DC_PUBLIC void	debug (SELF const *self, dc_debug_fmt fmt, FILE *stream)
	DC_TRAIT_QUEUE (SELF)

Macro Definition Documentation

INTERNAL_NAME

#define INTERNAL_NAME   ITEM_VECTORS

Definition at line 52 of file template.h.

INVARIANT_CHECK

#define INVARIANT_CHECK

(

self

)

Value:

DC_ASSUME(self);

Definition at line 67 of file template.h.

ITEM

#define ITEM   item_t

Definition at line 19 of file template.h.

ITEM_CLONE

#define ITEM_CLONE   item_clone

Definition at line 23 of file template.h.

ITEM_DEBUG

#define ITEM_DEBUG   item_debug

Definition at line 25 of file template.h.

ITEM_DELETE

#define ITEM_DELETE   item_delete

Definition at line 21 of file template.h.

ITEM_VECTORS

#define ITEM_VECTORS   NS(NAME, item_vectors)

Definition at line 44 of file template.h.

ITER

#define ITER   NS(SELF, iter)

Definition at line 226 of file template.h.

ITER_CONST

#define ITER_CONST   NS(SELF, iter_const)

Definition at line 273 of file template.h.

Typedef Documentation

item

typedef ITEM const* item

Definition at line 227 of file template.h.

Function Documentation

clone()

DC_PUBLIC SELF clone ( SELF const * other )

static

Definition at line 88 of file template.h.

                                                         {
    INVARIANT_CHECK(other);
    return (SELF){
        .front = NS(ITEM_VECTORS, clone)(&other->front),
        .back = NS(ITEM_VECTORS, clone)(&other->back),
        .derive_c_deque = dc_gdb_marker_new(),
        .iterator_invalidation_tracker = mutation_tracker_new(),
    };
}

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

                                                                                        {
    fprintf(stream, DC_EXPAND_STRING(SELF) "@%p {\n", self);
    fmt = dc_debug_fmt_scope_begin(fmt);
    dc_debug_fmt_print(fmt, stream, "size: %lu,\n", NS(SELF, size)(self));
 
    dc_debug_fmt_print(fmt, stream, "front: ");
    NS(ITEM_VECTORS, debug)(&self->front, fmt, stream);
    fprintf(stream, ",\n");
 
    dc_debug_fmt_print(fmt, stream, "back: ");
    NS(ITEM_VECTORS, debug)(&self->back, fmt, stream);
    fprintf(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 322 of file template.h.

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

empty() [1/3]

DC_PUBLIC bool empty ( ITER const * iter )

static

Definition at line 257 of file template.h.

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

empty() [2/3]

DC_PUBLIC bool empty ( ITER_CONST const * iter )

static

Definition at line 304 of file template.h.

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

empty() [3/3]

DC_PUBLIC bool empty ( SELF const * self )

static

Definition at line 103 of file template.h.

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

empty_item() [1/2]

DC_PUBLIC bool empty_item ( ITEM *const * item )

static

Definition at line 229 of file template.h.

{ return *item == NULL; }

empty_item() [2/2]

DC_PUBLIC bool empty_item ( ITEM const *const * item )

static

Definition at line 276 of file template.h.

{ return *item == NULL; }

get_iter()

DC_PUBLIC ITER get_iter ( SELF * self )

static

Definition at line 264 of file template.h.

                                                     {
    DC_ASSUME(self);
    return (ITER){.deque = self,
                  .pos = 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 311 of file template.h.

                                                                       {
    DC_ASSUME(self);
    return (ITER_CONST){
        .deque = self,
        .pos = 0,
        .version = mutation_tracker_get(&self->iterator_invalidation_tracker),
    };
}

ITEM_CLONE()

item_t ITEM_CLONE ( item_t const * self )

static

Definition at line 24 of file template.h.

{ return *self; }

ITEM_DEBUG()

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

static

Definition at line 26 of file template.h.

{}

ITEM_DELETE()

void ITEM_DELETE ( item_t * )

static

Definition at line 22 of file template.h.

{}

new()

DC_PUBLIC SELF new ( ref alloc_ref )

static

Definition at line 69 of file template.h.

                                                              {
    return (SELF){
        .front = NS(ITEM_VECTORS, new)(alloc_ref),
        .back = NS(ITEM_VECTORS, new)(alloc_ref),
        .derive_c_deque = dc_gdb_marker_new(),
        .iterator_invalidation_tracker = mutation_tracker_new(),
    };
}

new_with_capacity()

DC_PUBLIC SELF new_with_capacity ( size_t front_and_back_capacity, ref alloc_ref )

static

Definition at line 78 of file template.h.

                                                                            {
    return (SELF){
        .front = NS(ITEM_VECTORS, new_with_capacity)(front_and_back_capacity, alloc_ref),
        .back = NS(ITEM_VECTORS, new_with_capacity)(front_and_back_capacity, alloc_ref),
        .derive_c_deque = dc_gdb_marker_new(),
        .iterator_invalidation_tracker = mutation_tracker_new(),
    };
}

next() [1/2]

DC_PUBLIC ITEM * next ( ITER * iter )

static

Definition at line 237 of file template.h.

                                                  {
    DC_ASSUME(iter);
    mutation_version_check(&iter->version);
    size_t const front_size = NS(ITEM_VECTORS, size)(&iter->deque->front);
    size_t const back_size = NS(ITEM_VECTORS, size)(&iter->deque->back);
    size_t const 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;
}

next() [2/2]

DC_PUBLIC ITEM const * next ( ITER_CONST * iter )

static

Definition at line 284 of file template.h.

                                                                    {
    DC_ASSUME(iter);
    mutation_version_check(&iter->version);
    size_t const front_size = NS(ITEM_VECTORS, size)(&iter->deque->front);
    size_t const back_size = NS(ITEM_VECTORS, size)(&iter->deque->back);
    size_t const 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;
}

pop_back()

DC_PUBLIC ITEM pop_back ( SELF * self )

static

Definition at line 205 of file template.h.

                                                     {
    INVARIANT_CHECK(self);
    mutation_tracker_mutate(&self->iterator_invalidation_tracker);
    if (NS(ITEM_VECTORS, size)(&self->back) > 0) {
        ITEM result = NS(ITEM_VECTORS, pop)(&self->back);
        NS(SELF, rebalance)(self);
        return result;
    }
 
    // Back is empty, need to pop from front
    // Rebalance first to move elements to back, then pop
    // No need to rebalance again after pop since we just rebalanced
    if (NS(ITEM_VECTORS, size)(&self->front) > 0) {
        NS(SELF, rebalance)(self);
        return NS(ITEM_VECTORS, pop)(&self->back);
    }
 
    // Both sides empty - should not happen if deque is non-empty
    DC_UNREACHABLE("Cannot pop from empty deque");
}

pop_front()

DC_PUBLIC ITEM pop_front ( SELF * self )

static

Definition at line 184 of file template.h.

                                                      {
    INVARIANT_CHECK(self);
    mutation_tracker_mutate(&self->iterator_invalidation_tracker);
    if (NS(ITEM_VECTORS, size)(&self->front) > 0) {
        ITEM result = NS(ITEM_VECTORS, pop)(&self->front);
        NS(SELF, rebalance)(self);
        return result;
    }
 
    // Front is empty, need to pop from back
    // Rebalance first to move elements to front, then pop
    // No need to rebalance again after pop since we just rebalanced
    if (NS(ITEM_VECTORS, size)(&self->back) > 0) {
        NS(SELF, rebalance)(self);
        return NS(ITEM_VECTORS, pop)(&self->front);
    }
 
    // Both sides empty - should not happen if deque is non-empty
    DC_UNREACHABLE("Cannot pop from empty deque");
}

push_back()

DC_PUBLIC void push_back ( SELF * self, ITEM item )

static

Definition at line 177 of file template.h.

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

push_front()

DC_PUBLIC void push_front ( SELF * self, ITEM item )

static

Definition at line 170 of file template.h.

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

rebalance()

DC_PUBLIC void rebalance ( SELF * self )

static

Definition at line 108 of file template.h.

                                                      {
    INVARIANT_CHECK(self);
    mutation_tracker_mutate(&self->iterator_invalidation_tracker);
 
    size_t const front_size = NS(ITEM_VECTORS, size)(&self->front);
    size_t const back_size = NS(ITEM_VECTORS, size)(&self->back);
    size_t const total_size = front_size + back_size;
 
    // Let the rebalance policy decide if we should rebalance
    if (!_dc_deque_rebalance_policy(total_size, front_size, back_size)) {
        return;
    }
 
    ITEM_VECTORS* source;
    ITEM_VECTORS* target;
    size_t source_size;
    size_t target_size;
 
    if (front_size > back_size) {
        source = &self->front;
        target = &self->back;
        source_size = front_size;
        target_size = back_size;
    } else {
        source = &self->back;
        target = &self->front;
        source_size = back_size;
        target_size = front_size;
    }
 
    size_t to_move = (source_size - target_size) / 2;
    // If target is empty, we must move at least 1 element (or all if only 1 exists)
    if (target_size == 0 && source_size > 0) {
        to_move = (source_size + 1) / 2; // Move at least half, or 1 if only 1 element
    }
    NS(ITEM_VECTORS, transfer_reverse)(source, target, to_move);
}

size()

DC_PUBLIC size_t size ( SELF const * self )

static

Definition at line 98 of file template.h.

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

try_read_from_back()

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

static

Definition at line 158 of file template.h.

                                                                                          {
    return NS(SELF, try_read_from_front)(self, NS(SELF, size)(self) - 1 - index);
}

try_read_from_front()

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

static

Definition at line 146 of file template.h.

                                                                                           {
    INVARIANT_CHECK(self);
 
    if (index < NS(ITEM_VECTORS, size)(&self->front)) {
        size_t front_index = NS(ITEM_VECTORS, size)(&self->front) - 1 - index;
        return NS(ITEM_VECTORS, read)(&self->front, front_index);
    }
 
    size_t back_index = index - NS(ITEM_VECTORS, size)(&self->front);
    return NS(ITEM_VECTORS, try_read)(&self->back, back_index);
}

try_write_from_back()

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

static

Definition at line 166 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 162 of file template.h.

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