% Section 6.4, Algorithm L : Linear Probing and Insertion
% Author Chan Vinh VONG <chanvinh.vong@gmail.com>
% Draft Version 2012 April 8th
%
% [1st hit]
%   +-> found, A
%   +-> not found
%       [search consecutive sectors]
%         +-> found, S
%         +-> not found
%             [insert]
%               +-> OVERFLOW
%               +-> done
%
% Table structure:
%
%  >|<-----OCTA----->|<
%   +----------------+
%   |      NULL      | (TABLE-8) loop back marker for cyclic probing
%   +----------------+
%   |      slot      | (TABLE+0) TABLE[0]
%   +----------------+
%   |      ...       | ...
%   +----------------+
%   |      slot      | (TABLE+M*8) TABLE[M]
%   +----------------+
%   |   M - 1 - N    | (TABLE+(M+1)*8) VACANCIES
%   +----------------+
%
% Reminder:
% - the problem is to find the key ASAP, i.e the priority is NOT about
%   inserting the key; this obviously excludes checking vacancies first
% - there are two kinds of null markers (empty slots):
%   - at TABLE[-1] which indicates that the cursor should loop back
%   - any empty slot which indicates that search is done (because the
%     key can only be in an non-empty slot consecutively starting from
%     the 1st hit entry point); this excludes filling all the table, as
%     indicated in exercise 15, we must leave one such marker in the
%     table
%
%


% 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
:LPI    DIV   x,key,:M      % L1. hash
        GET   x,:rR         % h(k)
        SLU   i,x,3         % fine as long as M <= 2^61
        JMP 2F
8H      SLU   i,:M,3        % L3. advance
3H      SUB   i,i,8
2H      LDOU  x,i,:TABLE    % L2. compare
        CMP   t,x,key
        BZ    t,SUCCESS     % key found!
        BNZ   x,3B          % slot not empty, move to next
        BN    i,8B          % slot empty but i<0, loop back
        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 :