fqueue.h

Go to the documentation of this file.

/*  fqueue.h
 *
 *  Copyright (C) 2023 abxh
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2.1 of the License, or (at your option) any later version.
 *  See the file LICENSE included with this distribution for more
 *  information. */
 
// macro definitions: {{{
 
#ifndef FQUEUE_H
#define FQUEUE_H
 
#include "is_pow2.h"       // is_pow2
#include "paste.h"         // PASTE, XPASTE, JOIN
#include "round_up_pow2.h" // round_up_pow2_32
 
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
 
#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)++)
 
#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)++)
 
#define fqueue_calc_sizeof(fqueue_name, capacity) \
    (uint32_t)(offsetof(struct fqueue_name, values) + capacity * sizeof(((struct fqueue_name *)0)->values[0]))
 
#define fqueue_calc_sizeof_overflows(fqueue_name, capacity) \
    (capacity > (UINT32_MAX - offsetof(struct fqueue_name, values)) / sizeof(((struct fqueue_name *)0)->values[0]))
 
#endif // FQUEUE_H
 
#ifndef NAME
#define NAME fqueue
#error "Must define NAME."
#else
#define FQUEUE_NAME NAME
#endif
 
#ifndef VALUE_TYPE
#define VALUE_TYPE int
#error "Must define VALUE_TYPE."
#endif
 
#define FQUEUE_TYPE        struct FQUEUE_NAME
#define FQUEUE_CALC_SIZEOF JOIN(FQUEUE_NAME, calc_sizeof)
#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: {{{
 
struct FQUEUE_NAME {
    uint32_t begin_index; 
    uint32_t end_index;   
    uint32_t count;       
    uint32_t capacity;    
    VALUE_TYPE values[];  
};
 
// }}}
 
// function definitions: {{{
 
static inline 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;
}
 
static inline 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;
}
 
static inline void JOIN(FQUEUE_NAME, destroy)(FQUEUE_TYPE *self)
{
    assert(self != NULL);
 
    free(self);
}
 
static inline bool JOIN(FQUEUE_NAME, is_empty)(const FQUEUE_TYPE *self)
{
    assert(self != NULL);
 
    return self->count == 0;
}
 
static inline bool JOIN(FQUEUE_NAME, is_full)(const FQUEUE_TYPE *self)
{
    assert(self != NULL);
 
    return self->count == self->capacity;
}
 
static inline 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];
}
 
static inline 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];
}
 
static inline 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];
}
 
static inline VALUE_TYPE JOIN(FQUEUE_NAME, peek)(const FQUEUE_TYPE *self)
{
    return JOIN(FQUEUE_NAME, get_front)(self);
}
 
static inline 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;
}
 
static inline 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;
}
 
static inline void JOIN(FQUEUE_NAME, clear)(FQUEUE_TYPE *self)
{
    assert(self != NULL);
 
    self->count = 0;
    self->begin_index = self->end_index = 0;
}
 
static inline 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;
}
 
// }}}
 
// macro undefs: {{{
 
#undef NAME
#undef VALUE_TYPE
 
#undef FQUEUE_NAME
#undef FQUEUE_TYPE
#undef FQUEUE_CALC_SIZEOF
#undef FQUEUE_INIT
#undef FQUEUE_IS_EMPTY
#undef FQUEUE_IS_FULL
 
// }}}
 
// vim: ft=c fdm=marker