-
Notifications
You must be signed in to change notification settings - Fork 1
/
ijcringbuffer.h
369 lines (298 loc) · 11.7 KB
/
ijcringbuffer.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
/*
ijcringbuffer.h - v0.01 - public domain - @incrediblejr, Dec 2015
no warranty implied; use at your own risk
A continuous ringbuffer ala [@rygorous][2] ['magic ring buffer'][1] (without the magic)
ABOUT
ijcringbuffer is a ringbuffer that handles variable sized commands/data, inspired
by [@rygorous][2] blog post about the ['magic ring buffer'][1] (but implemented sans the magic).
The ring buffer guarantees that data will written as-is or not at all (no splitting).
This can be used when the consumer expects the data be linear in memory.
Usage examples (and tests) is at the bottom of the file in the IJCRINGBUFFER_TEST section.
USAGE
The ringbuffer is implemented as a [stb-style header-file library][3] which means that
in *ONE* source file, put:
#define IJCRINGBUFFER_IMPLEMENTATION
// if custom assert and memcpy is wanted/needed
// (and no dependencies on assert.h + string.h)
// you can define/override the default by :
// #define IJCRB_assert custom_assert
// #define IJCRB_memcpy custom_memcpy
#include "ijcringbuffer.h"
Other source files should just include ijcringbuffer.h
NOTES
There are a myriad of ways to implement said ring buffer, especially if you
would allow the producer to modify the read-cursor (but you have to
have _some_ standards).
I also wanted to solve the (not-in-real-life-?) problem when the read-cursor catches
up with the write-cursor, giving the producer only part of the buffer (worst case
half of the buffer) to write into, when we should be able to start writing to the
start of the buffer (essentially doing a buffer reset).
[1]: https://fgiesen.wordpress.com/2012/07/21/the-magic-ring-buffer/
[2]: https://twitter.com/rygorous
[3]: https://github.com/nothings/stb
LICENSE
This software is in the public domain. Where that dedication is not
recognized, you are granted a perpetual, irrevocable license to copy,
distribute, and modify this file as you see fit.
*/
#ifndef INCLUDE_IJCRINGBUFFER_H
#define INCLUDE_IJCRINGBUFFER_H
#ifdef IJCRB_STATIC
#define IJCRB_DEF static
#else
#define IJCRB_DEF extern
#endif
#ifdef __cplusplus
extern "C" {
#endif
typedef struct ijcringbuffer {
unsigned char *data;
unsigned size, mask; /* mask could be calculated each time (size-1) */
unsigned read_cursor, write_cursor, wrap_cursor;
} ijcringbuffer;
/* data_size must be a power of 2 */
IJCRB_DEF void ijcringbuffer_init(ijcringbuffer *self, void *data, unsigned data_size);
IJCRB_DEF void ijcringbuffer_reset(ijcringbuffer *self);
/* returns the number of continuous bytes that can be read/consumed */
IJCRB_DEF unsigned ijcringbuffer_consumeable_size_continuous(ijcringbuffer *self);
/* returns the number of bytes that can be read/consumed.
(as the buffer can split/wrap, this can be more than ijcringbuffer_consumeable_size_continuous)
*/
IJCRB_DEF unsigned ijcringbuffer_consumeable_size(ijcringbuffer *self);
/* advance the consume/read cursor (essentially freeing memory to be used for produce/write) */
IJCRB_DEF void ijcringbuffer_consume(ijcringbuffer *self, unsigned size);
/* returns the current read/consume pointer */
IJCRB_DEF void *ijcringbuffer_peek(ijcringbuffer *self);
IJCRB_DEF int ijcringbuffer_is_empty(ijcringbuffer *self);
IJCRB_DEF int ijcringbuffer_is_full(ijcringbuffer *self);
/* returns 1 on success (insize bytes is written), returns 0 on fail (0 bytes written) */
IJCRB_DEF int ijcringbuffer_produce(ijcringbuffer *self, void *indata, unsigned insize);
#ifdef __cplusplus
}
#endif
#endif
#ifdef IJCRINGBUFFER_IMPLEMENTATION
#ifndef IJCRB_assert
#include <assert.h>
#define IJCRB_assert assert
#endif
#ifndef IJCRB_memcpy
#include <string.h>
#define IJCRB_memcpy memcpy
#endif
static unsigned ijcringbuffer__difference(unsigned a, unsigned b)
{
unsigned ab = a - b;
unsigned ba = b - a;
return ab > ba ? ba : ab;
}
IJCRB_DEF void ijcringbuffer_init(ijcringbuffer *self, void *data, unsigned data_size)
{
IJCRB_assert(data_size > 0 && !(data_size & (data_size - 1)));
self->data = (unsigned char*)data;
self->size = data_size;
self->mask = data_size - 1;
self->read_cursor = self->write_cursor = self->wrap_cursor = 0;
}
IJCRB_DEF void ijcringbuffer_reset(ijcringbuffer *self)
{
self->read_cursor = self->write_cursor = self->wrap_cursor = 0;
}
static int ijcringbuffer__is_split(ijcringbuffer *self)
{
return ijcringbuffer__difference(self->read_cursor, self->write_cursor) > self->size;
}
IJCRB_DEF void *ijcringbuffer_peek(ijcringbuffer *self)
{
unsigned peek_rc;
if (self->read_cursor == self->wrap_cursor && ijcringbuffer__is_split(self))
peek_rc = 0;
else
peek_rc = self->read_cursor&self->mask;
return self->data+peek_rc;
}
static unsigned ijcringbuffer__consumeable_size(ijcringbuffer *self, int continuous)
{
unsigned cs;
if (ijcringbuffer__is_split(self)) {
if (self->read_cursor == self->wrap_cursor) {
/* check if the buffer is a wrap + full fill */
unsigned masked_write = self->write_cursor&self->mask;
cs = masked_write ? masked_write : self->size;
} else {
IJCRB_assert(self->size > ijcringbuffer__difference(self->wrap_cursor, self->read_cursor));
cs = ((self->wrap_cursor-self->read_cursor)&self->mask) + (continuous ? 0 : (self->write_cursor&self->mask));
}
} else {
cs = self->write_cursor - self->read_cursor;
}
IJCRB_assert(self->size >= cs);
return cs;
}
IJCRB_DEF unsigned ijcringbuffer_consumeable_size_continuous(ijcringbuffer *self)
{
return ijcringbuffer__consumeable_size(self, 1);
}
IJCRB_DEF unsigned ijcringbuffer_consumeable_size(ijcringbuffer *self)
{
return ijcringbuffer__consumeable_size(self, 0);
}
IJCRB_DEF void ijcringbuffer_consume(ijcringbuffer *self, unsigned size)
{
IJCRB_assert(ijcringbuffer_consumeable_size_continuous(self) >= size);
if (self->read_cursor == self->wrap_cursor && ijcringbuffer__is_split(self))
self->read_cursor += self->size + (self->size - (self->read_cursor&self->mask)) + size;
else
self->read_cursor += size;
}
IJCRB_DEF int ijcringbuffer_is_empty(ijcringbuffer *self) { return self->write_cursor == self->read_cursor; }
IJCRB_DEF int ijcringbuffer_is_full(ijcringbuffer *self) { return ijcringbuffer_consumeable_size(self) == self->size; }
IJCRB_DEF int ijcringbuffer_produce(ijcringbuffer *self, void *indata, unsigned insize)
{
unsigned masked_write = self->write_cursor&self->mask;
int is_empty;
if (ijcringbuffer__is_split(self)) {
unsigned avail_write_size;
if (self->wrap_cursor == self->read_cursor) {
avail_write_size = masked_write ? (self->size - masked_write) : 0;
}
else {
IJCRB_assert((self->read_cursor&self->mask) >= (self->write_cursor&self->mask));
avail_write_size = (self->read_cursor - self->write_cursor) & self->mask;
}
if (avail_write_size >= insize) {
IJCRB_memcpy(self->data + masked_write, indata, insize);
self->write_cursor += insize;
return 1;
}
return 0;
}
is_empty = ijcringbuffer_is_empty(self);
/*
check if we are empty and write cursor is not at the start, then we
start writing to the front and 'split' the buffer (giving us an 'auto-reset')
*/
if (masked_write && is_empty && self->size >= insize)
goto write_to_front;
/*
if !masked_write then
has_filled_the_whole_buffer
_or_
has_not_filled_anything -> read == write -> empty
*/
if (!masked_write && !is_empty) {
/* we can not write to _back_ but we still have to check if we can write to front */
goto check_front;
}
/* check write to back */
if ((self->size - masked_write) >= insize) {
IJCRB_memcpy(self->data + masked_write, indata, insize);
self->write_cursor += insize;
return 1;
}
check_front:
/* check write to front */
if ((self->read_cursor&self->mask) >= insize) {
write_to_front:
self->wrap_cursor = self->write_cursor;
IJCRB_memcpy(self->data, indata, insize);
/* 'split' the buffer */
self->write_cursor += self->size + (self->size - masked_write) + insize;
IJCRB_assert((self->write_cursor & self->mask) == insize);
return 1;
}
return 0;
}
#if defined(IJCRINGBUFFER_TEST) || defined(IJCRINGBUFFER_TEST_MAIN)
static void ijcringbuffer_test(void)
{
unsigned t;
ijcringbuffer ring, *r = ˚
char hex[16] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };
char temp[9]; memset(temp, 0, sizeof temp);
ijcringbuffer_init(r, temp, sizeof temp - 1);
/* */
IJCRB_assert(ijcringbuffer_produce(r, hex, 8));
IJCRB_assert(!ijcringbuffer_produce(r, hex, 1));
IJCRB_assert(ijcringbuffer_consumeable_size(r) == 8);
IJCRB_assert(memcmp(ijcringbuffer_peek(r), hex, 8) == 0);
ijcringbuffer_consume(r, 8);
IJCRB_assert(ijcringbuffer_produce(r, hex + 4, 7));
IJCRB_assert(ijcringbuffer_consumeable_size(r) == 7);
IJCRB_assert(memcmp(ijcringbuffer_peek(r), hex + 4, 7) == 0);
ijcringbuffer_consume(r, 6);
IJCRB_assert(ijcringbuffer_produce(r, hex, 6));
IJCRB_assert(memcmp(ijcringbuffer_peek(r), hex + 4 + 6, 1) == 0);
ijcringbuffer_consume(r, 1);
IJCRB_assert(ijcringbuffer_consumeable_size(r) == 6);
IJCRB_assert(memcmp(ijcringbuffer_peek(r), hex, 6) == 0);
ijcringbuffer_consume(r, 6);
IJCRB_assert(ijcringbuffer_is_empty(r));
/* */
ijcringbuffer_reset(r); memset(temp, 0, sizeof temp);
IJCRB_assert(ijcringbuffer_produce(r, hex, 6));
IJCRB_assert(ijcringbuffer_consumeable_size(r) == 6);
ijcringbuffer_consume(r, 5);
IJCRB_assert(ijcringbuffer_produce(r, hex, 4));
IJCRB_assert(ijcringbuffer_produce(r, hex, 1));
IJCRB_assert(!ijcringbuffer_produce(r, hex, 1));
/* */
ijcringbuffer_reset(r); memset(temp, 0, sizeof temp);
t = 0xffffffffu - 3u;
r->read_cursor = r->write_cursor = t;
IJCRB_assert(ijcringbuffer_produce(r, hex, 6));
IJCRB_assert(ijcringbuffer_produce(r, hex, 2));
IJCRB_assert(ijcringbuffer_consumeable_size(r) == 8);
IJCRB_assert(memcmp(ijcringbuffer_peek(r), hex, 6) == 0);
ijcringbuffer_consume(r, 6);
IJCRB_assert(ijcringbuffer_consumeable_size(r) == 2);
IJCRB_assert(memcmp(ijcringbuffer_peek(r), hex, 2) == 0);
ijcringbuffer_consume(r, 2);
/* */
ijcringbuffer_reset(r); memset(temp, 0, sizeof temp);
t = 0xffffffffu - 3u;
r->write_cursor = t;
r->read_cursor = t-1;
IJCRB_assert(ijcringbuffer_consumeable_size(r) == 1);
IJCRB_assert(ijcringbuffer_produce(r, hex, 4));
IJCRB_assert(ijcringbuffer_consumeable_size_continuous(r) == 5);
IJCRB_assert(ijcringbuffer_consumeable_size(r) == 5);
IJCRB_assert(!ijcringbuffer_produce(r, hex, 4));
IJCRB_assert(ijcringbuffer_produce(r, hex, 3));
IJCRB_assert(!ijcringbuffer_produce(r, hex, 1));
IJCRB_assert(ijcringbuffer_consumeable_size_continuous(r) == 5);
IJCRB_assert(ijcringbuffer_consumeable_size(r) == 8);
/* */
ijcringbuffer_reset(r); memset(temp, 0, sizeof temp);
IJCRB_assert(ijcringbuffer_produce(r, hex, 6));
ijcringbuffer_consume(r, 5);
IJCRB_assert(ijcringbuffer_consumeable_size(r) == 1);
IJCRB_assert(ijcringbuffer_produce(r, hex, 2));
IJCRB_assert(ijcringbuffer_consumeable_size_continuous(r) == 3);
IJCRB_assert(ijcringbuffer_produce(r, hex, 5));
IJCRB_assert(ijcringbuffer_consumeable_size_continuous(r) == 3);
IJCRB_assert(ijcringbuffer_consumeable_size(r) == 8);
/* */
ijcringbuffer_reset(r); memset(temp, 0, sizeof temp);
IJCRB_assert(ijcringbuffer_produce(r, hex, 8));
ijcringbuffer_consume(r, 1);
IJCRB_assert(ijcringbuffer_consumeable_size_continuous(r) == 7);
IJCRB_assert(ijcringbuffer_consumeable_size(r) == 7);
IJCRB_assert(ijcringbuffer_produce(r, hex + 1, 1));
IJCRB_assert(ijcringbuffer_consumeable_size_continuous(r) == 7);
IJCRB_assert(ijcringbuffer_consumeable_size(r) == 8);
ijcringbuffer_consume(r, 7);
IJCRB_assert(ijcringbuffer_consumeable_size_continuous(r) == 1);
IJCRB_assert(ijcringbuffer_consumeable_size(r) == 1);
IJCRB_assert(memcmp(ijcringbuffer_peek(r), hex + 1, 1) == 0);
}
#ifdef IJCRINGBUFFER_TEST_MAIN
int main(int argc, char **argv)
{
(void)(argc, argv);
ijcringbuffer_test();
return 0;
}
#endif /* IJCRINGBUFFER_TEST_MAIN */
#endif /* IJCRINGBUFFER_TEST */
#endif /* IJCRINGBUFFER_IMPLEMENTATION */