1/*
2 * BSD-3-Clause
3 *
4 * Copyright 2021 Ozan Tezcan
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright notice,
11 * this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright notice,
13 * this list of conditions and the following disclaimer in the documentation
14 * and/or other materials provided with the distribution.
15 * 3. Neither the name of the copyright holder nor the names of its contributors
16 * may be used to endorse or promote products derived from this software
17 * without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
23 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
24 * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
25 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
30 */
31
32#ifndef SC_QUEUE_H
33#define SC_QUEUE_H
34
35#include <assert.h>
36#include <stdbool.h>
37#include <stddef.h>
38#include <stdint.h>
39#include <stdlib.h>
40#include <string.h>
41
42#ifdef __cplusplus
43extern "C" {
44#endif
45
46#define SC_QUEUE_VERSION "2.0.0"
47
48#ifdef SC_HAVE_CONFIG_H
49#include "config.h"
50#else
51#define sc_queue_calloc calloc
52#define sc_queue_free free
53#endif
54
55#ifndef SC_QUEUE_MAX
56#define SC_QUEUE_MAX (SIZE_MAX)
57#endif
58
59#define sc_queue_def(T, name) \
60 struct sc_queue_##name { \
61 bool oom; \
62 size_t cap; \
63 size_t first; \
64 size_t last; \
65 /* NOLINTNEXTLINE */ \
66 T *elems; \
67 }
68
69#define sc_queue_expand(q) \
70 do { \
71 size_t _cap, _len, _off; \
72 size_t _pos = ((q)->last + 1) & ((q)->cap - 1); \
73 void *_dst, *_src; \
74 \
75 if (_pos == (q)->first) { \
76 if ((q)->cap > SC_QUEUE_MAX / 2ul) { \
77 (q)->oom = true; \
78 break; \
79 } \
80 _cap = (q)->cap * 2; \
81 _dst = sc_queue_calloc(_cap, sizeof(*((q)->elems))); \
82 if (_dst == NULL) { \
83 (q)->oom = true; \
84 break; \
85 } \
86 _len = ((q)->cap - (q)->first) * sizeof(*(q)->elems); \
87 _off = ((q)->first * sizeof(*((q)->elems))); \
88 _src = ((char *) (q)->elems) + _off; \
89 \
90 memcpy(_dst, _src, _len); \
91 memcpy(((char *) _dst) + _len, (q)->elems, _off); \
92 (q)->oom = false; \
93 (q)->last = (q)->cap - 1; \
94 (q)->first = 0; \
95 (q)->cap = _cap; \
96 sc_queue_free((q)->elems); \
97 (q)->elems = _dst; \
98 } \
99 } while (0)
100
101/**
102 * Init queue. Call sc_queue_oom(q) to see if memory allocation succeeded.
103 * @param q queue
104 */
105#define sc_queue_init(q) \
106 do { \
107 (q)->oom = false; \
108 (q)->cap = 8; \
109 (q)->first = 0; \
110 (q)->last = 0; \
111 (q)->elems = sc_queue_calloc(1, sizeof(*(q)->elems) * 8); \
112 if ((q)->elems == NULL) { \
113 (q)->oom = true; \
114 } \
115 } while (0)
116
117/**
118 * Destroy queue
119 * @param q queue
120 */
121#define sc_queue_term(q) \
122 do { \
123 sc_queue_free((q)->elems); \
124 (q)->elems = NULL; \
125 (q)->cap = 0; \
126 (q)->first = 0; \
127 (q)->last = 0; \
128 (q)->oom = false; \
129 } while (0)
130
131/**
132 * @param q queue
133 * @return true if last add operation failed, false otherwise.
134 */
135#define sc_queue_oom(q) ((q)->oom)
136
137/**
138 * @param q queue
139 * @return element count
140 */
141#define sc_queue_size(q) (((q)->last - (q)->first) & ((q)->cap - 1))
142
143/**
144 * Clear the queue without deallocating underlying memory.
145 * @param q queue
146 */
147#define sc_queue_clear(q) \
148 do { \
149 (q)->first = 0; \
150 (q)->last = 0; \
151 (q)->oom = false; \
152 } while (0)
153
154/**
155 * @param q queue
156 * @return true if queue is empty
157 */
158#define sc_queue_empty(q) (((q)->last == (q)->first))
159
160/**
161 * @param q queue
162 * @return index of the first element. If queue is empty, result is undefined.
163 */
164#define sc_queue_first(q) ((q)->first)
165
166/**
167 * @param q queue
168 * @return index of the last element. If queue is empty, result is undefined.
169 */
170#define sc_queue_last(q) ((q)->last)
171
172/**
173 * @param q queue
174 * @param i index
175 * @return index of the next element after i, if i is the last element,
176 * result is undefined.
177 */
178#define sc_queue_next(q, i) (((i) + 1) & ((q)->cap - 1))
179
180/**
181 * Returns element at index 'i', so regular loops are possible :
182 *
183 * for (size_t i = 0; i < sc_queue_size(q); i++) {
184 * printf("%d" \n, sc_queue_at(q, i));
185 * }
186 *
187 * @param q queue
188 * @return element at index i
189 */
190#define sc_queue_at(q, i) (q)->elems[(((q)->first) + (i)) & ((q)->cap - 1)]
191
192/**
193 * @param q queue
194 * @return peek first element, if queue is empty, result is undefined
195 */
196#define sc_queue_peek_first(q) ((q)->elems[(q)->first])
197
198/**
199 * @param q queue
200 * @return peek last element, if queue is empty, result is undefined
201 */
202#define sc_queue_peek_last(q) (q)->elems[((q)->last - 1) & ((q)->cap - 1)]
203
204/**
205 * Call sc_queue_oom(q) after this function to check out of memory condition.
206 *
207 * @param q queue
208 * @param elem elem to be added at the end of the list
209 */
210#define sc_queue_add_last(q, elem) \
211 do { \
212 sc_queue_expand(q); \
213 if ((q)->oom) { \
214 break; \
215 } \
216 (q)->oom = false; \
217 (q)->elems[(q)->last] = elem; \
218 (q)->last = ((q)->last + 1) & ((q)->cap - 1); \
219 } while (0)
220
221/**
222 * @param q queue
223 * @return delete the last element from the queue and return its value.
224 * If queue is empty, result is undefined.
225 */
226#define sc_queue_del_last(q) \
227 ((q)->elems[((q)->last = ((q)->last - 1) & ((q)->cap - 1))])
228
229/**
230 * Call sc_queue_oom(q) after this function to check out of memory condition.
231 *
232 * @param q queue.
233 * @param elem elem to be added at the head of the list.
234 */
235#define sc_queue_add_first(q, elem) \
236 do { \
237 sc_queue_expand(q); \
238 if ((q)->oom) { \
239 break; \
240 } \
241 (q)->oom = false; \
242 (q)->first = ((q)->first - 1) & ((q)->cap - 1); \
243 (q)->elems[(q)->first] = elem; \
244 } while (0)
245
246static inline size_t sc_queue_inc_first(size_t *first, size_t cap)
247{
248 size_t tmp = *first;
249
250 *first = (*first + 1) & (cap - 1);
251 return tmp;
252}
253
254/**
255 * @param q queue
256 * @return delete the first element from the queue and return its value.
257 * If queue is empty, result is undefined.
258 */
259#define sc_queue_del_first(q) \
260 (q)->elems[sc_queue_inc_first(&(q)->first, (q)->cap)]
261
262/**
263 * For each loop,
264 *
265 * struct sc_queue_int queue;
266 * sc_queue_init(&queue, 4);"
267 *
268 * int elem;
269 * sc_queue_foreach(&queue, elem) {
270 * printf("Elem : %d \n, elem);
271 * }
272 */
273#define sc_queue_foreach(q, elem) \
274 for (size_t _k = 1, _i = sc_queue_first(q); \
275 _k && _i != sc_queue_last(q); \
276 _k = !_k, _i = sc_queue_next(q, _i)) \
277 for ((elem) = (q)->elems[_i]; _k; _k = !_k)
278
279// (type, name)
280sc_queue_def(int, int);
281sc_queue_def(unsigned int, uint);
282sc_queue_def(long, long);
283sc_queue_def(long long, ll);
284sc_queue_def(unsigned long, ulong);
285sc_queue_def(unsigned long long, ull);
286sc_queue_def(uint32_t, 32);
287sc_queue_def(uint64_t, 64);
288sc_queue_def(double, double);
289sc_queue_def(const char *, str);
290sc_queue_def(void *, ptr);
291
292#ifdef __cplusplus
293}
294#endif
295
296#endif
297