add vectors

3 files changed, 282 insertions, 10 deletions

diff --git a/stage3/def.h b/stage3/def.h
index 35321e0..3ad53eb 100644
--- a/stage3/def.h
+++ b/stage3/def.h
@@ -30,17 +30,41 @@ typedef u8 bool;
 
 #define BITCAST(expr, from, to) (((union { from f; to t; }) { .f = expr }).t)
 
-typedef struct {
-	usize len;
-	char *data;
-} str;
-
-#define S(x) ((str) { sizeof (x) - 1, (x) })
-#define NILS ((str) { 0, nil })
-
 #define BARRIER_VAR(var) asm volatile(""::"m"(var))
 #define BARRIER() asm volatile("":::"memory")
 
 #define LEN(x) (sizeof (x) / sizeof *(x))
 
+#define MKVEC(T) typedef struct { usize len; T *data; } slice_ ## T; typedef struct { usize cap; slice_ ## T slice; } vec_ ## T;
+#define NILS { .len = 0, .data = nil }
+#define NILVEC { .cap = 0, .slice = NILS }
+
+#define S(x) ((str) { sizeof (x) - 1, (x) })
+#define SL(T, ...) ((slice_ ## T) { .len = LEN((T[]) { __VA_ARGS__ }), .data = (T[]) { __VA_ARGS__ } })
+
+MKVEC(char)
+MKVEC(bool)
+
+MKVEC(u8) MKVEC(i8)
+MKVEC(u16) MKVEC(i16)
+MKVEC(u32) MKVEC(i32)
+MKVEC(u64) MKVEC(i64)
+MKVEC(usize) MKVEC(isize) MKVEC(ssize)
+MKVEC(f32) MKVEC(f64)
+
+typedef slice_char str;
+
+typedef enum {
+	ORD_LESS = -1,
+	ORD_EQ = 0,
+	ORD_GREATER = 1,
+} ord;
+
+#define ORD(a, b) ( \
+	(a) < (b) ? ORD_LESS : \
+	(a) > (b) ? ORD_GREATER : \
+	ORD_EQ)
+
+#define CHAIN_ORD(A, B) (((A) == ORD_EQ) ? (B) : (A))
+
 #endif
diff --git a/stage3/string.c b/stage3/string.c
index c97330a..f60b5e4 100644
--- a/stage3/string.c
+++ b/stage3/string.c
@@ -52,7 +52,7 @@ usize str_parse_num(str s, u8 base, u64 *x)
 		*x = (*x) * base + d;
 	}
 
-    return s.len;
+	return s.len;
 }
 
 usize str_parse_dbl(str s, double *x)
@@ -89,7 +89,7 @@ usize str_parse_dbl(str s, double *x)
 str str_walk(str *s, str sep)
 {
 	if (s->len == 0)
-		return NILS;
+		return (str) NILS;
 
 	usize x = str_find(*s, sep);
 	usize o = x + (x < s->len);
diff --git a/stage3/vec.h b/stage3/vec.h
new file mode 100644
index 0000000..6732b35
--- /dev/null
+++ b/stage3/vec.h
@@ -0,0 +1,248 @@
+#ifndef T
+#error "missing #define T"
+#endif
+
+#include "def.h"
+#include "heap.h"
+#include "memory.h"
+
+#ifndef VEC_UTIL
+#define VEC_UTIL
+
+#define VECFN __attribute__((unused))
+
+#define ITER_VAR(S, I) for (usize I = 0; I < S.len; I++)
+#define ITER(S) ITER_VAR(S, i)
+
+#define VEC_CAT(X, Y) X ## Y
+#define VEC_CAT2(X, Y) VEC_CAT(X, Y)
+
+static inline usize bit_ceil(usize n)
+{
+	return n <= 1 ? n : 1UL << (64 - __builtin_clzl(n-1));
+}
+
+#define VEC_LSEARCH(self, i, f, user_data, found, other) \
+	for (usize i = 0; i < (self)->len; i++) { \
+		if ((f)(&(self)->data[i], user_data)) { \
+			found \
+		} \
+	} \
+	other
+
+#define VEC_BSEARCH(self, low, high, idx, f, user_data, found, other) \
+	usize low, high, idx; \
+	low = 0; \
+	high = (self)->len; \
+	while (low < high) { \
+		idx = (low + high) / 2; \
+		switch ((f)(&(self)->data[i], user_data)) { \
+			case ORD_EQ: \
+				found \
+				break; \
+			case ORD_LESS: high = idx; break; \
+			case ORD_GREATER: low = idx + 1; break; \
+		} \
+	} \
+	idx = low; \
+	other
+
+#endif
+
+#define VEC VEC_CAT2(vec_, T)
+#define SLICE VEC_CAT2(slice_, T)
+#define FN(F) VEC_CAT2(VEC, _ ## F)
+
+#ifdef BUILTIN_CMP
+#define CMP(A, B) ORD(*(A), *(B))
+#endif
+
+#if defined(BUILTIN_EQ) || defined(BUILTIN_CMP)
+#define EQ(A, B) (*(A) == *(B))
+#endif
+
+#if defined(CMP) && !defined(EQ)
+#define EQ(A, B) (CMP(A, B) == ORD_EQ)
+#endif
+
+#undef BUILTIN_CMP
+#undef BUILTIN_EQ
+
+VECFN void FN(grow)(VEC *self, usize cap)
+{
+	if (self->cap < cap)
+		self->cap = cap;
+	else if (self->slice.data != nil)
+		return;
+
+	self->slice.data = krealloc(self->slice.data, sizeof(T) * self->cap);
+}
+
+VECFN void FN(insert)(VEC *self, usize pos, T data)
+{
+	heap_check();
+	FN(grow)(self, bit_ceil(++self->slice.len));
+	heap_check();
+	rmemcpy(&self->slice.data[pos+1], &self->slice.data[pos], sizeof(T) * (self->slice.len-pos-1));
+	heap_check();
+	self->slice.data[pos] = data;
+	heap_check();
+}
+
+VECFN T FN(remove)(SLICE *self, usize pos)
+{
+	heap_check();
+
+	T x = self->data[pos];
+	lmemcpy(&self->data[pos], &self->data[pos+1], sizeof(T) * (--self->len - pos));
+
+	heap_check();
+	return x;
+}
+
+VECFN void FN(append)(VEC *self, T data)
+{
+	FN(insert)(self, self->slice.len, data);
+}
+
+VECFN SLICE FN(clone_slice)(SLICE *self)
+{
+	SLICE other = NILS;
+	other.data = kmalloc(sizeof(T) * (other.len = self->len));
+	lmemcpy(other.data, self->data, sizeof(T) * self->len);
+	return other;
+}
+
+VECFN VEC FN(clone)(VEC *self)
+{
+	return (VEC) {
+		.slice = FN(clone_slice)(&self->slice),
+		.cap = self->slice.len,
+	};
+}
+
+VECFN bool FN(eqf)(SLICE *a, SLICE *b, bool f(T *a, T *b))
+{
+	if (a->len != b->len)
+		return false;
+
+	for (usize i = 0; i < a->len; i++) {
+		if (!f(&a->data[i], &b->data[i]))
+			return false;
+	}
+
+	return true;
+}
+
+VECFN ord FN(cmpf)(SLICE *a, SLICE *b, ord f(T *a, T *b))
+{
+	for (usize i = 0; i < a->len; i++) {
+		if (i >= b->len)
+			return ORD_GREATER;
+
+		ord o = f(&a->data[i], &b->data[i]);
+		if (o != ORD_EQ)
+			return o;
+	}
+
+	return ORD_EQ;
+}
+
+VECFN bool FN(lsearchf)(SLICE *self, usize *pos, bool f(T *x, void *user_data), void *user_data)
+{
+	VEC_LSEARCH(self, i, f, user_data, *pos = i; return true;, return false;)
+}
+
+VECFN void FN(lset_addf)(VEC *self, bool f(T *a, T *b), T x)
+{
+	VEC_LSEARCH(&self->slice, i, f, &x,,FN(append)(self, x);)
+}
+
+VECFN void FN(lset_removef)(SLICE *self, bool f(T *a, T *b), T *x)
+{
+	VEC_LSEARCH(self, i, f, x, FN(remove)(self, i);,)
+}
+
+VECFN bool FN(bsearchf)(SLICE *self, usize *pos, ord f(T *x, void *user_data), void *user_data)
+{
+	VEC_BSEARCH(self, low, high, i, f, user_data, *pos = i; return true;, *pos = i; return false;)
+}
+
+VECFN void FN(bset_addf)(VEC *self, ord f(T *a, T *b), T x)
+{
+	VEC_BSEARCH(&self->slice, low, high, i, f, &x, return;, FN(insert)(self, i, x);)
+}
+
+VECFN void FN(bset_removef)(SLICE *self, ord f(T *a, T *b), T *x)
+{
+	VEC_BSEARCH(self, low, high, i, f, x, FN(remove)(self, i); return;,)
+}
+
+#ifdef EQ
+
+VECFN bool FN(_eq_scalar)(T *a, T *b)
+{
+	return EQ(a, b);
+}
+
+VECFN bool FN(_eq_scalar_void)(T *a, void *b)
+{
+	return EQ(a, (T *) b);
+}
+
+VECFN bool FN(eq)(SLICE *a, SLICE *b)
+{
+	return FN(eqf)(a, b, FN(_eq_scalar));
+}
+
+VECFN bool FN(lsearch)(SLICE *self, usize *pos, T *x)
+{
+	return FN(lsearchf)(self, pos, FN(_eq_scalar_void), x);
+}
+
+VECFN void FN(lset_add)(VEC *self, T x)
+{
+	return FN(lset_addf)(self, FN(_eq_scalar), x);
+}
+
+VECFN void FN(lset_remove)(SLICE *self, T *x)
+{
+	return FN(lset_removef)(self, FN(_eq_scalar), x);
+}
+
+#endif
+
+#ifdef CMP
+
+VECFN ord FN(_cmp_scalar)(T *a, T *b)
+{
+	return CMP(a, b);
+}
+
+VECFN ord FN(_cmp_scalar_void)(T *a, void *b)
+{
+	return CMP(a, (T *) b);
+}
+
+VECFN ord FN(cmp)(SLICE *a, SLICE *b)
+{
+	return FN(cmpf)(a, b, FN(_cmp_scalar));
+}
+
+VECFN bool FN(bsearch)(SLICE *self, usize *pos, T *x)
+{
+	return FN(bsearchf)(self, pos, FN(_cmp_scalar_void), x);
+}
+
+VECFN FN(binsert)(VEC *self, T x)
+{
+	FN(lsearch)(&self->slice)
+}
+
+#endif
+
+#undef T
+#undef VEC
+#undef FN
+#undef CMP
+#undef EQ