; Chunk based memory allocation system V1.02 11/2/08
; See cbma.h for docs
; Copyright 2008 Jeffrey Lee
; This file is part of WOUM.
; WOUM 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 3 of the License, or
; (at your option) any later version.
; WOUM 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 WOUM.  If not, see <http://www.gnu.org/licenses/>.

	GET	bindings.s

; Data structures. Do not change item ordering!
chunk_next	EQU	0 ; Next chunk ptr
chunk_data	EQU	4 ; Vari-size data block

heap_chunks	EQU	0 ; List of chunks
heap_listfree	EQU	4 ; List of free items, takes priority over firstfree
heap_firstfree	EQU	8 ; First free place in top chunk
heap_size	EQU	12 ; Size of each item (Must be >= 4)
heap_chunksize	EQU	16 ; Number of items per chunk
heap_alloced	EQU	20 ; Number of items allocated
heap_struct_size	EQU	24 ; Size of this structure

	AREA	cbma, CODE, READONLY

	IMPORT	malloc
	IMPORT	free

	EXPORT	cbma_new
	EXPORT	cbma_delete
	EXPORT	cbma_empty
	EXPORT	cbma_alloc
	EXPORT	cbma_free
	EXPORT	cbma_alloced

	FBEGIN cbma_new,1
	; r0 = data size, r1 = chunk size
	; returns ptr or 0
	ADD R0,R0,#3 ; Round size up to word boundary
	BICS R0,R0,#3
	MOVLE R0,#4 ; Avoid size of <=0
	CMP R1,#1
	MOVLT R1,#1
	STMFD R13!,{R0-R1,R14}
	MOV R0,#heap_struct_size
	BL malloc
	LDMFD R13!,{R1-R2,R14}
	CMP R0,#0
	MOVEQ PC,R14 ; Not enough memory
	MOV R3,#0
	STR R3,[R0,#heap_chunks] ; No chunks ATM
	STR R2,[R0,#heap_firstfree]
	STR R3,[R0,#heap_listfree]
	STR R1,[R0,#heap_size]
	STR R2,[R0,#heap_chunksize]
	STR R3,[R0,#heap_alloced]
	MOV PC,R14

	FBEGIN cbma_delete,1
	; r0 = heap ptr
	CMP R0,#0
	MOVEQ PC,R14
	STMFD R13!,{R0,R14}
	BL cbma_empty
	LDMFD R13!,{R0,R14}
	B free

	FBEGIN cbma_empty,1
	; r0 = heap ptr
	CMP R0,#0
	MOVEQ PC,R14
	STMFD R13!,{R4,R14}
	; Reset free list
	LDR R4,[R0,#heap_chunksize]
	STR R4,[R0,#heap_firstfree]
	MOV R1,#0
	STR R1,[R0,#heap_listfree]
	STR R1,[R0,#heap_alloced]
	; Delete chunks
	LDR R4,[R0,#heap_chunks] ; Get current chunk ptr
	STR R1,[R0,#heap_chunks] ; Reset chunk ptr
	MOVS R0,R4
	LDMEQFD R13!,{R4,PC} ; Return if no chunks to free
emptyloop
	LDR R4,[R4,#chunk_next] ; Get next ptr
	BL free ; Destroy chunk
	MOVS R0,R4
	BNE emptyloop
	LDMFD R13!,{R4,PC}

	FBEGIN cbma_alloc,1
	; r0 = heap ptr
	; Return new item or 0
	CMP R0,#0
	MOVEQ PC,R14
	; Assume we will succeed and increase alloced count immediately
	LDR R3,[R0,#heap_alloced]
	ADD R3,R3,#1
	STR R3,[R0,#heap_alloced]
	LDR R1,[R0,#heap_listfree] ; Free list?
	CMP R1,#0
	LDRNE R2,[R1] ; Yes, so return an item from it
	STRNE R2,[R0,#heap_listfree]
	MOVNE R0,R1
	MOVNE PC,R14
	; Check if top chunk has spaces left
	LDR R1,[R0,#heap_firstfree]
	LDR R2,[R0,#heap_chunksize]
	LDR R3,[R0,#heap_size]
	LDR R12,[R0,#heap_chunks]
	MUL R3,R1,R3 ; Either offset into chunk or size of chunk if chunk full
	ADD R3,R3,#chunk_data
	CMP R1,R2
	ADDLT R2,R1,#1 ; Yes, so return an item from it
	STRLT R2,[R0,#heap_firstfree]
	ADDLT R0,R3,R12
	MOVLT PC,R14
	; Else create new chunk
	STMFD R13!,{R0,R12,R14}
	MOV R0,R3
	BL malloc
	LDMFD R13!,{R1-R2,R14}
	CMP R0,#0
	; Fail? decrease alloced count
	LDREQ R3,[R1,#heap_alloced]
	SUBEQ R3,R3,#1
	STREQ R3,[R1,#heap_alloced]
	MOVEQ PC,R14
	STR R2,[R0,#chunk_next] ; Link new chunk into rest of list
	STR R0,[R1,#heap_chunks] ; Link list back into heap struct
	MOV R2,#1
	STR R2,[R1,#heap_firstfree] ; Reset firstfree count
	ADD R0,R0,#chunk_data ; Return ptr to 1st item
	MOV PC,R14

	FBEGIN cbma_free,1
	; r0=heap ptr, r1=item ptr
	CMP R0,#0
	CMPNE R1,#0
	LDRNE R2,[R0,#heap_listfree] ; Get current free list
	STRNE R2,[R1] ; Stick it on the end of the new item
	STRNE R1,[R0,#heap_listfree] ; Update list head
	LDRNE R3,[R0,#heap_alloced]
	SUBNE R3,R3,#1
	STRNE R3,[R0,#heap_alloced]
	MOV PC,R14

	FBEGIN cbma_alloced,1
	CMP R0,#0
	LDRNE R0,[R0,#heap_alloced]
	MOV PC,R14

	END

