Remove deprecated functions in test programs
[projects/chimara/chimara.git] / interpreters / git / heap.c
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
4 */
5
6 #define glulx_malloc malloc
7 #define glulx_free free
8
9 #ifndef TRUE
10 #define TRUE 1
11 #endif
12 #ifndef FALSE
13 #define FALSE 0
14 #endif
15
16 #include "glk.h"
17 #include "git.h"
18
19 typedef struct heapblock_struct {
20   glui32 addr;
21   glui32 len;
22   int isfree;
23   struct heapblock_struct *next;
24   struct heapblock_struct *prev;
25 } heapblock_t;
26
27 static glui32 heap_start = 0; /* zero for inactive heap */
28 static int alloc_count = 0;
29
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.
35
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.)
38
39    Adjacent free blocks may be merged at heap_alloc() time.
40
41    ### To make alloc more efficient, we could keep a separate
42    free-list. To make free more efficient, we could keep a hash
43    table of allocations.
44  */
45 static heapblock_t *heap_head = NULL;
46 static heapblock_t *heap_tail = NULL;
47
48 /* heap_clear():
49    Set the heap state to inactive, and free the block lists. This is
50    called when the game starts or restarts.
51 */
52 void heap_clear()
53 {
54   while (heap_head) {
55     heapblock_t *blo = heap_head;
56     heap_head = blo->next;
57     blo->next = NULL;
58     blo->prev = NULL;
59     glulx_free(blo);
60   }
61   heap_tail = NULL;
62
63   if (heap_start) {
64     glui32 res = resizeMemory(heap_start, 1);
65     if (res)
66       fatalError("Unable to revert memory size when deactivating heap.");
67   }
68
69   heap_start = 0;
70   alloc_count = 0;
71   /* heap_sanity_check(); */
72 }
73
74 /* heap_is_active():
75    Returns whether the heap is active.
76 */
77 int heap_is_active() {
78   return (heap_start != 0);
79 }
80
81 /* heap_get_start():
82    Returns the start address of the heap, or 0 if the heap is not active.
83  */
84 glui32 heap_get_start() {
85   return heap_start;
86 }
87
88 /* heap_alloc(): 
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.
91 */
92 glui32 heap_alloc(glui32 len)
93 {
94   heapblock_t *blo, *newblo;
95
96   if (len <= 0)
97     fatalError("Heap allocation length must be positive.");
98
99   blo = heap_head;
100   while (blo) {
101     if (blo->isfree && blo->len >= len)
102       break;
103
104     if (!blo->isfree) {
105       blo = blo->next;
106       continue;
107     }
108
109     if (!blo->next || !blo->next->isfree) {
110       blo = blo->next;
111       continue;
112     }
113
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
116        blo->next. */
117     newblo = blo->next;
118     blo->len += newblo->len;
119     if (newblo->next) {
120       blo->next = newblo->next;
121       newblo->next->prev = blo;
122     }
123     else {
124       blo->next = NULL;
125       heap_tail = blo;
126     }
127     newblo->next = NULL;
128     newblo->prev = NULL;
129     glulx_free(newblo);
130     newblo = NULL;
131     continue;
132   }
133
134   if (!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. */
138     glui32 res;
139     glui32 extension;
140     glui32 oldendmem = gEndMem;
141
142     extension = 0;
143     if (heap_start)
144       extension = gEndMem - heap_start;
145     if (extension < len)
146       extension = len;
147     if (extension < 256)
148       extension = 256;
149     /* And it must be rounded up to a multiple of 256. */
150     extension = (extension + 0xFF) & (~(glui32)0xFF);
151
152     res = resizeMemory(gEndMem+extension, 1);
153     if (res)
154       return 0;
155
156     /* If we just started the heap, note that. */
157     if (heap_start == 0)
158       heap_start = oldendmem;
159
160     if (heap_tail && heap_tail->isfree) {
161       /* Append the new space to the last block. */
162       blo = heap_tail;
163       blo->len += extension;
164     }
165     else {
166       /* Append the new space to the block list, as a new block. */
167       newblo = glulx_malloc(sizeof(heapblock_t));
168       if (!newblo)
169         fatalError("Unable to allocate record for heap block.");
170       newblo->addr = oldendmem;
171       newblo->len = extension;
172       newblo->isfree = TRUE;
173       newblo->next = NULL;
174       newblo->prev = NULL;
175
176       if (!heap_tail) {
177         heap_head = newblo;
178         heap_tail = newblo;
179       }
180       else {
181         blo = heap_tail;
182         heap_tail = newblo;
183         blo->next = newblo;
184         newblo->prev = blo;
185       }
186
187       blo = newblo;
188       newblo = NULL;
189     }
190
191     /* and continue forwards, using this new block (blo). */
192   }
193
194   /* Something strange happened. */
195   if (!blo || !blo->isfree || blo->len < len)
196     return 0;
197
198   /* We now have a free block of size len or longer. */
199
200   if (blo->len == len) {
201     blo->isfree = FALSE;
202   }
203   else {
204     newblo = glulx_malloc(sizeof(heapblock_t));
205     if (!newblo)
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;
210     blo->len = len;
211     blo->isfree = FALSE;
212     newblo->next = blo->next;
213     if (newblo->next)
214       newblo->next->prev = newblo;
215     newblo->prev = blo;
216     blo->next = newblo;
217     if (heap_tail == blo)
218       heap_tail = newblo;
219   }
220
221   alloc_count++;
222   /* heap_sanity_check(); */
223   return blo->addr;
224 }
225
226 /* heap_free():
227    Free a heap block. If necessary, deactivate the heap.
228 */
229 void heap_free(glui32 addr)
230 {
231   heapblock_t *blo;
232
233   for (blo = heap_head; blo; blo = blo->next) { 
234     if (blo->addr == addr)
235       break;
236   };
237   if (!blo || blo->isfree)
238     fatalError("Attempt to free unallocated address from heap.");
239
240   blo->isfree = TRUE;
241   alloc_count--;
242   if (alloc_count <= 0) {
243     heap_clear();
244   }
245
246   /* heap_sanity_check(); */
247 }
248
249 /* heap_get_summary():
250    Create an array of words, in the VM serialization format:
251
252      heap_start
253      alloc_count
254      addr of first block
255      len of first block
256      ...
257
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().)
261
262    If the heap is inactive, store NULL. Return 0 for success;
263    otherwise, the operation failed.
264
265    The array returned in summary must be freed with glulx_free() after
266    the caller uses it.
267 */
268 int heap_get_summary(glui32 *valcount, glui32 **summary)
269 {
270   glui32 *arr, len, pos;
271   heapblock_t *blo;
272
273   *valcount = 0;
274   *summary = NULL;
275
276   if (heap_start == 0)
277     return 0;
278
279   len = 2 + 2*alloc_count;
280   arr = glulx_malloc(len * sizeof(glui32));
281   if (!arr)
282     return 1;
283
284   pos = 0;
285   arr[pos++] = heap_start;
286   arr[pos++] = alloc_count;
287
288   for (blo = heap_head; blo; blo = blo->next) {
289     if (blo->isfree)
290       continue;
291     arr[pos++] = blo->addr;
292     arr[pos++] = blo->len;
293   }
294
295   if (pos != len)
296     fatalError("Wrong number of active blocks in heap");
297
298   *valcount = len;
299   *summary = arr;
300   return 0;
301 }
302
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
307    inactive.
308
309    Return 0 for success. Otherwise the operation failed (and, most
310    likely, caused a fatal error).
311 */
312 int heap_apply_summary(glui32 valcount, glui32 *summary)
313 {
314   glui32 lx, jx, lastend;
315
316   if (heap_start)
317     fatalError("Heap active when heap_apply_summary called");
318
319   if (valcount == 0 || summary == NULL)
320     return 0;
321   if (valcount == 2 && summary[0] == 0 && summary[1] == 0)
322     return 0;
323
324   lx = 0;
325   heap_start = summary[lx++];
326   alloc_count = summary[lx++];
327
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.");
331   }
332
333   lastend = heap_start;
334
335   while (lx < valcount || lastend < gEndMem) {
336     heapblock_t *blo;
337
338     blo = glulx_malloc(sizeof(heapblock_t));
339     if (!blo)
340       fatalError("Unable to allocate record for heap block.");
341
342     if (lx >= valcount) {
343       blo->addr = lastend;
344       blo->len = gEndMem - lastend;
345       blo->isfree = TRUE;
346     }
347     else {
348       if (lastend < summary[lx]) {
349         blo->addr = lastend;
350         blo->len = summary[lx] - lastend;
351         blo->isfree = TRUE;
352       }
353       else {
354         blo->addr = summary[lx++];
355         blo->len = summary[lx++];
356         blo->isfree = FALSE;
357       }
358     }
359
360     blo->prev = NULL;
361     blo->next = NULL;
362
363     if (!heap_head) {
364       heap_head = blo;
365       heap_tail = blo;
366     }
367     else {
368       heap_tail->next = blo;
369       blo->prev = heap_tail;
370       heap_tail = blo;
371     }
372
373     lastend = blo->addr + blo->len;
374   }
375
376   /* heap_sanity_check(); */
377
378   return 0;
379 }
380