GCC Code Coverage Report

Directory: src/
File: src/support/queue_template.h
Date: 2025-11-21 10:34:40
Exec Total Coverage
Lines: 52 73 71.2%
Functions: 19 19 100.0%
Branches: 23 60 38.3%
Line Branch Exec Source
1 /*********************************************************************************/
2 /* Copyright 2009-2024 Barcelona Supercomputing Center */
3 /* */
4 /* This file is part of the DLB library. */
5 /* */
6 /* DLB is free software: you can redistribute it and/or modify */
7 /* it under the terms of the GNU Lesser General Public License as published by */
8 /* the Free Software Foundation, either version 3 of the License, or */
9 /* (at your option) any later version. */
10 /* */
11 /* DLB is distributed in the hope that it will be useful, */
12 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
13 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
14 /* GNU Lesser General Public License for more details. */
15 /* */
16 /* You should have received a copy of the GNU Lesser General Public License */
17 /* along with DLB. If not, see <https://www.gnu.org/licenses/>. */
18 /*********************************************************************************/
19
20 /* Credits: https://www.davidpriver.com/ctemplates.html */
21
22 /* Include this header multiple times to implement a fixed-size circular queue.
23 * Before inclusion define at least QUEUE_T and QUEUE_SIZE to the type the
24 * queue can hold.
25 *
26 * QUEUE_KEY_T can be defined to set the type of the primary key, which should
27 * be either a subtype of QUEUE_T if using structs, or QUEUE_T.
28 */
29
30 #ifndef QUEUE_TEMPLATE_H
31 #define QUEUE_TEMPLATE_H
32
33 #include "support/debug.h"
34
35 #include <stdbool.h>
36 #include <stdlib.h>
37 #include <string.h>
38
39 #define QUEUE_IMPL(word) QUEUE_COMB1(QUEUE_PREFIX,word)
40 #define QUEUE_COMB1(pre, word) QUEUE_COMB2(pre, word)
41 #define QUEUE_COMB2(pre, word) pre##word
42
43 #endif /* QUEUE_TEMPLATE_H */
44
45 #ifndef QUEUE_T
46 #error "QUEUE_T must be defined"
47 #endif
48
49 #ifndef QUEUE_SIZE
50 #error "QUEUE_SIZE must be defined"
51 #endif
52
53 #ifndef QUEUE_KEY_T
54 #define QUEUE_KEY_T QUEUE_T
55 #endif
56
57 #define QUEUE_NAME QUEUE_COMB1(QUEUE_COMB1(queue,_), QUEUE_T)
58 #define QUEUE_PREFIX QUEUE_COMB1(QUEUE_NAME, _)
59
60 #define QUEUE_init QUEUE_IMPL(init)
61 #define QUEUE_clear QUEUE_IMPL(clear)
62 #define QUEUE_size QUEUE_IMPL(size)
63 #define QUEUE_empty QUEUE_IMPL(empty)
64 #define QUEUE_has_space QUEUE_IMPL(has_space)
65 #define QUEUE_front QUEUE_IMPL(front)
66 #define QUEUE_back QUEUE_IMPL(back)
67 #define QUEUE_next QUEUE_IMPL(next)
68 #define QUEUE_enqueue QUEUE_IMPL(enqueue)
69 #define QUEUE_dequeue QUEUE_IMPL(dequeue)
70 #define QUEUE_delete QUEUE_IMPL(delete)
71 #define QUEUE_remove QUEUE_IMPL(remove)
72 #define QUEUE_replace QUEUE_IMPL(replace)
73 #define QUEUE_search QUEUE_IMPL(search)
74
75 /* Queue template:
76 * - the actual capacity is QUEUE_SIZE - 1 because we don't save rear, but next. FIXME
77 * (it simplifies some functions a little bit)
78 * - 'front' points to the first element
79 * - 'next' points to the next spot where to push
80 */
81
82 typedef struct QUEUE_NAME {
83 QUEUE_T items[QUEUE_SIZE];
84 size_t front; /* position to the first element */
85 size_t next; /* position to the last empty spot */
86 size_t capacity;
87 } QUEUE_NAME;
88
89
90 /* Initializers */
91
92 1574 static inline void QUEUE_init(QUEUE_NAME *queue) {
93 1574 *queue = (const QUEUE_NAME) {
94 .capacity = QUEUE_SIZE, /* mainly for debugging */
95 };
96 1574 }
97
98 147 static inline void QUEUE_clear(QUEUE_NAME *queue) {
99 147 queue->front = 0;
100 147 queue->next = 0;
101 147 }
102
103
104 /* Capacity */
105
106 398 static inline size_t QUEUE_size(const QUEUE_NAME *queue) {
107 398 return queue->next >= queue->front
108 398 ? queue->next - queue->front
109
1/2
✓ Branch 0 taken 199 times.
✗ Branch 1 not taken.
 398 : QUEUE_SIZE - queue->front + queue->next;
110 }
111
112 3786 static inline bool QUEUE_empty(const QUEUE_NAME *queue) {
113 3786 return queue->front == queue->next;
114 }
115
116 6 static inline bool QUEUE_has_space(const QUEUE_NAME *queue) {
117 6 return (queue->next + 1) % QUEUE_SIZE != queue->front;
118 }
119
120
121 /* Element access */
122
123 758 static inline QUEUE_T* QUEUE_front(QUEUE_NAME *queue) {
124
2/2
✓ Branch 1 taken 75 times.
✓ Branch 2 taken 304 times.
 758 return QUEUE_empty(queue) ? NULL : &queue->items[queue->front];
125 }
126
127 static inline QUEUE_T* QUEUE_back(QUEUE_NAME *queue) {
128 size_t rear = queue->next > 0 ? queue->next-1 : QUEUE_SIZE-1;
129 return QUEUE_empty(queue) ? NULL : &queue->items[rear];
130 }
131
132 164 static inline QUEUE_T* QUEUE_next(QUEUE_NAME *queue, QUEUE_T *item) {
133
2/2
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 58 times.
 164 if (QUEUE_empty(queue) ) {
134 48 return NULL;
135 }
136
1/2
✓ Branch 0 taken 58 times.
✗ Branch 1 not taken.
 116 else if (queue->next > queue->front) {
137 /* queue is linear */
138 116 size_t next_index = item + 1 - queue->items;
139
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 39 times.
 116 return next_index < queue->next ? item + 1 : NULL;
140 }
141 else {
142 /* queue is circular */
143 ✗ size_t next_index = item + 1 < queue->items + QUEUE_SIZE
144 ✗ ? item + 1 - queue->items
145 ✗ : 0;
146 ✗ return next_index > queue->front || next_index < queue->next
147 ✗ ? &queue->items[next_index] : NULL;
148 }
149 }
150
151
152 /* Modifiers */
153
154 /* Enqueue item to the back of the queue */
155 166 static inline int QUEUE_enqueue(QUEUE_NAME *queue, QUEUE_T item) {
156 166 size_t new_next = (queue->next + 1) % QUEUE_SIZE;
157
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 83 times.
 166 if (unlikely(new_next == queue->front)) {
158 ✗ return -1;
159 }
160 166 queue->items[queue->next] = item;
161 166 queue->next = new_next;
162 166 return 0;
163 }
164
165 /* Dequeue item from the front of the queue */
166 static inline int QUEUE_dequeue(QUEUE_NAME *queue, QUEUE_T *item) {
167 if (QUEUE_empty(queue)) {
168 return -1;
169 }
170 *item = queue->items[queue->front];
171 queue->front = (queue->front + 1) % QUEUE_SIZE;
172 return 0;
173 }
174
175 /* Delete element pointed by argument */
176 54 static inline void QUEUE_delete(QUEUE_NAME *queue, const QUEUE_T *item) {
177
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 27 times.
 54 if (QUEUE_empty(queue)) {
178 ✗ return;
179 }
180
181
1/2
✓ Branch 0 taken 27 times.
✗ Branch 1 not taken.
 54 if (item == &queue->items[queue->front]) {
182 /* item is first element, just advance front */
183 54 queue->front = (queue->front + 1) % QUEUE_SIZE;
184 54 return;
185 }
186
187 ✗ size_t array_index = item - queue->items;
188
189 // FIXME: more efficient?
190 ✗ if (unlikely(
191 /* queue is linear */
192 (queue->next > queue->front
193 && (array_index < queue->front || array_index >= queue->next))
194 ||
195 /* queue is circular */
196 (queue->next <= queue->front
197 && (array_index >= queue->next && array_index < queue->front))
198 )) {
199 /* out of bounds */
200 ✗ return;
201 }
202
203 ✗ size_t write_index = array_index;
204 ✗ for (size_t read_index = (array_index + 1) % QUEUE_SIZE;
205 ✗ read_index != queue->next;
206 ✗ read_index = (read_index + 1) % QUEUE_SIZE) {
207 /* move items forward in the queue */
208 ✗ queue->items[write_index] = queue->items[read_index];
209 ✗ write_index = (write_index + 1) % QUEUE_SIZE;
210 }
211 ✗ queue->next = write_index;
212 }
213
214 /* Remove all items that match with key */
215 1352 static inline void QUEUE_remove(QUEUE_NAME *queue, QUEUE_KEY_T key) {
216
217 /* advance front for every first item that matches key */
218 1458 while (!QUEUE_empty(queue)
219
4/4
✓ Branch 0 taken 75 times.
✓ Branch 1 taken 654 times.
✓ Branch 2 taken 53 times.
✓ Branch 3 taken 22 times.
 1458 && memcmp(&queue->items[queue->front], &key, sizeof(QUEUE_KEY_T)) == 0) {
220 106 queue->front = (queue->front + 1) % QUEUE_SIZE;
221 }
222
223
2/2
✓ Branch 1 taken 654 times.
✓ Branch 2 taken 22 times.
 1352 if (QUEUE_empty(queue)) {
224 1308 return;
225 }
226
227 /* front does not match, iterate from 2nd item */
228 44 size_t write_index = (queue->front + 1) % QUEUE_SIZE;
229 44 for (size_t read_index = write_index;
230
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 22 times.
 58 read_index != queue->next;
231 14 read_index = (read_index + 1) % QUEUE_SIZE) {
232
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 7 times.
 14 if (read_index != write_index) {
233 /* move items forward in the queue */
234 ✗ queue->items[write_index] = queue->items[read_index];
235 }
236
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 1 times.
 14 if (memcmp(&queue->items[read_index], &key, sizeof(QUEUE_KEY_T)) != 0) {
237 /* write_index only advances when element is not to be removed */
238 12 write_index = (write_index + 1) % QUEUE_SIZE;
239 }
240 }
241 44 queue->next = write_index;
242 }
243
244 /* Replace the first item that matches by key */
245 static inline void QUEUE_replace(QUEUE_NAME *queue, QUEUE_T item) {
246 for (size_t index = queue->front;
247 index != queue->next;
248 index = (index + 1) % QUEUE_SIZE) {
249 if (memcmp(&queue->items[index], &item, sizeof(QUEUE_KEY_T)) == 0) {
250 queue->items[index] = item;
251 return;
252 }
253 }
254 }
255
256 /* Return reference to the first item that matches by key */
257 6 static inline QUEUE_T* QUEUE_search(QUEUE_NAME *queue, QUEUE_KEY_T key) {
258 6 for (size_t index = queue->front;
259
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 index != queue->next;
260 ✗ index = (index + 1) % QUEUE_SIZE) {
261 ✗ if (memcmp(&queue->items[index], &key, sizeof(QUEUE_KEY_T)) == 0) {
262 ✗ return &queue->items[index];
263 }
264 }
265 6 return NULL;
266 }
267
268 #undef QUEUE_T
269 #undef QUEUE_SIZE
270 #undef QUEUE_KEY_T
271 #undef QUEUE_PREFIX
272 #undef QUEUE_NAME
273 #undef QUEUE_init
274 #undef QUEUE_clear
275 #undef QUEUE_size
276 #undef QUEUE_empty
277 #undef QUEUE_has_space
278 #undef QUEUE_front
279 #undef QUEUE_back
280 #undef QUEUE_next
281 #undef QUEUE_enqueue
282 #undef QUEUE_dequeue
283 #undef QUEUE_delete
284 #undef QUEUE_remove
285 #undef QUEUE_replace
286 #undef QUEUE_search
287