GLK: GLULXE: Added heap methods

5 files changed, 413 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
diff --git a/engines/glk/module.mk b/engines/glk/module.mk
index f1dcd84d72..669f81168e 100644
--- a/engines/glk/module.mk
+++ b/engines/glk/module.mk
@@ -65,6 +65,7 @@ MODULE_OBJS := \
 	glulxe/gestalt.o \
 	glulxe/glkop.o \
 	glulxe/glulxe.o \
+	glulxe/heap.o \
 	magnetic/detection.o \
 	magnetic/magnetic.o \
 	scott/detection.o \