1 files changed, 248 insertions, 0 deletions
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