#ifndef ARENA_H
#define ARENA_H

#include <stdint.h>
#include <stddef.h>
#include <string.h>

typedef struct ArenaPg {
	struct ArenaPg *prev, *next;
	char *beg, *end;
	char data[];
} ArenaPg;

typedef struct {
	ArenaPg *pg;
	char *beg;
} ArenaMark;

typedef struct {
	ArenaPg *cur, *tail;
} Arena;

#define new(a, t)\
	(t*)arena_zeroed(arena_alloc(a, sizeof(t), _Alignof(t)), sizeof(t))

#define new_arr(a, t, n)\
	arena_alloc(a, sizeof(t) * n, _Alignof(t))

#define resize(a, p, old, new)\
	arena_realloc(a, p, (old) * sizeof(*(p)), (new) * sizeof(*(p)),\
			_Alignof(__typeof__(*(p))))

void arena_free(Arena *a);

void arena_save(Arena *a, ArenaMark *m);
void arena_load(Arena *a, ArenaMark *m);

void arena_reset(Arena *a);
void arena_reserve(Arena *a, ptrdiff_t n);

void *arena_alloc(Arena *a, ptrdiff_t n, ptrdiff_t align);
void *arena_realloc(Arena *a, void *ptr, ptrdiff_t old, ptrdiff_t new, ptrdiff_t align);
void *arena_zeroed(void *p, size_t n);

#define ARENA_BACKEND_MALLOC 0
#define ARENA_BACKEND_MMAP 1

#ifndef ARENA_BACKEND
#if defined(__linux__)
#	define ARENA_BACKEND ARENA_BACKEND_MMAP
#else
#	define ARENA_BACKEND ARENA_BACKEND_MALLOC
#endif
#endif

#ifdef ARENA_IMPL

#include <stdio.h>
#include <stdlib.h>
static void arena_pg_alloc_fail(void) {
	fprintf(stderr, "failed to allocate arena page\n");
	abort();
}

#if ARENA_BACKEND == ARENA_BACKEND_MMAP
#include <sys/mman.h>
#include <unistd.h>
#define ARENA_PG_SIZE sysconf(_SC_PAGESIZE)
static inline void *arena_pg_alloc(ptrdiff_t n) {
	void *p = mmap(NULL, n, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
	return p == MAP_FAILED ? NULL : p;
}
static inline void arena_pg_free(void *ptr, ptrdiff_t n) { munmap(ptr, n); }
#elif ARENA_BACKEND == ARENA_BACKEND_MALLOC
#define ARENA_PG_SIZE 8192
static inline void *arena_pg_alloc(ptrdiff_t n) { return malloc(n); }
static inline void arena_pg_free(void *ptr, ptrdiff_t n) { free(ptr); (void)n; }
#endif

void arena_free(Arena *a) {
	while (a->tail) {
		a->cur = a->tail->prev;
		arena_pg_free(a->tail, (uintptr_t)(a->tail->end - (char*)a->tail));
		a->tail = a->cur;
	}
}

void arena_reserve(Arena *a, ptrdiff_t n) {
	while (a->cur && a->cur->beg + n >= a->cur->end) a->cur = a->cur->next;
	if (a->cur) return;
	ptrdiff_t cap = n + sizeof(ArenaPg);
	cap += (uintptr_t)-cap & (ARENA_PG_SIZE - 1);
	ArenaPg *p = arena_pg_alloc(cap);
	if (!p) arena_pg_alloc_fail();
	p->next = NULL;
	p->prev = a->tail;
	p->beg = p->data;
	p->end = (char*)p + cap;
	if (a->tail) a->tail->next = p;
	a->cur = (a->tail = p);
}

void *arena_alloc(Arena *a, ptrdiff_t n, ptrdiff_t align) {
	arena_reserve(a, n + (align - 1));
	char *ptr = a->cur->beg + (-(uintptr_t)a->cur->beg & (align - 1));
	a->cur->beg = ptr + n;
	return ptr;
}

void *arena_realloc(Arena *a, void *ptr, ptrdiff_t old, ptrdiff_t new, ptrdiff_t align) {
	if (a->cur && ptr == a->cur->beg - old && (char*)ptr + new < a->cur->end) {
		a->cur->beg += new - old;
		return ptr;
	} else {
		void *p = arena_alloc(a, new, align);
		if (ptr) memcpy(p, ptr, old);
		return p;
	}
}

void *arena_zeroed(void *p, size_t n) {
	memset(p, 0, n);
	return p;
}

void arena_reset(Arena *a) {
	if (!a->cur) return;
	while (a->cur->prev) {
		a->cur->beg = a->cur->data;
		a->cur = a->cur->prev;
	}
	a->cur->beg = a->cur->data;
}

void arena_save(Arena *a, ArenaMark *m) {
	m->pg = a->cur;
	if (a->cur) m->beg = a->cur->beg;
}

void arena_load(Arena *a, ArenaMark *m) {
	while (a->cur && a->cur != m->pg) {
		a->cur->beg = a->cur->data;
		a->cur = a->cur->prev;
	}
	if (a->cur) a->cur->beg = m->beg;
}

#endif
#endif