[Amforth-devel] Heap?

[Christian B. <cas...@ca...>]

Servus,

are there any plans to have a heap like in C?

Maybe the simplest way would be to do it like most C implementations do it:

  v            v
YZ0123456....YZ0123456...

The pointers point at the start of the memory region the programm uses. 
(0123...) Just before that point, there is a word (YZ) which is there for 
memory management. That word contains the size of the memory region and a 
flag indicating wether it's in use or not.

So we would need 3 words:
http://www.complang.tuwien.ac.at/forth/gforth/Docs-html/Heap-Allocation.html

In short:
allocate       u -- a-addr wior
This word should search through the heap for free memory. It starts by the 
first pointer, which is somewhere stored in the system. It follows the size 
information until it found a free block which is large enought for the size 
requested. If the block is larger than the requested size it will be split 
into two. If there are not enought bytes to make a new block, the current one 
will be made bigger. If an error occurs, it will be reported in wior.

free       a-addr -- wior
This word looks for the next blocks, if those are free, it merges them with 
the current block. The current block is then set to be unused.
This simple routine will run into problems if memory is freed in the wrong 
direction. Then it will not be able to merge free blocks as it is unable to 
look towards low memory regions. Maybe a special word "clean-up" might be 
good. Or we could have an allocate which checks for successive free blocks.
Free will fail on blocks which are marked unused.

resize       a-addr1 u -- a-addr2 wior
This word would essentially allocate a new block of size u, copy the data from 
the old block and free the old block. Maybe optimisations could be done to 
expand the block towards lower memory regions even if the conventional 
allocate/free combination would not work.

Another word we should have, which is not included in gforth is:
sizeof	 	a-addr1 -- u
This word checks the pointer and returns the size of the block at its 
position. 
This would help us prevent many buffer overrun problems of C.



Dynamic memory would enable us to do lots of things. For example the video 
output could save on space. For example it could have a line pointer table 
which stores pointers for each (text) line of the display. Empty lines could 
just have a 0-entry in that table. Double width lines could just take up half 
the memory. Graphic lines could use more memory, etc. Overall we might save 
quite a bit of memory.

Servus
  Casandro