/* ScummVM - Graphic Adventure Engine
 *
 * ScummVM is the legal property of its developers, whose names
 * are too numerous to list here. Please refer to the COPYRIGHT
 * file distributed with this source distribution.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.

 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.

 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 *
 * $URL$
 * $Id$
 *
 */

/* Heap-like managed structure */

#ifndef SCI_ENGINE_HEAPMGR_H
#define SCI_ENGINE_HEAPMGR_H

#include "sci/tools.h"
#include "sci/sci_memory.h"

namespace Sci {

#define HEAPENTRY_INVALID -1

// FIXME: We write (i == 0 || i > 0) instead of (i >= 0) to silence certain annoying warnings:
// generated by GCC: "comparison is always true due to limited range of data type".
#define ENTRY_IS_VALID(t, i) ((i == 0 || i > 0) && (i) < (t)->max_entry && (t)->table[(i)].next_free == (i))

#define DECLARE_HEAPENTRY(ENTRY)						\
struct ENTRY##Entry {								\
	int next_free; /* Only used for free entries */				\
	ENTRY entry;								\
};										\
										\
struct ENTRY##Table {								\
	int entries_nr; /* Number of entries allocated */			\
	int first_free; /* Beginning of a singly linked list for entries */	\
	int entries_used; /* Statistical information */				\
	int max_entry; /* Highest entry used */					\
	ENTRY##Entry *table;							\
};										\
										\
void init_##ENTRY##_table(ENTRY##Table *table);					\
int alloc_##ENTRY##_entry(ENTRY##Table *table);					\
void free_##ENTRY##_entry(ENTRY##Table *table, int index);



#define DEFINE_HEAPENTRY_WITH_CLEANUP(ENTRY, INITIAL, INCREMENT, CLEANUP_FN)	\
void init_##ENTRY##_table(ENTRY##Table *table) {				\
	table->entries_nr = INITIAL;						\
	table->max_entry = 0;							\
	table->entries_used = 0;						\
	table->first_free = HEAPENTRY_INVALID;					\
	table->table = (ENTRY##Entry *)sci_malloc(sizeof(ENTRY##Entry) * INITIAL);\
	memset(table->table, 0, sizeof(ENTRY##Entry) * INITIAL);		\
}										\
										\
void free_##ENTRY##_entry(ENTRY##Table *table, int index) {			\
	ENTRY##Entry *e = table->table + index;					\
										\
	if (index < 0 || index >= table->max_entry) {				\
		fprintf(stderr, "heapmgr: Attempt to release"			\
			" invalid table index %d!\n", index);			\
		BREAKPOINT();							\
	}									\
	CLEANUP_FN(&(e->entry));						\
										\
	e->next_free = table->first_free;					\
	table->first_free = index;						\
	table->entries_used--;							\
}										\
										\
int	alloc_##ENTRY##_entry(ENTRY##Table *table) {				\
	table->entries_used++;							\
	if (table->first_free != HEAPENTRY_INVALID) {				\
		int oldff = table->first_free;					\
		table->first_free = table->table[oldff].next_free;		\
										\
		table->table[oldff].next_free = oldff;				\
		return oldff;							\
	} else {								\
		if (table->max_entry == table->entries_nr) {			\
			table->entries_nr += INCREMENT;				\
										\
			table->table = (ENTRY##Entry *)sci_realloc(table->table,\
						   sizeof(ENTRY##Entry) * table->entries_nr);\
			memset(&table->table[table->entries_nr-INCREMENT], 0, INCREMENT * sizeof(ENTRY##Entry));\
		}								\
		table->table[table->max_entry].next_free = table->max_entry; /* Tag as 'valid' */\
		return table->max_entry++;					\
	}									\
}

#define _HEAPENTRY_IGNORE_ME(x)
#define DEFINE_HEAPENTRY(e, i, p) DEFINE_HEAPENTRY_WITH_CLEANUP(e, i, p, _HEAPENTRY_IGNORE_ME)

} // End of namespace Sci

#endif // SCI_ENGINE_HEAPMGR_H