Created
May 31, 2011 12:08
-
-
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.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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); | |
| } | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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 |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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