Instantly share code, notes, and snippets.

Embed
What would you like to do?
Lock-free ring-buffer for single reader/writer without atomic primitives.
// 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 -- 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:
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment