/*
 *  Example memory allocator with pool allocation for small sizes and
 *  fallback into malloc/realloc/free for larger sizes or when the pools
 *  are exhausted.
 *
 *  Useful to reduce memory churn or work around a platform allocator
 *  that doesn't handle a lot of small allocations efficiently.
 */

#include "duktape.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

/* Define to enable some debug printfs. */
/* #define DUK_ALLOC_HYBRID_DEBUG */

typedef struct {
	size_t size;
	int count;
} pool_size_spec;

static pool_size_spec pool_sizes[] = {
	{ 32, 1024 },
	{ 48, 2048 },
	{ 64, 2048 },
	{ 128, 2048 },
	{ 256, 512 },
	{ 1024, 64 },
	{ 2048, 32 }
};

#define  NUM_POOLS  (sizeof(pool_sizes) / sizeof(pool_size_spec))

/* This must fit into the smallest pool entry. */
struct pool_free_entry;
typedef struct pool_free_entry pool_free_entry;
struct pool_free_entry {
	pool_free_entry *next;
};

typedef struct {
	pool_free_entry *free;
	char *alloc_start;
	char *alloc_end;
	size_t size;
	int count;
} pool_header;

typedef struct {
	pool_header headers[NUM_POOLS];
	size_t pool_max_size;
	char *alloc_start;
	char *alloc_end;
} pool_state;

#define ADDR_IN_STATE_ALLOC(st,p) \
	((char *) (p) >= (st)->alloc_start && (char *) (p) < (st)->alloc_end)
#define ADDR_IN_HEADER_ALLOC(hdr,p) \
	((char *) (p) >= (hdr)->alloc_start && (char *) (p) < (hdr)->alloc_end)

#ifdef DUK_ALLOC_HYBRID_DEBUG
static void dump_pool_state(pool_state *st) {
	pool_free_entry *free;
	int free_len;
	int i;

	printf("=== Pool state: st=%p\n", (void *) st);
	for (i = 0; i < (int) NUM_POOLS; i++) {
		pool_header *hdr = st->headers + i;

		for (free = hdr->free, free_len = 0; free != NULL; free = free->next) {
			free_len++;
		}

		printf("[%d]: size %ld, count %ld, used %ld, free list len %ld\n",
		       i, (long) hdr->size, (long) hdr->count,
		       (long) (hdr->count - free_len),
		       (long) free_len);
	}
}
#else
static void dump_pool_state(pool_state *st) {
	(void) st;
}
#endif

void *duk_alloc_hybrid_init(void) {
	pool_state *st;
	size_t total_size, max_size;
	int i, j;
	char *p;

	st = (pool_state *) malloc(sizeof(pool_state));
	if (!st) {
		return NULL;
	}
	memset((void *) st, 0, sizeof(pool_state));
	st->alloc_start = NULL;
	st->alloc_end = NULL;

	for (i = 0, total_size = 0, max_size = 0; i < (int) NUM_POOLS; i++) {
#ifdef DUK_ALLOC_HYBRID_DEBUG
		printf("Pool %d: size %ld, count %ld\n", i, (long) pool_sizes[i].size, (long) pool_sizes[i].count);
#endif
		total_size += pool_sizes[i].size * pool_sizes[i].count;
		if (pool_sizes[i].size > max_size) {
			max_size = pool_sizes[i].size;
		}
	}
#ifdef DUK_ALLOC_HYBRID_DEBUG
	printf("Total size %ld, max pool size %ld\n", (long) total_size, (long) max_size);
#endif

	st->alloc_start = (char *) malloc(total_size);
	if (!st->alloc_start) {
		free(st);
		return NULL;
	}
	st->alloc_end = st->alloc_start + total_size;
	st->pool_max_size = max_size;
	memset((void *) st->alloc_start, 0, total_size);

	for (i = 0, p = st->alloc_start; i < (int) NUM_POOLS; i++) {
		pool_header *hdr = st->headers + i;

		hdr->alloc_start = p;
		hdr->alloc_end = p + pool_sizes[i].size * pool_sizes[i].count;
		hdr->free = (pool_free_entry *) (void *) p;
		hdr->size = pool_sizes[i].size;
		hdr->count = pool_sizes[i].count;

		for (j = 0; j < pool_sizes[i].count; j++) {
			pool_free_entry *ent = (pool_free_entry *) (void *) p;
			if (j == pool_sizes[i].count - 1) {
				ent->next = (pool_free_entry *) NULL;
			} else {
				ent->next = (pool_free_entry *) (void *) (p + pool_sizes[i].size);
			}
			p += pool_sizes[i].size;
		}
	}

	dump_pool_state(st);

	/* Use 'st' as udata. */
	return (void *) st;
}

void *duk_alloc_hybrid(void *udata, duk_size_t size) {
	pool_state *st = (pool_state *) udata;
	int i;
	void *new_ptr;

#if 0
	dump_pool_state(st);
#endif

	if (size == 0) {
		return NULL;
	}
	if (size > st->pool_max_size) {
#ifdef DUK_ALLOC_HYBRID_DEBUG
		printf("alloc fallback: %ld\n", (long) size);
#endif
		return malloc(size);
	}

	for (i = 0; i < (int) NUM_POOLS; i++) {
		pool_header *hdr = st->headers + i;
		if (hdr->size < size) {
			continue;
		}

		if (hdr->free) {
#if 0
			printf("alloc from pool: %ld -> pool size %ld\n", (long) size, (long) hdr->size);
#endif
			new_ptr = (void *) hdr->free;
			hdr->free = hdr->free->next;
			return new_ptr;
		} else {
#ifdef DUK_ALLOC_HYBRID_DEBUG
			printf("alloc out of pool entries: %ld -> pool size %ld\n", (long) size, (long) hdr->size);
#endif
			break;
		}
	}

#ifdef DUK_ALLOC_HYBRID_DEBUG
	printf("alloc fallback (out of pool): %ld\n", (long) size);
#endif
	return malloc(size);
}

void *duk_realloc_hybrid(void *udata, void *ptr, duk_size_t size) {
	pool_state *st = (pool_state *) udata;
	void *new_ptr;
	int i;

#if 0
	dump_pool_state(st);
#endif

	if (ADDR_IN_STATE_ALLOC(st, ptr)) {
		/* 'ptr' cannot be NULL. */
		for (i = 0; i < (int) NUM_POOLS; i++) {
			pool_header *hdr = st->headers + i;
			if (ADDR_IN_HEADER_ALLOC(hdr, ptr)) {
				if (size <= hdr->size) {
					/* Still fits, no shrink support. */
#if 0
					printf("realloc original from pool: still fits, size %ld, pool size %ld\n",
					       (long) size, (long) hdr->size);
#endif
					return ptr;
				}

				new_ptr = duk_alloc_hybrid(udata, size);
				if (!new_ptr) {
#ifdef DUK_ALLOC_HYBRID_DEBUG
					printf("realloc original from pool: needed larger size, failed to alloc\n");
#endif
					return NULL;
				}
				memcpy(new_ptr, ptr, hdr->size);

				((pool_free_entry *) ptr)->next = hdr->free;
				hdr->free = (pool_free_entry *) ptr;
#if 0
				printf("realloc original from pool: size %ld, pool size %ld\n", (long) size, (long) hdr->size);
#endif
				return new_ptr;
			}
		}
#ifdef DUK_ALLOC_HYBRID_DEBUG
		printf("NEVER HERE\n");
#endif
		return NULL;
	} else if (ptr != NULL) {
		if (size == 0) {
			free(ptr);
			return NULL;
		} else {
#ifdef DUK_ALLOC_HYBRID_DEBUG
			printf("realloc fallback: size %ld\n", (long) size);
#endif
			return realloc(ptr, size);
		}
	} else {
#if 0
		printf("realloc NULL ptr, call alloc: %ld\n", (long) size);
#endif
		return duk_alloc_hybrid(udata, size);
	}
}

void duk_free_hybrid(void *udata, void *ptr) {
	pool_state *st = (pool_state *) udata;
	int i;

#if 0
	dump_pool_state(st);
#endif

	if (!ADDR_IN_STATE_ALLOC(st, ptr)) {
		if (ptr == NULL) {
			return;
		}
#if 0
		printf("free out of pool: %p\n", (void *) ptr);
#endif
		free(ptr);
		return;
	}

	for (i = 0; i < (int) NUM_POOLS; i++) {
		pool_header *hdr = st->headers + i;
		if (ADDR_IN_HEADER_ALLOC(hdr, ptr)) {
			((pool_free_entry *) ptr)->next = hdr->free;
			hdr->free = (pool_free_entry *) ptr;
#if 0
			printf("free from pool: %p\n", ptr);
#endif
			return;
		}
	}

#ifdef DUK_ALLOC_HYBRID_DEBUG
	printf("NEVER HERE\n");
#endif
}