#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