path: root/engines/glk/glulxe/heap.cpp

/* 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.
 *
 */

#include "glk/glulxe/glulxe.h"

namespace Glk {
namespace Glulxe {

void Glulxe::heap_clear() {
	while (heap_head) {
		heapblock_t *blo = heap_head;
		heap_head = blo->next;
		blo->next = nullptr;
		blo->prev = nullptr;
		glulx_free(blo);
	}
	heap_tail = nullptr;

	if (heap_start) {
		uint res = change_memsize(heap_start, true);
		if (res)
			fatal_error_i("Unable to revert memory size when deactivating heap.",
			              heap_start);
	}

	heap_start = 0;
	alloc_count = 0;
	/* heap_sanity_check(); */
}

int Glulxe::heap_is_active() const {
	return (heap_start != 0);
}

uint Glulxe::heap_get_start() const {
	return heap_start;
}

uint Glulxe::heap_alloc(uint len) {
	heapblock_t *blo, *newblo;

#ifdef FIXED_MEMSIZE
	return 0;
#else /* FIXED_MEMSIZE */

	if (len <= 0)
		fatal_error("Heap allocation length must be positive.");

	blo = heap_head;
	while (blo) {
		if (blo->isfree && blo->len >= len)
			break;

		if (!blo->isfree) {
			blo = blo->next;
			continue;
		}

		if (!blo->next || !blo->next->isfree) {
			blo = blo->next;
			continue;
		}

		/* This is a free block, but the next block in the list is also
		   free, so we "advance" by merging rather than by going to
		   blo->next. */
		newblo = blo->next;
		blo->len += newblo->len;
		if (newblo->next) {
			blo->next = newblo->next;
			newblo->next->prev = blo;
		} else {
			blo->next = nullptr;
			heap_tail = blo;
		}
		newblo->next = nullptr;
		newblo->prev = nullptr;
		glulx_free(newblo);
		newblo = nullptr;
		continue;
	}

	if (!blo) {
		/* No free area is visible on the list. Try extending memory. How
		   much? Double the heap size, or by 256 bytes, or by the memory
		   length requested -- whichever is greatest. */
		uint res;
		uint extension;
		uint oldendmem = endmem;

		extension = 0;
		if (heap_start)
			extension = endmem - heap_start;
		if (extension < len)
			extension = len;
		if (extension < 256)
			extension = 256;
		/* And it must be rounded up to a multiple of 256. */
		extension = (extension + 0xFF) & (~(uint)0xFF);

		res = change_memsize(endmem + extension, true);
		if (res)
			return 0;

		/* If we just started the heap, note that. */
		if (heap_start == 0)
			heap_start = oldendmem;

		if (heap_tail && heap_tail->isfree) {
			/* Append the new space to the last block. */
			blo = heap_tail;
			blo->len += extension;
		} else {
			/* Append the new space to the block list, as a new block. */
			newblo = (heapblock_t *)glulx_malloc(sizeof(heapblock_t));
			if (!newblo)
				fatal_error("Unable to allocate record for heap block.");
			newblo->addr = oldendmem;
			newblo->len = extension;
			newblo->isfree = true;
			newblo->next = nullptr;
			newblo->prev = nullptr;

			if (!heap_tail) {
				heap_head = newblo;
				heap_tail = newblo;
			} else {
				blo = heap_tail;
				heap_tail = newblo;
				blo->next = newblo;
				newblo->prev = blo;
			}

			blo = newblo;
			newblo = nullptr;
		}

		/* and continue forwards, using this new block (blo). */
	}

	/* Something strange happened. */
	if (!blo || !blo->isfree || blo->len < len)
		return 0;

	/* We now have a free block of size len or longer. */

	if (blo->len == len) {
		blo->isfree = false;
	} else {
		newblo = (heapblock_t *)glulx_malloc(sizeof(heapblock_t));
		if (!newblo)
			fatal_error("Unable to allocate record for heap block.");
		newblo->isfree = true;
		newblo->addr = blo->addr + len;
		newblo->len = blo->len - len;
		blo->len = len;
		blo->isfree = false;
		newblo->next = blo->next;
		if (newblo->next)
			newblo->next->prev = newblo;
		newblo->prev = blo;
		blo->next = newblo;
		if (heap_tail == blo)
			heap_tail = newblo;
	}

	alloc_count++;
	/* heap_sanity_check(); */
	return blo->addr;

#endif /* FIXED_MEMSIZE */
}

void Glulxe::heap_free(uint addr) {
	heapblock_t *blo;

	for (blo = heap_head; blo; blo = blo->next) {
		if (blo->addr == addr)
			break;
	};
	if (!blo || blo->isfree)
		fatal_error_i("Attempt to free unallocated address from heap.", addr);

	blo->isfree = true;
	alloc_count--;
	if (alloc_count <= 0) {
		heap_clear();
	}

	/* heap_sanity_check(); */
}

int Glulxe::heap_get_summary(uint *valcount, uint **summary) {
	uint *arr, len, pos;
	heapblock_t *blo;

	*valcount = 0;
	*summary = nullptr;

	if (heap_start == 0)
		return 0;

	len = 2 + 2 * alloc_count;
	arr = (uint *)glulx_malloc(len * sizeof(uint));
	if (!arr)
		return 1;

	pos = 0;
	arr[pos++] = heap_start;
	arr[pos++] = alloc_count;

	for (blo = heap_head; blo; blo = blo->next) {
		if (blo->isfree)
			continue;
		arr[pos++] = blo->addr;
		arr[pos++] = blo->len;
	}

	if (pos != len)
		fatal_error("Wrong number of active blocks in heap");

	*valcount = len;
	*summary = arr;
	return 0;
}

int Glulxe::heap_apply_summary(uint valcount, uint *summary) {
	uint lx, jx, lastend;

	if (heap_start)
		fatal_error("Heap active when heap_apply_summary called");

	if (valcount == 0 || summary == nullptr)
		return 0;
	if (valcount == 2 && summary[0] == 0 && summary[1] == 0)
		return 0;

#ifdef FIXED_MEMSIZE
	return 1;
#else /* FIXED_MEMSIZE */

	lx = 0;
	heap_start = summary[lx++];
	alloc_count = summary[lx++];

	for (jx = lx; jx + 2 < valcount; jx += 2) {
		if (summary[jx] >= summary[jx + 2])
			fatal_error("Heap block summary is out of order.");
	}

	lastend = heap_start;

	while (lx < valcount || lastend < endmem) {
		heapblock_t *blo;

		blo = (heapblock_t *)glulx_malloc(sizeof(heapblock_t));
		if (!blo)
			fatal_error("Unable to allocate record for heap block.");

		if (lx >= valcount) {
			blo->addr = lastend;
			blo->len = endmem - lastend;
			blo->isfree = true;
		} else {
			if (lastend < summary[lx]) {
				blo->addr = lastend;
				blo->len = summary[lx] - lastend;
				blo->isfree = true;
			} else {
				blo->addr = summary[lx++];
				blo->len = summary[lx++];
				blo->isfree = false;
			}
		}

		blo->prev = nullptr;
		blo->next = nullptr;

		if (!heap_head) {
			heap_head = blo;
			heap_tail = blo;
		} else {
			heap_tail->next = blo;
			blo->prev = heap_tail;
			heap_tail = blo;
		}

		lastend = blo->addr + blo->len;
	}

	/* heap_sanity_check(); */

	return 0;
#endif /* FIXED_MEMSIZE */
}

} // End of namespace Glulxe
} // End of namespace Glk