rcx

commit 853a532d3addbf69971fe39916f4999ebbc9fa54
parent 94123210c18a67caa77489bcb62b1b5cffb18e0a
Author: robert <robertrussell.72001@gmail.com>
Date:   Mon, 18 Jul 2022 17:15:03 -0700

Add generic ring buffer/queue data structure

Diffstat:
A
inc/cext/ring.h
 | 
95
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
inc/cext/vector.h
 | 
1
+

2 files changed, 96 insertions(+), 0 deletions(-)
diff --git a/inc/cext/ring.h b/inc/cext/ring.h
@@ -0,0 +1,95 @@
+#pragma once
+
+#include <string.h>
+
+#include "cext/alloc.h"
+#include "cext/def.h"
+
+/* Defaults */
+#define RING_STATIC
+#define METHOD(name, prefix) JOIN(JOIN(prefix,_),name)
+#define RING_MIN_BITS 3 /* 1<<3 = 8 elements */
+#define RING_ALLOC ereallocn
+#define RING_FREE free
+
+/* Invariants: 
+ * Empty iff r == cap && w == 0
+ * Full iff r == w */
+
+#define RING_DECLARE(R, T, ...)\
+typedef struct R { \
+	T *arr; \
+	usize cap; /* Always a power of 2 for fast mod */ \
+	usize r, w; \
+} R; \
+RING_STATIC void METHOD(free,##__VA_ARGS__)(R *r); \
+RING_STATIC usize METHOD(len,##__VA_ARGS__)(R *r); \
+RING_STATIC usize METHOD(cap,##__VA_ARGS__)(R *r); \
+RING_STATIC int METHOD(reserve,##__VA_ARGS__)(R *r, usize n); \
+RING_STATIC int METHOD(enq,##__VA_ARGS__)(R *r, T e); \
+RING_STATIC T METHOD(deq,##__VA_ARGS__)(R *r); \
+RING_STATIC T *METHOD(idx,##__VA_ARGS__)(R *r, usize i);
+
+#define RING_DEFINE(R, T, ...)\
+void METHOD(free,##__VA_ARGS__)(R *r) { \
+	RING_FREE(r->arr); \
+	*r = (R){0}; \
+} \
+usize METHOD(len,##__VA_ARGS__)(R *r) { \
+	return r->r == r->w ? r->cap : (r->w - r->r) & (r->cap - 1); \
+} \
+usize METHOD(cap,##__VA_ARGS__)(R *r) { \
+	return r->cap; \
+} \
+int METHOD(reserve,##__VA_ARGS__)(R *r, usize n) { \
+	usize rem = r->cap - METHOD(len,##__VA_ARGS__)(r); \
+	if (n <= rem) \
+		return 0; \
+	usize need = n - rem; \
+	usize ncap = MAX(r->cap, 1<<RING_MIN_BITS); \
+	while (need > ncap - r->cap) { \
+		ncap <<= 1; \
+		if (ncap == 0) \
+			return -1; /* Overflow */ \
+	} \
+	T *narr = RING_ALLOC(r->arr, ncap, sizeof *narr); \
+	if (!narr) \
+		return -1; \
+	if (r->r == r->cap) { \
+		r->r = ncap; /* Maintain invariant for empty rings */ \
+	} else if (r->w <= r->r) { \
+		/* Move as little as possible */ \
+		if (r->w <= r->cap - r->r) { \
+			memcpy(&narr[r->cap], &narr[0], r->w * sizeof *narr); \
+			r->w += r->cap; \
+		} else { \
+			usize m = r->cap - r->r; \
+			memcpy(&narr[ncap-m], &narr[r->r], m * sizeof *narr); \
+			r->r = ncap - m; \
+		} \
+	} \
+	r->arr = narr; \
+	r->cap = ncap; \
+	return 0; \
+} \
+int METHOD(enq,##__VA_ARGS__)(R *r, T e) { \
+	if (METHOD(reserve,##__VA_ARGS__)(r, 1) < 0) \
+		return -1; \
+	r->arr[r->w] = e; \
+	r->w = (r->w + 1) & (r->cap - 1); \
+	if (r->r == r->cap) \
+		r->r = 0; \
+	return 0; \
+} \
+T METHOD(deq,##__VA_ARGS__)(R *r) { \
+	T e = r->arr[r->r]; \
+	r->r = (r->r + 1) & (r->cap - 1); \
+	if (r->r == r->w) { \
+		r->r = r->cap; \
+		r->w = 0; \
+	} \
+	return e; \
+} \
+T *METHOD(idx,##__VA_ARGS__)(R *r, usize i) { \
+	return &r->arr[(r->r + i) & (r->cap - 1)]; \
+}
diff --git a/inc/cext/vector.h b/inc/cext/vector.h
@@ -63,6 +63,7 @@ int METHOD(reserve,##__VA_ARGS__)(T **v, usize n) { \
 	usize rem = h ? h->cap - h->len : 0; \
 	if (n > rem) { \
 		usize need = n - rem; \
+		/* TODO: overflow check */ \
 		usize cap = h ? h->cap + MAX(h->cap, need) : need; \
 		return METHOD(resize,##__VA_ARGS__)(v, cap); \
 	} else { \