fpqueue_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 <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 FPQUEUE_LEFT_CHILD
#define FPQUEUE_LEFT_CHILD(index) (2 * (index) + 1)
#endif

#ifndef FPQUEUE_RIGHT_CHILD
#define FPQUEUE_RIGHT_CHILD(index) (2 * (index) + 2)
#endif

#ifndef FPQUEUE_PARENT
#define FPQUEUE_PARENT(index) (((index) - 1) / 2)
#endif

#ifndef FPQUEUE_FOR_EACH
#define FPQUEUE_FOR_EACH(self, index, value_) \
    for ((index) = 0; (index) < (self)->count && ((value_) = (self)->elements[(index)].value, true); (index)++)
#endif

#ifndef FPQUEUE_CALC_SIZEOF
#define FPQUEUE_CALC_SIZEOF(fpqueue_name, capacity) \
    (uint32_t)(offsetof(struct fpqueue_name, elements) + capacity * sizeof(((struct fpqueue_name *)0)->elements[0]))
#endif

#ifndef FPQUEUE_CALC_SIZEOF_OVERFLOWS
#define FPQUEUE_CALC_SIZEOF_OVERFLOWS(fpqueue_name, capacity) \
    (capacity                                                 \
     > (UINT32_MAX - offsetof(struct fpqueue_name, elements)) / sizeof(((struct fpqueue_name *)0)->elements[0]))
#endif

#ifndef NAME
#error "Must define NAME."
#else
#define FPQUEUE_NAME NAME
#endif

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

#ifndef FUNCTION_LINKAGE
#define FUNCTION_LINKAGE
#endif

#define FPQUEUE_TYPE         struct FPQUEUE_NAME
#define FPQUEUE_ELEMENT_TYPE struct JOIN(FPQUEUE_NAME, element)
#define FPQUEUE_INIT         JOIN(FPQUEUE_NAME, init)
#define FPQUEUE_IS_EMPTY     JOIN(FPQUEUE_NAME, is_empty)
#define FPQUEUE_IS_FULL      JOIN(FPQUEUE_NAME, is_full)
#define FPQUEUE_UPHEAP       JOIN(internal, JOIN(FPQUEUE_NAME, upheap))
#define FPQUEUE_DOWNHEAP     JOIN(internal, JOIN(FPQUEUE_NAME, downheap))
 
// }}}
 
// type definitions: {{{

#ifdef TYPE_DEFINITIONS

struct JOIN(FPQUEUE_NAME, element) {
    uint32_t priority; 
    VALUE_TYPE value;  
};

struct FPQUEUE_NAME {
    uint32_t count;                  
    uint32_t capacity;               
    FPQUEUE_ELEMENT_TYPE elements[]; 
};
 
#endif
 
// }}}
 
// function declarations: {{{

FUNCTION_LINKAGE FPQUEUE_TYPE *JOIN(FPQUEUE_NAME, init)(FPQUEUE_TYPE *self, const uint32_t capacity);

FUNCTION_LINKAGE FPQUEUE_TYPE *JOIN(FPQUEUE_NAME, create)(const uint32_t capacity);

FUNCTION_LINKAGE void JOIN(FPQUEUE_NAME, destroy)(FPQUEUE_TYPE *self);

FUNCTION_LINKAGE bool JOIN(FPQUEUE_NAME, is_empty)(const FPQUEUE_TYPE *self);

FUNCTION_LINKAGE bool JOIN(FPQUEUE_NAME, is_full)(const FPQUEUE_TYPE *self);

FUNCTION_LINKAGE VALUE_TYPE JOIN(FPQUEUE_NAME, get_max)(const FPQUEUE_TYPE *self);

FUNCTION_LINKAGE VALUE_TYPE JOIN(FPQUEUE_NAME, peek)(const FPQUEUE_TYPE *self);

FUNCTION_LINKAGE VALUE_TYPE JOIN(FPQUEUE_NAME, pop_max)(FPQUEUE_TYPE *self);

FUNCTION_LINKAGE void JOIN(FPQUEUE_NAME, push)(FPQUEUE_TYPE *self, VALUE_TYPE value, const uint32_t priority);

FUNCTION_LINKAGE void JOIN(FPQUEUE_NAME, push)(FPQUEUE_TYPE *self, VALUE_TYPE value, const uint32_t priority);

FUNCTION_LINKAGE void JOIN(FPQUEUE_NAME, clear)(FPQUEUE_TYPE *self);

FUNCTION_LINKAGE void JOIN(FPQUEUE_NAME, copy)(FPQUEUE_TYPE *restrict dest_ptr, const FPQUEUE_TYPE *restrict src_ptr);
 
// @}}}
 
// function definitions: {{{

#ifdef FUNCTION_DEFINITIONS

 
/* push a node down the heap. for restoring the heap property after insertion */
static inline void JOIN(internal, JOIN(FPQUEUE_NAME, downheap))(FPQUEUE_TYPE *self, const uint32_t index);
 
/* push a node up the heap. for restoring the heap property after deletion */
static inline void JOIN(internal, JOIN(FPQUEUE_NAME, upheap))(FPQUEUE_TYPE *self, uint32_t index);

 
FUNCTION_LINKAGE FPQUEUE_TYPE *JOIN(FPQUEUE_NAME, init)(FPQUEUE_TYPE *self, const uint32_t capacity)
{
    assert(self);
 
    self->count = 0;
    self->capacity = capacity;
 
    return self;
}
 
FUNCTION_LINKAGE FPQUEUE_TYPE *JOIN(FPQUEUE_NAME, create)(const uint32_t capacity)
{
    if (capacity == 0 || FPQUEUE_CALC_SIZEOF_OVERFLOWS(FPQUEUE_NAME, capacity)) {
        return NULL;
    }
 
    const uint32_t size = FPQUEUE_CALC_SIZEOF(FPQUEUE_NAME, capacity);
 
    FPQUEUE_TYPE *self = (FPQUEUE_TYPE *)calloc(1, size);
 
    if (!self) {
        return NULL;
    }
 
    FPQUEUE_INIT(self, capacity);
 
    return self;
}
 
FUNCTION_LINKAGE void JOIN(FPQUEUE_NAME, destroy)(FPQUEUE_TYPE *self)
{
    assert(self != NULL);
 
    free(self);
}
 
FUNCTION_LINKAGE bool JOIN(FPQUEUE_NAME, is_empty)(const FPQUEUE_TYPE *self)
{
    assert(self != NULL);
 
    return self->count == 0;
}
 
FUNCTION_LINKAGE bool JOIN(FPQUEUE_NAME, is_full)(const FPQUEUE_TYPE *self)
{
    assert(self != NULL);
 
    return self->count == self->capacity;
}
 
FUNCTION_LINKAGE VALUE_TYPE JOIN(FPQUEUE_NAME, get_max)(const FPQUEUE_TYPE *self)
{
    assert(self != NULL);
    assert(FPQUEUE_IS_EMPTY(self) == false);
 
    return self->elements[0].value;
}
 
FUNCTION_LINKAGE VALUE_TYPE JOIN(FPQUEUE_NAME, peek)(const FPQUEUE_TYPE *self)
{
    return JOIN(FPQUEUE_NAME, get_max)(self);
}
 
FUNCTION_LINKAGE VALUE_TYPE JOIN(FPQUEUE_NAME, pop_max)(FPQUEUE_TYPE *self)
{
    assert(self != NULL);
    assert(FPQUEUE_IS_EMPTY(self) == false);
 
    VALUE_TYPE max_priority_value = self->elements[0].value;
 
    self->elements[0] = self->elements[self->count - 1];
 
    self->count--;
 
    JOIN(internal, JOIN(FPQUEUE_NAME, downheap))(self, 0);
 
    return max_priority_value;
}
 
FUNCTION_LINKAGE void JOIN(FPQUEUE_NAME, push)(FPQUEUE_TYPE *self, VALUE_TYPE value, const uint32_t priority)
{
    assert(self != NULL);
    assert(FPQUEUE_IS_FULL(self) == false);
 
    const uint32_t index = self->count;
 
    self->elements[index] = (FPQUEUE_ELEMENT_TYPE){.priority = priority, .value = value};
 
    self->count++;
 
    JOIN(internal, JOIN(FPQUEUE_NAME, upheap))(self, index);
}
 
FUNCTION_LINKAGE void JOIN(FPQUEUE_NAME, clear)(FPQUEUE_TYPE *self)
{
    assert(self != NULL);
 
    self->count = 0;
}
 
FUNCTION_LINKAGE void JOIN(FPQUEUE_NAME, copy)(FPQUEUE_TYPE *restrict dest_ptr, const FPQUEUE_TYPE *restrict src_ptr)
{
    assert(src_ptr != NULL);
    assert(dest_ptr != NULL);
    assert(src_ptr->count <= dest_ptr->capacity);
    assert(FPQUEUE_IS_EMPTY(dest_ptr));
 
    for (uint32_t i = 0; i < src_ptr->count; i++) {
        dest_ptr->elements[i] = src_ptr->elements[i];
    }
    dest_ptr->count = src_ptr->count;
}

 
static inline void JOIN(internal, JOIN(FPQUEUE_NAME, upheap))(FPQUEUE_TYPE *self, uint32_t index)
{
    assert(self != NULL);
    assert(index < self->count);
 
    uint32_t parent;
    while (index > 0) {
        parent = FPQUEUE_PARENT(index);
 
        const bool sorted = self->elements[parent].priority >= self->elements[index].priority;
 
        if (sorted) {
            break;
        }
 
        const FPQUEUE_ELEMENT_TYPE temp = self->elements[index];
        self->elements[index] = self->elements[parent];
        self->elements[parent] = temp;
 
        index = parent;
    }
}
 
static inline void JOIN(internal, JOIN(FPQUEUE_NAME, downheap))(FPQUEUE_TYPE *self, const uint32_t index)
{
    assert(self != NULL);
    assert(self->count == 0 || index < self->count);
 
    const uint32_t l = FPQUEUE_LEFT_CHILD(index);
    const uint32_t r = FPQUEUE_RIGHT_CHILD(index);
 
    uint32_t largest = index;
    if (l < self->count && self->elements[l].priority > self->elements[index].priority) {
        largest = l;
    }
    if (r < self->count && self->elements[r].priority > self->elements[largest].priority) {
        largest = r;
    }
 
    if (largest == index) {
        return;
    }
 
    const FPQUEUE_ELEMENT_TYPE temp = self->elements[index];
    self->elements[index] = self->elements[largest];
    self->elements[largest] = temp;
 
    JOIN(internal, JOIN(FPQUEUE_NAME, downheap))(self, largest);
}
 
#endif
 
// }}}
 
// macro undefs: {{{
 
#undef NAME
#undef VALUE_TYPE
#undef FUNCTION_LINKAGE
#undef FUNCTION_DEFINITIONS
#undef TYPE_DEFINITIONS
 
#undef FPQUEUE_NAME
#undef FPQUEUE_TYPE
#undef FPQUEUE_ELEMENT_TYPE
#undef FPQUEUE_INIT
#undef FPQUEUE_IS_EMPTY
#undef FPQUEUE_IS_FULL
#undef FPQUEUE_CALC_SIZEOF
#undef FHASHTABLE_UPHEAP
#undef FHASHTABLE_DOWNHEAP
 
// }}}
 
#ifdef __cplusplus
}
#endif
 
// vim: ft=c fdm=marker