%%off
%	Reserved block:	 TETRA	Size,1, ... ,X,1
%	Free block:	 TETRA	Size,Right,Left,0 ... ,0,Size  
%	with Left, Right, and Size even. Size = the complete size in byte.

		PREFIX	:Allocate:
%%%		assuming we are in some sort of data/pool segment
%%on	
Base		GREG	@			Base address of allocated memory.
Avail		IS	0			Relative address of list head.
0H		TETRA	0,#18,#18,0    		List Head, uses \.{\#10} byte.
		OCTA	1			Mark as used (see Algorithm C).
		TETRA	Total-#20,Avail		\qquad First \.{OCTA} of free block
		TETRA	0,Avail			Second \.{OCTA} of free block.
		LOC	0B+Total-#10		Position of last \.{OCTA} of free block.
		OCTA	Total-#20		\qquad Last word of free block.
		OCTA	1			Mark as used (see Algorithm C).
Rover		GREG	Avail			Initialized with 0.			
%%off
n		IS	$0			Parameter: Number of Byte needed.

P 		IS	$1
f		IS	$2
Right		IS	$4
Left		IS	$5
Previous	IS	$6
k		IS	$7
t		IS	$8
L		IS	$9		Return value.
s		IS	$10
Q		IS	$11
c		IS	32		Minimum 24 (three \.{OCTA}).


%%%		we switch to the text segment assuming this is the first piece of code.
		LOC	#100
%%on
:Allocate	SET	P,Rover		\ul{\sl A.1 Initialize}
		SET	f,0
Size		IS	Base		Offsets to access \.{Size} field,
		ADDU	Right,Base,4	\qquad  \.{Right} field,
		ADDU	Left,Base,8	\qquad  \.{Left} field, 
		SUBU	Previous,Base,8	\qquad and the preceeding \.{OCTA}.
		ADD	n,n,16+7	Add overhead of two \.{OCTA} and 
		ANDN	n,n,7		round $n$ up to a multiple of 8.
		JMP	A2
%%%
A3		LDTU	s,Size,P	\ul{\sl A3. Is \.{Size} enough?}
		SUB	k,s,n		
		BNN	k,A4
		LDTU	P,Right,P
%%%
A2		BNZ	P,A3		\ul{\sl A2. End of list?}
		BNZ	f,8F		Overflow if $P=0$ and $f\ne 0$.
		LDTU	P,Right,Avail
		SET	f,1
		JMP	A2
%%%
A4		LDTU	Rover,Right,P	\ul{\sl A4. Reserve $n$.} Move \.{Rover} right of $P$.	
		CMP	t,k,c	
		BNN	t,1F		Jump if $k\ge c$.
%%%	Delete
		LDTU	Q,Left,P	Delete $P$ from list.
		STTU	Rover,Right,Q
		STTU	Q,Left,Rover
		SET	L,P		Result is $P$.
		SET	n,s		Size of Result is size of $P$.
		JMP	2F
%%%	Split
1H		ADDU	L,P,k		Split $P$ into $P$ and $L$.
		STTU	k,Size,P	$\.{Size}\is k$ in first
		STO	k,Previous,L	and last \.{OCTA} of $P$.
%%%
2H		STCO	1,Base,L	$\.{Tag}(L)\is 1$.
		STTU	n,Size,L	$\.{Size}(L)\is n$.
		ADDU	Q,L,n		Advance to block after $L$.
		STCO	1,Previous,Q	$\.{Tag}(L)\is 1$.
%%%
		ADDU	$0,Left,L	Usable memory starts here.
		POP	1,0
%%%
8H		SET	$0,0		Overflow. 
		POP	1,0
%%off	
		PREFIX	: