1 /*
2 * ringbuf.c - C ring buffer (FIFO) implementation.
3 *
4 * Written in 2011 by Drew Hess <dhess-src@bothan.net>.
5 *
6 * To the extent possible under law, the author(s) have dedicated all
7 * copyright and related and neighboring rights to this software to
8 * the public domain worldwide. This software is distributed without
9 * any warranty.
10 *
11 * You should have received a copy of the CC0 Public Domain Dedication
12 * along with this software. If not, see
13 * <http://creativecommons.org/publicdomain/zero/1.0/>.
14 */
15
16 #ifndef KITTY_DEBUG_BUILD
17 #define NDEBUG 1
18 #endif
19 #include "ringbuf.h"
20
21 #include <stdint.h>
22 #include <stdlib.h>
23 #include <string.h>
24 #include <sys/types.h>
25 #include <unistd.h>
26 #include <sys/param.h>
27 #include <assert.h>
28
29 static size_t
size_t_min(size_t x,size_t y)30 size_t_min(size_t x, size_t y) {
31 return x > y ? y : x;
32 }
33
34 /*
35 * The code is written for clarity, not cleverness or performance, and
36 * contains many assert()s to enforce invariant assumptions and catch
37 * bugs. Feel free to optimize the code and to remove asserts for use
38 * in your own projects, once you're comfortable that it functions as
39 * intended.
40 */
41
42 struct ringbuf_t
43 {
44 uint8_t *buf;
45 uint8_t *head, *tail;
46 size_t size;
47 };
48
49 ringbuf_t
ringbuf_new(size_t capacity)50 ringbuf_new(size_t capacity)
51 {
52 ringbuf_t rb = malloc(sizeof(struct ringbuf_t));
53 if (rb) {
54
55 /* One byte is used for detecting the full condition. */
56 rb->size = capacity + 1;
57 rb->buf = malloc(rb->size);
58 if (rb->buf)
59 ringbuf_reset(rb);
60 else {
61 free(rb);
62 return 0;
63 }
64 }
65 return rb;
66 }
67
68 size_t
ringbuf_buffer_size(const struct ringbuf_t * rb)69 ringbuf_buffer_size(const struct ringbuf_t *rb)
70 {
71 return rb->size;
72 }
73
74 void
ringbuf_reset(ringbuf_t rb)75 ringbuf_reset(ringbuf_t rb)
76 {
77 rb->head = rb->tail = rb->buf;
78 }
79
80 void
ringbuf_free(ringbuf_t * rb)81 ringbuf_free(ringbuf_t *rb)
82 {
83 assert(rb && *rb);
84 free((*rb)->buf);
85 free(*rb);
86 *rb = 0;
87 }
88
89 size_t
ringbuf_capacity(const struct ringbuf_t * rb)90 ringbuf_capacity(const struct ringbuf_t *rb)
91 {
92 return ringbuf_buffer_size(rb) - 1;
93 }
94
95 /*
96 * Return a pointer to one-past-the-end of the ring buffer's
97 * contiguous buffer. You shouldn't normally need to use this function
98 * unless you're writing a new ringbuf_* function.
99 */
100 static const uint8_t *
ringbuf_end(const struct ringbuf_t * rb)101 ringbuf_end(const struct ringbuf_t *rb)
102 {
103 return rb->buf + ringbuf_buffer_size(rb);
104 }
105
106 size_t
ringbuf_bytes_free(const struct ringbuf_t * rb)107 ringbuf_bytes_free(const struct ringbuf_t *rb)
108 {
109 if (rb->head >= rb->tail)
110 return ringbuf_capacity(rb) - (rb->head - rb->tail);
111 else
112 return rb->tail - rb->head - 1;
113 }
114
115 size_t
ringbuf_bytes_used(const struct ringbuf_t * rb)116 ringbuf_bytes_used(const struct ringbuf_t *rb)
117 {
118 return ringbuf_capacity(rb) - ringbuf_bytes_free(rb);
119 }
120
121 int
ringbuf_is_full(const struct ringbuf_t * rb)122 ringbuf_is_full(const struct ringbuf_t *rb)
123 {
124 return ringbuf_bytes_free(rb) == 0;
125 }
126
127 int
ringbuf_is_empty(const struct ringbuf_t * rb)128 ringbuf_is_empty(const struct ringbuf_t *rb)
129 {
130 return ringbuf_bytes_free(rb) == ringbuf_capacity(rb);
131 }
132
133 const void *
ringbuf_tail(const struct ringbuf_t * rb)134 ringbuf_tail(const struct ringbuf_t *rb)
135 {
136 return rb->tail;
137 }
138
139 const void *
ringbuf_head(const struct ringbuf_t * rb)140 ringbuf_head(const struct ringbuf_t *rb)
141 {
142 return rb->head;
143 }
144
145 /*
146 * Given a ring buffer rb and a pointer to a location within its
147 * contiguous buffer, return the a pointer to the next logical
148 * location in the ring buffer.
149 */
150 static uint8_t *
ringbuf_nextp(ringbuf_t rb,const uint8_t * p)151 ringbuf_nextp(ringbuf_t rb, const uint8_t *p)
152 {
153 /*
154 * The assert guarantees the expression (++p - rb->buf) is
155 * non-negative; therefore, the modulus operation is safe and
156 * portable.
157 */
158 assert((p >= rb->buf) && (p < ringbuf_end(rb)));
159 return rb->buf + ((++p - rb->buf) % ringbuf_buffer_size(rb));
160 }
161
162 size_t
ringbuf_findchr(const struct ringbuf_t * rb,int c,size_t offset)163 ringbuf_findchr(const struct ringbuf_t *rb, int c, size_t offset)
164 {
165 const uint8_t *bufend = ringbuf_end(rb);
166 size_t bytes_used = ringbuf_bytes_used(rb);
167 if (offset >= bytes_used)
168 return bytes_used;
169
170 const uint8_t *start = rb->buf +
171 (((rb->tail - rb->buf) + offset) % ringbuf_buffer_size(rb));
172 assert(bufend > start);
173 size_t n = size_t_min(bufend - start, bytes_used - offset);
174 const uint8_t *found = memchr(start, c, n);
175 if (found)
176 return offset + (found - start);
177 else
178 return ringbuf_findchr(rb, c, offset + n);
179 }
180
181 size_t
ringbuf_memset(ringbuf_t dst,int c,size_t len)182 ringbuf_memset(ringbuf_t dst, int c, size_t len)
183 {
184 const uint8_t *bufend = ringbuf_end(dst);
185 size_t nwritten = 0;
186 size_t count = size_t_min(len, ringbuf_buffer_size(dst));
187 int overflow = count > ringbuf_bytes_free(dst);
188
189 while (nwritten != count) {
190
191 /* don't copy beyond the end of the buffer */
192 assert(bufend > dst->head);
193 size_t n = size_t_min(bufend - dst->head, count - nwritten);
194 memset(dst->head, c, n);
195 dst->head += n;
196 nwritten += n;
197
198 /* wrap? */
199 if (dst->head == bufend)
200 dst->head = dst->buf;
201 }
202
203 if (overflow) {
204 dst->tail = ringbuf_nextp(dst, dst->head);
205 assert(ringbuf_is_full(dst));
206 }
207
208 return nwritten;
209 }
210
211 void *
ringbuf_memcpy_into(ringbuf_t dst,const void * src,size_t count)212 ringbuf_memcpy_into(ringbuf_t dst, const void *src, size_t count)
213 {
214 const uint8_t *u8src = src;
215 const uint8_t *bufend = ringbuf_end(dst);
216 int overflow = count > ringbuf_bytes_free(dst);
217 size_t nread = 0;
218
219 while (nread != count) {
220 /* don't copy beyond the end of the buffer */
221 assert(bufend > dst->head);
222 size_t n = size_t_min(bufend - dst->head, count - nread);
223 memcpy(dst->head, u8src + nread, n);
224 dst->head += n;
225 nread += n;
226
227 /* wrap? */
228 if (dst->head == bufend)
229 dst->head = dst->buf;
230 }
231
232 if (overflow) {
233 dst->tail = ringbuf_nextp(dst, dst->head);
234 assert(ringbuf_is_full(dst));
235 }
236
237 return dst->head;
238 }
239
240 ssize_t
ringbuf_read(int fd,ringbuf_t rb,size_t count)241 ringbuf_read(int fd, ringbuf_t rb, size_t count)
242 {
243 const uint8_t *bufend = ringbuf_end(rb);
244 size_t nfree = ringbuf_bytes_free(rb);
245
246 /* don't write beyond the end of the buffer */
247 assert(bufend > rb->head);
248 count = size_t_min(bufend - rb->head, count);
249 ssize_t n = read(fd, rb->head, count);
250 if (n > 0) {
251 assert(rb->head + n <= bufend);
252 rb->head += n;
253
254 /* wrap? */
255 if (rb->head == bufend)
256 rb->head = rb->buf;
257
258 /* fix up the tail pointer if an overflow occurred */
259 if ((size_t)n > nfree) {
260 rb->tail = ringbuf_nextp(rb, rb->head);
261 assert(ringbuf_is_full(rb));
262 }
263 }
264
265 return n;
266 }
267
268 void *
ringbuf_memmove_from(void * dst,ringbuf_t src,size_t count)269 ringbuf_memmove_from(void *dst, ringbuf_t src, size_t count)
270 {
271 size_t bytes_used = ringbuf_bytes_used(src);
272 if (count > bytes_used)
273 return 0;
274
275 uint8_t *u8dst = dst;
276 const uint8_t *bufend = ringbuf_end(src);
277 size_t nwritten = 0;
278 while (nwritten != count) {
279 assert(bufend > src->tail);
280 size_t n = size_t_min(bufend - src->tail, count - nwritten);
281 memcpy(u8dst + nwritten, src->tail, n);
282 src->tail += n;
283 nwritten += n;
284
285 /* wrap ? */
286 if (src->tail == bufend)
287 src->tail = src->buf;
288 }
289
290 assert(count + ringbuf_bytes_used(src) == bytes_used);
291 return src->tail;
292 }
293
294 unsigned char
ringbuf_move_char(ringbuf_t src)295 ringbuf_move_char(ringbuf_t src) {
296 assert(!ringbuf_is_empty(src));
297 const uint8_t *bufend = ringbuf_end(src);
298 assert(bufend > src->tail);
299 uint8_t ans = *src->tail;
300 src->tail += 1;
301 if (src->tail == bufend)
302 src->tail = src->buf;
303 return ans;
304 }
305
306 size_t
ringbuf_memcpy_from(void * dst,const ringbuf_t src,size_t count)307 ringbuf_memcpy_from(void *dst, const ringbuf_t src, size_t count)
308 {
309 size_t bytes_used = ringbuf_bytes_used(src);
310 if (count > bytes_used) count = bytes_used;
311
312 uint8_t *u8dst = dst;
313 const uint8_t *bufend = ringbuf_end(src);
314 size_t nwritten = 0;
315 const uint8_t* tail = src->tail;
316 while (nwritten != count) {
317 assert(bufend > tail);
318 size_t n = size_t_min(bufend - tail, count - nwritten);
319 memcpy(u8dst + nwritten, tail, n);
320 tail += n;
321 nwritten += n;
322
323 /* wrap ? */
324 if (tail == bufend)
325 tail = src->buf;
326 }
327
328 assert(ringbuf_bytes_used(src) == bytes_used);
329 return count;
330 }
331
332
333 ssize_t
ringbuf_write(int fd,ringbuf_t rb,size_t count)334 ringbuf_write(int fd, ringbuf_t rb, size_t count)
335 {
336 size_t bytes_used = ringbuf_bytes_used(rb);
337 if (count > bytes_used)
338 return 0;
339
340 const uint8_t *bufend = ringbuf_end(rb);
341 assert(bufend > rb->head);
342 count = size_t_min(bufend - rb->tail, count);
343 ssize_t n = write(fd, rb->tail, count);
344 if (n > 0) {
345 assert(rb->tail + n <= bufend);
346 rb->tail += n;
347
348 /* wrap? */
349 if (rb->tail == bufend)
350 rb->tail = rb->buf;
351
352 assert(n + ringbuf_bytes_used(rb) == bytes_used);
353 }
354
355 return n;
356 }
357
358 void *
ringbuf_copy(ringbuf_t dst,ringbuf_t src,size_t count)359 ringbuf_copy(ringbuf_t dst, ringbuf_t src, size_t count)
360 {
361 size_t src_bytes_used = ringbuf_bytes_used(src);
362 if (count > src_bytes_used)
363 return 0;
364 int overflow = count > ringbuf_bytes_free(dst);
365
366 const uint8_t *src_bufend = ringbuf_end(src);
367 const uint8_t *dst_bufend = ringbuf_end(dst);
368 size_t ncopied = 0;
369 while (ncopied != count) {
370 assert(src_bufend > src->tail);
371 size_t nsrc = size_t_min(src_bufend - src->tail, count - ncopied);
372 assert(dst_bufend > dst->head);
373 size_t n = size_t_min(dst_bufend - dst->head, nsrc);
374 memcpy(dst->head, src->tail, n);
375 src->tail += n;
376 dst->head += n;
377 ncopied += n;
378
379 /* wrap ? */
380 if (src->tail == src_bufend)
381 src->tail = src->buf;
382 if (dst->head == dst_bufend)
383 dst->head = dst->buf;
384 }
385
386 assert(count + ringbuf_bytes_used(src) == src_bytes_used);
387
388 if (overflow) {
389 dst->tail = ringbuf_nextp(dst, dst->head);
390 assert(ringbuf_is_full(dst));
391 }
392
393 return dst->head;
394 }
395