;
; heap.s
;
; A resizing, nonshifting heap (MDW)
;
;  1994-1998 Straylight
;

;----- Licensing note -------------------------------------------------------
;
; This file is part of Straylight's heap.
;
; Heap is free software; you can redistribute it and/or modify
; it under the terms of the GNU General Public License as published by
; the Free Software Foundation; either version 2, or (at your option)
; any later version.
;
; Heap is distributed in the hope that it will be useful,
; but WITHOUT ANY WARRANTY; without even the implied warranty of
; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
; GNU General Public License for more details.
;
; You should have received a copy of the GNU General Public License
; along with Heap.  If not, write to the Free Software Foundation,
; 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

;----- New unified version --------------------------------------------------
;
; I'm finally fed up of maintaining two different versions of this code.
; From now on, there is only this one.
;
; Lots of options are supported:
;
; OPT_APCS	Generate an APCS-compatible version
; OPT_SAPPHIRE	Generate a Sapphire-compatible version
; OPT_STANDALONE Build a standalone assembler version (default)
; OPT_DLL	Generate absolute address relocation for DLL code
;
;								[mdw]

;----- Set up some options --------------------------------------------------

		MACRO
		DCLOPT	$var
		[	:DEF:$var
$var		SETL	{TRUE}
		|
		GBLL	$var
$var		SETL	{FALSE}
		]
		MEND

		DCLOPT	OPT_APCS
		DCLOPT	OPT_SAPPHIRE
		DCLOPT	OPT_STANDALONE
		DCLOPT	OPT_DLL

	[ :LNOT:OPT_APCS:LAND::LNOT:OPT_SAPPHIRE:LAND::LNOT:OPT_STANDALONE
		GBLL	OPT_STANDALONE
OPT_STANDALONE	SETL	{TRUE}
	]

;----- Standard header ------------------------------------------------------

		GET	libs:header
		GET	libs:swis

;----- External dependencies ------------------------------------------------

	[ OPT_SAPPHIRE
		GET	sapphire:alloc
		GET	sapphire:flex
		GET	sapphire:msgs
		GET	sapphire:fastMove
		GET	sapphire:sapphire
	|
		IMPORT	fastMove
		IMPORT	flex_init
		IMPORT	flex_alloc
		IMPORT	flex_extend
	]

;----- Workspace macros -----------------------------------------------------

	[ OPT_APCS

		MACRO
$label		WSPACE	$addr,$reg
		LCLS	r
		[	"$reg"=""
r		SETS	"R12"
		|
r		SETS	"$reg"
		]
		ALIGN
$label
		LDR	$r,$addr
		[	OPT_DLL
		LDR	R14,[R10,#-536]
		ADD	$r,R14,$r
		]
		MEND

	]

;----- External routines ----------------------------------------------------

	[ OPT_SAPPHIRE
		AREA	|Sapphire$$Code|,CODE,READONLY
	]
	[ OPT_APCS
		AREA	|C$$Code|,CODE,READONLY
	]
	[ OPT_STANDALONE
		AREA	|Straylight$$Code|,CODE,READONLY
	]

; --- heap_init ---
;
; On entry:	--
;
; On exit:	--
;
; Use:		Initialises the heap system for use.

		EXPORT	heap_init

heap_init	ROUT

		STMFD	R13!,{R0,R1,R12,R14}	;Stash some registers
		WSPACE	heap__wSpace		;Find my workspace

	[ OPT_SAPPHIRE
		BL	msgs_init		;Make sure msgs is going
	]
		BL	flex_init		;Make sure flex is up

	[ :LNOT:OPT_STANDALONE

		; --- Ensure I'm not already initialised ---

		LDR	R0,heap__flex		;Get my flex pointer
		CMP	R0,#0			;Is it a silly value?
		LDMNEFD	R13!,{R0,R1,R12,PC}^	;Yes -- return now

	]

		; --- Read the machine chunk size ---

		SWI	OS_ReadMemMapInfo	;Get page size (in R0)
		STR	R0,heap__chunkSize	;Store for future reference

		; --- Allocate the base flex block ---

		SUB	R1,R0,#8		;Need to allocate memory
		ADR	R0,heap__flex		;Point to flex anchor
		BL	flex_alloc		;Hope it worked
	[ OPT_APCS
		CMP	R0,#0			;Check the result code
		BEQ	%99heap_init		;If it failed, go ahead
	|
		BCS	%99heap_init		;If it failed, go ahead
	]

		; --- Initialise the rest of the workspace ---

		MOV	R0,#0
		STR	R0,heap__alloced
		MOV	R0,#-1
		STR	R0,heap__freeList
		LDR	R0,heap__chunkSize
		SUB	R0,R0,#8
		STR	R0,heap__size
		LDMFD	R13!,{R0,R1,R12,PC}^

99heap_init	ADR	R0,heap__nomem		;Point to the error block
	[ OPT_SAPPHIRE
		BL	msgs_error		;Translate the message
	]
		SWI	OS_GenerateError	;And really moan about it

heap__nomem	DCD	1
	[ OPT_SAPPHIRE
		DCB	"hpNEMI",0
	|
		DCB	"Not enough memory to build heap",0
	]
		ALIGN

	[ OPT_SAPPHIRE
heap__wSpace	DCD	0
	]

	[ OPT_APCS
heap__wSpace	DCD	heap__sSpace
	]

		LTORG

	[ OPT_SAPPHIRE

; --- heap_useHeap ---
;
; On entry:	--
;
; On exit:	--
;
; Use:		Registers the resizing heap as the current allocator.

		EXPORT	heap_useHeap
heap_useHeap	ROUT

		STMFD	R13!,{R0-R2,R14}	;Save some registers
		ADR	R0,heap_alloc		;Point to the allocator
		ADR	R1,heap_free		;And to the freer
		MOV	R2,#0			;Don't care about workspace
		BL	alloc_register		;Make heap the allocator
		LDMFD	R13!,{R0-R2,PC}^	;Return to caller

		LTORG

	]

; --- heap_info ---
;
; On entry:	R0 == pointer to structure to fill in (APCS)
;
; On exit:	R0 == current heap size (Sapphire)
;		R1 == amount of memory free in the heap (Sapphire)
;		R2 == size of the largest block free (Sapphire)
;
; Use:		Describes the heap's current status.

		EXPORT	heap_info
heap_info	ROUT

	[ OPT_APCS
		STMFD	R13!,{R4,R5,R12,R14}
		WSPACE	heap__wSpace
		MOV	R5,R0
	|
		STMFD	R13!,{R3,R4,R12,R14}
		WSPACE	heap__wSpace
	]

		; --- Set up some registers ---

		LDR	R0,heap__size		;Get size of heap

		LDR	R4,heap__flex		;Pointer to the heap
		LDR	R14,heap__freeList	;Offset to first free block
		LDR	R2,heap__alloced	;Length of allocated region
		SUB	R1,R0,R2		;This area is free
		MOV	R2,R1			;Largest block found yet

		; --- Now we can proceed through the loop ---

00heap_info	CMP	R14,#-1			;Is this the end of the list?
		BEQ	%01heap_info		;Yes - wrap things up nicely
		ADD	R14,R14,R4		;Convert to a pointer
		LDR	R3,[R14,#0]		;Get the length of this block
		ADD	R1,R1,R3		;Add to free size
		CMP	R3,R2			;Is it the biggest one yet?
		MOVGT	R2,R3			;Yes - remember it
		LDR	R14,[R14,#4]		;Get next offset
		B	%00heap_info		;And loop round again

		; --- Now return this information ---

	[ OPT_APCS
01heap_info	STMIA	R5,{R0-R2}
		LDMFD	R13!,{R4,R5,R12,PC}^
	|
01heap_info	LDMFD	R13!,{R3,R4,R12,PC}^	;Return to caller
	]

		LTORG

; --- heap_alloc ---
;
; On entry:	R0 == size of block wanted
;
; On exit:	Sapphire: CC if enough memory, R0 == address; CS if no
;			memory, R0 corrupted
;		APCS: R0 == pointer to memory, or zero if not enough
;
; Use:		Allocates a block of at least a given size from a heap.  If
;		the heap is not big enough, more is claimed from the
;		operating system.

		EXPORT	heap_alloc
heap_alloc	ROUT

		; --- Make sure there's something to do ---

		CMP	R0,#0			;Is the required size 0?
		MOVEQS	PC,R14			;Yes -- return a NULL pointer

		; --- Start everything up then ---

	[ :LNOT:OPT_APCS
		BIC	R14,R14,#C_flag
	]
		STMFD	R13!,{R1-R6,R12,R14}	;Save a load of registers
		WSPACE	heap__wSpace

		; --- First, set up parameters ---

		ADD	R0,R0,#11		;Add overhead and align to
		BIC	R0,R0,#7		; multiple of 8

		; --- Initialise for a loop through the free list ---

		LDR	R6,heap__flex		;Point to heap start
		MOV	R5,#-1			;Previous block
		LDR	R4,heap__freeList	;Point to free list to scan

		; --- This is the free list scanning loop ---

00heap_alloc	CMP	R4,#-1			;Is this the end?
		BEQ	%02heap_alloc		;Yes - try unallocated region
		ADD	R4,R4,R6		;Translate offset to address
		LDR	R1,[R4,#0]		;Get length word
		CMP	R1,R0			;Check sizes
		MOVCC	R5,R4			;Too small - set up prev ptr
		LDRCC	R4,[R4,#4]		;Get next pointer
		BCC	%00heap_alloc		;And try next block

		; --- If block is right size, remove from the chain ---

		LDREQ	R2,[R4,#4]		;Get next offset
		ADDEQ	R2,R2,R6		;Translate to address
		BEQ	%01heap_alloc		;And branch ahead

		; --- Now, we try to hack off the bit we need ---

		STR	R0,[R4,#0]		;Store block's new length
		ADD	R2,R0,R4		;R2 points to next block
		SUB	R3,R1,R0		;Space left in this block
		STR	R3,[R2,#0]		;Store in length field
		LDR	R3,[R4,#4]		;Now get next pointer
		STR	R3,[R2,#4]		;Store.

		; --- Now put in link from previous block and return ---

01heap_alloc	SUB	R2,R2,R6		;Translate back to an offset
		CMP	R5,#-1			;Is there a previous block?
		STRNE	R2,[R5,#4]		;Store in previous block
		STREQ	R2,heap__freeList	;No - stick it in the front
		ADD	R0,R4,#4		;Leave out the length field
		LDMFD	R13!,{R1-R6,R12,PC}^	;And return to caller

		; --- Check the free area is big enough for the block ---

02heap_alloc	LDR	R4,heap__alloced	;Offset to free area
		LDR	R5,heap__size		;Current size of heap
		ADD	R6,R4,R0		;How big the area needs to be
		CMP	R5,R6			;Is this sufficient?
		BCS	%03heap_alloc		;Yes - allocate block

		; --- We need more memory in the heap.  Call flex for it ---

		MOV	R5,R0			;Preserve the caller's length
		LDR	R1,heap__chunkSize	;Units of allocation
		SUB	R1,R1,#1		;For alignment purposes
		ADD	R6,R6,#8
		ADD	R6,R6,R1		;First step in alignment
		BIC	R6,R6,R1		;Second step
		SUB	R6,R6,#8
		ADR	R0,heap__flex		;Point to anchor
		MOV	R1,R6			;New size we want
		BL	flex_extend		;Try to get memory
	[ OPT_APCS
		CMP	R0,#0			;If it failed,
		LDMEQFD	R13!,{R1-R6,R12,PC}^	;Return a null pointer
	|
		LDMCSFD	R13!,{R1-R6,R12,R14}	;If it failed, return with...
		ORRCSS	PC,R14,#C_flag		;...carry set
	]
		STR	R6,heap__size		;Store new heap size
		MOV	R0,R5			;Restore the desired length

		; --- Now allocate a block from the free area properly ---

03heap_alloc	LDR	R1,heap__flex		;Point to start of heap
		ADD	R2,R4,R1		;R2 points to new block
		STR	R0,[R2,#0]		;Store the length
		ADD	R4,R4,R0		;Get new free offset
		STR	R4,heap__alloced	;Store permanently
		ADD	R0,R2,#4		;Point to free part of block
		LDMFD	R13!,{R1-R6,R12,PC}^	;Return flushed with success

		LTORG

; --- heap_free ---
;
; On entry:	R0 == pointer to a block created with heap_alloc
;
; On exit:	--
;
; Use:		Frees a block allocated using heap_alloc.  It tries to
;		shrink the heap as much as possible afterwards.

		EXPORT	heap_free
heap_free	ROUT

		; --- Make sure the user's not being stupid ---

		CMP	R0,#0
		MOVEQS	PC,R14

		; --- Proceed as normal ---

		STMFD	R13!,{R0-R8,R12,R14}
		WSPACE	heap__wSpace

		; --- Scan the free list ---
		;
		; Now first we run through the free list trying to find
		; a free block (a) immediately before the current one and
		; (b) immediately after the current one.

		SUB	R5,R0,#4		;Point to real block start
		LDR	R6,[R5,#0]		;Get length of block
		ADD	R6,R5,R6		;R6 points off end of block
		MOV	R7,#-1			;Haven't found preblock
		MOV	R8,#-1			;Haven't found postblock
		LDR	R4,heap__flex		;Pointer to start of heap
		MOV	R1,#0			;Previous block in the chain
		LDR	R0,heap__freeList	;Scan the free list

		; --- Now do the scanning loop ---

00heap_free	CMP	R0,#-1			;Have we reached the end?
		BEQ	%01heap_free		;Yes - free the block
		ADD	R0,R0,R4		;Convert to a pointer
		CMP	R0,R6			;Could this be postblock?
		MOVEQ	R8,R1			;Yes - remember
		LDR	R2,[R0,#0]		;Get length
		ADD	R2,R0,R2		;R2 points past that block
		CMP	R2,R5			;Is this preblock?
		MOVEQ	R7,R1			;Yes - remember
		MOV	R1,R0			;Shift prev block along
		LDR	R0,[R0,#4]		;And get next block in list
		B	%00heap_free		;Loop round until finished

		; --- Now try and coagulate the blocks ---

01heap_free	CMP	R7,#-1			;Did we find preblock?
		BEQ	%02heap_free		;No - try postblock
		CMP	R7,#0			;Is it the first block?
		LDREQ	R0,heap__freeList	;Yes - get offset
		LDRNE	R0,[R7,#4]		;No - get offset (!)
		ADD	R0,R0,R4		;Convert to a pointer
		LDR	R1,[R0,#0]		;Get block length
		LDR	R2,[R5,#0]		;Get length of block to free
		ADD	R1,R1,R2		;Add them together
		STR	R1,[R0,#0]		;Store back in block
		LDR	R1,[R0,#4]		;Get next block offset
		CMP	R7,#0			;Is there a previous block?
		STREQ	R1,heap__freeList	;No - start the list with it
		STRNE	R1,[R7,#4]		;Yes - link in as normal
		MOV	R5,R0			;This is the block to free

		CMP	R8,R0			;Is this prev to postblock?
		MOVEQ	R8,R7			;Yes - show we've delinked

02heap_free	CMP	R8,#-1			;Did we find postblock?
		BEQ	%03heap_free		;No - free the block
		CMP	R8,#0			;Is it the first block?
		LDREQ	R0,heap__freeList	;Yes - get offset
		LDRNE	R0,[R8,#4]		;No - get offset (!)
		ADD	R0,R0,R4		;Convert to a pointer
		LDR	R1,[R0,#0]		;Get block length
		LDR	R2,[R5,#0]		;Get length of block to free
		ADD	R1,R1,R2		;Add them together
		STR	R1,[R5,#0]		;Store back in block
		LDR	R1,[R0,#4]		;Get next block offset
		CMP	R8,#0			;Is there a previous block?
		STREQ	R1,heap__freeList	;No - start the list with it
		STRNE	R1,[R8,#4]		;Yes - link in as normal

		; --- Now we try to reduce the allocated area ---

03heap_free	LDR	R0,heap__alloced	;Find end of allocated area
		ADD	R1,R0,R4		;Convert to a pointer
		LDR	R2,[R5,#0]		;Get length of our block
		ADD	R3,R5,R2		;Find the end of it
		CMP	R3,R1			;Are they the same?
		BNE	%04heap_free		;No - old-fashioned method!
		SUB	R0,R0,R2		;Reduce the allocated region
		STR	R0,heap__alloced	;Remember this!
		LDR	R1,heap__chunkSize	;Get the chunk size
		SUB	R1,R1,#1		;More useful like this!
		ADD	R0,R0,#8
		ADD	R0,R0,R1		;Alignment step 1
		BIC	R7,R0,R1		;Alignment step 2
		SUB	R7,R7,#8
		LDR	R2,heap__size		;Get current heap size
		CMP	R7,R2			;Are they the same?
		LDMGEFD	R13!,{R0-R8,R12,PC}^	;Yes - nothing doing
		ADR	R0,heap__flex		;Point to flex anchor
		MOV	R1,R7			;New size for block
		BL	flex_extend		;Try and reduce
	[ OPT_APCS
		CMP	R0,#0			;Did it fail (unlikely!)
		STRNE	R7,heap__size		;No - remember new size
	|
		STRCC	R7,heap__size
	]
		LDMFD	R13!,{R0-R8,R12,PC}^	;Return to sender

		; --- Now use the old fashioned method to link the block ---

04heap_free	LDR	R0,heap__freeList	;Get current first free block
		STR	R0,[R5,#4]		;Store in our block
		SUB	R5,R5,R4		;Turn back into an offset
		STR	R5,heap__freeList	;Store as new first free
		LDMFD	R13!,{R0-R8,R12,PC}^	;Return to sender

		LTORG

; --- heap_reAlloc ---
;
; On entry:	R0 == pointer to block whose size we want to change
;		R1 == the new size of the block
;
; On exit:	Sapphire: CC and R0 == pointer to block if OK, CS if no mem
;		APCS: R0 == pointer to block if OK, or null if no mem
;
; Use:		Changes the size of a heap block.  If possible, the block's
;		position is unchanged, but this may not always be the case.
;
;		Note that changing a block's size to 0 is permitted.

		EXPORT	heap_reAlloc
		EXPORT	heap_realloc
heap_reAlloc	ROUT
heap_realloc

		; --- Some ANSI-compatible checks on the parameters ---

		CMP	R0,#0			;If the pointer is NULL...
		MOVEQ	R0,R1			;This should just do a malloc
		BEQ	heap_alloc

	[ :LNOT:OPT_APCS
		BIC	R14,R14,#C_flag		;Clr carry flag on offchance
	]
		STMFD	R13!,{R1-R8,R12,R14}

		CMP	R1,#0			;If new size is NULL
		BLEQ	heap_free		;This should just free it
		MOVEQ	R0,#0			;Return a NULL pointer
		LDMEQDB	R13!,{R1-R8,R12,PC}^	;And return to caller

		; --- First set things up nicely ---
		;
		; Make sure we actually have to do anything.

		WSPACE	heap__wSpace		;Get global heap data
		ADD	R6,R1,#11		;Add 4 bytes length and align
		BIC	R6,R6,#7		;to a multiple of 8
		SUB	R5,R0,#4		;Point to length word
		LDR	R7,[R5,#0]		;Get the length word
		CMP	R7,R6			;Do we have to do any work?
		LDMEQDB	R13!,{R1-R8,R12,PC}^	;No - don't then!

		; --- Try for some easy cases ---
		;
		; If this block is at the end of the allocated area, we
		; can just extend this area and the block size.  So check
		; for this case.

		ADD	R2,R5,R7		;Find end of the block
		LDR	R8,heap__alloced	;Offset of free space
		LDR	R4,heap__flex		;Pointer to start of heap
		ADD	R3,R8,R4		;Convert offset to pointer
		CMP	R2,R3			;Are they the same?
		BNE	%02heap_reAlloc		;No - deal with other case

		; --- Just extend the area then ---
		;
		; Now we shall need to make sure that the free area is big
		; enough (or maybe reduce it!)  This may, of course, fail.

		SUB	R8,R8,R7		;Remove the original length
		ADD	R8,R8,R6		;And add the new length
		ADD	R4,R8,#8		;Add on flex's two words
		LDR	R0,heap__chunkSize	;Get the chunk size
		SUB	R0,R0,#1		;For aligning purposes
		ADD	R4,R4,R0		;Alignment step 1
		BIC	R4,R4,R0		;Alignment step 2
		SUB	R4,R4,#8		;Remove flex's words again
		LDR	R0,heap__size		;Find the heap's size
		CMP	R0,R4			;How different are they?
		BEQ	%00heap_reAlloc		;If they're the same, no prob
		ADR	R0,heap__flex		;Point to block anchor
		MOV	R1,R4			;Set up new size
		BL	flex_extend		;Try and change block size
	[ OPT_APCS
		CMP	R0,#0			;Did it fail?
		BEQ	%01heap_reAlloc		;Yes - try some other way
	|
		BCS	%01heap_reAlloc		;Failed - try some other way
	]

00heap_reAlloc	STR	R4,heap__size		;Remember new size
		STR	R8,heap__alloced	;And new free offset
		STR	R6,[R5,#0]		;Store new length
		ADD	R0,R5,#4		;Set up return pointer
		B	%80heap_reAlloc		;Return the pointer back

		; --- Try fiddling around inside the heap block ---
		;
		; This sets up all the registers again

01heap_reAlloc	LDR	R2,[R5,#0]		;Get block length
		ADD	R2,R5,R2		;Point to end of block
		LDR	R4,heap__flex		;Point to heap base

		; --- It wasn't at the end ---
		;
		; Now, if the caller wants to reduce the block size, we can
		; manage that.

02heap_reAlloc	SUBS	R1,R7,R6		;Is the old size bigger?
		BLT	%03heap_reAlloc		;No - we'll struggle on
		ADD	R0,R5,R6		;Point to end of (new) block
		STR	R1,[R0,#0]		;Store in there
		STR	R6,[R5,#0]		;Store also new size in block
		ADD	R0,R0,#4		;Point to second block
		BL	heap_free		;Attach in free chain
		ADD	R0,R5,#4		;Setup return pointer
		B	%80heap_reAlloc		;And return to the caller

		; --- We're extending the block ---
		;
		; Loop through, finding either preblock or postblock (as for
		; freeing).  If we can, merge these three together, and then
		; hope the result is big enough.
		;
		; At this point, some register usage notes might be handy:
		;
		;   R2 -> end of block
		;   R4 -> start of heap
		;   R5 -> block to resize
		;   R6 == new size wanted
		;
		; We will use:
		;
		;   R0 -> preblock
		;   R1 -> postblock
		;   R3 -> list ptr
		;
		; R7 will be previous block, R8 will be used as scratch
		; space
		;
		; So, onwards ever...

03heap_reAlloc	LDR	R3,heap__freeList	;Set up list pointer
		MOV	R0,#-1			;No preblock
		MOV	R1,#-1			;Or postblock found yet
		MOV	R7,#0			;Previous block invalid

		; --- Now for the loop ---

04heap_reAlloc	CMP	R3,#-1			;Is this the end?
		BEQ	%05heap_reAlloc		;Try and join the blocks
		ADD	R3,R3,R4		;Convert to an address
		CMP	R3,R2			;Is this postblock?
		MOVEQ	R0,R7			;Yes - remember it
		LDR	R8,[R3,#0]		;Get size of this block
		ADD	R8,R3,R8		;And point to the end
		CMP	R5,R8			;Is this preblock?
		MOVEQ	R1,R7			;Yes - remember
		MOV	R7,R3			;Move previous pointer on
		LDR	R3,[R3,#4]		;Get next one in the list
		B	%04heap_reAlloc		;Loop round for another go

		; --- Now find out if it will help to join the blocks up ---

05heap_reAlloc	LDR	R2,[R5,#0]		;Current size
		CMP	R0,#-1			;Did we find preblock?
		BEQ	%06heap_reAlloc		;No - try postblock
		CMP	R0,#0			;Is it first block in list?
		LDREQ	R3,heap__freeList	;Yes - get offset
		LDRNE	R3,[R0,#4]		;No - get offset (!)
		LDR	R7,[R3,#0]		;Get its size
		ADD	R2,R2,R7		;Add it onto our total
06heap_reAlloc	CMP	R1,#-1			;Did we find postblock?
		BEQ	%07heap_reAlloc		;No - check the total
		CMP	R1,#0			;Is it first block in list?
		LDREQ	R3,heap__freeList	;Yes - get offset
		LDRNE	R3,[R1,#4]		;No - get offset (!)
		LDR	R7,[R3,#0]		;Get its size
		ADD	R2,R2,R7		;Add it onto our total
07heap_reAlloc	CMP	R2,R6			;Is this big enough?
		BCC	%11heap_reAlloc		;No -- do it the hard way

		; --- Now try and join on preblock ---
		;
		; Note - this is almost the same as the heap_free code, but
		; with different registers)

08heap_reAlloc	CMP	R0,#-1			;Did we find preblock?
		BEQ	%09heap_reAlloc		;No - try postblock
		CMP	R0,#0			;Is it first block in list?
		LDREQ	R3,heap__freeList	;Yes - get offset
		LDRNE	R3,[R0,#4]		;No - get offset (!)
		ADD	R3,R3,R4		;Convert offset to pointer
		LDR	R7,[R3,#0]		;Get the length of the block
		LDR	R8,[R5,#0]		;Length of block to resize
		ADD	R7,R7,R8		;Add them together
		STR	R7,[R3,#0]		;Store the combined length
		LDR	R7,[R3,#4]		;Get next block in list
		CMP	R0,#0			;Is there a previous block?
		STREQ	R7,heap__freeList	;No - start the list with it
		STRNE	R7,[R0,#4]		;Yes - link in as normal

		; --- Now shift the data down into the bigger block ---

		STMFD	R13!,{R0-R3}		;Store registers
		ADD	R0,R3,#4		;Destination data start
		ADD	R1,R5,#4		;Source destination start
		LDR	R2,[R5,#0]		;Size of the source block
		SUBS	R2,R2,#4		;We don't need to copy this
		BLNE	fastMove		;Does the Right Thing when
						;the blocks overlap
		LDMFD	R13!,{R0-R3}		;Restore our registers

		; --- Some fiddling before handling postblock ---

		MOV	R5,R3			;This is now block to size

		CMP	R1,R3			;Is this prev to postblock?
		MOVEQ	R1,R0			;Yes - show we've delinked

		; --- Now process postblock in the same way ---

09heap_reAlloc	CMP	R1,#-1			;Did we find postblock?
		BEQ	%10heap_reAlloc		;No - try and resize
		CMP	R1,#0			;Is it first block in list?
		LDREQ	R3,heap__freeList	;Yes - get offset
		LDRNE	R3,[R1,#4]		;No - get offset (!)
		ADD	R3,R3,R4		;Convert offset to pointer
		LDR	R7,[R3,#0]		;Get the length of the block
		LDR	R8,[R5,#0]		;Length of block to resize
		ADD	R7,R7,R8		;Add them together
		STR	R7,[R5,#0]		;Store the combined length
		LDR	R7,[R3,#4]		;Get next block in list
		CMP	R0,#0			;Is there a previous block?
		STREQ	R7,heap__freeList	;No - start the list with it
		STRNE	R7,[R0,#4]		;Yes - link in as normal

		; --- Now take off the bit we need ---
		;
		; We've already checked that it's big enough).  We do the
		; freeing ourselves, to avoid a pointless loop in heap_free

10heap_reAlloc	LDR	R7,[R5,#0]		;Get the new length
		SUB	R1,R7,R6		;Get difference in sizes
		ADD	R0,R5,R6		;Point to end of (new) block
		STR	R1,[R0,#0]		;Store in there
		STR	R6,[R5,#0]		;Store also new size in block
		LDR	R1,heap__freeList	;Get the first block in list
		STR	R1,[R0,#4]		;Store in the new free block
		SUB	R0,R0,R4		;Convert pointer to an offset
		STR	R0,heap__freeList	;It's now linked in
		ADD	R0,R5,#4		;Setup return pointer
		B	%80heap_reAlloc		;Return to caller nicely

		; --- Well, we did our best ---
		;
		; All we can do now is to try and allocate a new block, copy
		; the data, and free the old one, causing massive
		; fragmentation :-(

11heap_reAlloc	SUB	R0,R6,#4		;Size of block for heap_alloc
		BL	heap_alloc		;Try and allocate
	[ OPT_APCS
		CMP	R0,#0			;Did it fail?
		BEQ	%90heap_reAlloc		;Yes -- then return null
	|
		BCS	%90heap_reAlloc		;Failed -- return C set
	]
		MOV	R7,R0			;Remeber this pointer
		ADD	R1,R5,#4		;Source of data to copy
		LDR	R2,[R5,#0]		;Length of stuff to copy
		SUBS	R2,R2,#4		;Remove length word first
		BLNE	fastMove		;Move the data across
		ADD	R0,R5,#4		;Now free the old block
		BL	heap_free		;Do the freeing business
		MOV	R0,R7			;Give caller his pointer

		; --- Return, preserving R0 to give to the caller ---

80heap_reAlloc	LDMFD	R13!,{R1-R8,R12,PC}^

		; --- Return, setting the C flag ---

	[ OPT_APCS
90heap_reAlloc	MOV	R0,#0
		LDMFD	R13!,{R1-R8,R12,PC}^
	|
90heap_reAlloc	LDMFD	R13!,{R1-R8,R12,R14}
		ORRS	PC,R14,#C_flag
	]

		LTORG

;----- Data definitions -----------------------------------------------------

	[ :LNOT:OPT_STANDALONE

		^	0,R12
heap__wStart	#	0

		GET	libs:sh.heapws

heap__wSize	EQU	{VAR}-heap__wStart

	]

	[ OPT_SAPPHIRE
		AREA	|Sapphire$$LibData|,CODE,READONLY
		DCD	heap__wSize
		DCD	heap__wSpace
		DCD	0
		DCD	heap_init
	]

	[ OPT_APCS
		AREA	|C$$zidata|,DATA,NOINIT
heap__sSpace	%	heap__wSize
	]

;----- That's all, folks ----------------------------------------------------

		END
