45#define fqueue_for_each(self, index, value) \
46 for ((index) = 0; (index) < (self)->count \
47 && ((value) = (self)->values[((self)->begin_index + (index)) & ((self)->capacity - 1)], true); \
60#define fqueue_for_each_reverse(self, index, value) \
61 for ((index) = 0; (index) < (self)->count \
62 && ((value) = (self)->values[((self)->end_index - 1 - (index)) & ((self)->capacity - 1)], true); \
75#define fqueue_calc_sizeof(fqueue_name, capacity) \
76 (uint32_t)(offsetof(struct fqueue_name, values) + capacity * sizeof(((struct fqueue_name *)0)->values[0]))
88#define fqueue_calc_sizeof_overflows(fqueue_name, capacity) \
89 (capacity > (UINT32_MAX - offsetof(struct fqueue_name, values)) / sizeof(((struct fqueue_name *)0)->values[0]))
102#error "Must define NAME."
104#define FQUEUE_NAME NAME
115#define VALUE_TYPE int
116#error "Must define VALUE_TYPE."
120#define FQUEUE_TYPE struct FQUEUE_NAME
121#define FQUEUE_CALC_SIZEOF JOIN(FQUEUE_NAME, calc_sizeof)
122#define FQUEUE_INIT JOIN(FQUEUE_NAME, init)
123#define FQUEUE_IS_EMPTY JOIN(FQUEUE_NAME, is_empty)
124#define FQUEUE_IS_FULL JOIN(FQUEUE_NAME, is_full)
152static inline FQUEUE_TYPE *
JOIN(FQUEUE_NAME, init)(FQUEUE_TYPE *self,
const uint32_t pow2_capacity)
155 assert(
is_pow2(pow2_capacity));
157 self->begin_index = self->end_index = 0;
159 self->capacity = pow2_capacity;
174static inline FQUEUE_TYPE *
JOIN(FQUEUE_NAME, create)(
const uint32_t min_capacity)
176 if (min_capacity == 0 || min_capacity > UINT32_MAX / 2 + 1) {
188 FQUEUE_TYPE *self = (FQUEUE_TYPE *)calloc(1, size);
194 FQUEUE_INIT(self, capacity);
206static inline void JOIN(FQUEUE_NAME, destroy)(FQUEUE_TYPE *self)
208 assert(self != NULL);
220static inline bool JOIN(FQUEUE_NAME, is_empty)(
const FQUEUE_TYPE *self)
222 assert(self != NULL);
224 return self->count == 0;
234static inline bool JOIN(FQUEUE_NAME, is_full)(
const FQUEUE_TYPE *self)
236 assert(self != NULL);
238 return self->count == self->capacity;
252static inline VALUE_TYPE JOIN(FQUEUE_NAME, at)(
const FQUEUE_TYPE *self,
const uint32_t index)
254 assert(self != NULL);
255 assert(index < self->count);
257 const uint32_t index_mask = (self->capacity - 1);
259 return self->values[(self->begin_index + index) & index_mask];
271 assert(self != NULL);
272 assert(!FQUEUE_IS_EMPTY(self));
274 return self->values[self->begin_index];
286 assert(self != NULL);
287 assert(!FQUEUE_IS_EMPTY(self));
289 const uint32_t index_mask = (self->capacity - 1);
291 return self->values[(self->end_index - 1) & index_mask];
303 return JOIN(FQUEUE_NAME, get_front)(self);
312static inline bool JOIN(FQUEUE_NAME, enqueue)(FQUEUE_TYPE *self,
const VALUE_TYPE value)
314 assert(self != NULL);
315 assert(!FQUEUE_IS_FULL(self));
317 const uint32_t index_mask = (self->capacity - 1);
319 self->values[self->end_index] = value;
321 self->end_index &= index_mask;
336 assert(self != NULL);
337 assert(!FQUEUE_IS_EMPTY(self));
339 const uint32_t index_mask = (self->capacity - 1);
341 const VALUE_TYPE value = self->values[self->begin_index];
343 self->begin_index &= index_mask;
354static inline void JOIN(FQUEUE_NAME, clear)(FQUEUE_TYPE *self)
356 assert(self != NULL);
359 self->begin_index = self->end_index = 0;
368static inline void JOIN(FQUEUE_NAME, copy)(FQUEUE_TYPE *restrict dest_ptr,
const FQUEUE_TYPE *restrict src_ptr)
370 assert(src_ptr != NULL);
371 assert(dest_ptr != NULL);
372 assert(src_ptr->count <= dest_ptr->capacity);
373 assert(FQUEUE_IS_EMPTY(dest_ptr));
375 const uint32_t src_begin_index = src_ptr->begin_index;
376 const uint32_t src_index_mask = src_ptr->capacity - 1;
378 for (uint32_t i = 0; i < src_ptr->count; i++) {
379 dest_ptr->values[i] = src_ptr->values[(src_begin_index + i) & src_index_mask];
382 dest_ptr->count = src_ptr->count;
383 dest_ptr->begin_index = 0;
384 dest_ptr->end_index = src_ptr->count;
396#undef FQUEUE_CALC_SIZEOF
398#undef FQUEUE_IS_EMPTY
#define VALUE_TYPE
The value type. This must be manually defined before including this header file.
Definition fhashtable.h:144
#define fqueue_calc_sizeof(fqueue_name, capacity)
Calculate the size of the queue struct. No overflow checks.
Definition fqueue.h:75
#define fqueue_calc_sizeof_overflows(fqueue_name, capacity)
Check for a given capacity, if the equivalent size of the queue struct overflows.
Definition fqueue.h:88
#define VALUE_TYPE
Queue value type. This must be manually defined before including this header file.
Definition fqueue.h:115
Check if a number is a power of two.
static size_t is_pow2(const size_t x)
Check if a number is a power of two.
Definition is_pow2.h:34
C preprocessor macros for pasting tokens together.
#define JOIN(a, b)
First expand tokens, then paste them together with a _ in between.
Definition paste.h:35
Round up to the next power of two.
static uint32_t round_up_pow2_32(uint32_t x)
Definition round_up_pow2.h:39
uint32_t count
Number of values.
Definition fqueue.h:137
uint32_t end_index
Index used to track the back of the queue.
Definition fqueue.h:136
uint32_t begin_index
Index used to track the front of the queue.
Definition fqueue.h:135
uint32_t capacity
Maximum number of values allocated for.
Definition fqueue.h:138