Lock-free ring-buffer for single reader/writer without atomic primitives.

ring_buffer.c

// ring_buffer.c

// ring_buffer -- Trivial lock-free (wait-free) ring-buffer for use in
// single-reader/single-writer scenarios without using atomic primitives.
// Copyright (C) 2017  Isabell Cowan
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

#include <stddef.h>
#include <stdlib.h>
#include <stdbool.h>

#include "ring_buffer.h"

static size_t ring_buffer_next (const ring_buffer_t *rb, size_t i) {
	return (i + 1) % rb->size;
}

ring_buffer_t new_ring_buffer (size_t n) {
	ring_buffer_t rb = {
		.size = n,
		.buffer = malloc (n),
		.write_offset = 0,
		.read_offset = 0
	};

	// Do whatever your going to do if ENOMEM on malloc either here or in the caller.

	return rb;
}

void destroy_ring_buffer (ring_buffer_t *rb) {
	free (rb->buffer);
	rb->buffer = NULL;
}

// Wastes one byte
bool ring_buffer_is_full (const ring_buffer_t *rb) {
	return rb->read_offset == ring_buffer_next (rb, rb->write_offset);
}

bool ring_buffer_is_empty (const ring_buffer_t *rb) {
	return rb->read_offset == rb->write_offset;
}

void ring_buffer_writeb (ring_buffer_t *rb, char c) {
// Caller must call ring_buffer_is_full first, we will thus assume that it is not full.
	rb->buffer[rb->write_offset] = c;
// Memory barrier needed?
	rb->write_offset = ring_buffer_next (rb, rb->write_offset);
}

char ring_buffer_readb (ring_buffer_t *rb) {
// Caller must call ring_buffer_is_empty first, we will thus assume that it is not empty.
	char c = rb->buffer[rb->read_offset];
// Memory barrier needed?
	rb->read_offset = ring_buffer_next (rb, rb->read_offset);
	
	return c;
}

// vim: set ts=4 sw=4 noet syn=c:

ring_buffer.h

// ring_buffer.h

// ring_buffer -- Trivial lock-free (wait-free) ring-buffer for use in
// single-reader/single-writer scenarios without using atomic primitives.
// Copyright (C) 2017  Isabell Cowan
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

typedef struct ring_buffer_struct {
	size_t size;
	volatile char *buffer;
	volatile size_t write_offset;
	volatile size_t read_offset;
} ring_buffer_t;

ring_buffer_t new_ring_buffer (size_t);
bool ring_buffer_is_full (const ring_buffer_t *);
bool ring_buffer_is_empty (const ring_buffer_t *);
void ring_buffer_writeb (ring_buffer_t *, char);
char ring_buffer_readb (ring_buffer_t *);

// vim: set ts=4 sw=4 noet syn=c: