% TAOCP Vol 1, Section 2.5, Exercise 27. MMIX version. 
% Algorithms R and S pg. 443, buddy system reservation and liberation.
% Complete runnable code for testing.
% Author  Ladislav Sladecek
% Please read README.


% Node and Avail[] structure
POINTERSIZE 	IS 	8 	
LINKF		IS	0
LINKB		IS	LINKF+POINTERSIZE
KVAL		IS	LINKB+POINTERSIZE


		PREFIX	:FindTag
:FindTag	LOC	@	
% This procedure finds the tag bit which corresponds to a given
% address p. 

					% leaf procedure
p IS $0					% input
ret_addr IS $0	% output - address of the byte containing  the tagbit
ret_mask IS $1	% output - mask of the tagbit
ret_data IS $2 	% output - MEM[ret_addr]
t IS :t					% globals
		SUB	t,p,:MEM0
		SRU	t,t,:MIN_K	% address to nodes
		AND	ret_mask,t,8-1
		SRU	t,t,3		% 2^3=8
		LDA	ret_addr,t,:TAGS0
		LDBU	ret_data,ret_addr,0
		SLU	ret_mask,:ONE,ret_mask
		POP	3,0		
		PREFIX	:


		PREFIX	:BuddyReserve

k IS $0					% input
p IS $1;q IS $2;j IS $3;l IS $4		% locals
return IS $0				% out
savedJ IS $5				% non-leaf procedure
para0 IS $6;para1 IS $7;para2 IS $8	% call registers
tag_addr IS para1;tag_mask IS para2;tag_data IS para0
t IS :t					% globals

:BuddyReserve	LOC	@
		GET	savedJ,:rJ
R1		SET	j,k		% Find block.
4H		CMP	t,j,:m
		PBNP	t,1F
		SET	l,:ZERO
		JMP	terminate
1H		16ADDU	q,j,:AVAIL0
		LDOU	l,q,:LINKF
		CMP	t,q,l
		BNZ	t,R2
		INCL	j,1
		JMP	4B
R2		LDOU	p,l,:LINKF	% Remove from list.
		STOU	p,q,:LINKF
		STOU	q,p,:LINKB
		SET	para1,l		% 0->TAG(p)
		PUSHJ	para0,:FindTag
		ANDN	tag_data,tag_data,tag_mask
		STBU	tag_data,tag_addr,0
R3		CMP	t,j,k		% Split required.
		PBZ	t,terminate
R4		SUB	j,j,1		% Split.
		SLU	t,:ONE,j
		LDA	p,l,t
		SET	para1,p
		PUSHJ	para0,:FindTag	% 1->TAG(p)
		OR	tag_data,tag_data,tag_mask
		STBU	tag_data,tag_addr,0
		STBU	j,p,:KVAL
		16ADDU	q,j,:AVAIL0
		STOU	q,p,:LINKF
		STOU	q,p,:LINKB
		STOU	p,q,:LINKF
		STOU	p,q,:LINKB
		JMP	R3
terminate	SET	return,l
		PUT	:rJ,savedJ
		POP	1,0
		PREFIX	:


		PREFIX	:BuddyLiberate
l IS $0;k IS $1				% input
p IS $2;q IS $3;lf IS $4;lb IS $5	% locals
savedJ IS $6				% non-leaf procedure
para0 IS $7;para1 IS $8;para2 IS $9	% call registers
tag_addr IS para1;tag_mask IS para2;tag_data IS para0
t IS :t					% globals

:BuddyLiberate	LOC	@
		GET	savedJ,:rJ
S1		SLU	t,:ONE,k	% Is buddy available?
		XOR	p,l,t
		CMP	t,k,:m
		BZ	t,S3
		SET	para1,p			
		PUSHJ	para0,:FindTag	% ?TAG(p)
		AND	t,tag_data,tag_mask
		PBZ	t,S3
		LDBU	t,p,:KVAL
		CMP	t,t,k
		BNZ	t,S3
S2		LDOU	lf,p,:LINKF	% Combine with buddy.
		LDOU	lb,p,:LINKB
		STOU	lf,lb,:LINKF		
		STOU	lb,lf,:LINKB
		INCL	k,1
		CMP	t,l,p
		PBN	t,S1
		SET	l,p
		JMP	S1
S3		SET	para1,l		% Put on list.	
		PUSHJ	para0,:FindTag	% 1->TAG(p)
		OR	tag_data,tag_data,tag_mask
		STBU	tag_data,tag_addr,0
		16ADDU	q,k,:AVAIL0	
		LDOU	p,q,:LINKF	
		STOU	p,l,:LINKF
		STOU	l,p,:LINKB
		STBU	k,l,:KVAL
		STOU	q,l,:LINKB
		STOU	l,q,:LINKF
		PUT	:rJ,savedJ
		POP	0,0		

		PREFIX	: