From 7022f39e10551d7ab325d196884de301ddb3087e Mon Sep 17 00:00:00 2001
From: dzwdz
Date: Sun, 10 Apr 2022 17:14:10 +0200
Subject: shared: implement a basic ring buffer

---
 src/kernel/tests/util.c     | 31 +++++++++++++++++++++++++++++++
 src/shared/container/ring.c | 35 +++++++++++++++++++++++++++++++++++
 src/shared/container/ring.h | 16 ++++++++++++++++
 3 files changed, 82 insertions(+)
 create mode 100644 src/shared/container/ring.c
 create mode 100644 src/shared/container/ring.h

diff --git a/src/kernel/tests/util.c b/src/kernel/tests/util.c
index e7dcb82..2442d47 100644
--- a/src/kernel/tests/util.c
+++ b/src/kernel/tests/util.c
@@ -1,5 +1,6 @@
 #include <kernel/tests/base.h>
 #include <kernel/tests/tests.h>
+#include <shared/container/ring.h>
 #include <shared/mem.h>
 
 TEST(memcmp) {
@@ -30,7 +31,37 @@ TEST(strcmp) {
 	TEST_COND(0 != strcmp("stress", "string"));
 }
 
+TEST(ring) {
+	char buf[16], backbuf[16];
+	size_t num_read = 0, num_written = 0;
+	uint8_t c;
+
+	ring_t r = {backbuf, 16, 0, 0};
+
+	TEST_COND(ring_size(&r) == 0);
+	for (size_t i = 0; i < 7; i++)
+		ring_put1b(&r, num_written++);
+	TEST_COND(ring_size(&r) == 7);
+	for (size_t i = 0; i < 3; i++) {
+		ring_get(&r, &c, 1);
+		TEST_COND(num_read++ == c);
+	}
+	TEST_COND(ring_size(&r) == 4);
+
+	for (size_t j = 0; j < 40; j++) {
+		for (size_t i = 0; i < 7; i++)
+			ring_put1b(&r, num_written++ & 0xff);
+		TEST_COND(ring_size(&r) == 11);
+		for (size_t i = 0; i < 7; i++) {
+			ring_get(&r, &c, 1);
+			TEST_COND((num_read++ & 0xff) == c);
+		}
+		TEST_COND(ring_size(&r) == 4);
+	}
+}
+
 void tests_utils(void) {
 	TEST_RUN(memcmp);
 	TEST_RUN(strcmp);
+	TEST_RUN(ring);
 }
diff --git a/src/shared/container/ring.c b/src/shared/container/ring.c
new file mode 100644
index 0000000..525fade
--- /dev/null
+++ b/src/shared/container/ring.c
@@ -0,0 +1,35 @@
+#include <shared/container/ring.h>
+#include <stdbool.h>
+// TODO use memcpy
+
+static bool at_end(ring_t *r) {
+	return  r->_head + 1 == r->_tail
+		|| (r->_head + 1 == r->capacity && r->_tail == 0);
+}
+
+size_t ring_size(ring_t *r) {
+	if (r->_head >= r->_tail)
+		return r->_head - r->_tail;
+	else
+		return r->_head + r->capacity - r->_tail;
+}
+
+void ring_put(ring_t *r, void *buf, size_t len) {
+	for (size_t i = 0; i < len; i++)
+		ring_put1b(r, ((uint8_t*)buf)[i]);
+}
+
+void ring_put1b(ring_t *r, uint8_t byte) {
+	if (at_end(r)) return;
+	((uint8_t*)r->buf)[r->_head++] = byte;
+	if (r->_head >= r->capacity) r->_head = 0;
+}
+
+size_t ring_get(ring_t *r, void *buf, size_t len) {
+	for (size_t i = 0; i < len; i++) {
+		if (at_end(r)) return i;
+		((uint8_t*)buf)[i] = ((uint8_t*)r->buf)[r->_tail++];
+		if (r->_tail >= r->capacity) r->_tail = 0;
+	}
+	return len;
+}
diff --git a/src/shared/container/ring.h b/src/shared/container/ring.h
new file mode 100644
index 0000000..434f6aa
--- /dev/null
+++ b/src/shared/container/ring.h
@@ -0,0 +1,16 @@
+#pragma once
+#include <stddef.h>
+#include <stdint.h>
+
+typedef struct {
+	void *buf;
+	size_t capacity;
+	size_t _head, _tail;
+} ring_t;
+
+size_t	ring_size(ring_t*);
+
+void	ring_put(ring_t*, void*, size_t);
+void	ring_put1b(ring_t*, uint8_t);
+
+size_t	ring_get(ring_t*, void*, size_t);
-- 
cgit v1.2.3