GCC Code Coverage Report

Directory: src/
File: src/support/queues.c
Date: 2025-11-21 10:34:40
Exec Total Coverage
Lines: 285 295 96.6%
Functions: 39 40 97.5%
Branches: 157 176 89.2%
Line Branch Exec Source
1 /*********************************************************************************/
2 /* Copyright 2009-2023 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 #ifdef HAVE_CONFIG_H
21 #include <config.h>
22 #endif
23
24 #include "support/queues.h"
25
26 #include "support/debug.h"
27 #include "apis/dlb_errors.h"
28
29 #include <string.h>
30
31 enum { NOBODY = 0 };
32
33 /*** queue_lewi_reqs_t ***********************************************************/
34
35 13 void queue_lewi_reqs_init(queue_lewi_reqs_t *queue) {
36 13 memset(queue, 0, sizeof(*queue));
37 13 }
38
39 1207 unsigned int queue_lewi_reqs_size(const queue_lewi_reqs_t *queue) {
40 1207 return queue->head;
41 }
42
43 /* Remove entry with given <pid> and pack list, return previous value if exists */
44 380 unsigned int queue_lewi_reqs_remove(queue_lewi_reqs_t *queue, pid_t pid) {
45
46
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 379 times.
 380 if (unlikely(pid == 0)) return 0;
47
2/2
✓ Branch 0 taken 38 times.
✓ Branch 1 taken 341 times.
 379 if (queue->head == 0) return 0;
48
49 /* The queue does not need to be ordered. Find element to remove and swap
50 * last position */
51
2/2
✓ Branch 0 taken 12702 times.
✓ Branch 1 taken 43 times.
 12745 for (unsigned int i=0; i < queue->head; ++i) {
52 12702 lewi_request_t *request = &queue->queue[i];
53
2/2
✓ Branch 0 taken 298 times.
✓ Branch 1 taken 12404 times.
 12702 if (request->pid == pid) {
54 // return value
55 298 int howmany = request->howmany;
56
57
2/2
✓ Branch 0 taken 204 times.
✓ Branch 1 taken 94 times.
 298 if (i+1 < queue->head) {
58 // this is not the last element, copy last one here
59 204 *request = queue->queue[queue->head-1];
60 }
61 298 --queue->head;
62
63 298 return howmany;
64 }
65 }
66
67 43 return 0;
68 }
69
70 /* Push entry with given <pid>, add value if already present */
71 924 int queue_lewi_reqs_push(queue_lewi_reqs_t *queue, pid_t pid, unsigned int howmany) {
72
73
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 923 times.
 924 if (unlikely(pid == 0)) return DLB_NOUPDT;
74
75 /* Remove entry if value is reset to 0 */
76
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 922 times.
 923 if (howmany == 0) {
77 1 queue_lewi_reqs_remove(queue, pid);
78 1 return DLB_SUCCESS;
79 }
80
81 /* Find entry, if exists */
82 unsigned int i;
83
2/2
✓ Branch 0 taken 33242 times.
✓ Branch 1 taken 367 times.
 33609 for (i=0; i<queue->head; ++i) {
84
2/2
✓ Branch 0 taken 555 times.
✓ Branch 1 taken 32687 times.
 33242 if (queue->queue[i].pid == pid) {
85 /* Found, just update value */
86 555 queue->queue[i].howmany += howmany;
87 555 return DLB_SUCCESS;
88 }
89 }
90
91 /* No existing entry and 'head' points to the last position, which is reserved */
92
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 366 times.
 367 if (queue->head == QUEUE_LEWI_REQS_SIZE-1) {
93 1 return DLB_ERR_REQST;
94 }
95
96 /* 'i' (and 'head') points the new spot. Add entry. */
97 366 queue->queue[i] = (const lewi_request_t) {
98 .pid = pid,
99 .howmany = howmany,
100 };
101 366 ++queue->head;
102 366 return DLB_SUCCESS;
103 }
104
105 /* Remove entries with no values (howmany == 0) */
106 100 static void queue_lewi_reqs_pack(queue_lewi_reqs_t *queue) {
107 unsigned int i, i_write;
108
2/2
✓ Branch 0 taken 119 times.
✓ Branch 1 taken 100 times.
 219 for (i=0, i_write=0; i<queue->head; ++i) {
109
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 31 times.
 119 if (queue->queue[i].howmany > 0) {
110
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 87 times.
 88 if (i != i_write) {
111 1 queue->queue[i_write] = queue->queue[i];
112 }
113 88 ++i_write;
114 }
115 }
116 100 queue->head = i_write;
117 100 }
118
119 /* Sort in descending order by number of requests */
120 22 static int sort_queue_lewi_reqs(const void *elem1, const void *elem2) {
121 22 return ((lewi_request_t*)elem2)->howmany - ((lewi_request_t*)elem1)->howmany;
122 }
123
124 /* Pop ncpus from the queue in an equal distribution, return array of accepted requests
125 * by argument, and number of CPUs not assigned */
126 101 unsigned int queue_lewi_reqs_pop_ncpus(queue_lewi_reqs_t *queue, unsigned int ncpus,
127 lewi_request_t *requests, unsigned int *nreqs, unsigned int maxreqs) {
128
129 101 unsigned int queue_size = queue_lewi_reqs_size(queue);
130
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 100 times.
 101 if (queue_size == 0) {
131 1 *nreqs = 0;
132 1 return ncpus;
133 }
134
135 /* For evenly distribute CPU removal, we need to sort the queue by number
136 * of requests per process */
137 100 qsort(queue->queue, queue_size, sizeof(queue->queue[0]), sort_queue_lewi_reqs);
138
139
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 100 times.
 100 ensure(queue->queue[queue->head-1].howmany > 0, "Empty spots in the queue");
140
141 unsigned int i, j;
142
4/6
✓ Branch 0 taken 119 times.
✓ Branch 1 taken 100 times.
✓ Branch 2 taken 119 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 119 times.
✗ Branch 5 not taken.
 219 for (i = queue->head, j = 0; i-- > 0 && ncpus > 0 && j < maxreqs; ) {
143 119 lewi_request_t *request = &queue->queue[i];
144 /* For every iteration, we compute the CPUs to be popped by computing
145 * the minimum between an even distribution and the current request
146 * value. */
147 119 unsigned int ncpus_popped = min_uint(ncpus/(i+1), request->howmany);
148
2/2
✓ Branch 0 taken 117 times.
✓ Branch 1 taken 2 times.
 119 if (ncpus_popped > 0) {
149 /* Assign number of CPUs to output array */
150 117 requests[j++] = (const lewi_request_t) {
151 117 .pid = request->pid,
152 .howmany = ncpus_popped,
153 };
154
155 /* Remove the CPUs from the queue */
156 117 request->howmany -= ncpus_popped;
157
158 /* Update number of CPUs to be popped */
159 117 ncpus -= ncpus_popped;
160 }
161 }
162
163 /* Update output array size */
164 100 *nreqs = j;
165
166 /* Pack queue, remove elements if howmany reached 0 */
167 100 queue_lewi_reqs_pack(queue);
168
169 100 return ncpus;
170 }
171
172 /* Return the value of requests of the given pid */
173 313 unsigned int queue_lewi_reqs_get(queue_lewi_reqs_t *queue, pid_t pid) {
174
175
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 313 times.
 313 if (unlikely(pid == 0)) return 0;
176
177
2/2
✓ Branch 0 taken 32725 times.
✓ Branch 1 taken 22 times.
 32747 for (unsigned int i = 0; i < queue->head; ++i) {
178
2/2
✓ Branch 0 taken 291 times.
✓ Branch 1 taken 32434 times.
 32725 if (queue->queue[i].pid == pid) {
179 291 return queue->queue[i].howmany;
180 }
181 }
182
183 22 return 0;
184 }
185
186
187 /*** queue_proc_reqs_t ***********************************************************/
188
189 3 void queue_proc_reqs_init(queue_proc_reqs_t *queue) {
190 3 memset(queue, 0, sizeof(*queue));
191 3 }
192
193 16406 unsigned int queue_proc_reqs_size(const queue_proc_reqs_t *queue) {
194 16406 return queue->head >= queue->tail
195 8208 ? queue->head - queue->tail
196
2/2
✓ Branch 0 taken 8208 times.
✓ Branch 1 taken 8198 times.
 16406 : QUEUE_PROC_REQS_SIZE - queue->tail + queue->head;
197 }
198
199 8192 process_request_t* queue_proc_reqs_front(queue_proc_reqs_t *queue) {
200 8192 return &queue->queue[queue->tail];
201 }
202
203 12297 process_request_t* queue_proc_reqs_back(queue_proc_reqs_t *queue) {
204
2/2
✓ Branch 0 taken 4102 times.
✓ Branch 1 taken 8195 times.
 12297 unsigned int prev_head = queue->head > 0 ? queue->head-1 : QUEUE_PROC_REQS_SIZE-1;
205 12297 return &queue->queue[prev_head];
206 }
207
208 3 void queue_proc_reqs_remove(queue_proc_reqs_t *queue, pid_t pid) {
209
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 if (unlikely(!pid)) return;
210
211 unsigned int i;
212
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 3 times.
 14 for (i=queue->tail; i!=queue->head; i=(i+1)%QUEUE_PROC_REQS_SIZE) {
213
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 7 times.
 11 if (queue->queue[i].pid == pid) {
214 /* Clear request */
215 4 memset(&queue->queue[i], 0, sizeof(process_request_t));
216 }
217 /* Advance tail if it points to invalid elements */
218
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 6 times.
 11 if (queue->queue[i].pid == NOBODY
219
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 4 times.
 5 && i == queue->tail) {
220 1 queue->tail = (queue->tail+1) % QUEUE_PROC_REQS_SIZE;
221 }
222 }
223 }
224
225 12298 int queue_proc_reqs_push(queue_proc_reqs_t *queue, pid_t pid,
226 unsigned int howmany, const cpu_set_t *allowed) {
227 /* Remove entry if value is reset to 0 */
228
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 12297 times.
 12298 if (howmany == 0) {
229 1 queue_proc_reqs_remove(queue, pid);
230 1 return DLB_SUCCESS;
231 }
232
233 /* If the last request belongs to the same pid, just increment value */
234 12297 process_request_t *last_req = queue_proc_reqs_back(queue);
235
2/2
✓ Branch 0 taken 8191 times.
✓ Branch 1 taken 4106 times.
 12297 if (last_req->pid == pid) {
236 8191 last_req->howmany += howmany;
237 8191 return DLB_NOTED;
238 }
239
240 /* If the queue is full, return error code */
241 4106 unsigned int next_head = (queue->head + 1) % QUEUE_PROC_REQS_SIZE;
242
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 4105 times.
 4106 if (__builtin_expect((next_head == queue->tail), 0)) {
243 1 return DLB_ERR_REQST;
244 }
245
246 /* Otherwise, push new entry */
247 4105 queue->queue[queue->head].pid = pid;
248 4105 queue->queue[queue->head].howmany = howmany;
249
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4101 times.
 4105 if (allowed) {
250 4 memcpy(&queue->queue[queue->head].allowed, allowed, sizeof(*allowed));
251 } else {
252 4101 memset(&queue->queue[queue->head].allowed,0xff, sizeof(*allowed));
253 }
254 4105 queue->head = next_head;
255
256 4105 return DLB_NOTED;
257 }
258
259 ✗ void queue_proc_reqs_pop(queue_proc_reqs_t *queue, process_request_t *request) {
260 /* If front is valid, extract request */
261 ✗ process_request_t *front = queue_proc_reqs_front(queue);
262 ✗ if (front->pid != NOBODY) {
263 ✗ if (request != NULL) {
264 /* Copy request if argument is valid */
265 ✗ memcpy(request, front, sizeof(process_request_t));
266 }
267 /* Clear request */
268 ✗ memset(front, 0, sizeof(process_request_t));
269 }
270
271 /* Advance tail as long as it points to invalid elements */
272 ✗ while(queue->head != queue->tail
273 ✗ && queue->queue[queue->tail].pid == NOBODY) {
274 ✗ queue->tail = (queue->tail + 1) % QUEUE_PROC_REQS_SIZE;
275 }
276 }
277
278 45166 void queue_proc_reqs_get(queue_proc_reqs_t *queue, pid_t *pid, int cpuid) {
279 45166 *pid = NOBODY;
280 45166 unsigned int pointer = queue->tail;
281
4/4
✓ Branch 0 taken 90226 times.
✓ Branch 1 taken 109 times.
✓ Branch 2 taken 45169 times.
✓ Branch 3 taken 45057 times.
 90335 while(pointer != queue->head && *pid == NOBODY) {
282 45169 process_request_t *request = &queue->queue[pointer];
283
2/2
✓ Branch 0 taken 45166 times.
✓ Branch 1 taken 3 times.
 45169 if (request->pid != NOBODY
284
5/6
✓ Branch 0 taken 45166 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 45162 times.
✓ Branch 3 taken 4 times.
✓ Branch 4 taken 45162 times.
✓ Branch 5 taken 4 times.
 45166 && CPU_ISSET(cpuid, &request->allowed)) {
285 /* request is valid */
286 45162 *pid = request->pid;
287
2/2
✓ Branch 0 taken 4101 times.
✓ Branch 1 taken 41061 times.
 45162 if (--request->howmany == 0) {
288 4101 request->pid = NOBODY;
289 4101 CPU_ZERO(&request->allowed);
290 }
291 }
292
293 /* Advance tail if possible */
294
2/2
✓ Branch 0 taken 45164 times.
✓ Branch 1 taken 5 times.
 45169 if (pointer == queue->tail
295
2/2
✓ Branch 0 taken 4099 times.
✓ Branch 1 taken 41065 times.
 45164 && request->pid == NOBODY) {
296 4099 queue->tail = (queue->tail + 1) % QUEUE_PROC_REQS_SIZE;
297 }
298
299 /* Advance pointer */
300 45169 pointer = (pointer + 1) % QUEUE_PROC_REQS_SIZE;
301 }
302
303 /* Advance tail as long as it points to invalid elements */
304 45166 while(queue->head != queue->tail
305
4/4
✓ Branch 0 taken 45165 times.
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 5 times.
✓ Branch 3 taken 45160 times.
 45171 && queue->queue[queue->tail].pid == NOBODY) {
306 5 queue->tail = (queue->tail + 1) % QUEUE_PROC_REQS_SIZE;
307 }
308 45166 }
309
310 /*********************************************************************************/
311
312 /*** queue_pids_t ****************************************************************/
313
314 1 void queue_pids_init(queue_pids_t *queue) {
315 1 memset(queue, 0, sizeof(*queue));
316 1 }
317
318 26 unsigned int queue_pids_size(const queue_pids_t *queue) {
319 26 return queue->head >= queue->tail
320 20 ? queue->head - queue->tail
321
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 6 times.
 26 : QUEUE_PIDS_SIZE - queue->tail + queue->head;
322 }
323
324 5 void queue_pids_remove(queue_pids_t *queue, pid_t pid) {
325 unsigned int i;
326
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 5 times.
 25 for (i=queue->tail; i!=queue->head; i=(i+1)%QUEUE_PIDS_SIZE) {
327
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 11 times.
 20 if (queue->queue[i] == pid) {
328 9 queue->queue[i] = NOBODY;
329 }
330 /* Advance tail if it points to invalid elements */
331
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 8 times.
 20 if (queue->queue[i] == NOBODY
332
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 3 times.
 12 && i == queue->tail) {
333 9 queue->tail = (queue->tail+1) % QUEUE_PIDS_SIZE;
334 }
335 }
336 5 }
337
338 13 int queue_pids_push(queue_pids_t *queue, pid_t pid) {
339 13 unsigned int next_head = (queue->head + 1) % QUEUE_PIDS_SIZE;
340
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 12 times.
 13 if (__builtin_expect((next_head == queue->tail), 0)) {
341 1 return DLB_ERR_REQST;
342 }
343 12 queue->queue[queue->head] = pid;
344 12 queue->head = next_head;
345 12 return DLB_NOTED;
346 }
347
348 7 void queue_pids_pop(queue_pids_t *queue, pid_t *pid) {
349 7 *pid = NOBODY;
350
4/4
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 7 times.
✓ Branch 3 taken 6 times.
 14 while(queue->head != queue->tail && *pid == NOBODY) {
351 7 *pid = queue->queue[queue->tail];
352 7 queue->queue[queue->tail] = NOBODY;
353 7 queue->tail = (queue->tail + 1) % QUEUE_PIDS_SIZE;
354 }
355 7 }
356 /*********************************************************************************/
357
358 /*** queue_t *********************************************************************/
359
360 typedef struct queue_t {
361 void * queue;
362 bool queue_is_internal;
363
364 queue_allocator_t allocator;
365
366 size_t element_size;
367
368 unsigned int elements;
369 unsigned int capacity;
370
371 unsigned int head;
372 unsigned int tail;
373 } queue_t;
374
375 9 queue_t* queue__init(size_t element_size, unsigned int capacity, void *ptr,
376 queue_allocator_t allocator) {
377
378 // When the container is managed by the user (ptr != NULL) we can not use the
379 // QUEUE_ALLOC_REALLOC because we would corrupt the users pointer. Hence the queue
380 // init fails returning NULL.
381
4/4
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 5 times.
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 3 times.
 9 if (allocator == QUEUE_ALLOC_REALLOC && ptr != NULL) {
382 1 return NULL;
383 }
384
385 8 queue_t * queue = malloc(sizeof(queue_t));
386
387 8 *queue = (const queue_t) {
388
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 2 times.
 8 .queue = ptr == NULL ? malloc(capacity * element_size) : ptr,
389 8 .queue_is_internal = ptr == NULL,
390 .allocator = allocator,
391 .element_size = element_size,
392 .elements = 0,
393 .capacity = capacity,
394 .head = 0,
395 .tail = 0,
396 };
397
398 8 return queue;
399 }
400
401 6 void queue__destroy(queue_t *queue) {
402
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 1 times.
 6 if (queue->queue_is_internal) {
403 5 free(queue->queue);
404 }
405 6 free(queue);
406 6 }
407
408 50 unsigned int queue__get_size(const queue_t *queue) {
409 50 return queue->elements;
410 }
411
412 41 unsigned int queue__get_capacity(const queue_t *queue) {
413 41 return queue->capacity;
414 }
415
416 8 bool queue__is_empty(const queue_t *queue) {
417 8 return queue->elements == 0;
418 }
419
420 90 bool queue__is_at_capacity(const queue_t *queue) {
421 90 return queue->elements == queue->capacity;
422 }
423
424 350 static void * queue__get_element_ptr(queue_t *queue, unsigned int idx) {
425 350 return (unsigned char *)queue->queue + (queue->element_size * idx);
426 }
427
428 23 int queue__take_head(queue_t *queue, void * poped) {
429
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 21 times.
 23 if (queue->elements == 0) {
430 2 return DLB_NOUPDT;
431 }
432
433 21 queue->elements--;
434
435 // Move head back
436
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 20 times.
 21 if (queue->head == 0) queue->head = queue->capacity;
437 21 queue->head--;
438
439 // Fetch data from queue
440 21 void * head = queue__get_element_ptr(queue, queue->head);
441
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 1 times.
 21 if (poped != NULL) {
442 20 memcpy(poped, head, queue->element_size);
443 }
444
445 21 return DLB_SUCCESS;
446 }
447
448 12 int queue__take_tail(queue_t *queue, void * poped) {
449
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 11 times.
 12 if (queue->elements == 0) {
450 1 return DLB_NOUPDT;
451 }
452
453 11 queue->elements--;
454
455 // Fetch data form queue
456 11 void * tail = queue__get_element_ptr(queue, queue->tail);
457
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 1 times.
 11 if (poped != NULL) {
458 10 memcpy(poped, tail, queue->element_size);
459 }
460
461 // Move tail forward
462 11 queue->tail++;
463
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 9 times.
 11 if (queue->tail >= queue->capacity) queue->tail = 0;
464
465 11 return DLB_SUCCESS;
466 }
467
468 6 int queue__peek_head(queue_t *queue, void **value_ptr) {
469
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 5 times.
 6 if (queue->elements == 0) {
470 1 return DLB_NOUPDT;
471 }
472
473 // Move head back
474 5 unsigned int peek_head = queue->head;
475
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 4 times.
 5 if (peek_head == 0) peek_head = queue->elements;
476 5 peek_head--;
477
478 // Fetch pointer to queue storage
479 5 *value_ptr = queue__get_element_ptr(queue, peek_head);
480
481 5 return DLB_SUCCESS;
482 }
483
484 6 int queue__peek_tail(queue_t *queue, void **value_ptr) {
485
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 5 times.
 6 if (queue->elements == 0) {
486 1 return DLB_NOUPDT;
487 }
488
489 // Fetch pointer to queue storage
490 5 *value_ptr = queue__get_element_ptr(queue, queue->tail);
491
492 5 return DLB_SUCCESS;
493 }
494
495 15 static void queue__realloc(queue_t *queue) {
496
497
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 3 times.
 15 unsigned int new_capacity = queue->capacity == 0 ? 1 : queue->capacity * 2;
498 15 void *new_queue = malloc(new_capacity * queue->element_size);
499 15 void *old_queue = queue->queue;
500
501 //ensure(queue->elements != 0 && queue->elements == queue->capacity, "");
502
503 // If the data is in order in the storage then we just make one memcpy.
504
4/6
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 9 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 9 times.
✗ Branch 5 not taken.
 15 if (queue->tail == 0 && queue->head == 0 && queue->elements == queue->capacity) {
505 9 memcpy(new_queue, old_queue, queue->elements * queue->element_size);
506 }
507 // Otherwise first we copy from head to capacyty and then from 0 to tail.
508 else {
509 12 unsigned int n_elements_first_copy = (queue->tail >= queue->head ?
510
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 queue->capacity : queue->head) - queue->tail;
511
512 6 memcpy(
513 new_queue,
514 6 (unsigned char *)old_queue + queue->tail * queue->element_size,
515 6 n_elements_first_copy * queue->element_size
516 );
517
518 6 memcpy(
519 6 (unsigned char *)new_queue + (queue->capacity - queue->tail) * queue->element_size,
520 old_queue,
521 6 queue->head * queue->element_size
522 );
523 }
524
525 15 queue->queue = new_queue;
526 15 queue->tail = 0;
527 15 queue->head = queue->elements;
528 15 queue->capacity = new_capacity;
529
530 15 free(old_queue);
531 15 }
532
533 89 static bool queue__check_capacity(queue_t *queue) {
534
2/2
✓ Branch 1 taken 19 times.
✓ Branch 2 taken 70 times.
 89 if (queue__is_at_capacity(queue)) {
535
3/4
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 15 times.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 19 switch (queue->allocator) {
536 3 case QUEUE_ALLOC_FIXED:
537 3 return false;
538 15 case QUEUE_ALLOC_REALLOC:
539 15 queue__realloc(queue);
540 15 break;
541 1 case QUEUE_ALLOC_OVERWRITE:
542 1 break;
543 ✗ default: return false;
544 }
545 }
546
547 86 return true;
548 }
549
550 65 void * queue__push_head(queue_t *queue, const void * new) {
551
552
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 64 times.
 65 if (! queue__check_capacity(queue)) return NULL;
553
554 64 void * head = queue__get_element_ptr(queue, queue->head);
555 64 memcpy(head, new, queue->element_size);
556
557 64 unsigned int old_head = queue->head;
558
559 // Move head forward
560 64 queue->head++;
561
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 56 times.
 64 if (queue->head >= queue->capacity) {
562 8 queue->head = 0;
563 }
564
565 64 queue->elements++;
566
567 64 return queue__get_element_ptr(queue, old_head);
568 }
569
570 24 void * queue__push_tail(queue_t *queue, const void * new) {
571
572
2/2
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 22 times.
 24 if (! queue__check_capacity(queue)) return NULL;
573
574 // Move tail back
575
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 11 times.
 22 if (queue->tail == 0) queue->tail = queue->capacity;
576 22 queue->tail--;
577
578 22 queue->elements++;
579
580 22 void * tail = queue__get_element_ptr(queue, queue->tail);
581 22 memcpy(tail, new, queue->element_size);
582
583 22 return queue__get_element_ptr(queue, queue->tail);
584 }
585
586 /*********************************************************************************/
587
588 /*** queue_t generic functions for iterators *************************************/
589
590 typedef struct queue_iter_t {
591 void* (*next)(void*);
592 } queue_iter_t;
593
594 2 void queue_iter__foreach(void *iter, void (*fn)(void*, void*), void* args) {
595 2 queue_iter_t *it = iter;
596 2 void * i = NULL;
597
2/2
✓ Branch 1 taken 12 times.
✓ Branch 2 taken 2 times.
 14 while ( (i = it->next(iter)) != NULL) {
598 12 fn(args, i);
599 }
600 2 }
601
602 22 void* queue_iter__get_nth(void *iter, unsigned int n) {
603 22 queue_iter_t *it = iter;
604 22 void * i = NULL;
605
606 22 unsigned int count = 0;
607
2/2
✓ Branch 1 taken 124 times.
✓ Branch 2 taken 1 times.
 125 while ( (i = it->next(iter)) != NULL) {
608
2/2
✓ Branch 0 taken 21 times.
✓ Branch 1 taken 103 times.
 124 if (count == n) {
609 21 return i;
610 }
611
612 103 count++;
613 }
614
615 1 return NULL;
616 }
617
618 /*** queue_iter_head2tail_t implementation ***************************************/
619
620 139 static void * queue_iter_head2tail__next(void *iter) {
621 139 queue_iter_head2tail_t *it = iter;
622
623
3/4
✓ Branch 0 taken 136 times.
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 136 times.
 139 if (it->done || it->queue->elements == 0) {
624 3 return NULL;
625 }
626
627
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 135 times.
 136 if (it->curr <= 0) {
628 1 it->curr = queue__get_capacity(it->queue);
629 }
630 136 it->curr--;
631
632
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 131 times.
 136 if (it->curr == it->tail) {
633 5 it->done = true;
634 }
635
636 136 return queue__get_element_ptr(it->queue, it->curr);
637 }
638
639 24 queue_iter_head2tail_t queue__into_head2tail_iter(queue_t * queue) {
640 48 return (queue_iter_head2tail_t) {
641 .next = queue_iter_head2tail__next,
642 .queue = queue,
643 .done = false,
644 24 .curr = queue->head,
645 24 .tail = queue->tail,
646 };
647 }
648
649 /*********************************************************************************/
650