%%off
%	Author M. Ruckert
%	6.4 Program C using relative Links = Offsets and Keys in TETRAs
%	neagtive link = empty, odd Link = end of chain R is offset
%	this version is closer to Don Knuths version testing key and link
%       once before entering the loop. The gains are two instructions
%	(2oops+1mem) in the first iteration of the loop, (if
%	the first probe was not empty and contained the wrong key)
%	adding four lines of code.

	PREFIX	:hash:
H	IS	$0	Tabledefinitionblock: Data, Modul, Free
k	IS	$1	Key

m	IS	$2	Local Variables
i	IS	$3
Tk	IS	$4
Tl	IS	$5	
t	IS	$6
ip	IS	$7


rR	IS	:rR

TABLE	IS	0
M	IS	8
R	IS	16

%%on
Start	LDO	m,H,M		\hfil$1$& $m\is H_M$
	LDOU	Tk,H,TABLE	\hfil$1$& $T_k\is H_T$
	ADDU	Tl,Tk,4		\hfil$1$& $T_l\is H_T+4$
	DIV	t,k,m		\hfil$60$& {\ul{\sl C1. Hash.}}
	GET	ip,rR		\hfil$1$& $i\is k \mod m$
	SL	ip,ip,3		\hfil$1$& $i\is 8i$
	LDT	i,Tl,ip		\hfil$1$&{\ul{\sl C2. Is there a list?}}	
        BN	i,6F		\hfil$3-2A$& If empty goto C6.
%%%
	LDT	t,Tk,ip		\hfil$A$& $t\is \.{KEY}[i]$
	CMP	t,t,k		\hfil$A$&{\ul{\sl C3. Compare.}}
	PBZ	t,Found		\hfil$3A-2S1$&
	BOD	i,5F		\hfil$A-S1$&
%%%
3H	SET	ip,i		\hfil$C-S$&{\ul{\sl C4. Advance to next.}}
	LDT	t,Tk,ip		\hfil$C$& $t\is \.{KEY}[i]$
	CMP	t,t,k		\hfil$C$&{\ul{\sl C3. Compare.}}
	PBZ	t,Found		\hfil$3C-2S$&
	LDT	i,Tl,ip		\hfil$C-S$&$i\is \.{LINK}[i^\prime]$		
	BEV	i,3B		\hfil$3C-2A-S$&
%%%
5H	LDO	i,H,R		\hfil$A-S$& {\ul{\sl C5. Find empty node.}} $i\is H_R$
0H	SUB	i,i,8		\hfil$T$& Decrease $i$.
	BN	i,Fail		\hfil$T$&
	LDT	t,Tl,i		\hfil$T$&$t\is \.{LINK}[i]$
	BNN	t,0B		\hfil$3T-2(A-S)$& Repeat if $T$ non empty.
	STO	i,H,R		\hfil$A-S$&$H_R\is i$
	STT	i,Tl,ip		\hfil$A-S$&$\.{LINK}[i^\prime]\is i$
	SET	ip,i
%%%
6H	SET	t,1		\hfil$1-S$&{\ul{\sl C6. Insert new key.}} 
	STT	t,Tl,ip		\hfil$1-S$& Make link odd (non empty).
	STT	k,Tk,ip		\hfil$1-S$& Store key.
	POP	0,0
%%%
Found	ADDU	$0,Tk,ip	\hfil$S$&
	POP	1,0
Fail	NEG	$0,1		\hfil$0$&
	POP	1,0
%%off


Init	LDO	m,H,M	
	SL	m,m,3
	STO	m,H,R
	LDO	Tk,H,TABLE
	ADDU	Tl,Tk,4
	NEG	t,1
1H	SUB	m,m,8
	STT	t,Tl,m
	BP	m,1B
	POP	0,0

	PREFIX :