1 /* ScummVM - Graphic Adventure Engine
2 *
3 * ScummVM is the legal property of its developers, whose names
4 * are too numerous to list here. Please refer to the COPYRIGHT
5 * file distributed with this source distribution.
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20 *
21 */
22
23 #include "glk/glulx/glulx.h"
24
25 namespace Glk {
26 namespace Glulx {
27
heap_clear()28 void Glulx::heap_clear() {
29 while (heap_head) {
30 heapblock_t *blo = heap_head;
31 heap_head = blo->next;
32 blo->next = nullptr;
33 blo->prev = nullptr;
34 glulx_free(blo);
35 }
36 heap_tail = nullptr;
37
38 if (heap_start) {
39 uint res = change_memsize(heap_start, true);
40 if (res)
41 fatal_error_i("Unable to revert memory size when deactivating heap.",
42 heap_start);
43 }
44
45 heap_start = 0;
46 alloc_count = 0;
47 /* heap_sanity_check(); */
48 }
49
heap_is_active() const50 int Glulx::heap_is_active() const {
51 return (heap_start != 0);
52 }
53
heap_get_start() const54 uint Glulx::heap_get_start() const {
55 return heap_start;
56 }
57
heap_alloc(uint len)58 uint Glulx::heap_alloc(uint len) {
59 heapblock_t *blo, *newblo;
60
61 #ifdef FIXED_MEMSIZE
62 return 0;
63 #else /* FIXED_MEMSIZE */
64
65 if (len <= 0)
66 fatal_error("Heap allocation length must be positive.");
67
68 blo = heap_head;
69 while (blo) {
70 if (blo->isfree && blo->len >= len)
71 break;
72
73 if (!blo->isfree) {
74 blo = blo->next;
75 continue;
76 }
77
78 if (!blo->next || !blo->next->isfree) {
79 blo = blo->next;
80 continue;
81 }
82
83 /* This is a free block, but the next block in the list is also
84 free, so we "advance" by merging rather than by going to
85 blo->next. */
86 newblo = blo->next;
87 blo->len += newblo->len;
88 if (newblo->next) {
89 blo->next = newblo->next;
90 newblo->next->prev = blo;
91 } else {
92 blo->next = nullptr;
93 heap_tail = blo;
94 }
95 newblo->next = nullptr;
96 newblo->prev = nullptr;
97 glulx_free(newblo);
98 newblo = nullptr;
99 continue;
100 }
101
102 if (!blo) {
103 /* No free area is visible on the list. Try extending memory. How
104 much? Double the heap size, or by 256 bytes, or by the memory
105 length requested -- whichever is greatest. */
106 uint res;
107 uint extension;
108 uint oldendmem = endmem;
109
110 extension = 0;
111 if (heap_start)
112 extension = endmem - heap_start;
113 if (extension < len)
114 extension = len;
115 if (extension < 256)
116 extension = 256;
117 /* And it must be rounded up to a multiple of 256. */
118 extension = (extension + 0xFF) & (~(uint)0xFF);
119
120 res = change_memsize(endmem + extension, true);
121 if (res)
122 return 0;
123
124 /* If we just started the heap, note that. */
125 if (heap_start == 0)
126 heap_start = oldendmem;
127
128 if (heap_tail && heap_tail->isfree) {
129 /* Append the new space to the last block. */
130 blo = heap_tail;
131 blo->len += extension;
132 } else {
133 /* Append the new space to the block list, as a new block. */
134 newblo = (heapblock_t *)glulx_malloc(sizeof(heapblock_t));
135 if (!newblo)
136 fatal_error("Unable to allocate record for heap block.");
137 newblo->addr = oldendmem;
138 newblo->len = extension;
139 newblo->isfree = true;
140 newblo->next = nullptr;
141 newblo->prev = nullptr;
142
143 if (!heap_tail) {
144 heap_head = newblo;
145 heap_tail = newblo;
146 } else {
147 blo = heap_tail;
148 heap_tail = newblo;
149 blo->next = newblo;
150 newblo->prev = blo;
151 }
152
153 blo = newblo;
154 newblo = nullptr;
155 }
156
157 /* and continue forwards, using this new block (blo). */
158 }
159
160 /* Something strange happened. */
161 if (!blo || !blo->isfree || blo->len < len)
162 return 0;
163
164 /* We now have a free block of size len or longer. */
165
166 if (blo->len == len) {
167 blo->isfree = false;
168 } else {
169 newblo = (heapblock_t *)glulx_malloc(sizeof(heapblock_t));
170 if (!newblo)
171 fatal_error("Unable to allocate record for heap block.");
172 newblo->isfree = true;
173 newblo->addr = blo->addr + len;
174 newblo->len = blo->len - len;
175 blo->len = len;
176 blo->isfree = false;
177 newblo->next = blo->next;
178 if (newblo->next)
179 newblo->next->prev = newblo;
180 newblo->prev = blo;
181 blo->next = newblo;
182 if (heap_tail == blo)
183 heap_tail = newblo;
184 }
185
186 alloc_count++;
187 /* heap_sanity_check(); */
188 return blo->addr;
189
190 #endif /* FIXED_MEMSIZE */
191 }
192
heap_free(uint addr)193 void Glulx::heap_free(uint addr) {
194 heapblock_t *blo;
195
196 for (blo = heap_head; blo; blo = blo->next) {
197 if (blo->addr == addr)
198 break;
199 };
200 if (!blo || blo->isfree)
201 fatal_error_i("Attempt to free unallocated address from heap.", addr);
202
203 blo->isfree = true;
204 alloc_count--;
205 if (alloc_count <= 0) {
206 heap_clear();
207 }
208
209 /* heap_sanity_check(); */
210 }
211
heap_get_summary(uint * valcount,uint ** summary)212 int Glulx::heap_get_summary(uint *valcount, uint **summary) {
213 uint *arr, len, pos;
214 heapblock_t *blo;
215
216 *valcount = 0;
217 *summary = nullptr;
218
219 if (heap_start == 0)
220 return 0;
221
222 len = 2 + 2 * alloc_count;
223 arr = (uint *)glulx_malloc(len * sizeof(uint));
224 if (!arr)
225 return 1;
226
227 pos = 0;
228 arr[pos++] = heap_start;
229 arr[pos++] = alloc_count;
230
231 for (blo = heap_head; blo; blo = blo->next) {
232 if (blo->isfree)
233 continue;
234 arr[pos++] = blo->addr;
235 arr[pos++] = blo->len;
236 }
237
238 if (pos != len)
239 fatal_error("Wrong number of active blocks in heap");
240
241 *valcount = len;
242 *summary = arr;
243 return 0;
244 }
245
heap_apply_summary(uint valcount,uint * summary)246 int Glulx::heap_apply_summary(uint valcount, uint *summary) {
247 uint lx, jx, lastend;
248
249 if (heap_start)
250 fatal_error("Heap active when heap_apply_summary called");
251
252 if (valcount == 0 || summary == nullptr)
253 return 0;
254 if (valcount == 2 && summary[0] == 0 && summary[1] == 0)
255 return 0;
256
257 #ifdef FIXED_MEMSIZE
258 return 1;
259 #else /* FIXED_MEMSIZE */
260
261 lx = 0;
262 heap_start = summary[lx++];
263 alloc_count = summary[lx++];
264
265 for (jx = lx; jx + 2 < valcount; jx += 2) {
266 if (summary[jx] >= summary[jx + 2])
267 fatal_error("Heap block summary is out of order.");
268 }
269
270 lastend = heap_start;
271
272 while (lx < valcount || lastend < endmem) {
273 heapblock_t *blo;
274
275 blo = (heapblock_t *)glulx_malloc(sizeof(heapblock_t));
276 if (!blo)
277 fatal_error("Unable to allocate record for heap block.");
278
279 if (lx >= valcount) {
280 blo->addr = lastend;
281 blo->len = endmem - lastend;
282 blo->isfree = true;
283 } else {
284 if (lastend < summary[lx]) {
285 blo->addr = lastend;
286 blo->len = summary[lx] - lastend;
287 blo->isfree = true;
288 } else {
289 blo->addr = summary[lx++];
290 blo->len = summary[lx++];
291 blo->isfree = false;
292 }
293 }
294
295 blo->prev = nullptr;
296 blo->next = nullptr;
297
298 if (!heap_head) {
299 heap_head = blo;
300 heap_tail = blo;
301 } else {
302 heap_tail->next = blo;
303 blo->prev = heap_tail;
304 heap_tail = blo;
305 }
306
307 lastend = blo->addr + blo->len;
308 }
309
310 /* heap_sanity_check(); */
311
312 return 0;
313 #endif /* FIXED_MEMSIZE */
314 }
315
316 } // End of namespace Glulx
317 } // End of namespace Glk
318