C Container Collection (CCC)
Loading...
Searching...
No Matches
impl_priority_queue.h
1#ifndef CCC_IMPL_PRIORITY_QUEUE_H
2#define CCC_IMPL_PRIORITY_QUEUE_H
3
5#include <stddef.h>
8#include "../types.h"
9
10/* NOLINTBEGIN(readability-identifier-naming) */
11
13struct ccc_pq_elem_
14{
15 struct ccc_pq_elem_ *left_child_;
16 struct ccc_pq_elem_ *next_sibling_;
17 struct ccc_pq_elem_ *prev_sibling_;
18 struct ccc_pq_elem_ *parent_;
19};
20
22struct ccc_pq_
23{
24 struct ccc_pq_elem_ *root_;
25 size_t sz_;
26 size_t pq_elem_offset_;
27 size_t elem_sz_;
28 ccc_alloc_fn *alloc_;
29 ccc_cmp_fn *cmp_;
30 ccc_threeway_cmp order_;
31 void *aux_;
32};
33
34/*========================= Private Interface ==========================*/
35
37void ccc_impl_pq_push(struct ccc_pq_ *, struct ccc_pq_elem_ *);
39struct ccc_pq_elem_ *ccc_impl_pq_elem_in(struct ccc_pq_ const *, void const *);
41void ccc_impl_pq_update_fixup(struct ccc_pq_ *, struct ccc_pq_elem_ *);
43void ccc_impl_pq_increase_fixup(struct ccc_pq_ *, struct ccc_pq_elem_ *);
45void ccc_impl_pq_decrease_fixup(struct ccc_pq_ *, struct ccc_pq_elem_ *);
46
47/*========================= Macro Implementations ======================*/
48
50#define ccc_impl_pq_init(struct_name, pq_elem_field, pq_order, cmp_fn, \
51 alloc_fn, aux_data) \
52 { \
53 .root_ = NULL, \
54 .sz_ = 0, \
55 .pq_elem_offset_ = offsetof(struct_name, pq_elem_field), \
56 .elem_sz_ = sizeof(struct_name), \
57 .alloc_ = (alloc_fn), \
58 .cmp_ = (cmp_fn), \
59 .order_ = (pq_order), \
60 .aux_ = (aux_data), \
61 }
62
64#define ccc_impl_pq_emplace(pq_ptr, lazy_value...) \
65 (__extension__({ \
66 typeof(lazy_value) *pq_res_ = NULL; \
67 struct ccc_pq_ *pq_ = (pq_ptr); \
68 if (pq_) \
69 { \
70 assert(sizeof(*pq_res_) == pq_->elem_sz_); \
71 if (!pq_->alloc_) \
72 { \
73 pq_res_ = NULL; \
74 } \
75 else \
76 { \
77 pq_res_ = pq_->alloc_(NULL, pq_->elem_sz_, pq_->aux_); \
78 if (pq_res_) \
79 { \
80 *pq_res_ = lazy_value; \
81 ccc_impl_pq_push(pq_, ccc_impl_pq_elem_in(pq_, pq_res_)); \
82 } \
83 } \
84 } \
85 pq_res_; \
86 }))
87
89#define ccc_impl_pq_update_w(pq_ptr, pq_elem_ptr, update_closure_over_T...) \
90 (__extension__({ \
91 struct ccc_pq_ *const pq_ = (pq_ptr); \
92 ccc_tribool pq_update_res_ = CCC_FALSE; \
93 struct ccc_pq_elem_ *const pq_elem_ptr_ = (pq_elem_ptr); \
94 if (pq_ && pq_elem_ptr_ && pq_elem_ptr_->next_sibling_ \
95 && pq_elem_ptr_->prev_sibling_) \
96 { \
97 pq_update_res_ = CCC_TRUE; \
98 {update_closure_over_T} ccc_impl_pq_update_fixup(pq_, \
99 pq_elem_ptr_); \
100 } \
101 pq_update_res_; \
102 }))
103
105#define ccc_impl_pq_increase_w(pq_ptr, pq_elem_ptr, \
106 increase_closure_over_T...) \
107 (__extension__({ \
108 struct ccc_pq_ *const pq_ = (pq_ptr); \
109 ccc_tribool pq_increase_res_ = CCC_FALSE; \
110 struct ccc_pq_elem_ *const pq_elem_ptr_ = (pq_elem_ptr); \
111 if (pq_ && pq_elem_ptr_ && pq_elem_ptr_->next_sibling_ \
112 && pq_elem_ptr_->prev_sibling_) \
113 { \
114 pq_increase_res_ = CCC_TRUE; \
115 {increase_closure_over_T} ccc_impl_pq_increase_fixup( \
116 pq_, pq_elem_ptr_); \
117 } \
118 pq_increase_res_; \
119 }))
120
122#define ccc_impl_pq_decrease_w(pq_ptr, pq_elem_ptr, \
123 decrease_closure_over_T...) \
124 (__extension__({ \
125 struct ccc_pq_ *const pq_ = (pq_ptr); \
126 ccc_tribool pq_decrease_res_ = CCC_FALSE; \
127 struct ccc_pq_elem_ *const pq_elem_ptr_ = (pq_elem_ptr); \
128 if (pq_ && pq_elem_ptr_ && pq_elem_ptr_->next_sibling_ \
129 && pq_elem_ptr_->prev_sibling_) \
130 { \
131 pq_decrease_res_ = CCC_TRUE; \
132 {decrease_closure_over_T} ccc_impl_pq_decrease_fixup( \
133 pq_, pq_elem_ptr_); \
134 } \
135 pq_decrease_res_; \
136 }))
137
138/* NOLINTEND(readability-identifier-naming) */
139
140#endif /* CCC_IMPL_PRIORITY_QUEUE_H */
ccc_cmp_fn
ccc_threeway_cmp ccc_cmp_fn(ccc_cmp)
A callback function for comparing two elements in a container.
Definition: types.h:291
ccc_alloc_fn
void * ccc_alloc_fn(void *ptr, size_t size, void *aux)
An allocation function at the core of all containers.
Definition: types.h:283
ccc_threeway_cmp
ccc_threeway_cmp
A three-way comparison for comparison functions.
Definition: types.h:138