*
* 高速malloc/realloc/free
*  OH!X 1994/03 p106-109より
*   Ｃの関数として使えるように少し変更＋デバッグ
*     どれ位速いのかといえば、newmallocの実に１３倍！！
*
*  calloc()だけはアセンブラーでは記述しにくいのでＣで作る。
*
*  確保されたメモリーブロックはnewmallocと同じように扱えるが、
*    メモリーの確保方法そのものは異なるので、標準のfreeでは解放しないこと。
*
*  このメモリー確保ではmain()内にあるヒープのポインターを使わないので、
*    main3()/main4()でもメモリー確保が出来るようになる・・・はずである。
*
*  各関数は、Ｃだけでなくアセンブラーからも使いやすいように、d0.lレジスター以外は
*    破壊しない。引数の受け渡しはスタック渡しだけど。
*
	.include	doscall.mac

	.xdef	_FASTmalloc
	.xdef	_FASTrealloc
	.xdef	_FASTfree

HEAPSIZE	equ	1024*64		* 初期 HEAP SIZE
NALLOC		equ	1024*4		* HEAP SIZE 増分

*
* メモリーブロックヘッダー構造
*
	.offset	0
MSIZE:		.ds.l	1		* ヘッダーを含むバイト数（負なら使用中）
MNEXT:		.ds.l	1		* 次のメモリーブロック
MPREV:		.ds.l	1		* 前のメモリーブロック
		.ds.l	1		* 未使用
SIZEofMHEADER:
MCONTENTS:				* メモリーブロック本体先頭

*
* 関数引数構造
*
		.offset	4		* FASTmallocの引数
SIZE:		.ds.l	1		* 確保するバイト数

		.offset	4		* FASTfreeの引数
MEMPTR:		.ds.l	1		* 解放するメモリーブロックアドレス

		.offset	4		* FASTreallocの引数
OLDMEMPTR:	.ds.l	1		* 元のメモリーブロックアドレス
NEWSIZE:	.ds.l	1		* 新しいサイズ

*
* 関数本体
*
	.text
	.even
*
allocptr:	.ds.l	1		* 次回の検索位置
heaphead:	.ds.l	1		* ヒープ先頭
heaptail:	.ds.l	1		* ヒープ末尾

HEAD	equ	heaphead-allocptr
TAIL	equ	heaptail-allocptr
*
* void *FASTmalloc(size_t size)
* 指定サイズのメモリーブロックを確保する
*
_FASTmalloc:
	movem.l	d1/a0-a2,-(sp)
	moveq.l	#SIZEofMHEADER*2-1,d1
	add.l	SIZE+(1+3)*4(sp),d1
	bcs	error
	andi.b	#-SIZEofMHEADER,d1
	lea.l	allocptr(pc),a2
	movea.l	(a2),a0
	move.l	a0,d0
	bne	allocnext
newheap:	* ヒープを初期化する
	move.l	#HEAPSIZE,-(sp)
	DOS	_MALLOC
	move.l	(sp)+,a1
	move.l	d0,HEAD(a2)
	bmi	error
	movea.l	d0,a0
	move.l	a1,(a0)+
	move.l	d0,(a0)+
	move.l	d0,(a0)+
	movea.l	d0,a0
	adda.l	a0,a1
	move.l	a1,TAIL(a2)
	bra	allocnext

expandheap:	* ヒープを拡大する
	move.l	d1,a1
	addi.l	#NALLOC-1,d1
	andi.l	#-NALLOC,d1
	movem.l	HEAD(a2),d0/a0
	add.l	d1,a0
	sub.l	d0,a0
	movem.l	d0/a0,-(sp)
	movea.l	d0,a0
	DOS	_SETBLOCK
	addq.w	#8,sp
	tst.l	d0
	bmi	error
	add.l	d1,TAIL(a2)
	move.l	d1,d0
	move.l	a1,d1
	movea.l	MPREV(a0),a0
	tst.l	(a0)
	bmi	addnode
	add.l	d0,(a0)
	bra	allocnext

addnode:
	move.l	(a0),d0
	movea.l	a0,a1
	suba.l	d0,a0
	move.l	a0,MNEXT(a1)
	move.l	a1,MPREV(a0)
	movea.l	HEAD(a2),a1
	move.l	a1,MNEXT(a0)
	move.l	a0,MPREV(a1)
	movea.l	TAIL(a2),a1
	suba.l	a0,a1
	move.l	a1,(a0)
	bra	allocnext

allocloop:
	movea.l	(a0),a0
	cmpa.l	d0,a0
	beq	expandheap
allocnext:
	cmp.l	(a0)+,d1
	bgt	allocloop
	beq	justfit
	move.l	-(a0),d0
	sub.l	d1,d0
	lea.l	(a0,d1.l),a1
	move.l	a1,(a2)
	neg.l	d1
	move.l	d1,(a0)
	movea.l	MNEXT(a0),a2
	move.l	a1,MPREV(a2)
	move.l	a1,MNEXT(a0)
	move.l	d0,(a1)+
	move.l	a2,(a1)+
	move.l	a0,(a1)+
mallocdone:
	lea.l	MCONTENTS(a0),a0
	move.l	a0,d0			* d0=アドレス
mallocretn:
	movem.l	(sp)+,d1/a0-a2
	rts
*
justfit:
	move.l	(a0),(a2)
	neg.l	-(a0)
	bra	mallocdone
*
error:
	moveq.l	#0,d0			* d0=0=NULL
	bra	mallocretn
*
* void *FASTrealloc(void *oldptr,size_t size)
* メモリーブロックを指定サイズにて再割り当てする
*
_FASTrealloc:
	movem.l	d1/a0-a2,-(sp)
	movem.l	OLDMEMPTR+(1+3)*4(sp),a0/a1
	move.l	a0,d0			* 引数が0=NULLならnewmalloc()と全く同じ
	beq	new
	moveq.l	#SIZEofMHEADER*2-1,d1
	add.l	a1,d1
	bcs	error
	andi.b	#-SIZEofMHEADER,d1
	lea.l	-SIZEofMHEADER(a0),a0
	move.l	(a0),d0
	bpl	error
	movea.l	a0,a1
	suba.l	d0,a1
	movea.l	MNEXT(a0),a2
	add.l	d1,d0
	bhi	shrink
	beq	reallocdone
expand:		* 拡大する
	cmp.l	(a2),d0
	bgt	expand2
	neg.l	d0
	cmpa.l	a2,a1
	beq	cat
expand2:
	lea.l	MCONTENTS(a0),a1
	moveq.l	#SIZEofMHEADER,d0
	sub.l	d0,d1
	move.l	d1,-(sp)
	bsr	_FASTmalloc	* 新ブロック確保
	addq.w	#4,sp
	tst.l	d0
	beq	reallocretn	* error
	move.l	a1,-(sp)
	bsr	_FASTfree	* 旧ブロック解放
	addq.w	#4,sp		*（ポインター的に解放するだけで、内容は残っている）
	*
	* 旧ブロックの内容を新ブロックにコピーする
	movea.l	a0,a2
	lsr.l	#2,d1
	bra	copynext
copylooph:
	swap	d1
copyloopl:
	move.l	(a1)+,(a2)+
copynext:
	dbra	d1,copyloopl
	swap	d1
	dbra	d1,copylooph
	move.l	a0,d0
	bra	reallocretn

shrink:		* 縮小する
	neg.l	d0
	tst.l	(a2)
	bmi	split
	cmpa.l	a1,a2
	bne	split
cat:
	add.l	(a2),d0
	movea.l	MNEXT(a2),a2
	bne	split
	neg.l	d1
	move.l	d1,(a0)
	move.l	a2,MNEXT(a0)
	move.l	a0,MPREV(a2)
	move.l	a2,allocptr
	bra	reallocdone

split:		* 分割する
	lea.l	(a0,d1.l),a1
	neg.l	d1
	move.l	d1,(a0)
	move.l	a1,MNEXT(a0)
	move.l	a1,MPREV(a2)
	move.l	a1,allocptr
	move.l	d0,(a1)+
	move.l	a2,(a1)+
	move.l	a0,(a1)+
reallocdone:
	lea.l	MCONTENTS(a0),a0	* 新アドレス
	move.l	a0,d0
reallocretn:
	movem.l	(sp)+,d1/a0-a2
	rts
*
new:	* 実は新規確保であった
	move.l	a1,-(sp)
	bsr	_FASTmalloc
	addq.w	#4,sp
	bra	reallocretn

*
* void FASTfree(void *memptr)
* FASTmalloc()/FASTrealloc()/FASTcalloc()で確保したメモリーブロックを解放する
*
_FASTfree:
	movem.l	d1/a0-a2,-(sp)
	move.l	MEMPTR+(1+3)*4(sp),d0
	beq	freeretn
	movea.l	d0,a0
	lea.l	-SIZEofMHEADER(a0),a0
	move.l	(a0),d0
	neg.l	d0
	lea.l	allocptr(pc),a2
chknext:
	movea.l	MNEXT(a0),a1
	move.l	(a1),d1
	bmi	chkprev
	adda.l	d0,a0
	cmpa.l	a0,a1
	suba.l	d0,a0
	bne	chkprev
	cmpa.l	(a2),a1
	bne	catnext
	move.l	a0,(a2)
catnext:
	add.l	d1,d0
	movea.l	MNEXT(a1),a1
	move.l	a1,MNEXT(a0)
	move.l	a0,MPREV(a1)
chkprev:
	movea.l	MPREV(a0),a1
	move.l	(a1),d1
	bmi	freedone
	adda.l	d1,a1
	cmpa.l	a1,a0
	bne	freedone
	suba.l	d1,a1
	cmpa.l	(a2),a0
	bne	catprev
	move.l	a1,(a2)
catprev:
	add.l	d1,d0
	movea.l	MNEXT(a0),a0
	move.l	a0,MNEXT(a1)
	move.l	a1,MPREV(a0)
	movea.l	a1,a0
freedone:
	move.l	d0,(a0)
freeretn:
	movem.l	(sp)+,d1/a0-a2
	rts
*
	.end
