aboutsummaryrefslogtreecommitdiff
path: root/engines/glk/glulxe
diff options
context:
space:
mode:
authorPaul Gilbert2019-04-14 21:41:16 -0700
committerPaul Gilbert2019-04-17 20:46:06 -0700
commit9ceb83972adc62aff28618c196f0a473fb85b1a0 (patch)
tree42f8573cb9d73307a9a28b472da381dfb5451f34 /engines/glk/glulxe
parent0b628784bd9a65322fc6c04be41267310f497dea (diff)
downloadscummvm-rg350-9ceb83972adc62aff28618c196f0a473fb85b1a0.tar.gz
scummvm-rg350-9ceb83972adc62aff28618c196f0a473fb85b1a0.tar.bz2
scummvm-rg350-9ceb83972adc62aff28618c196f0a473fb85b1a0.zip
GLK: GLULXE: Added heap methods
Diffstat (limited to 'engines/glk/glulxe')
-rw-r--r--engines/glk/glulxe/glulxe.cpp6
-rw-r--r--engines/glk/glulxe/glulxe.h81
-rw-r--r--engines/glk/glulxe/glulxe_types.h8
-rw-r--r--engines/glk/glulxe/heap.cpp322
4 files changed, 412 insertions, 5 deletions
diff --git a/engines/glk/glulxe/glulxe.cpp b/engines/glk/glulxe/glulxe.cpp
index 1f05b9432a..d16ecfb8cc 100644
--- a/engines/glk/glulxe/glulxe.cpp
+++ b/engines/glk/glulxe/glulxe.cpp
@@ -35,10 +35,12 @@ Glulxe::Glulxe(OSystem *syst, const GlkGameDescription &gameDesc) : GlkAPI(syst,
startfuncaddr(0), checksum(0), stackptr(0), frameptr(0), pc(0), prevpc(0), origstringtable(0),
stringtable(0), valstackbase(0), localsbase(0), endmem(0), protectstart(0), protectend(0),
stream_char_handler(nullptr), stream_unichar_handler(nullptr),
- // Accel
+ // accel
classes_table(0), indiv_prop_start(0), class_metaclass(0), object_metaclass(0),
routine_metaclass(0), string_metaclass(0), self(0), num_attr_bytes(0), cpv__start(0),
- accelentries(nullptr) {
+ accelentries(nullptr),
+ // heap
+ heap_start(0), alloc_count(0), heap_head(nullptr), heap_tail(nullptr) {
g_vm = this;
}
diff --git a/engines/glk/glulxe/glulxe.h b/engines/glk/glulxe/glulxe.h
index 2eed876ffe..eacc51fd56 100644
--- a/engines/glk/glulxe/glulxe.h
+++ b/engines/glk/glulxe/glulxe.h
@@ -80,6 +80,34 @@ public:
accelentry_t **accelentries;
/**@}*/
+
+ /**
+ * \defgroup heap fields
+ * @{
+ */
+
+ uint heap_start = 0; ///< zero for inactive heap
+ int alloc_count = 0;
+
+ /* The heap_head/heap_tail is a doubly-linked list of blocks, both
+ free and allocated. It is kept in address order. It should be
+ complete -- that is, the first block starts at heap_start, and each
+ block ends at the beginning of the next block, until the last one,
+ which ends at endmem.
+
+ (Heap_start is never the same as end_mem; if there is no heap space,
+ then the heap is inactive and heap_start is zero.)
+
+ Adjacent free blocks may be merged at heap_alloc() time.
+
+ ### To make alloc more efficient, we could keep a separate
+ free-list. To make free more efficient, we could keep a hash
+ table of allocations.
+ */
+ heapblock_t *heap_head = NULL;
+ heapblock_t *heap_tail = NULL;
+
+ /**@}*/
protected:
/**
* \defgroup glkop fields
@@ -370,14 +398,61 @@ public:
* \defgroup Heap access methods
* @{
*/
+
+ /**
+ * Set the heap state to inactive, and free the block lists. This is called when the game
+ * starts or restarts.
+ */
void heap_clear(void);
- int heap_is_active(void);
- uint heap_get_start(void);
+
+ /**
+ * Returns whether the heap is active.
+ */
+ int heap_is_active() const;
+
+ /**
+ * Returns the start address of the heap, or 0 if the heap is not active.
+ */
+ uint heap_get_start() const;
+
+ /**
+ * Allocate a block. If necessary, activate the heap and/or extend memory. This may not be
+ * available at all; #define FIXED_MEMSIZE if you want the interpreter to unconditionally refuse.
+ * Returns the memory address of the block, or 0 if the operation failed.
+ */
uint heap_alloc(uint len);
+
+ /**
+ * Free a heap block. If necessary, deactivate the heap.
+ */
void heap_free(uint addr);
+
+ /**
+ * Create an array of words, in the VM serialization format:
+ *
+ * heap_start
+ * alloc_count
+ * addr of first block
+ * len of first block
+ * ...
+ *
+ * (Note that these are uint values -- native byte ordering. Also, the blocks will be in address order,
+ * which is a stricter guarantee than the VM specifies; that'll help in heap_apply_summary().)
+ *
+ * If the heap is inactive, store NULL. Return 0 for success; otherwise, the operation failed.
+ *
+ * The array returned in summary must be freed with glulx_free() after the caller uses it.
+ */
int heap_get_summary(uint *valcount, uint **summary);
+
+ /**
+ * Given an array of words in the above format, set up the heap to contain it. As noted above,
+ * the caller must ensure that the blocks are in address order. When this is called, the heap
+ * must be inactive.
+ *
+ * Return 0 for success. Otherwise the operation failed (and, most likely, caused a fatal error).
+ */
int heap_apply_summary(uint valcount, uint *summary);
- void heap_sanity_check(void);
/**@}*/
diff --git a/engines/glk/glulxe/glulxe_types.h b/engines/glk/glulxe/glulxe_types.h
index c6ce238460..96943d2f2a 100644
--- a/engines/glk/glulxe/glulxe_types.h
+++ b/engines/glk/glulxe/glulxe_types.h
@@ -348,6 +348,14 @@ typedef accelentry_struct accelentry_t;
#define ACCEL_HASH_SIZE (511)
+struct heapblock_struct {
+ uint addr;
+ uint len;
+ int isfree;
+ struct heapblock_struct *next;
+ struct heapblock_struct *prev;
+};
+typedef heapblock_struct heapblock_t;
} // End of namespace Glulxe
} // End of namespace Glk
diff --git a/engines/glk/glulxe/heap.cpp b/engines/glk/glulxe/heap.cpp
new file mode 100644
index 0000000000..29d9405aca
--- /dev/null
+++ b/engines/glk/glulxe/heap.cpp
@@ -0,0 +1,322 @@
+/* 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 "engines/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