% Section 6.4, Algorithm D : Open Addressing with Double Hashing
% Author Chan Vinh VONG <chanvinh.vong@gmail.com>
% Draft Version 2012 April 8th
%
% [1st hit]
%   +-> found, A
%   +-> not found
%       [compute coprime-hash]
%       [search consecutive sectors]
%         +-> found, S
%         +-> not found
%             [insert]
%               +-> OVERFLOW
%               +-> done
%
% Table structure: same as for S64PL-LPI, minus the TABLE[-1] marker
% which can't be used here because using the coprime makes possible
% jumps to far lower than TABLE[-1].
%
% Reminder:
% - same as for S64PL-LPI
% - using coprime hash allows a more evenly scan of the table w/o
%   encountering infinite loops
%
%   M=5, coprime-hash=2
%
%       [ | | | | ]
%       [ | | | |X]1st hit
%       [ | |X| | ]
%       [X| | | | ]
%    X|-[ | | | | ]
%     ========> loop back + M
%       [ | | |X| ]
%       [ |X| | | ]
%
%   at least one slot is kept empty, thus the algorithm terminates.
%

% Calling Sequence:
%     $1 <- key to be searched (long keys would be in memory but that
%           is not the purpose here)
%     PUSHJ $0,LPI
%
% Global Registers:
% :TABLE is the base address of the hash table
% :VACANCIES is the address of the vacancies
% :M is the hash-modulo value
%
% Exit Conditions:
%     returns 0 on SUCCESS, else 1
%
        PREFIX LPI:
key     IS $0
x       IS $1
i       IS $2
t       IS $3
h2      IS $4
:LPI    DIV   h2,key,:M      % L1. hash
        GET   x,:rR         % h(k)
        SLU   i,x,3         % fine as long as M <= 2^61
        LDOU  x,i,:TABLE    % L2. compare
        CMP   t,x,key
        BZ    t,SUCCESS     % key found!
        BZ    x,4F          % slot is empty, insert
        SUB   x,:M,2        % h2(K) = 1 + [K/M] mod (M-2)
        DIV   x,h2,x
        GET   h2,:rR
        ADD   h2,h2,1
        SLU   h2,h2,3      
3H      SUB   i,i,h2
        BNN   i,8F          % i<0 => i <- i + M
        8ADDU x,:M,0
        ADD   i,x,i 
8H      LDOU  x,i,:TABLE    % L2. compare
        CMP   t,x,key
        BZ    t,SUCCESS     % key found!
        BNZ   x,3B          % slot not empty, move to next        
4H      LDOU  x,:VACANCIES  % L4. insert
        BZ    x,OVFL
        SUB   x,x,1
        STOU  x,:VACANCIES
        STOU  key,i,:TABLE
        JMP SUCCESS      
OVFL    SET $0,1
        POP 0,0
SUCCESS SET $0,0
        POP 0,0
        
        PREFIX :