1 files changed, 82 insertions, 0 deletions
diff --git a/xar.h b/xar.h
new file mode 100644
index 0000000..e448889
--- /dev/null
+++ b/xar.h
@@ -0,0 +1,82 @@
+#ifndef XAR_H
+#define XAR_H
+
+/* inspired by andrew reece's "exponential array" */
+/* see https://danielchasehooper.com/posts/segment_array/ */
+
+#include <stdbit.h>
+#include "arena.h"
+
+#define XAR_INIT_SZ 8
+#define XAR_MAX_DOUBLE 26
+
+typedef struct {
+	int n, chunks;
+	void *chunk[XAR_MAX_DOUBLE];
+} XarHdr;
+
+#define XAR(T) struct { int n, chunks; T *chunk[XAR_MAX_DOUBLE]; }
+#define XAR_GET_T(xar, T, idx) (T*)(xar_get((XarHdr*)(xar), idx, sizeof(T)))
+#define XAR_PUT_T(xar, T, idx, a) (T*)(xar_put((XarHdr*)(xar), idx, sizeof(T), a))
+#define XAR_GET(xar, idx) XAR_GET_T(xar, typeof(**(xar)->chunk), idx)
+#define XAR_PUT(xar, idx, a) XAR_PUT_T(xar, typeof(**(xar)->chunk), idx, a)
+#define XAR_PUSH(xar, v, a) (*XAR_PUT(xar, (xar)->n++, a) = (v))
+#define XAR_PUSH_T(xar, T, v, a) (*XAR_PUT_T(xar, T, (xar)->n++, a) = (v))
+#define XAR_CHUNK(idx) (unsigned)(31 - stdc_leading_zeros(((unsigned)(idx) / XAR_INIT_SZ) + 1))
+#define XAR_CHUNK_SZ(chnk) (XAR_INIT_SZ << (chnk))
+#define XAR_SLOT(chnk, idx) ((idx) - (XAR_CHUNK_SZ(chnk) - XAR_CHUNK_SZ(0)))
+
+static inline void *xar_get(XarHdr *xar, uint32_t idx, size_t elsz) {
+	uint32_t chnk = XAR_CHUNK(idx);
+	uint32_t slot = XAR_SLOT(chnk, idx);
+	return (char*)xar->chunk[chnk] + (slot * elsz);
+}
+
+static inline void *xar_put(XarHdr *xar, uint32_t idx, size_t elsz, Arena *a) {
+	uint32_t chnk = XAR_CHUNK(idx);
+	uint32_t slot = XAR_SLOT(chnk, idx);
+	while (xar->chunks <= chnk) {
+		xar->chunk[xar->chunks] = arena_alloc(a, elsz * XAR_CHUNK_SZ(xar->chunks), elsz);
+		xar->chunks++;
+	}
+	return (char*)xar->chunk[chnk] + (slot * elsz);
+}
+
+#define XAR_FOR_IDX_PTR_T(x, T, i, v, ...)\
+	do {\
+		int i = 0;\
+		for (int xar_for_chnk = 0; xar_for_chnk < (x)->chunks; xar_for_chnk++) {\
+			T *v = (x)->chunk[xar_for_chnk];\
+			T *xar_for_chnk_end = v + (xar_for_chnk == (x)->chunks - 1\
+				? XAR_SLOT(xar_for_chnk, (x)->n)\
+				: XAR_CHUNK_SZ(xar_for_chnk));\
+			while (v != xar_for_chnk_end) {\
+				__VA_ARGS__;\
+				v++;\
+				i++;\
+			}\
+		}\
+	} while(0)
+
+#define XAR_FOR_IDX_VAL_T(x, T, i, v, ...)\
+	XAR_FOR_IDX_PTR_T(x, T, i, xar_for_chnk_##v##_ptr, {\
+		T v = *xar_for_chnk_##v##_ptr;\
+		__VA_ARGS__;\
+	})
+
+#define XAR_FOR_PTR_T(x, T, v, ...)\
+	XAR_FOR_IDX_PTR_T(x, T, _xar_foreach_i, v, __VA_ARGS__)
+
+#define XAR_FOR_VAL_T(x, T, v, ...)\
+	XAR_FOR_IDX_VAL_T(x, T, _xar_foreach_i, v, __VA_ARGS__)
+
+#define XAR_FOR_IDX_PTR(xar, i, v, ...)\
+	XAR_FOR_IDX_PTR_T(xar, typeof(**(xar)->chunk), i, v, __VA_ARGS__)
+
+#define XAR_FOR_IDX_VAL(xar, i, v, ...)\
+	XAR_FOR_IDX_VAL_T(xar, typeof(**(xar)->chunk), i, v, __VA_ARGS__)
+
+#define XAR_FOR_VAL(xar, v, ...)\
+	XAR_FOR_VAL_T(xar, typeof(**(xar)->chunk), v, __VA_ARGS__)
+
+#endif