jamie@216: /*
jamie@216:  * ringbuf.c - C ring buffer (FIFO) implementation.
jamie@216:  *
jamie@216:  * Written in 2011 by Drew Hess <dhess-src@bothan.net>.
jamie@216:  *
jamie@216:  * To the extent possible under law, the author(s) have dedicated all
jamie@216:  * copyright and related and neighboring rights to this software to
jamie@216:  * the public domain worldwide. This software is distributed without
jamie@216:  * any warranty.
jamie@216:  *
jamie@216:  * You should have received a copy of the CC0 Public Domain Dedication
jamie@216:  * along with this software. If not, see
jamie@216:  * <http://creativecommons.org/publicdomain/zero/1.0/>.
jamie@216:  */
jamie@216: 
jamie@216: #include "ringbuf.h"
jamie@216: 
jamie@216: #include <stdint.h>
jamie@216: #include <stdlib.h>
jamie@216: #include <string.h>
jamie@216: #include <sys/types.h>
jamie@216: #include <assert.h>
jamie@216: 
jamie@279: #ifndef MIN
jamie@279: #define MIN(x,y) ((x)>(y)?(y):(x))
jamie@279: #endif
jamie@216: /*
jamie@216:  * The code is written for clarity, not cleverness or performance, and
jamie@216:  * contains many assert()s to enforce invariant assumptions and catch
jamie@216:  * bugs. Feel free to optimize the code and to remove asserts for use
jamie@216:  * in your own projects, once you're comfortable that it functions as
jamie@216:  * intended.
jamie@216:  */
jamie@216: 
jamie@216: struct ringbuf_t
jamie@216: {
jamie@216:     uint8_t *buf;
jamie@216:     uint8_t *head, *tail;
jamie@216:     size_t size;
jamie@216: };
jamie@216: 
jamie@216: ringbuf_t
jamie@216: ringbuf_new(size_t capacity)
jamie@216: {
jamie@216:     ringbuf_t rb = malloc(sizeof(struct ringbuf_t));
jamie@216:     if (rb) {
jamie@216: 
jamie@216:         /* One byte is used for detecting the full condition. */
jamie@216:         rb->size = capacity + 1;
jamie@216:         rb->buf = malloc(rb->size);
jamie@216:         if (rb->buf)
jamie@216:             ringbuf_reset(rb);
jamie@216:         else {
jamie@216:             free(rb);
jamie@216:             return 0;
jamie@216:         }
jamie@216:     }
jamie@216:     return rb;
jamie@216: }
jamie@216: 
jamie@216: size_t
jamie@216: ringbuf_buffer_size(const struct ringbuf_t *rb)
jamie@216: {
jamie@216:     return rb->size;
jamie@216: }
jamie@216: 
jamie@216: void
jamie@216: ringbuf_reset(ringbuf_t rb)
jamie@216: {
jamie@216:     rb->head = rb->tail = rb->buf;
jamie@216: }
jamie@216: 
jamie@216: void
jamie@216: ringbuf_free(ringbuf_t *rb)
jamie@216: {
jamie@216:     assert(rb && *rb);
jamie@216:     free((*rb)->buf);
jamie@216:     free(*rb);
jamie@216:     *rb = 0;
jamie@216: }
jamie@216: 
jamie@216: size_t
jamie@216: ringbuf_capacity(const struct ringbuf_t *rb)
jamie@216: {
jamie@216:     return ringbuf_buffer_size(rb) - 1;
jamie@216: }
jamie@216: 
jamie@216: /*
jamie@216:  * Return a pointer to one-past-the-end of the ring buffer's
jamie@216:  * contiguous buffer. You shouldn't normally need to use this function
jamie@216:  * unless you're writing a new ringbuf_* function.
jamie@216:  */
jamie@216: static const uint8_t *
jamie@216: ringbuf_end(const struct ringbuf_t *rb)
jamie@216: {
jamie@216:     return rb->buf + ringbuf_buffer_size(rb);
jamie@216: }
jamie@216: 
jamie@216: size_t
jamie@216: ringbuf_bytes_free(const struct ringbuf_t *rb)
jamie@216: {
jamie@216:     if (rb->head >= rb->tail)
jamie@216:         return ringbuf_capacity(rb) - (rb->head - rb->tail);
jamie@216:     else
jamie@216:         return rb->tail - rb->head - 1;
jamie@216: }
jamie@216: 
jamie@216: size_t
jamie@216: ringbuf_bytes_used(const struct ringbuf_t *rb)
jamie@216: {
jamie@216:     return ringbuf_capacity(rb) - ringbuf_bytes_free(rb);
jamie@216: }
jamie@216: 
jamie@216: int
jamie@216: ringbuf_is_full(const struct ringbuf_t *rb)
jamie@216: {
jamie@216:     return ringbuf_bytes_free(rb) == 0;
jamie@216: }
jamie@216: 
jamie@216: int
jamie@216: ringbuf_is_empty(const struct ringbuf_t *rb)
jamie@216: {
jamie@216:     return ringbuf_bytes_free(rb) == ringbuf_capacity(rb);
jamie@216: }
jamie@216: 
jamie@216: const void *
jamie@216: ringbuf_tail(const struct ringbuf_t *rb)
jamie@216: {
jamie@216:     return rb->tail;
jamie@216: }
jamie@216: 
jamie@216: const void *
jamie@216: ringbuf_head(const struct ringbuf_t *rb)
jamie@216: {
jamie@216:     return rb->head;
jamie@216: }
jamie@216: 
jamie@216: /*
jamie@216:  * Given a ring buffer rb and a pointer to a location within its
jamie@216:  * contiguous buffer, return the a pointer to the next logical
jamie@216:  * location in the ring buffer.
jamie@216:  */
jamie@216: static uint8_t *
jamie@216: ringbuf_nextp(ringbuf_t rb, const uint8_t *p)
jamie@216: {
jamie@216:     /*
jamie@216:      * The assert guarantees the expression (++p - rb->buf) is
jamie@216:      * non-negative; therefore, the modulus operation is safe and
jamie@216:      * portable.
jamie@216:      */
jamie@216:     assert((p >= rb->buf) && (p < ringbuf_end(rb)));
jamie@216:     return rb->buf + ((++p - rb->buf) % ringbuf_buffer_size(rb));
jamie@216: }
jamie@216: 
jamie@216: size_t
jamie@216: ringbuf_findchr(const struct ringbuf_t *rb, int c, size_t offset)
jamie@216: {
jamie@216:     const uint8_t *bufend = ringbuf_end(rb);
jamie@216:     size_t bytes_used = ringbuf_bytes_used(rb);
jamie@216:     if (offset >= bytes_used)
jamie@216:         return bytes_used;
jamie@216: 
jamie@216:     const uint8_t *start = rb->buf +
jamie@216:         (((rb->tail - rb->buf) + offset) % ringbuf_buffer_size(rb));
jamie@216:     assert(bufend > start);
jamie@216:     size_t n = MIN(bufend - start, bytes_used - offset);
jamie@216:     const uint8_t *found = memchr(start, c, n);
jamie@216:     if (found)
jamie@216:         return offset + (found - start);
jamie@216:     else
jamie@216:         return ringbuf_findchr(rb, c, offset + n);
jamie@216: }
jamie@216: 
jamie@216: size_t
jamie@216: ringbuf_memset(ringbuf_t dst, int c, size_t len)
jamie@216: {
jamie@216:     const uint8_t *bufend = ringbuf_end(dst);
jamie@216:     size_t nwritten = 0;
jamie@216:     size_t count = MIN(len, ringbuf_buffer_size(dst));
jamie@216:     int overflow = count > ringbuf_bytes_free(dst);
jamie@216: 
jamie@216:     while (nwritten != count) {
jamie@216: 
jamie@216:         /* don't copy beyond the end of the buffer */
jamie@216:         assert(bufend > dst->head);
jamie@216:         size_t n = MIN(bufend - dst->head, count - nwritten);
jamie@216:         memset(dst->head, c, n);
jamie@216:         dst->head += n;
jamie@216:         nwritten += n;
jamie@216: 
jamie@216:         /* wrap? */
jamie@216:         if (dst->head == bufend)
jamie@216:             dst->head = dst->buf;
jamie@216:     }
jamie@216: 
jamie@216:     if (overflow) {
jamie@216:         dst->tail = ringbuf_nextp(dst, dst->head);
jamie@216:         assert(ringbuf_is_full(dst));
jamie@216:     }
jamie@216: 
jamie@216:     return nwritten;
jamie@216: }
jamie@216: 
jamie@216: void *
jamie@216: ringbuf_memcpy_into(ringbuf_t dst, const void *src, size_t count)
jamie@216: {
jamie@216:     const uint8_t *u8src = src;
jamie@216:     const uint8_t *bufend = ringbuf_end(dst);
jamie@216:     int overflow = count > ringbuf_bytes_free(dst);
jamie@216:     size_t nread = 0;
jamie@216: 
jamie@216:     while (nread != count) {
jamie@216:         /* don't copy beyond the end of the buffer */
jamie@216:         assert(bufend > dst->head);
jamie@216:         size_t n = MIN(bufend - dst->head, count - nread);
jamie@216:         memcpy(dst->head, u8src + nread, n);
jamie@216:         dst->head += n;
jamie@216:         nread += n;
jamie@216: 
jamie@216:         /* wrap? */
jamie@216:         if (dst->head == bufend)
jamie@216:             dst->head = dst->buf;
jamie@216:     }
jamie@216: 
jamie@216:     if (overflow) {
jamie@216:         dst->tail = ringbuf_nextp(dst, dst->head);
jamie@216:         assert(ringbuf_is_full(dst));
jamie@216:     }
jamie@216: 
jamie@216:     return dst->head;
jamie@216: }
jamie@216: 
jamie@216: ssize_t
jamie@216: ringbuf_read(int fd, ringbuf_t rb, size_t count)
jamie@216: {
jamie@216:     const uint8_t *bufend = ringbuf_end(rb);
jamie@216:     size_t nfree = ringbuf_bytes_free(rb);
jamie@216: 
jamie@216:     /* don't write beyond the end of the buffer */
jamie@216:     assert(bufend > rb->head);
jamie@216:     count = MIN(bufend - rb->head, count);
jamie@216:     ssize_t n = read(fd, rb->head, count);
jamie@216:     if (n > 0) {
jamie@216:         assert(rb->head + n <= bufend);
jamie@216:         rb->head += n;
jamie@216: 
jamie@216:         /* wrap? */
jamie@216:         if (rb->head == bufend)
jamie@216:             rb->head = rb->buf;
jamie@216: 
jamie@216:         /* fix up the tail pointer if an overflow occurred */
jamie@216:         if (n > nfree) {
jamie@216:             rb->tail = ringbuf_nextp(rb, rb->head);
jamie@216:             assert(ringbuf_is_full(rb));
jamie@216:         }
jamie@216:     }
jamie@216: 
jamie@216:     return n;
jamie@216: }
jamie@216: 
jamie@216: void *
jamie@216: ringbuf_memcpy_from(void *dst, ringbuf_t src, size_t count, bool destroy)
jamie@216: {
jamie@216:     size_t bytes_used = ringbuf_bytes_used(src);
jamie@216:     if (count > bytes_used)
jamie@216:         return 0;
jamie@216: 
jamie@216:     uint8_t *u8dst = dst;
jamie@216:     const uint8_t *bufend = ringbuf_end(src);
jamie@216:     uint8_t *tail = src->tail;
jamie@216:     size_t nwritten = 0;
jamie@216:     while (nwritten != count) {
jamie@216:         assert(bufend > src->tail);
jamie@283:         size_t n = MIN(bufend - src->tail, (count - nwritten));
jamie@216:         memcpy(u8dst + nwritten, src->tail, n);
jamie@216:         src->tail += n;
jamie@216:         nwritten += n;
jamie@216: 
jamie@216:         /* wrap ? */
jamie@216:         if (src->tail == bufend)
jamie@216:             src->tail = src->buf;
jamie@216:     }
jamie@216: 
jamie@216:     if (!destroy)
jamie@216:     {
jamie@216:         src->tail = tail;
jamie@237:         assert(ringbuf_bytes_used(src) == bytes_used);
jamie@216:     }
jamie@237:     else
jamie@237:     {
jamie@237:         assert(count + ringbuf_bytes_used(src) == bytes_used);
jamie@237:     }
jamie@216:     return src->tail;
jamie@216: }
jamie@216: 
jamie@216: ssize_t
jamie@216: ringbuf_write(int fd, ringbuf_t rb, size_t count)
jamie@216: {
jamie@216:     size_t bytes_used = ringbuf_bytes_used(rb);
jamie@216:     if (count > bytes_used)
jamie@216:         return 0;
jamie@216: 
jamie@216:     const uint8_t *bufend = ringbuf_end(rb);
jamie@216:     assert(bufend > rb->head);
jamie@216:     count = MIN(bufend - rb->tail, count);
jamie@216:     ssize_t n = write(fd, rb->tail, count);
jamie@216:     if (n > 0) {
jamie@216:         assert(rb->tail + n <= bufend);
jamie@216:         rb->tail += n;
jamie@216: 
jamie@216:         /* wrap? */
jamie@216:         if (rb->tail == bufend)
jamie@216:             rb->tail = rb->buf;
jamie@216: 
jamie@216:         assert(n + ringbuf_bytes_used(rb) == bytes_used);
jamie@216:     }
jamie@216: 
jamie@216:     return n;
jamie@216: }
jamie@216: 
jamie@216: void *
jamie@216: ringbuf_copy(ringbuf_t dst, ringbuf_t src, size_t count)
jamie@216: {
jamie@216:     size_t src_bytes_used = ringbuf_bytes_used(src);
jamie@216:     if (count > src_bytes_used)
jamie@216:         return 0;
jamie@216:     int overflow = count > ringbuf_bytes_free(dst);
jamie@216: 
jamie@216:     const uint8_t *src_bufend = ringbuf_end(src);
jamie@216:     const uint8_t *dst_bufend = ringbuf_end(dst);
jamie@216:     size_t ncopied = 0;
jamie@216:     while (ncopied != count) {
jamie@216:         assert(src_bufend > src->tail);
jamie@216:         size_t nsrc = MIN(src_bufend - src->tail, count - ncopied);
jamie@216:         assert(dst_bufend > dst->head);
jamie@216:         size_t n = MIN(dst_bufend - dst->head, nsrc);
jamie@216:         memcpy(dst->head, src->tail, n);
jamie@216:         src->tail += n;
jamie@216:         dst->head += n;
jamie@216:         ncopied += n;
jamie@216: 
jamie@216:         /* wrap ? */
jamie@216:         if (src->tail == src_bufend)
jamie@216:             src->tail = src->buf;
jamie@216:         if (dst->head == dst_bufend)
jamie@216:             dst->head = dst->buf;
jamie@216:     }
jamie@216: 
jamie@216:     assert(count + ringbuf_bytes_used(src) == src_bytes_used);
jamie@216:     
jamie@216:     if (overflow) {
jamie@216:         dst->tail = ringbuf_nextp(dst, dst->head);
jamie@216:         assert(ringbuf_is_full(dst));
jamie@216:     }
jamie@216: 
jamie@216:     return dst->head;
jamie@216: }