1 /*
2 * Copyright (c) 2013 Hugh Bailey <obs.jim@gmail.com>
3 *
4 * Permission to use, copy, modify, and distribute this software for any
5 * purpose with or without fee is hereby granted, provided that the above
6 * copyright notice and this permission notice appear in all copies.
7 *
8 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15 */
16
17 #pragma once
18
19 #include "c99defs.h"
20 #include <string.h>
21 #include <stdlib.h>
22 #include <assert.h>
23
24 #include "bmem.h"
25
26 #ifdef __cplusplus
27 extern "C" {
28 #endif
29
30 /* Dynamic circular buffer */
31
32 struct circlebuf {
33 void *data;
34 size_t size;
35
36 size_t start_pos;
37 size_t end_pos;
38 size_t capacity;
39 };
40
circlebuf_init(struct circlebuf * cb)41 static inline void circlebuf_init(struct circlebuf *cb)
42 {
43 memset(cb, 0, sizeof(struct circlebuf));
44 }
45
circlebuf_free(struct circlebuf * cb)46 static inline void circlebuf_free(struct circlebuf *cb)
47 {
48 bfree(cb->data);
49 memset(cb, 0, sizeof(struct circlebuf));
50 }
51
circlebuf_reorder_data(struct circlebuf * cb,size_t new_capacity)52 static inline void circlebuf_reorder_data(struct circlebuf *cb,
53 size_t new_capacity)
54 {
55 size_t difference;
56 uint8_t *data;
57
58 if (!cb->size || !cb->start_pos || cb->end_pos > cb->start_pos)
59 return;
60
61 difference = new_capacity - cb->capacity;
62 data = (uint8_t *)cb->data + cb->start_pos;
63 memmove(data + difference, data, cb->capacity - cb->start_pos);
64 cb->start_pos += difference;
65 }
66
circlebuf_ensure_capacity(struct circlebuf * cb)67 static inline void circlebuf_ensure_capacity(struct circlebuf *cb)
68 {
69 size_t new_capacity;
70 if (cb->size <= cb->capacity)
71 return;
72
73 new_capacity = cb->capacity * 2;
74 if (cb->size > new_capacity)
75 new_capacity = cb->size;
76
77 cb->data = brealloc(cb->data, new_capacity);
78 circlebuf_reorder_data(cb, new_capacity);
79 cb->capacity = new_capacity;
80 }
81
circlebuf_reserve(struct circlebuf * cb,size_t capacity)82 static inline void circlebuf_reserve(struct circlebuf *cb, size_t capacity)
83 {
84 if (capacity <= cb->capacity)
85 return;
86
87 cb->data = brealloc(cb->data, capacity);
88 circlebuf_reorder_data(cb, capacity);
89 cb->capacity = capacity;
90 }
91
circlebuf_upsize(struct circlebuf * cb,size_t size)92 static inline void circlebuf_upsize(struct circlebuf *cb, size_t size)
93 {
94 size_t add_size = size - cb->size;
95 size_t new_end_pos = cb->end_pos + add_size;
96
97 if (size <= cb->size)
98 return;
99
100 cb->size = size;
101 circlebuf_ensure_capacity(cb);
102
103 if (new_end_pos > cb->capacity) {
104 size_t back_size = cb->capacity - cb->end_pos;
105 size_t loop_size = add_size - back_size;
106
107 if (back_size)
108 memset((uint8_t *)cb->data + cb->end_pos, 0, back_size);
109
110 memset(cb->data, 0, loop_size);
111 new_end_pos -= cb->capacity;
112 } else {
113 memset((uint8_t *)cb->data + cb->end_pos, 0, add_size);
114 }
115
116 cb->end_pos = new_end_pos;
117 }
118
119 /** Overwrites data at a specific point in the buffer (relative). */
circlebuf_place(struct circlebuf * cb,size_t position,const void * data,size_t size)120 static inline void circlebuf_place(struct circlebuf *cb, size_t position,
121 const void *data, size_t size)
122 {
123 size_t end_point = position + size;
124 size_t data_end_pos;
125
126 if (end_point > cb->size)
127 circlebuf_upsize(cb, end_point);
128
129 position += cb->start_pos;
130 if (position >= cb->capacity)
131 position -= cb->capacity;
132
133 data_end_pos = position + size;
134 if (data_end_pos > cb->capacity) {
135 size_t back_size = data_end_pos - cb->capacity;
136 size_t loop_size = size - back_size;
137
138 memcpy((uint8_t *)cb->data + position, data, loop_size);
139 memcpy(cb->data, (uint8_t *)data + loop_size, back_size);
140 } else {
141 memcpy((uint8_t *)cb->data + position, data, size);
142 }
143 }
144
circlebuf_push_back(struct circlebuf * cb,const void * data,size_t size)145 static inline void circlebuf_push_back(struct circlebuf *cb, const void *data,
146 size_t size)
147 {
148 size_t new_end_pos = cb->end_pos + size;
149
150 cb->size += size;
151 circlebuf_ensure_capacity(cb);
152
153 if (new_end_pos > cb->capacity) {
154 size_t back_size = cb->capacity - cb->end_pos;
155 size_t loop_size = size - back_size;
156
157 if (back_size)
158 memcpy((uint8_t *)cb->data + cb->end_pos, data,
159 back_size);
160 memcpy(cb->data, (uint8_t *)data + back_size, loop_size);
161
162 new_end_pos -= cb->capacity;
163 } else {
164 memcpy((uint8_t *)cb->data + cb->end_pos, data, size);
165 }
166
167 cb->end_pos = new_end_pos;
168 }
169
circlebuf_push_front(struct circlebuf * cb,const void * data,size_t size)170 static inline void circlebuf_push_front(struct circlebuf *cb, const void *data,
171 size_t size)
172 {
173 cb->size += size;
174 circlebuf_ensure_capacity(cb);
175
176 if (cb->start_pos < size) {
177 size_t back_size = size - cb->start_pos;
178
179 if (cb->start_pos)
180 memcpy(cb->data, (uint8_t *)data + back_size,
181 cb->start_pos);
182
183 cb->start_pos = cb->capacity - back_size;
184 memcpy((uint8_t *)cb->data + cb->start_pos, data, back_size);
185 } else {
186 cb->start_pos -= size;
187 memcpy((uint8_t *)cb->data + cb->start_pos, data, size);
188 }
189 }
190
circlebuf_push_back_zero(struct circlebuf * cb,size_t size)191 static inline void circlebuf_push_back_zero(struct circlebuf *cb, size_t size)
192 {
193 size_t new_end_pos = cb->end_pos + size;
194
195 cb->size += size;
196 circlebuf_ensure_capacity(cb);
197
198 if (new_end_pos > cb->capacity) {
199 size_t back_size = cb->capacity - cb->end_pos;
200 size_t loop_size = size - back_size;
201
202 if (back_size)
203 memset((uint8_t *)cb->data + cb->end_pos, 0, back_size);
204 memset(cb->data, 0, loop_size);
205
206 new_end_pos -= cb->capacity;
207 } else {
208 memset((uint8_t *)cb->data + cb->end_pos, 0, size);
209 }
210
211 cb->end_pos = new_end_pos;
212 }
213
circlebuf_push_front_zero(struct circlebuf * cb,size_t size)214 static inline void circlebuf_push_front_zero(struct circlebuf *cb, size_t size)
215 {
216 cb->size += size;
217 circlebuf_ensure_capacity(cb);
218
219 if (cb->start_pos < size) {
220 size_t back_size = size - cb->start_pos;
221
222 if (cb->start_pos)
223 memset(cb->data, 0, cb->start_pos);
224
225 cb->start_pos = cb->capacity - back_size;
226 memset((uint8_t *)cb->data + cb->start_pos, 0, back_size);
227 } else {
228 cb->start_pos -= size;
229 memset((uint8_t *)cb->data + cb->start_pos, 0, size);
230 }
231 }
232
circlebuf_peek_front(struct circlebuf * cb,void * data,size_t size)233 static inline void circlebuf_peek_front(struct circlebuf *cb, void *data,
234 size_t size)
235 {
236 assert(size <= cb->size);
237
238 if (data) {
239 size_t start_size = cb->capacity - cb->start_pos;
240
241 if (start_size < size) {
242 memcpy(data, (uint8_t *)cb->data + cb->start_pos,
243 start_size);
244 memcpy((uint8_t *)data + start_size, cb->data,
245 size - start_size);
246 } else {
247 memcpy(data, (uint8_t *)cb->data + cb->start_pos, size);
248 }
249 }
250 }
251
circlebuf_peek_back(struct circlebuf * cb,void * data,size_t size)252 static inline void circlebuf_peek_back(struct circlebuf *cb, void *data,
253 size_t size)
254 {
255 assert(size <= cb->size);
256
257 if (data) {
258 size_t back_size = (cb->end_pos ? cb->end_pos : cb->capacity);
259
260 if (back_size < size) {
261 size_t front_size = size - back_size;
262 size_t new_end_pos = cb->capacity - front_size;
263
264 memcpy((uint8_t *)data + (size - back_size), cb->data,
265 back_size);
266 memcpy(data, (uint8_t *)cb->data + new_end_pos,
267 front_size);
268 } else {
269 memcpy(data, (uint8_t *)cb->data + cb->end_pos - size,
270 size);
271 }
272 }
273 }
274
circlebuf_pop_front(struct circlebuf * cb,void * data,size_t size)275 static inline void circlebuf_pop_front(struct circlebuf *cb, void *data,
276 size_t size)
277 {
278 circlebuf_peek_front(cb, data, size);
279
280 cb->size -= size;
281 if (!cb->size) {
282 cb->start_pos = cb->end_pos = 0;
283 return;
284 }
285
286 cb->start_pos += size;
287 if (cb->start_pos >= cb->capacity)
288 cb->start_pos -= cb->capacity;
289 }
290
circlebuf_pop_back(struct circlebuf * cb,void * data,size_t size)291 static inline void circlebuf_pop_back(struct circlebuf *cb, void *data,
292 size_t size)
293 {
294 circlebuf_peek_back(cb, data, size);
295
296 cb->size -= size;
297 if (!cb->size) {
298 cb->start_pos = cb->end_pos = 0;
299 return;
300 }
301
302 if (cb->end_pos <= size)
303 cb->end_pos = cb->capacity - (size - cb->end_pos);
304 else
305 cb->end_pos -= size;
306 }
307
circlebuf_data(struct circlebuf * cb,size_t idx)308 static inline void *circlebuf_data(struct circlebuf *cb, size_t idx)
309 {
310 uint8_t *ptr = (uint8_t *)cb->data;
311 size_t offset = cb->start_pos + idx;
312
313 if (idx >= cb->size)
314 return NULL;
315
316 if (offset >= cb->capacity)
317 offset -= cb->capacity;
318
319 return ptr + offset;
320 }
321
322 #ifdef __cplusplus
323 }
324 #endif
325