Skip to content

Instantly share code, notes, and snippets.

@jsimmons
Created May 31, 2011 12:08
Show Gist options
  • Select an option

  • Save jsimmons/1000397 to your computer and use it in GitHub Desktop.

Select an option

Save jsimmons/1000397 to your computer and use it in GitHub Desktop.
Didn't want to loose this to the depths of my projects folder. Note to self, comment your damn implementation too.
#include "ring-buffer.h"
#include <stdlib.h>
#include <string.h>
#include <assert.h>
RingBuffer *rb_new(size_t size)
{
RingBuffer *buf = malloc(sizeof(*buf));
assert(buf != NULL);
buf->data = malloc(size);
assert(buf->data != NULL);
buf->size = size;
buf->head = buf->fill = 0;
return buf;
}
static inline void advance_tail(RingBuffer *buf, size_t bytes)
{
buf->fill += bytes;
}
void rb_write(RingBuffer *buf, const char *from, size_t bytes)
{
assert(bytes <= rb_remain(buf));
char *tail = buf->data + ((buf->head + buf->fill) % buf->size);
char *write_end = buf->data + ((buf->head + buf->fill + bytes) % buf->size);
if(tail <= write_end)
{
memcpy(tail, from, bytes);
}
else
{
char *end = buf->data + buf->size;
size_t first_write = end - tail;
memcpy(tail, from, first_write);
size_t second_write = bytes - first_write;
memcpy(buf->data, from + first_write, second_write);
}
advance_tail(buf, bytes);
}
char *rb_write_pointer(const RingBuffer *buf, size_t *writable)
{
if(rb_is_full(buf))
{
*writable = 0;
return NULL;
}
char *head = buf->data + buf->head;
char *tail = buf->data + ((buf->head + buf->fill) % buf->size);
if(tail < head)
{
*writable = head - tail;
}
else
{
char *end = buf->data + buf->size;
*writable = end - tail;
}
return tail;
}
void rb_write_commit(RingBuffer *buf, size_t bytes)
{
assert(bytes <= rb_remain(buf));
advance_tail(buf, bytes);
}
static inline void advance_head(RingBuffer *buf, size_t bytes)
{
buf->head = (buf->head + bytes) % buf->size;
buf->fill -= bytes;
}
void rb_read(RingBuffer *buf, char *to, size_t bytes)
{
assert(bytes <= rb_used(buf));
char *head = buf->data + buf->head;
char *end_read = buf->data + ((buf->head + bytes) % buf->size);
if(end_read <= head)
{
char *end = buf->data + buf->size;
size_t first_read = end - head;
memcpy(to, head, first_read);
size_t second_read = bytes - first_read;
memcpy(to + first_read, buf->data, second_read);
}
else
{
memcpy(to, head, bytes);
}
advance_head(buf, bytes);
}
const char *rb_read_pointer(const RingBuffer *buf, size_t offset, size_t *readable)
{
if(rb_is_empty(buf))
{
*readable = 0;
return NULL;
}
char *head = buf->data + buf->head + offset;
char *tail = buf->data + ((buf->head + offset + buf->fill) % buf->size);
if(tail <= head)
{
char *end = buf->data + buf->size;
*readable = end - head;
}
else
{
*readable = tail - head;
}
return head;
}
void rb_read_commit(RingBuffer *buf, size_t bytes)
{
assert(rb_used(buf) >= bytes);
advance_head(buf, bytes);
}
void rb_stream(const RingBuffer *from, RingBuffer *to, size_t bytes)
{
assert(rb_used(from) <= bytes);
assert(rb_remain(to) >= bytes);
size_t copied = 0;
while(copied < bytes)
{
size_t can_read;
const char *from_ptr = rb_read_pointer(from, copied, &can_read);
size_t copied_this_read = 0;
while(copied_this_read < can_read)
{
size_t can_write;
char *to_ptr = rb_write_pointer(to, &can_write);
size_t write = (can_read > can_write) ? can_write : can_read;
memcpy(to_ptr, from_ptr, write);
copied_this_read += write;
}
copied += copied_this_read;
}
advance_tail(to, copied);
}
void rb_free(RingBuffer *buf)
{
if(buf != NULL)
{
free(buf->data);
free(buf);
}
}
#ifndef RIRC_RING_BUFFER_H
#define RIRC_RING_BUFFER_H
#include <stdbool.h>
#include <stddef.h>
/**
* @file ring-buffer.h
*/
/// Fixed size continuous FIFO buffer.
typedef struct
{
/**
* Pointer to data.
*/
char *data;
/**
* Length of data.
*/
size_t size;
/**
* Offset in data for finding the start of valid data.
*/
size_t head;
/**
* Length of valid data.
*/
size_t fill;
} RingBuffer;
/// Create a new ring buffer.
/**
* @param size Length of buffer in bytes.
* @return Pointer to a newly allocated RingBuffer.
* @sa rb_free
*/
RingBuffer *rb_new(size_t size);
/// Check if buffer is empty.
/**
* @param buf Buffer.
* @return True if buffer is empty otherwise false.
*/
static inline bool rb_is_empty(const RingBuffer *buf)
{
return buf->fill == 0;
}
/// Check if buffer is full.
/**
* @param buf Buffer.
* @return True if buffer is full.
*/
static inline bool rb_is_full(const RingBuffer *buf)
{
return buf->fill == buf->size;
}
/// Get the length of the buffer.
/**
* @param buf Buffer.
* @return Size of buffer in bytes.
*/
static inline size_t rb_size(const RingBuffer *buf)
{
return buf->size;
}
/// Get the length of valid data.
/**
* @param buf Buffer.
* @return Length of valid data in bytes.
*/
static inline size_t rb_used(const RingBuffer *buf)
{
return buf->fill;
}
/// Get the free space remaining.
/**
* @param buf Buffer.
* @return Length of free space in bytes.
*/
static inline size_t rb_remain(const RingBuffer *buf)
{
return buf->size - buf->fill;
}
/// Empty the buffer of valid data.
/**
* @param buf Buffer.
*/
static inline void rb_empty(RingBuffer *buf)
{
buf->head = buf->fill = 0;
}
/// Copy data into buffer.
/**
* @remark This will extend the valid section so calling rb_write_commit() manually is
* unnecessary.
*
* @param buf Target.
* @param from Pointer to data.
* @param bytes Length of data to copy in bytes.
*/
void rb_write(RingBuffer *buf, const char *from, size_t bytes);
/// Get a pointer to directly writable space.
/**
* @remark The number of bytes given by writable may be less than the total number remaining
* free in the buffer, but the rest will be writable from a second call to this function
* that will return a different pointer. This is because of the 'wrap around' from the end
* to the beginning of the buffer's memory block.
*
* @param buf Buffer.
* @param[out] writable Length of writable area in bytes.
* @return Pointer to writable data.
* @sa rb_write_commit
*/
char *rb_write_pointer(const RingBuffer *buf, size_t *writable);
/// Extend the valid section after a write operation.
/**
* @remark If this is not called following a write the data written is essentially discarded.
*
* @param buf Buffer.
* @param bytes Length by which to extend the valid section.
* @sa rb_write_pointer
*/
void rb_write_commit(RingBuffer *buf, size_t bytes);
/// Copy data from a buffer.
/**
* @remark This advances the buffer as well as copying the data so calling rb_read_commit() is
* unnecessary.
*
* @param buf Buffer.
* @param to Target of copy.
* @param bytes Number of bytes to copy.
* @sa rb_read_pointer
*/
void rb_read(RingBuffer *buf, char *to, size_t bytes);
/// Get a pointer to directly readable space in buffer.
/**
* @remark The number of bytes given by readable may be less than the total number used by
* the buffer, but the rest will be writable from a second call to this function
* that will return a different pointer. This is because of the 'wrap around' from
* the end to the beginning of the buffer's memory block.
*
* @param buf Buffer.
* @param offset Offset into valid data from which to read.
* @param[out] readable Length of readable data in bytes.
* @return Pointer to readable data.
* @sa rb_read_commit
*/
const char *rb_read_pointer(const RingBuffer *buf, size_t offset, size_t *readable);
/// Advance head of valid data.
/**
* This updates the buffer's state moving the head of the valid data forwards such
* that data at the beginning of the valid section is discarded.
*
* @remark This can be called following rb_read_pointer(), or not. The lifetime of
* specific data in the buffer is up to the user.
*
* @param buf Buffer.
* @param bytes Amount to advance head by in bytes.
*/
void rb_read_commit(RingBuffer *buf, size_t bytes);
/// Stream the contents of one buffer into another.
/**
* @param from Buffer to copy from.
* @param to Buffer to copy to.
* @param bytes Number of bytes to copy.
*/
void rb_stream(const RingBuffer *from, RingBuffer *to, size_t bytes);
/// Free a RingBuffer object allocated by rb_new() and the data backing it.
/**
* @remark Can be called safely on a NULL pointer.
* @param buf Buffer.
* @sa rb_new
*/
void rb_free(RingBuffer *buf);
#endif
#include "tests.h"
#include <stdlib.h>
#include <string.h>
#include <glib.h>
#include <ring-buffer.h>
static const size_t BUFFER_SIZE = 512;
typedef struct
{
RingBuffer *buffer;
} RingBufferFixture;
static void setup(RingBufferFixture *fixture, gconstpointer static_data)
{
g_assert(static_data == NULL);
fixture->buffer = rb_new(BUFFER_SIZE);
}
static void teardown(RingBufferFixture *fixture, gconstpointer static_data)
{
g_assert(static_data == NULL);
rb_free(fixture->buffer);
}
static void test_new_free()
{
RingBuffer *buf = rb_new(BUFFER_SIZE);
g_assert(buf != NULL);
g_assert(buf->data != NULL);
g_assert_cmpuint(buf->size, ==, BUFFER_SIZE);
g_assert_cmpuint(buf->head, ==, 0);
g_assert_cmpuint(buf->fill, ==, 0);
g_assert(rb_is_empty(buf));
g_assert(!rb_is_full(buf));
g_assert_cmpuint(rb_size(buf), ==, BUFFER_SIZE);
g_assert_cmpuint(rb_used(buf), ==, 0);
g_assert_cmpuint(rb_remain(buf), ==, BUFFER_SIZE);
rb_free(buf);
}
static void test_rw(RingBufferFixture *fixture, gconstpointer static_data)
{
g_assert(static_data == NULL);
RingBuffer *buf = fixture->buffer;
/// WRITING
const char *data = "Hello, World!";
size_t data_length = strlen(data) + 1;
// Simple write.
g_assert_cmpuint(rb_remain(buf), >=, data_length);
rb_write(buf, data, data_length);
g_assert_cmpuint(rb_used(buf), ==, data_length);
// Block write.
size_t writable;
char *writer = rb_write_pointer(buf, &writable);
g_assert(writer != NULL);
g_assert_cmpuint(writable, >=, data_length);
memcpy(writer, data, data_length);
rb_write_commit(buf, data_length);
g_assert_cmpuint(rb_used(buf), ==, data_length * 2);
/// READING
char *data_out = malloc(sizeof(data_length));
// Simple read.
rb_read(buf, data_out, data_length);
g_assert_cmpstr(data_out, ==, data);
// Buffer should have advanced after read.
g_assert_cmpuint(rb_used(buf), ==, data_length);
memset(data_out, 0, data_length);
// Block read.
size_t readable;
size_t read = 0;
do
{
g_assert(!rb_is_empty(buf));
const char *out = rb_read_pointer(buf, 0, &readable);
g_assert(out != NULL);
g_assert_cmpuint(readable, >, 0);
memcpy(data_out + read, out, readable);
read += readable;
rb_read_commit(buf, readable);
} while(read < data_length);
g_assert(rb_is_empty(buf));
g_assert_cmpstr(data_out, ==, data);
}
static void test_stream(RingBufferFixture *fixture, gconstpointer static_data)
{
g_assert(static_data == NULL);
RingBuffer *buf = fixture->buffer;
const char *data = "Hello, World!";
size_t data_length = strlen(data) + 1;
for(int i = 0; i < 5; i++)
{
rb_write(buf, data, data_length);
}
RingBuffer *buf2 = rb_new(data_length * 5);
rb_stream(buf, buf2, rb_used(buf));
g_assert(rb_is_full(buf2));
rb_empty(buf);
g_assert(rb_is_empty(buf));
char *out = malloc(data_length);
g_assert(out != NULL);
for(int i = 0; i < 5; i++)
{
memset(out, 0, data_length);
rb_read(buf2, out, data_length);
g_assert_cmpstr(data, ==, out);
}
g_assert(rb_is_empty(buf));
}
void test_wrap_around(RingBufferFixture *fixture, gconstpointer static_data)
{
g_assert(static_data == NULL);
RingBuffer *buf = fixture->buffer;
const char *data = "Hello, World!";
size_t data_length = strlen(data) + 1;
rb_write(buf, data, data_length);
for(int i = 0; i < 500; i++)
{
rb_write(buf, data, data_length);
rb_read_commit(buf, data_length);
}
char *out = malloc(data_length);
g_assert(out != NULL);
rb_read(buf, out, data_length);
g_assert_cmpstr(data, ==, out);
g_assert(rb_is_empty(buf));
}
void ringbuffer_setup_tests()
{
g_test_add_func("/ringbuffer/new free", test_new_free);
g_test_add("/ringbuffer/read write", RingBufferFixture, NULL, setup, test_rw, teardown);
g_test_add("/ringbuffer/stream", RingBufferFixture, NULL, setup, test_stream, teardown);
g_test_add("/ringbuffer/wrap around", RingBufferFixture, NULL, setup, test_wrap_around, teardown);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment