fpqueue.h

Go to the documentation of this file.

/*  fpqueue.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 FPQUEUE_H
#define FPQUEUE_H
 
#include "paste.h" // PASTE, XPASTE, JOIN
 
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
 
#define fpqueue_left_child(index) (2 * (index) + 1)
 
#define fpqueue_right_child(index) (2 * (index) + 2)
 
#define fpqueue_parent(index) (((index) - 1) / 2)
 
#define fpqueue_for_each(self, index, value_) \
    for ((index) = 0; (index) < (self)->count && ((value_) = (self)->elements[(index)].value, true); (index)++)
 
#define fpqueue_calc_sizeof(fpqueue_name, capacity) \
    (uint32_t)(offsetof(struct fpqueue_name, elements) + capacity * sizeof(((struct fpqueue_name *)0)->elements[0]))
 
#define fpqueue_calc_sizeof_overflows(fpqueue_name, capacity) \
    (capacity                                                 \
     > (UINT32_MAX - offsetof(struct fpqueue_name, elements)) / sizeof(((struct fpqueue_name *)0)->elements[0]))
 
#endif // FPQUEUE_H
 
#ifndef NAME
#define NAME fpqueue
#error "Must define NAME."
#else
#define FPQUEUE_NAME NAME
#endif
 
#ifndef VALUE_TYPE
#error "Must declare VALUE_TYPE."
#define VALUE_TYPE int
#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_CALC_SIZEOF  JOIN(FPQUEUE_NAME, calc_sizeof)
#define FPQUEUE_UPHEAP       JOIN(internal, JOIN(FPQUEUE_NAME, upheap))
#define FPQUEUE_DOWNHEAP     JOIN(internal, JOIN(FPQUEUE_NAME, downheap))
 
// }}}
 
// 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[]; 
};
 
// }}}
 
// 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);
 
 
static inline FPQUEUE_TYPE *JOIN(FPQUEUE_NAME, init)(FPQUEUE_TYPE *self, const uint32_t capacity)
{
    assert(self);
 
    self->count = 0;
    self->capacity = capacity;
 
    return self;
}
 
static inline 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;
}
 
static inline void JOIN(FPQUEUE_NAME, destroy)(FPQUEUE_TYPE *self)
{
    assert(self != NULL);
 
    free(self);
}
 
static inline bool JOIN(FPQUEUE_NAME, is_empty)(const FPQUEUE_TYPE *self)
{
    assert(self != NULL);
 
    return self->count == 0;
}
 
static inline bool JOIN(FPQUEUE_NAME, is_full)(const FPQUEUE_TYPE *self)
{
    assert(self != NULL);
 
    return self->count == self->capacity;
}
 
static inline 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;
}
 
static inline VALUE_TYPE JOIN(FPQUEUE_NAME, peek)(const FPQUEUE_TYPE *self)
{
    return JOIN(FPQUEUE_NAME, get_max)(self);
}
 
static inline 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;
}
 
static inline void JOIN(FPQUEUE_NAME, push)(FPQUEUE_TYPE *self, VALUE_TYPE value, 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);
}
 
static inline void JOIN(FPQUEUE_NAME, clear)(FPQUEUE_TYPE *self)
{
    assert(self != NULL);
 
    self->count = 0;
}
 
static inline 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);
}
 
// }}}
 
// macro undefs: {{{
 
#undef NAME
#undef VALUE_TYPE
 
#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
 
// }}}
 
// vim: ft=c fdm=marker