commit e29fb98961064d27943027480672e903dcae1d5e
parent 2d70e4444719f01c9c8236dcf37b05e7f5a8f3f8
Author: Robert Russell <robertrussell.72001@gmail.com>
Date: Sun, 24 Sep 2023 13:09:31 -0700
Rewrite generic dynamic array data stucture
- Rename vector -> list (vectors are for math!).
- Change len and cap signature to match other methods.
- Rename ins and cat methods.
- Remove some bloat (e.g., null term and header type options, which were
originally added to support making an efficient string type, but now I
have an ad hoc Str type).
- Add bounds checks and the ability to disable them in debug builds or
enable them in release builds by redefining LIST_ASSERT.
- Change the generics implementation style from DECLARE and DEFINE macros
to include files, which is more ergonomic and flexible. Of course, I
will change the other generic data structures to this style, too.
Diffstat:
11 files changed, 214 insertions(+), 150 deletions(-)
diff --git a/inc/internal/util.h b/inc/internal/util.h
@@ -1,8 +1,13 @@
+#pragma once
+
+#include <stdbool.h>
+
+#include "../def.h"
+
/* If s1 < MUL_NO_OVERFLOW and s2 < MUL_NO_OVERFLOW, then s1*s2 <= USIZE_MAX
* (but not conversely). This lets us avoid division in overflow checks. */
#define MUL_NO_OVERFLOW ((usize) 1 << (sizeof(usize) * 4))
-/* This is exposed to user when included in vector.h, so try to hide it. */
static inline bool
r_mul_will_overflow_(usize a, usize b) {
return (a >= MUL_NO_OVERFLOW || b >= MUL_NO_OVERFLOW)
diff --git a/inc/list/declare.h b/inc/list/declare.h
@@ -0,0 +1,6 @@
+#include "../def.h"
+
+#include "impl/macro.h"
+#include "impl/common.h"
+#include "impl/declare.h"
+#include "impl/unmacro.h"
diff --git a/inc/list/define.h b/inc/list/define.h
@@ -0,0 +1,9 @@
+#include <errno.h>
+#include <string.h>
+
+#include "../def.h"
+#include "../internal/util.h"
+
+#include "impl/macro.h"
+#include "impl/define.h"
+#include "impl/unmacro.h"
diff --git a/inc/list/impl/common.h b/inc/list/impl/common.h
@@ -0,0 +1,9 @@
+#pragma once
+
+typedef struct r_list_hdr_ RListHdr_;
+
+struct r_list_hdr_ {
+ usize len;
+ usize cap;
+ maxalign arr[];
+};
diff --git a/inc/list/impl/declare.h b/inc/list/impl/declare.h
@@ -0,0 +1,72 @@
+#ifndef LIST_STATIC
+#define LIST_STATIC
+#endif
+
+LIST_STATIC UNUSED int LIST_METHOD(resize)(LIST_T **l, usize cap);
+LIST_STATIC UNUSED int LIST_METHOD(reserve)(LIST_T **l, usize n);
+LIST_STATIC UNUSED int LIST_METHOD(insarr)(LIST_T **dst, usize i, LIST_T *src, usize n);
+LIST_STATIC UNUSED LIST_T LIST_METHOD(del)(LIST_T **l, usize i);
+
+#undef LIST_STATIC
+
+static inline UNUSED void
+LIST_METHOD(free)(LIST_T **l) {
+ if (*l) LIST_FREE(LIST_HDR(*l));
+ *l = 0;
+}
+
+static inline UNUSED usize
+LIST_METHOD(len)(LIST_T **l) {
+ return *l ? LIST_HDR(*l)->len : 0;
+}
+
+static inline UNUSED usize
+LIST_METHOD(cap)(LIST_T **l) {
+ return *l ? LIST_HDR(*l)->cap : 0;
+}
+
+static inline UNUSED int
+LIST_METHOD(ins)(LIST_T **l, usize i, LIST_T e) {
+ return LIST_METHOD(insarr)(l, i, &e, 1);
+}
+
+static inline UNUSED int
+LIST_METHOD(inslst)(LIST_T **dst, usize i, LIST_T *src) {
+ return LIST_METHOD(insarr)(dst, i, src, LIST_METHOD(len)(&src));
+}
+
+static inline UNUSED int
+LIST_METHOD(catarr)(LIST_T **dst, LIST_T *src, usize n) {
+ return LIST_METHOD(insarr)(dst, LIST_METHOD(len)(dst), src, n);
+}
+
+static inline UNUSED int
+LIST_METHOD(catlst)(LIST_T **dst, LIST_T *src) {
+ return LIST_METHOD(catarr)(dst, src, LIST_METHOD(len)(&src));
+}
+
+static inline UNUSED int
+LIST_METHOD(push)(LIST_T **l, LIST_T e) {
+ return LIST_METHOD(catarr)(l, &e, 1);
+}
+
+static inline UNUSED LIST_T
+LIST_METHOD(pop)(LIST_T **l) {
+ LIST_ASSERT(LIST_METHOD(len)(l) > 0,
+ STRINGIFY(LIST_METHOD(pop))" called on empty list");
+ return LIST_METHOD(del)(l, LIST_HDR(*l)->len - 1);
+}
+
+static inline UNUSED LIST_T
+LIST_METHOD(peek)(LIST_T **l) {
+ LIST_ASSERT(LIST_METHOD(len)(l) > 0,
+ STRINGIFY(LIST_METHOD(peek))" called on empty list");
+ return (*l)[LIST_HDR(*l)->len - 1];
+}
+
+static inline UNUSED void
+LIST_METHOD(trunc)(LIST_T **l, usize n) {
+ LIST_ASSERT(n <= LIST_METHOD(len)(l),
+ STRINGIFY(LIST_METHOD(trunc))" called with n > len");
+ if (*l) LIST_HDR(*l)->len = n;
+}
diff --git a/inc/list/impl/define.h b/inc/list/impl/define.h
@@ -0,0 +1,65 @@
+int
+LIST_METHOD(resize)(LIST_T **l, usize cap) {
+ if (cap == 0) {
+ LIST_METHOD(free)(l);
+ return 0;
+ }
+
+ cap = MAX(cap, LIST_MIN_CAP);
+ RListHdr_ *h = *l ? LIST_HDR(*l) : 0;
+ usize len = h ? h->len : 0;
+ usize arrsize = cap * sizeof (*l)[0];
+ if (r_mul_will_overflow_(cap, sizeof (*l)[0])
+ || sizeof *h > USIZE_MAX - arrsize) {
+ errno = ENOMEM;
+ return -1;
+ }
+ if (LIST_REALLOC(&h, sizeof *h + arrsize) < 0) return -1;
+ h->len = MIN(len, cap);
+ h->cap = cap;
+ *l = (void *)(h + 1);
+ return 0;
+}
+
+int
+LIST_METHOD(reserve)(LIST_T **l, usize n) {
+ RListHdr_ *h = *l ? LIST_HDR(*l) : 0;
+ usize rem = h ? h->cap - h->len : 0;
+ if (n > rem) {
+ usize need = n - rem;
+ /* Set cap such that the list capacity at least doubles. */
+ usize cap = h ? h->cap + MAX(h->cap, need) : need;
+ /* Check for overflow. */
+ if (h && cap < h->cap) {
+ errno = ENOMEM;
+ return -1;
+ }
+ return LIST_METHOD(resize)(l, cap);
+ }
+ return 0;
+}
+
+int
+LIST_METHOD(insarr)(LIST_T **dst, usize i, LIST_T *src, usize n) {
+ LIST_ASSERT(i <= LIST_METHOD(len)(dst),
+ STRINGIFY(LIST_METHOD(insarr))" called with i > len");
+ /* Return early with n == 0, so that LIST_HDR use below is valid. */
+ if (n == 0) return 0;
+ if (LIST_METHOD(reserve)(dst, n) < 0) return -1;
+ usize m = LIST_HDR(*dst)->len - i;
+ memmove(&(*dst)[i+n], &(*dst)[i], m * sizeof (*dst)[0]);
+ memcpy(&(*dst)[i], src, n * sizeof (*dst)[0]);
+ LIST_HDR(*dst)->len += n;
+ return 0;
+}
+
+LIST_T
+LIST_METHOD(del)(LIST_T **l, usize i) {
+ LIST_ASSERT(i < LIST_METHOD(len)(l),
+ STRINGIFY(LIST_METHOD(del))" called with i >= len");
+ LIST_T e = (*l)[i];
+ usize m = LIST_HDR(*l)->len - i - 1;
+ memmove(&(*l)[i], &(*l)[i+1], m * sizeof (*l)[0]);
+ LIST_HDR(*l)->len -= 1;
+ return e;
+}
diff --git a/inc/list/impl/macro.h b/inc/list/impl/macro.h
@@ -0,0 +1,28 @@
+#ifndef LIST_T
+#error "rcx/list: LIST_T must be defined"
+#endif
+
+#ifndef LIST_METHOD
+#define LIST_METHOD(name) name
+#endif
+
+#ifndef LIST_MIN_CAP
+#define LIST_MIN_CAP 8
+#endif
+
+#if !defined(LIST_REALLOC) || !defined(LIST_FREE)
+#include "../../alloc.h"
+#endif
+#ifndef LIST_REALLOC
+#define LIST_REALLOC r_erealloc
+#endif
+#ifndef LIST_FREE
+#define LIST_FREE free
+#endif
+
+#ifndef LIST_ASSERT
+#include "../../debug.h"
+#define LIST_ASSERT ASSERT
+#endif
+
+#define LIST_HDR(l) ((RListHdr_ *)(l) - 1)
diff --git a/inc/list/impl/unmacro.h b/inc/list/impl/unmacro.h
@@ -0,0 +1,7 @@
+#undef LIST_HDR
+#undef LIST_ASSERT
+#undef LIST_FREE
+#undef LIST_REALLOC
+#undef LIST_MIN_CAP
+#undef LIST_METHOD
+#undef LIST_T
diff --git a/inc/list/static.h b/inc/list/static.h
@@ -0,0 +1,12 @@
+#include <errno.h>
+#include <string.h>
+
+#include "../def.h"
+#include "../internal/util.h"
+
+#include "impl/macro.h"
+#include "impl/common.h"
+#define LIST_STATIC static
+#include "impl/declare.h"
+#include "impl/define.h"
+#include "impl/unmacro.h"
diff --git a/inc/vector-defaults.h b/inc/vector-defaults.h
@@ -1,20 +0,0 @@
-#undef R_VECTOR_STATIC
-#define R_VECTOR_STATIC
-
-#undef R_VECTOR_METHOD
-#define R_VECTOR_METHOD(name, prefix) JOIN(JOIN(prefix,_),name)
-
-#undef R_VECTOR_NULL_TERM
-#define R_VECTOR_NULL_TERM false
-
-#undef R_VECTOR_MIN_CAP
-#define R_VECTOR_MIN_CAP 8
-
-#undef R_VECTOR_HDR_TYPE
-#define R_VECTOR_HDR_TYPE RVectorGenericHdr_
-
-#undef R_VECTOR_REALLOC
-#define R_VECTOR_REALLOC r_erealloc
-
-#undef R_VECTOR_FREE
-#define R_VECTOR_FREE free
diff --git a/inc/vector.h b/inc/vector.h
@@ -1,129 +0,0 @@
-#pragma once
-
-#include <errno.h>
-#include <stdbool.h>
-#include <string.h>
-
-#include "alloc.h"
-#include "def.h"
-#include "internal/util.h"
-
-typedef struct r_vector_generic_hdr_ RVectorGenericHdr_;
-
-struct r_vector_generic_hdr_ {
- usize len;
- usize cap;
- maxalign arr[];
-};
-
-#define R_VECTOR_HDR_(v) ((R_VECTOR_HDR_TYPE *)(v) - 1)
-
-#include "vector-defaults.h"
-
-#define R_VECTOR_DECLARE(T, ...)\
-static inline UNUSED usize R_VECTOR_METHOD(len,##__VA_ARGS__)(T *v) { return v ? R_VECTOR_HDR_(v)->len : 0; } \
-static inline UNUSED usize R_VECTOR_METHOD(cap,##__VA_ARGS__)(T *v) { return v ? R_VECTOR_HDR_(v)->cap : 0; } \
-R_VECTOR_STATIC UNUSED void R_VECTOR_METHOD(free,##__VA_ARGS__)(T **v); \
-R_VECTOR_STATIC UNUSED int R_VECTOR_METHOD(resize,##__VA_ARGS__)(T **v, usize cap); \
-R_VECTOR_STATIC UNUSED int R_VECTOR_METHOD(reserve,##__VA_ARGS__)(T **v, usize n); \
-R_VECTOR_STATIC UNUSED int R_VECTOR_METHOD(ins,##__VA_ARGS__)(T **v, usize i, T e); \
-R_VECTOR_STATIC UNUSED int R_VECTOR_METHOD(insv,##__VA_ARGS__)(T **dst, usize i, T *src); \
-R_VECTOR_STATIC UNUSED int R_VECTOR_METHOD(insn,##__VA_ARGS__)(T **dst, usize i, T *src, usize n); \
-R_VECTOR_STATIC UNUSED int R_VECTOR_METHOD(push,##__VA_ARGS__)(T **v, T e); \
-R_VECTOR_STATIC UNUSED int R_VECTOR_METHOD(cat,##__VA_ARGS__)(T **dst, T *src); \
-R_VECTOR_STATIC UNUSED int R_VECTOR_METHOD(catn,##__VA_ARGS__)(T **dst, T *src, usize n); \
-R_VECTOR_STATIC UNUSED T R_VECTOR_METHOD(del,##__VA_ARGS__)(T **v, usize i); \
-R_VECTOR_STATIC UNUSED T R_VECTOR_METHOD(pop,##__VA_ARGS__)(T **v); \
-static inline UNUSED T R_VECTOR_METHOD(peek,##__VA_ARGS__)(T **v) { return (*v)[R_VECTOR_HDR_(*v)->len - 1]; }
-
-#define R_VECTOR_DEFINE(T, ...)\
-void R_VECTOR_METHOD(free,##__VA_ARGS__)(T **v) { \
- if (*v) \
- R_VECTOR_FREE(R_VECTOR_HDR_(*v)); \
- *v = 0; \
-} \
-int R_VECTOR_METHOD(resize,##__VA_ARGS__)(T **v, usize cap) { \
- if (cap == 0) { \
- R_VECTOR_METHOD(free,##__VA_ARGS__)(v); \
- } else { \
- cap = MAX(cap, R_VECTOR_MIN_CAP); \
- R_VECTOR_HDR_TYPE *h = *v ? R_VECTOR_HDR_(*v) : 0; \
- usize len = h ? h->len : 0; \
- usize arrsize = cap * sizeof (*v)[0]; \
- if (r_mul_will_overflow_(cap, sizeof (*v)[0]) \
- || sizeof *h > USIZE_MAX - arrsize) { \
- errno = ENOMEM; \
- return -1; \
- } \
- if (R_VECTOR_REALLOC(&h, sizeof *h + arrsize) < 0) \
- return -1; \
- h->len = MIN(len, cap - !!R_VECTOR_NULL_TERM); \
- h->cap = cap; \
- *v = (void *)(h + 1); \
- if (R_VECTOR_NULL_TERM) \
- memset(&(*v)[h->len], 0, sizeof (*v)[0]); \
- } \
- return 0; \
-} \
-int R_VECTOR_METHOD(reserve,##__VA_ARGS__)(T **v, usize n) { \
- R_VECTOR_HDR_TYPE *h = *v ? R_VECTOR_HDR_(*v) : 0; \
- usize rem = h ? h->cap - h->len - !!R_VECTOR_NULL_TERM : 0; \
- if (n > rem) { \
- usize need = n - rem; \
- usize cap = h ? h->cap + MAX(h->cap, need) \
- : need + !!R_VECTOR_NULL_TERM; \
- if ((h && cap < h->cap) || (R_VECTOR_NULL_TERM && cap == 0)) { \
- errno = ENOMEM; \
- return -1; \
- } \
- return R_VECTOR_METHOD(resize,##__VA_ARGS__)(v, cap); \
- } else { \
- return 0; \
- } \
-} \
-int R_VECTOR_METHOD(ins,##__VA_ARGS__)(T **v, usize i, T e) { \
- return R_VECTOR_METHOD(insn,##__VA_ARGS__)(v, i, &e, 1); \
-} \
-int R_VECTOR_METHOD(insv,##__VA_ARGS__)(T **dst, usize i, T *src) { \
- return R_VECTOR_METHOD(insn,##__VA_ARGS__)(dst, i, src, \
- R_VECTOR_METHOD(len,##__VA_ARGS__)(src)); \
-} \
-int R_VECTOR_METHOD(insn,##__VA_ARGS__)(T **dst, usize i, T *src, usize n) { \
- if (R_VECTOR_METHOD(reserve,##__VA_ARGS__)(dst, n)) \
- return -1; \
- usize m = R_VECTOR_HDR_(*dst)->len - i + !!R_VECTOR_NULL_TERM; \
- memmove(&(*dst)[i+n], &(*dst)[i], m * sizeof (*dst)[0]); \
- memcpy(&(*dst)[i], src, n * sizeof (*dst)[0]); \
- R_VECTOR_HDR_(*dst)->len += n; \
- return 0; \
-} \
-int R_VECTOR_METHOD(push,##__VA_ARGS__)(T **v, T e) { \
- return R_VECTOR_METHOD(catn,##__VA_ARGS__)(v, &e, 1); \
-} \
-int R_VECTOR_METHOD(cat,##__VA_ARGS__)(T **dst, T *src) { \
- return R_VECTOR_METHOD(catn,##__VA_ARGS__)(dst, \
- src, R_VECTOR_METHOD(len,##__VA_ARGS__)(src)); \
-} \
-int R_VECTOR_METHOD(catn,##__VA_ARGS__)(T **dst, T *src, usize n) { \
- return R_VECTOR_METHOD(insn,##__VA_ARGS__)(dst, \
- R_VECTOR_METHOD(len,##__VA_ARGS__)(*dst), src, n); \
-} \
-T R_VECTOR_METHOD(del,##__VA_ARGS__)(T **v, usize i) { \
- T e = (*v)[i]; \
- usize m = R_VECTOR_HDR_(*v)->len - i - 1 + !!R_VECTOR_NULL_TERM; \
- memmove(&(*v)[i], &(*v)[i+1], m * sizeof (*v)[0]); \
- R_VECTOR_HDR_(*v)->len -= 1; \
- return e; \
-} \
-T R_VECTOR_METHOD(pop,##__VA_ARGS__)(T **v) { \
- return R_VECTOR_METHOD(del,##__VA_ARGS__)(v, R_VECTOR_HDR_(*v)->len - 1); \
-}
-
-/* TODO?
-deln
-clr => set length to 0 without resizing
-optionally take cmp function and define:
- sort => qsort wrapper
- bsearch => bsearch wrapper
- lsearch => linear search on unsorted array
-*/
