commit 47310052d443ce4ea458ae114a302b56e2efc604
parent cde87b8d22ef2a7804b8496e9a31b7099a6e3b6d
Author: robert <robertrussell.72001@gmail.com>
Date: Tue, 19 Jul 2022 11:17:52 -0700
Generalize rings to deques
Diffstat:
3 files changed, 125 insertions(+), 97 deletions(-)
diff --git a/inc/cext/all.h b/inc/cext/all.h
@@ -1,5 +1,6 @@
#include "cext/alloc.h"
#include "cext/cext.h"
+#include "cext/deque.h"
#include "cext/log.h"
#include "cext/opt.h"
#include "cext/utf8.h"
diff --git a/inc/cext/deque.h b/inc/cext/deque.h
@@ -0,0 +1,124 @@
+#pragma once
+
+#include <string.h>
+
+#include "cext/alloc.h"
+#include "cext/def.h"
+
+/* Defaults */
+#define DEQUE_STATIC
+#define METHOD(name, prefix) JOIN(JOIN(prefix,_),name)
+#define DEQUE_MIN_BITS 3 /* 1<<3 = 8 elements */
+#define DEQUE_ALLOC ereallocn
+#define DEQUE_FREE free
+
+#define DEQUE_TYPEDEF(D, T)\
+typedef struct D { \
+ T *arr; \
+ usize cap; /* Always a power of 2 for fast mod */ \
+ usize l; /* Left end of active region */ \
+ usize r; /* 1 past right end of active region */ \
+} D;
+
+/* Invariants:
+ * Empty iff l == cap && r == 0
+ * Full iff l == r */
+
+#define DEQUE_DECLARE(D, T, ...)\
+DEQUE_STATIC void METHOD(free,##__VA_ARGS__)(D *d); \
+DEQUE_STATIC usize METHOD(len,##__VA_ARGS__)(D *d); \
+DEQUE_STATIC usize METHOD(cap,##__VA_ARGS__)(D *d); \
+DEQUE_STATIC int METHOD(reserve,##__VA_ARGS__)(D *d, usize n); \
+DEQUE_STATIC int METHOD(pushl,##__VA_ARGS__)(D *d, T e); \
+DEQUE_STATIC int METHOD(pushr,##__VA_ARGS__)(D *d, T e); \
+DEQUE_STATIC T METHOD(popl,##__VA_ARGS__)(D *d); \
+DEQUE_STATIC T METHOD(popr,##__VA_ARGS__)(D *d); \
+DEQUE_STATIC T METHOD(peekl,##__VA_ARGS__)(D *d); \
+DEQUE_STATIC T METHOD(peekr,##__VA_ARGS__)(D *d); \
+DEQUE_STATIC T *METHOD(idx,##__VA_ARGS__)(D *d, usize i);
+
+#define DEQUE_DEFINE(D, T, ...)\
+void METHOD(free,##__VA_ARGS__)(D *d) { \
+ DEQUE_FREE(d->arr); \
+ *d = (D){0}; \
+} \
+usize METHOD(len,##__VA_ARGS__)(D *d) { \
+ return d->l == d->r ? d->cap : (d->r - d->l) & (d->cap - 1); \
+} \
+usize METHOD(cap,##__VA_ARGS__)(D *d) { \
+ return d->cap; \
+} \
+int METHOD(reserve,##__VA_ARGS__)(D *d, usize n) { \
+ usize rem = d->cap - METHOD(len,##__VA_ARGS__)(d); \
+ if (n <= rem) \
+ return 0; \
+ usize need = n - rem; \
+ usize ncap = MAX(d->cap, 1<<DEQUE_MIN_BITS); \
+ while (need > ncap - d->cap) { \
+ ncap <<= 1; \
+ if (ncap == 0) \
+ return -1; /* Overflow */ \
+ } \
+ T *narr = DEQUE_ALLOC(d->arr, ncap, sizeof *narr); \
+ if (!narr) \
+ return -1; \
+ if (d->l == d->cap) { \
+ d->l = ncap; /* Maintain invariant for empty deques */ \
+ } else if (d->r <= d->l) { \
+ /* Move as little as possible */ \
+ if (d->r <= d->cap - d->l) { \
+ memcpy(&narr[d->cap], &narr[0], d->r * sizeof *narr); \
+ d->r += d->cap; \
+ } else { \
+ usize m = d->cap - d->l; \
+ memcpy(&narr[ncap-m], &narr[d->l], m * sizeof *narr); \
+ d->l = ncap - m; \
+ } \
+ } \
+ d->arr = narr; \
+ d->cap = ncap; \
+ return 0; \
+} \
+int METHOD(pushl,##__VA_ARGS__)(D *d, T e) { \
+ if (METHOD(reserve,##__VA_ARGS__)(d, 1) < 0) \
+ return -1; \
+ d->l = (d->l - 1) & (d->cap - 1); \
+ d->arr[d->l] = e; \
+ return 0; \
+} \
+int METHOD(pushr,##__VA_ARGS__)(D *d, T e) { \
+ if (METHOD(reserve,##__VA_ARGS__)(d, 1) < 0) \
+ return -1; \
+ d->arr[d->r] = e; \
+ d->r = (d->r + 1) & (d->cap - 1); \
+ if (d->l == d->cap) \
+ d->l = 0; \
+ return 0; \
+} \
+T METHOD(popl,##__VA_ARGS__)(D *d) { \
+ T e = d->arr[d->l]; \
+ d->l = (d->l + 1) & (d->cap - 1); \
+ if (d->l == d->r) { \
+ d->l = d->cap; \
+ d->r = 0; \
+ } \
+ return e; \
+} \
+T METHOD(popr,##__VA_ARGS__)(D *d) { \
+ d->r = (d->r - 1) & (d->cap - 1); \
+ T e = d->arr[d->r]; \
+ if (d->l == d->r) { \
+ d->l = d->cap; \
+ d->r = 0; \
+ } \
+ return e; \
+} \
+T METHOD(peekl,##__VA_ARGS__)(D *d) { \
+ return d->arr[d->l]; \
+} \
+T METHOD(peekr,##__VA_ARGS__)(D *d) { \
+ return d->arr[(d->r - 1) & (d->cap - 1)]; \
+} \
+T *METHOD(idx,##__VA_ARGS__)(D *d, usize i) { \
+ return &d->arr[(d->l + i) & (d->cap - 1)]; \
+}
diff --git a/inc/cext/ring.h b/inc/cext/ring.h
@@ -1,97 +0,0 @@
-#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_TYPEDEF(R, T)\
-typedef struct R { \
- T *arr; \
- usize cap; /* Always a power of 2 for fast mod */ \
- usize r, w; \
-} R;
-
-#define RING_DECLARE(R, T, ...)\
-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)]; \
-}
