Introduce RingBuffer

diff --git a/CMakeLists.txt b/CMakeLists.txt
index 23e623e45922095de400dfd251ff40efec0804b6..2c702734189446c3169ad0e3a2717f95917f8d70 100644 (file)
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -160,6 +160,8 @@ add_executable(nothing
   src/dynarray.c
   src/system/file.h
   src/system/file.c
+  src/ring_buffer.h
+  src/ring_buffer.c
 )
 target_link_libraries(nothing ${SDL2_LIBRARIES})
 

diff --git a/nothing.c b/nothing.c
index ba503438a35e219ff976c0f7c86a638fd992bb31..0c0a9482bc4147c48b2690d8fb296b234c675131 100644 (file)
--- a/nothing.c
+++ b/nothing.c
@@ -50,3 +50,4 @@
 #include "src/system/str.c"
 #include "src/dynarray.c"
 #include "src/system/file.c"
+#include "src/ring_buffer.c"

diff --git a/src/ring_buffer.c b/src/ring_buffer.c
new file mode 100644 (file)
index 0000000..905d177
--- /dev/null
+++ b/src/ring_buffer.c
@@ -0,0 +1,50 @@
+#include "ring_buffer.h"
+#include "system/stacktrace.h"
+
+void ring_buffer_push(RingBuffer *buffer,
+                      void *element)
+{
+    trace_assert(buffer);
+    trace_assert(element);
+
+    size_t i = (buffer->begin + buffer->count) % buffer->capacity;
+
+    if (buffer->count < buffer->capacity) {
+        memcpy(
+            buffer->data + i * buffer->element_size,
+            element,
+            buffer->element_size);
+        buffer->count += 1;
+    } else {
+        if (buffer->dtor) buffer->dtor(buffer->data + i * buffer->element_size);
+        memcpy(
+            buffer->data + i * buffer->element_size,
+            element,
+            buffer->element_size);
+        buffer->begin = (buffer->begin + 1) % buffer->capacity;
+    }
+}
+
+int ring_buffer_pop(RingBuffer *buffer)
+{
+    trace_assert(buffer);
+
+    if (buffer->count == 0) return 0;
+
+    if (buffer->dtor) {
+        size_t i = (buffer->begin + buffer->count - 1) % buffer->capacity;
+        buffer->dtor(buffer->data + i * buffer->element_size);
+    }
+
+    buffer->count--;
+
+    return 1;
+}
+
+void *ring_buffer_top(RingBuffer *buffer)
+{
+    trace_assert(buffer);
+    if (buffer->count == 0) return NULL;
+    size_t i = (buffer->begin + buffer->count - 1) % buffer->capacity;
+    return buffer->data + i * buffer->element_size;
+}

diff --git a/src/ring_buffer.h b/src/ring_buffer.h
new file mode 100644 (file)
index 0000000..acb86e2
--- /dev/null
+++ b/src/ring_buffer.h
@@ -0,0 +1,44 @@
+#ifndef RING_BUFFER_H_
+#define RING_BUFFER_H_
+
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <string.h>
+
+typedef void (*RingBufferDtor)(void *element);
+
+typedef struct {
+    size_t element_size;
+    size_t capacity;
+    size_t count;
+    size_t begin;
+    uint8_t *data;
+    RingBufferDtor dtor;
+} RingBuffer;
+
+static inline
+RingBuffer create_ring_buffer(size_t element_size,
+                              size_t capacity,
+                              RingBufferDtor dtor)
+{
+    RingBuffer result = {0};
+    result.element_size = element_size;
+    result.capacity = capacity;
+    result.dtor = dtor;
+    result.data = malloc(result.element_size * result.capacity);
+    return result;
+}
+
+static inline
+void destroy_ring_buffer(RingBuffer buffer)
+{
+    free(buffer.data);
+}
+
+void ring_buffer_push(RingBuffer *buffer, void *element);
+int ring_buffer_pop(RingBuffer *buffer);
+void *ring_buffer_top(RingBuffer *buffer);
+
+#endif  // RING_BUFFER_H_