Deque with thread safe manager (untested)

5 files changed, 121 insertions, 2 deletions

diff --git a/Justfile b/Justfile
index 9ce70a1..3d1d661 100644
--- a/Justfile
+++ b/Justfile
@@ -4,7 +4,7 @@ test_dir := "tests"
 build_dir := "build"
 cc := "cc"
 cflags := "-Wall -Wextra -Wpedantic -Werror -std=c23 -fPIC"
-lflags := "-lm"
+lflags := "-lm -lpthread"
 prefix := "/usr/local"
 extra_cflags := ""
 
diff --git a/src/deque.c b/src/deque.c
new file mode 100644
index 0000000..35f1907
--- /dev/null
+++ b/src/deque.c
@@ -0,0 +1,75 @@
+#include "deque.h"
+#include "smrt_arena.h"
+
+#include <bits/pthreadtypes.h>
+#include <pthread.h>
+#include <semaphore.h>
+#include <stdlib.h>
+#include <string.h>
+
+ez_deque_t *ez_deque_create(smrt_arena_t *arena, u64 elem_size, u64 size) {
+    u64 total_size = EZ_DEQUE_BASE_POS + (elem_size * size);
+
+    ez_deque_t *q = smrt_arena_push(arena, total_size, true);
+    q->size = size;
+    q->element_size_bytes = elem_size;
+
+    return q;
+}
+
+// Returns false if queue can't hold elem.
+b32 ez_deque_enqueue(ez_deque_t *q, void *elem) {
+    if (q->occupied < q->size) {
+        u64 insert_pos = EZ_DEQUE_BASE_POS + (q->back * q->element_size_bytes);
+        memcpy((u8*)q+insert_pos, elem, q->element_size_bytes);
+        q->back = (q->back + 1) % q->size;
+        q->occupied++;
+        return true;
+    }
+    return false;
+}
+
+void *ez_deque_pop(ez_deque_t *q) {
+    if (q->occupied == 0) return NULL;
+    u64 pop_pos = EZ_DEQUE_BASE_POS + (q->front * q->element_size_bytes);
+    q->front = (q->front + 1) % q->size;
+    q->occupied--;
+    return (u8*)q + pop_pos;
+}
+
+ts_deque_t ts_deque_create(ez_deque_t *q) {
+    pthread_mutex_t *m = malloc(sizeof(pthread_mutex_t));
+    *m = (pthread_mutex_t)PTHREAD_MUTEX_INITIALIZER;
+
+    sem_t *s = malloc(sizeof(sem_t));
+    sem_init(s, 0, 0);
+
+    return (ts_deque_t){
+        .queue = q,
+        .write_lock = m,
+        .count_sem = s,
+    };
+}
+
+void ts_deque_destroy(ts_deque_t tsq) {
+    sem_destroy(tsq.count_sem);
+    free(tsq.count_sem);
+    pthread_mutex_destroy(tsq.write_lock);
+    free(tsq.write_lock);
+}
+
+b32 ts_deque_enqueue(ts_deque_t tsq, void *elem) {
+    pthread_mutex_lock(tsq.write_lock);
+    b32 result = ez_deque_enqueue(tsq.queue, elem);
+    pthread_mutex_unlock(tsq.write_lock);
+    if (result) sem_post(tsq.count_sem);
+    return result;
+}
+
+void *ts_deque_pop(ts_deque_t tsq) {
+    sem_wait(tsq.count_sem);
+    pthread_mutex_lock(tsq.write_lock);
+    void *result = ez_deque_pop(tsq.queue);
+    pthread_mutex_unlock(tsq.write_lock);
+    return result;
+}
diff --git a/src/deque.h b/src/deque.h
new file mode 100644
index 0000000..26b686e
--- /dev/null
+++ b/src/deque.h
@@ -0,0 +1,43 @@
+#pragma once
+
+#include "common.h"
+#include "smrt_arena.h"
+
+#include <bits/pthreadtypes.h>
+#include <pthread.h>
+#include <semaphore.h>
+
+#define EZ_DEQUE_BASE_POS (sizeof(ez_deque_t))
+
+typedef struct {
+     u64               size;
+     u64           occupied;
+     u64              front;
+     u64               back;
+     u64 element_size_bytes;
+} ez_deque_t;
+
+#define SMRTA_ALLOC_EZDEQUE(arena, T, n) (ez_deque_t*)ez_deq_create((arena), sizeof(T), (n))
+
+ez_deque_t *ez_deque_create(smrt_arena_t *arena, u64 elem_size, u64 size);
+
+// Returns false if queue can't hold elem.
+       b32 ez_deque_enqueue(ez_deque_t *q, void *elem);
+// Returns deque backed memory. Copy if needed.
+      void *   ez_deque_pop(ez_deque_t *q);
+
+// Thread-safe deque (SPMC)
+// Does not own queue
+typedef struct {
+     ez_deque_t *     queue;
+pthread_mutex_t *write_lock;
+          sem_t * count_sem;
+} ts_deque_t;
+
+ts_deque_t   ts_deque_create(ez_deque_t * q);
+      void  ts_deque_destroy(ts_deque_t tsq);
+
+// Deal with re-enqueueing yourself
+       b32  ts_deque_enqueue(ts_deque_t tsq ,
+                                 void *elem);
+      void *    ts_deque_pop(ts_deque_t tsq);
diff --git a/src/slidingwindow.h b/src/slidingwindow.h
index 3cfe821..17de775 100644
--- a/src/slidingwindow.h
+++ b/src/slidingwindow.h
@@ -12,7 +12,7 @@ typedef struct {
      u64 element_size_bytes;
 } sliding_window_array_t;
 
-#define SMRTA_ALLOC_SLIDINGWINDOW(arena, T, n) (sliding_window_array_t*)sw_create(arena, sizeof(T), (n))
+#define SMRTA_ALLOC_SLIDINGWINDOW(arena, T, n) (sliding_window_array_t*)sw_create((arena), sizeof(T), (n))
 #define SLIDINGWINDOW_GET(w, T) ((T*)((u8*)(w) + SLIDING_WINDOW_BASE_POS) + (w)->start_idx)
 
 sliding_window_array_t *sw_create(smrt_arena_t *arena, u64 elem_size, u64 size);
diff --git a/src/unity.c b/src/unity.c
index 61d5b02..a1273be 100644
--- a/src/unity.c
+++ b/src/unity.c
@@ -20,6 +20,7 @@
 #include "vec2.c"
 #include "slidingwindow.c"
 #include "vec2sw.c"
+#include "deque.c"
 
 // DSP/Audio
 #include "wav.c"