HeapShift  -  Shifting heap demonstration

by Alan Wrigley

HeapShift is a small application that introduces the concept of a shifting heap memory manager, as described in the Wimp Topics article in this month's RISC User magazine. You should read the article for an explanation of the techniques involved and how to use the heap manager routines in your own programs.

The program can be run from the RISC User menu system or by double-clicking on its icon in a filer window. A window will open on the screen showing information for up to eight blocks of memory which can be allocated, deallocated and resized. The current size of each block is shown together with the start address of the block.

Initially all blocks are unallocated, but clicking over the pop-up menu icon to the right of one of the blocks brings up a dialogue box enabling you to allocate a block of memory of any size you choose. You should enter the size into the writable icon, either in decimal format or in hex preceded by a "&" character.

Provided there is sufficient memory in your machine you will now see the size and start address displayed in the main window. If you open the Task Manager display window at the same time, you will see the effect of allocating extra memory to the task. If you have RISC OS 3.5 or 3.6, a dynamic area will have been created called HeapShift which will be the next highest multiple of 4K (the memory page size for these versions of the OS). If you have an older computer you will see that HeapShift's Wimp slot has increased by the next highest multiple of the memory page size for the machine (8K for 1Mb, 16K for 2Mb and 32K for all others).

If you now create a further block by clicking on the pop-up menu icon for one of the other items in the window and using the Create window again, you will again see the Task Manager display alter, provided that this second block pushes the total memory used above the next highest multiple of the page size. If it does not, then the block will take up some of the spare space already available in the heap after the previous allocation.

If you wish to alter the size of any block once created, clicking on the pop-up icon again will now display the Alter dialogue box. This is similar in design to Create, but this time you must specify the amount by which the size should be altered, i.e. a positive or negative value which will be added to or subtracted from the existing size. If you enter a negative value equal to the existing size, the block will be deallocated.

If the block you are altering is not the last one to be created, you will see that all the blocks with starting addresses above the one being altered will move up or down to accommodate the difference in size. This is the essence of a shifting heap - it maintains the exact amount of memory required at any one time without any wasted space due to 'holes' in the heap where a block has been shrunk or removed.

Because the pointer to the start of each block may change at any time (i.e. whenever another block is shrunk or expanded), you cannot rely on the value remaining the same as when it was originally created. For this reason, the routines set up a pointer to a pointer, and you must read this second pointer from the first whenever you wish to access the memory. A full explanation is provided in the accompanying article in the magazine.

Copyright  RISC User 1995