%%off % Author M. Ruckert % 6.4 Program L PREFIX :hash: H IS $0 Tabledefinitionblock: Table, M, Vacancies k IS $1 Key m IS $2 Local Variables i IS $3 T IS $4 ki IS $5 t IS $6 c IS $7 q IS $8 rR IS :rR TABLE IS 0 M IS 8 V IS 16 %%on Start LDO m,H,M \hfil$1$& $m\is H_M$ LDOU T,H,TABLE \hfil$1$& $T_k\is H_T$ DIV q,k,m \hfil$60$& {\ul{\sl D1. First Hash.}} GET i,rR \hfil$1$& $i\is k \mod m$ SL i,i,3 \hfil$1$& $i\is 8i$ LDO ki,T,i \hfil$1$& {\ul{\sl D2. First probe.}} CMP t,ki,k \hfil$1$& $k_i=k$? PBZ t,Found \hfil$3-2S1$&Exit if $k_i=k$. PBZ ki,4F \hfil$1-3S1+2A$&To D6 if $T_i$ empty. SUB t,m,2 \hfil$A-S1$& {\ul{\sl D3. Second Hash.}} DIV t,k,t \hfil$60(A-S1)$& %%% except for test case 10, dividing k is better than dividing q (as in Knuths program D) GET c,rR \hfil$A-S1$& $c\is k \mod (m-2)$ 8ADDU c,c,8 \hfil$A-S1$& $c\is 8(1+(k \mod (m-2)))$ 4H SUB i,i,c \hfil$C-1$& {\ul{\sl D4. Advance to next.}} 8ADDU t,m,i \hfil$C-1$& $t\is i+8m$. CSN i,i,t \hfil$C-1$& if $i<0$, then $i\is i+8m$. LDO ki,T,i \hfil$C-1$& {\ul{\sl D5. Compare.}} CMP t,ki,k \hfil$C-1$& $k_i=k$? PBZ t,Found \hfil$3(C-1)-2S2$&Exit if $k_i=k$. BNZ ki,4B \hfil$3C-S2-5$&To D4 if $T_i$ nonempty. %%% 3(C-1-S2)-2(1-S2)=3C-5-S2 %%% 6H LDO t,H,V \hfil$1-S$&{\ul{\sl D6. Insert.}} $t\is H_V$. BZ t,Fail \hfil$1-S$& Overflow if $N=M-1$. SUB t,t,1 \hfil$1-S$& STO t,H,V \hfil$1-S$& Increase $N$ by 1. STO k,T,i \hfil$1-S$& Store key. POP 0,0 %%% Found ADDU $0,T,i \hfil$S$& POP 1,0 Fail NEG $0,1 \hfil$0$& POP 1,0 %%off PREFIX :