1 /* heap.c: Glulxe code related to the dynamic allocation heap.
2 Designed by Andrew Plotkin <erkyrath@eblong.com>
3 http://eblong.com/zarf/glulx/index.html
6 #define glulx_malloc malloc
7 #define glulx_free free
19 typedef struct heapblock_struct {
23 struct heapblock_struct *next;
24 struct heapblock_struct *prev;
27 static glui32 heap_start = 0; /* zero for inactive heap */
28 static int alloc_count = 0;
30 /* The heap_head/heap_tail is a doubly-linked list of blocks, both
31 free and allocated. It is kept in address order. It should be
32 complete -- that is, the first block starts at heap_start, and each
33 block ends at the beginning of the next block, until the last one,
34 which ends at gEndMem.
36 (Heap_start is never the same as end_mem; if there is no heap space,
37 then the heap is inactive and heap_start is zero.)
39 Adjacent free blocks may be merged at heap_alloc() time.
41 ### To make alloc more efficient, we could keep a separate
42 free-list. To make free more efficient, we could keep a hash
45 static heapblock_t *heap_head = NULL;
46 static heapblock_t *heap_tail = NULL;
49 Set the heap state to inactive, and free the block lists. This is
50 called when the game starts or restarts.
55 heapblock_t *blo = heap_head;
56 heap_head = blo->next;
64 glui32 res = resizeMemory(heap_start, 1);
66 fatalError("Unable to revert memory size when deactivating heap.");
71 /* heap_sanity_check(); */
75 Returns whether the heap is active.
77 int heap_is_active() {
78 return (heap_start != 0);
82 Returns the start address of the heap, or 0 if the heap is not active.
84 glui32 heap_get_start() {
89 Allocate a block. If necessary, activate the heap and/or extend memory.
90 Returns the memory address of the block, or 0 if the operation failed.
92 glui32 heap_alloc(glui32 len)
94 heapblock_t *blo, *newblo;
97 fatalError("Heap allocation length must be positive.");
101 if (blo->isfree && blo->len >= len)
109 if (!blo->next || !blo->next->isfree) {
114 /* This is a free block, but the next block in the list is also
115 free, so we "advance" by merging rather than by going to
118 blo->len += newblo->len;
120 blo->next = newblo->next;
121 newblo->next->prev = blo;
135 /* No free area is visible on the list. Try extending memory. How
136 much? Double the heap size, or by 256 bytes, or by the memory
137 length requested -- whichever is greatest. */
140 glui32 oldendmem = gEndMem;
144 extension = gEndMem - heap_start;
149 /* And it must be rounded up to a multiple of 256. */
150 extension = (extension + 0xFF) & (~(glui32)0xFF);
152 res = resizeMemory(gEndMem+extension, 1);
156 /* If we just started the heap, note that. */
158 heap_start = oldendmem;
160 if (heap_tail && heap_tail->isfree) {
161 /* Append the new space to the last block. */
163 blo->len += extension;
166 /* Append the new space to the block list, as a new block. */
167 newblo = glulx_malloc(sizeof(heapblock_t));
169 fatalError("Unable to allocate record for heap block.");
170 newblo->addr = oldendmem;
171 newblo->len = extension;
172 newblo->isfree = TRUE;
191 /* and continue forwards, using this new block (blo). */
194 /* Something strange happened. */
195 if (!blo || !blo->isfree || blo->len < len)
198 /* We now have a free block of size len or longer. */
200 if (blo->len == len) {
204 newblo = glulx_malloc(sizeof(heapblock_t));
206 fatalError("Unable to allocate record for heap block.");
207 newblo->isfree = TRUE;
208 newblo->addr = blo->addr + len;
209 newblo->len = blo->len - len;
212 newblo->next = blo->next;
214 newblo->next->prev = newblo;
217 if (heap_tail == blo)
222 /* heap_sanity_check(); */
227 Free a heap block. If necessary, deactivate the heap.
229 void heap_free(glui32 addr)
233 for (blo = heap_head; blo; blo = blo->next) {
234 if (blo->addr == addr)
237 if (!blo || blo->isfree)
238 fatalError("Attempt to free unallocated address from heap.");
242 if (alloc_count <= 0) {
246 /* heap_sanity_check(); */
249 /* heap_get_summary():
250 Create an array of words, in the VM serialization format:
258 (Note that these are glui32 values -- native byte ordering. Also,
259 the blocks will be in address order, which is a stricter guarantee
260 than the VM specifies; that'll help in heap_apply_summary().)
262 If the heap is inactive, store NULL. Return 0 for success;
263 otherwise, the operation failed.
265 The array returned in summary must be freed with glulx_free() after
268 int heap_get_summary(glui32 *valcount, glui32 **summary)
270 glui32 *arr, len, pos;
279 len = 2 + 2*alloc_count;
280 arr = glulx_malloc(len * sizeof(glui32));
285 arr[pos++] = heap_start;
286 arr[pos++] = alloc_count;
288 for (blo = heap_head; blo; blo = blo->next) {
291 arr[pos++] = blo->addr;
292 arr[pos++] = blo->len;
296 fatalError("Wrong number of active blocks in heap");
303 /* heap_apply_summary():
304 Given an array of words in the above format, set up the heap to
305 contain it. As noted above, the caller must ensure that the blocks
306 are in address order. When this is called, the heap must be
309 Return 0 for success. Otherwise the operation failed (and, most
310 likely, caused a fatal error).
312 int heap_apply_summary(glui32 valcount, glui32 *summary)
314 glui32 lx, jx, lastend;
317 fatalError("Heap active when heap_apply_summary called");
319 if (valcount == 0 || summary == NULL)
321 if (valcount == 2 && summary[0] == 0 && summary[1] == 0)
325 heap_start = summary[lx++];
326 alloc_count = summary[lx++];
328 for (jx=lx; jx+2<valcount; jx+=2) {
329 if (summary[jx] >= summary[jx+2])
330 fatalError("Heap block summary is out of order.");
333 lastend = heap_start;
335 while (lx < valcount || lastend < gEndMem) {
338 blo = glulx_malloc(sizeof(heapblock_t));
340 fatalError("Unable to allocate record for heap block.");
342 if (lx >= valcount) {
344 blo->len = gEndMem - lastend;
348 if (lastend < summary[lx]) {
350 blo->len = summary[lx] - lastend;
354 blo->addr = summary[lx++];
355 blo->len = summary[lx++];
368 heap_tail->next = blo;
369 blo->prev = heap_tail;
373 lastend = blo->addr + blo->len;
376 /* heap_sanity_check(); */