43#define fpqueue_left_child(index) (2 * (index) + 1)
51#define fpqueue_right_child(index) (2 * (index) + 2)
59#define fpqueue_parent(index) (((index) - 1) / 2)
72#define fpqueue_for_each(self, index, value_) \
73 for ((index) = 0; (index) < (self)->count && ((value_) = (self)->elements[(index)].value, true); (index)++)
85#define fpqueue_calc_sizeof(fpqueue_name, capacity) \
86 (uint32_t)(offsetof(struct fpqueue_name, elements) + capacity * sizeof(((struct fpqueue_name *)0)->elements[0]))
98#define fpqueue_calc_sizeof_overflows(fpqueue_name, capacity) \
100 > (UINT32_MAX - offsetof(struct fpqueue_name, elements)) / sizeof(((struct fpqueue_name *)0)->elements[0]))
113#error "Must define NAME."
115#define FPQUEUE_NAME NAME
126#error "Must declare VALUE_TYPE."
127#define VALUE_TYPE int
131#define FPQUEUE_TYPE struct FPQUEUE_NAME
132#define FPQUEUE_ELEMENT_TYPE struct JOIN(FPQUEUE_NAME, element)
133#define FPQUEUE_INIT JOIN(FPQUEUE_NAME, init)
134#define FPQUEUE_IS_EMPTY JOIN(FPQUEUE_NAME, is_empty)
135#define FPQUEUE_IS_FULL JOIN(FPQUEUE_NAME, is_full)
136#define FPQUEUE_CALC_SIZEOF JOIN(FPQUEUE_NAME, calc_sizeof)
137#define FPQUEUE_UPHEAP JOIN(internal, JOIN(FPQUEUE_NAME, upheap))
138#define FPQUEUE_DOWNHEAP JOIN(internal, JOIN(FPQUEUE_NAME, downheap))
148struct JOIN(FPQUEUE_NAME, element) {
159 FPQUEUE_ELEMENT_TYPE elements[];
169static inline void JOIN(internal,
JOIN(FPQUEUE_NAME, downheap))(FPQUEUE_TYPE *self,
const uint32_t index);
172static inline void JOIN(internal,
JOIN(FPQUEUE_NAME, upheap))(FPQUEUE_TYPE *self, uint32_t index);
182static inline FPQUEUE_TYPE *
JOIN(FPQUEUE_NAME, init)(FPQUEUE_TYPE *self,
const uint32_t capacity)
187 self->capacity = capacity;
202static inline FPQUEUE_TYPE *
JOIN(FPQUEUE_NAME, create)(
const uint32_t capacity)
210 FPQUEUE_TYPE *self = (FPQUEUE_TYPE *)calloc(1, size);
216 FPQUEUE_INIT(self, capacity);
228static inline void JOIN(FPQUEUE_NAME, destroy)(FPQUEUE_TYPE *self)
230 assert(self != NULL);
242static inline bool JOIN(FPQUEUE_NAME, is_empty)(
const FPQUEUE_TYPE *self)
244 assert(self != NULL);
246 return self->count == 0;
256static inline bool JOIN(FPQUEUE_NAME, is_full)(
const FPQUEUE_TYPE *self)
258 assert(self != NULL);
260 return self->count == self->capacity;
272 assert(self != NULL);
273 assert(FPQUEUE_IS_EMPTY(self) ==
false);
275 return self->elements[0].value;
288 return JOIN(FPQUEUE_NAME, get_max)(self);
300 assert(self != NULL);
301 assert(FPQUEUE_IS_EMPTY(self) ==
false);
303 VALUE_TYPE max_priority_value = self->elements[0].value;
305 self->elements[0] = self->elements[self->count - 1];
309 JOIN(internal,
JOIN(FPQUEUE_NAME, downheap))(self, 0);
311 return max_priority_value;
322static inline void JOIN(FPQUEUE_NAME, push)(FPQUEUE_TYPE *self,
VALUE_TYPE value, uint32_t priority)
324 assert(self != NULL);
325 assert(FPQUEUE_IS_FULL(self) ==
false);
327 const uint32_t index = self->count;
329 self->elements[index] = (FPQUEUE_ELEMENT_TYPE){.priority = priority, .value = value};
333 JOIN(internal,
JOIN(FPQUEUE_NAME, upheap))(self, index);
341static inline void JOIN(FPQUEUE_NAME, clear)(FPQUEUE_TYPE *self)
343 assert(self != NULL);
355static inline void JOIN(FPQUEUE_NAME, copy)(FPQUEUE_TYPE *restrict dest_ptr,
const FPQUEUE_TYPE *restrict src_ptr)
357 assert(src_ptr != NULL);
358 assert(dest_ptr != NULL);
359 assert(src_ptr->count <= dest_ptr->capacity);
360 assert(FPQUEUE_IS_EMPTY(dest_ptr));
362 for (uint32_t i = 0; i < src_ptr->count; i++) {
363 dest_ptr->elements[i] = src_ptr->elements[i];
365 dest_ptr->count = src_ptr->count;
370static inline void JOIN(internal,
JOIN(FPQUEUE_NAME, upheap))(FPQUEUE_TYPE *self, uint32_t index)
372 assert(self != NULL);
373 assert(index < self->count);
379 const bool sorted = self->elements[parent].priority >= self->elements[index].priority;
385 const FPQUEUE_ELEMENT_TYPE temp = self->elements[index];
386 self->elements[index] = self->elements[parent];
387 self->elements[parent] = temp;
393static inline void JOIN(internal,
JOIN(FPQUEUE_NAME, downheap))(FPQUEUE_TYPE *self,
const uint32_t index)
395 assert(self != NULL);
396 assert(self->count == 0 || index < self->count);
401 uint32_t largest = index;
402 if (l < self->count && self->elements[l].priority > self->elements[index].priority) {
405 if (r < self->count && self->elements[r].priority > self->elements[largest].priority) {
409 if (largest == index) {
413 const FPQUEUE_ELEMENT_TYPE temp = self->elements[index];
414 self->elements[index] = self->elements[largest];
415 self->elements[largest] = temp;
417 JOIN(internal,
JOIN(FPQUEUE_NAME, downheap))(self, largest);
430#undef FPQUEUE_ELEMENT_TYPE
432#undef FPQUEUE_IS_EMPTY
433#undef FPQUEUE_IS_FULL
434#undef FPQUEUE_CALC_SIZEOF
435#undef FHASHTABLE_UPHEAP
436#undef FHASHTABLE_DOWNHEAP
#define VALUE_TYPE
The value type. This must be manually defined before including this header file.
Definition fhashtable.h:144
#define fpqueue_calc_sizeof(fpqueue_name, capacity)
Calculate the size of the pqueue struct. No overflow checks.
Definition fpqueue.h:85
#define fpqueue_parent(index)
Given an element index, get the index of the parent.
Definition fpqueue.h:59
#define fpqueue_calc_sizeof_overflows(fpqueue_name, capacity)
Check for a given capacity, if the equivalent size of the pqueue struct overflows.
Definition fpqueue.h:98
#define fpqueue_left_child(index)
Given an element index, get the index of the left child.
Definition fpqueue.h:43
#define fpqueue_right_child(index)
Given an element index, get the index of the right child.
Definition fpqueue.h:51
#define VALUE_TYPE
Priority queue value type. This must be manually defined before including this header file.
Definition fpqueue.h:127
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
uint32_t priority
Element priority (highest is next to-be-popped).
Definition fpqueue.h:149
VALUE_TYPE value
Element value member.
Definition fpqueue.h:150
uint32_t capacity
Number of elements allocated for.
Definition fpqueue.h:158
uint32_t count
Number of non-empty elements.
Definition fpqueue.h:157