fqueue_template.h

Go to the documentation of this file.

 
#ifdef __cplusplus
#ifdef __GNUC__
#define restrict __restrict__
#else
#define restrict
#endif
extern "C" {
#endif
 
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
 
// macro definitions: {{{

#ifndef PASTE
#define PASTE(a, b) a##b
#endif

#ifndef XPASTE
#define XPASTE(a, b) PASTE(a, b)
#endif

#ifndef JOIN
#define JOIN(a, b) XPASTE(a, XPASTE(_, b))
#endif

#ifndef IS_POW2
#define IS_POW2(X) ((X) != 0 && ((X) & ((X) - 1)) == 0)
#endif

#ifndef FQUEUE_FOR_EACH
#define FQUEUE_FOR_EACH(self, index, value)                                                                          \
    for ((index) = 0; (index) < (self)->count                                                                        \
                      && ((value) = (self)->values[((self)->begin_index + (index)) & ((self)->capacity - 1)], true); \
         (index)++)
#endif

#ifndef FQUEUE_FOR_EACH_REVERSE
#define FQUEUE_FOR_EACH_REVERSE(self, index, value)                                                                    \
    for ((index) = 0; (index) < (self)->count                                                                          \
                      && ((value) = (self)->values[((self)->end_index - 1 - (index)) & ((self)->capacity - 1)], true); \
         (index)++)
#endif

#ifndef FQUEUE_CALC_SIZEOF
#define FQUEUE_CALC_SIZEOF(fqueue_name, capacity) \
    (uint32_t)(offsetof(struct fqueue_name, values) + capacity * sizeof(((struct fqueue_name *)0)->values[0]))
#endif

#ifndef FQUEUE_CALC_SIZEOF_OVERFLOWS
#define FQUEUE_CALC_SIZEOF_OVERFLOWS(fqueue_name, capacity) \
    (capacity > (UINT32_MAX - offsetof(struct fqueue_name, values)) / sizeof(((struct fqueue_name *)0)->values[0]))
#endif

#ifndef NAME
#define NAME fqueue
#error "Must define NAME."
#else
#define FQUEUE_NAME NAME
#endif

#ifndef VALUE_TYPE
#define VALUE_TYPE int
#define FUNCTION_DEFINITIONS
#define TYPE_DEFINITIONS
#error "Must define VALUE_TYPE."
#endif

#ifndef FUNCTION_LINKAGE
#define FUNCTION_LINKAGE
#endif

#define FQUEUE_TYPE     struct FQUEUE_NAME
#define FQUEUE_INIT     JOIN(FQUEUE_NAME, init)
#define FQUEUE_IS_EMPTY JOIN(FQUEUE_NAME, is_empty)
#define FQUEUE_IS_FULL  JOIN(FQUEUE_NAME, is_full)
 
// }}}
 
// type definitions: {{{

#ifdef TYPE_DEFINITIONS

struct FQUEUE_NAME {
    uint32_t begin_index; 
    uint32_t end_index;   
    uint32_t count;       
    uint32_t capacity;    
    VALUE_TYPE values[];  
};
 
#endif
 
// }}}
 
// function declarations: {{{

FUNCTION_LINKAGE FQUEUE_TYPE *JOIN(FQUEUE_NAME, init)(FQUEUE_TYPE *self, const uint32_t pow2_capacity);

FUNCTION_LINKAGE FQUEUE_TYPE *JOIN(FQUEUE_NAME, create)(const uint32_t min_capacity);

FUNCTION_LINKAGE void JOIN(FQUEUE_NAME, destroy)(FQUEUE_TYPE *self);

FUNCTION_LINKAGE bool JOIN(FQUEUE_NAME, is_empty)(const FQUEUE_TYPE *self);

FUNCTION_LINKAGE bool JOIN(FQUEUE_NAME, is_full)(const FQUEUE_TYPE *self);

FUNCTION_LINKAGE VALUE_TYPE JOIN(FQUEUE_NAME, at)(const FQUEUE_TYPE *self, const uint32_t index);

FUNCTION_LINKAGE VALUE_TYPE JOIN(FQUEUE_NAME, get_front)(const FQUEUE_TYPE *self);

FUNCTION_LINKAGE VALUE_TYPE JOIN(FQUEUE_NAME, get_back)(const FQUEUE_TYPE *self);

FUNCTION_LINKAGE VALUE_TYPE JOIN(FQUEUE_NAME, peek)(const FQUEUE_TYPE *self);

FUNCTION_LINKAGE bool JOIN(FQUEUE_NAME, enqueue)(FQUEUE_TYPE *self, const VALUE_TYPE value);

FUNCTION_LINKAGE VALUE_TYPE JOIN(FQUEUE_NAME, dequeue)(FQUEUE_TYPE *self);

FUNCTION_LINKAGE void JOIN(FQUEUE_NAME, clear)(FQUEUE_TYPE *self);

FUNCTION_LINKAGE void JOIN(FQUEUE_NAME, copy)(FQUEUE_TYPE *restrict dest_ptr, const FQUEUE_TYPE *restrict src_ptr);
 
// }}}
 
// function definitions: {{{

#ifdef FUNCTION_DEFINITIONS
 
#include "round_up_pow2_32.h" // round_up_pow2_32
 
FUNCTION_LINKAGE FQUEUE_TYPE *JOIN(FQUEUE_NAME, init)(FQUEUE_TYPE *self, const uint32_t pow2_capacity)
{
    assert(self);
    assert(IS_POW2(pow2_capacity));
 
    self->begin_index = self->end_index = 0;
    self->count = 0;
    self->capacity = pow2_capacity;
 
    return self;
}
 
FUNCTION_LINKAGE FQUEUE_TYPE *JOIN(FQUEUE_NAME, create)(const uint32_t min_capacity)
{
    if (min_capacity == 0 || min_capacity > UINT32_MAX / 2 + 1) {
        return NULL;
    }
 
    const uint32_t capacity = round_up_pow2_32(min_capacity);
 
    if (FQUEUE_CALC_SIZEOF_OVERFLOWS(FQUEUE_NAME, capacity)) {
        return NULL;
    }
 
    const uint32_t size = FQUEUE_CALC_SIZEOF(FQUEUE_NAME, capacity);
 
    FQUEUE_TYPE *self = (FQUEUE_TYPE *)calloc(1, size);
 
    if (!self) {
        return NULL;
    }
 
    FQUEUE_INIT(self, capacity);
 
    return self;
}
 
FUNCTION_LINKAGE void JOIN(FQUEUE_NAME, destroy)(FQUEUE_TYPE *self)
{
    assert(self != NULL);
 
    free(self);
}
 
FUNCTION_LINKAGE bool JOIN(FQUEUE_NAME, is_empty)(const FQUEUE_TYPE *self)
{
    assert(self != NULL);
 
    return self->count == 0;
}
 
FUNCTION_LINKAGE bool JOIN(FQUEUE_NAME, is_full)(const FQUEUE_TYPE *self)
{
    assert(self != NULL);
 
    return self->count == self->capacity;
}
 
FUNCTION_LINKAGE VALUE_TYPE JOIN(FQUEUE_NAME, at)(const FQUEUE_TYPE *self, const uint32_t index)
{
    assert(self != NULL);
    assert(index < self->count);
 
    const uint32_t index_mask = (self->capacity - 1);
 
    return self->values[(self->begin_index + index) & index_mask];
}
 
FUNCTION_LINKAGE VALUE_TYPE JOIN(FQUEUE_NAME, get_front)(const FQUEUE_TYPE *self)
{
    assert(self != NULL);
    assert(!FQUEUE_IS_EMPTY(self));
 
    return self->values[self->begin_index];
}
 
FUNCTION_LINKAGE VALUE_TYPE JOIN(FQUEUE_NAME, get_back)(const FQUEUE_TYPE *self)
{
    assert(self != NULL);
    assert(!FQUEUE_IS_EMPTY(self));
 
    const uint32_t index_mask = (self->capacity - 1);
 
    return self->values[(self->end_index - 1) & index_mask];
}
 
FUNCTION_LINKAGE VALUE_TYPE JOIN(FQUEUE_NAME, peek)(const FQUEUE_TYPE *self)
{
    return JOIN(FQUEUE_NAME, get_front)(self);
}
 
FUNCTION_LINKAGE bool JOIN(FQUEUE_NAME, enqueue)(FQUEUE_TYPE *self, const VALUE_TYPE value)
{
    assert(self != NULL);
    assert(!FQUEUE_IS_FULL(self));
 
    const uint32_t index_mask = (self->capacity - 1);
 
    self->values[self->end_index] = value;
    self->end_index++;
    self->end_index &= index_mask;
    self->count++;
 
    return true;
}
 
FUNCTION_LINKAGE VALUE_TYPE JOIN(FQUEUE_NAME, dequeue)(FQUEUE_TYPE *self)
{
    assert(self != NULL);
    assert(!FQUEUE_IS_EMPTY(self));
 
    const uint32_t index_mask = (self->capacity - 1);
 
    const VALUE_TYPE value = self->values[self->begin_index];
    self->begin_index++;
    self->begin_index &= index_mask;
    self->count--;
 
    return value;
}
 
FUNCTION_LINKAGE void JOIN(FQUEUE_NAME, clear)(FQUEUE_TYPE *self)
{
    assert(self != NULL);
 
    self->count = 0;
    self->begin_index = self->end_index = 0;
}
 
FUNCTION_LINKAGE void JOIN(FQUEUE_NAME, copy)(FQUEUE_TYPE *restrict dest_ptr, const FQUEUE_TYPE *restrict src_ptr)
{
    assert(src_ptr != NULL);
    assert(dest_ptr != NULL);
    assert(src_ptr->count <= dest_ptr->capacity);
    assert(FQUEUE_IS_EMPTY(dest_ptr));
 
    const uint32_t src_begin_index = src_ptr->begin_index;
    const uint32_t src_index_mask = src_ptr->capacity - 1;
 
    for (uint32_t i = 0; i < src_ptr->count; i++) {
        dest_ptr->values[i] = src_ptr->values[(src_begin_index + i) & src_index_mask];
    }
 
    dest_ptr->count = src_ptr->count;
    dest_ptr->begin_index = 0;
    dest_ptr->end_index = src_ptr->count;
}
 
#endif
 
// }}}
 
// macro undefs: {{{
 
#undef NAME
#undef VALUE_TYPE
#undef FUNCTION_LINKAGE
#undef FUNCTION_DEFINITIONS
#undef TYPE_DEFINITIONS
 
#undef FQUEUE_NAME
#undef FQUEUE_TYPE
#undef FQUEUE_CALC_SIZEOF
#undef FQUEUE_INIT
#undef FQUEUE_IS_EMPTY
#undef FQUEUE_IS_FULL
 
// }}}
 
#ifdef __cplusplus
}
#endif
 
// vim: ft=c fdm=marker