% Section 6.4 Program C : Chained Hash Table Search and Insertion
% Author: Chan Vinh VONG <chanvinh.vong@gmail.com>
% Draft Version 2012 April 7th
%
% This is a proposal for the MMIX translation of Program C of Section
% 6.4 of TAoCP volume 3.
%
% All nodes have the following structure:
%
%       >|<-----OCTA----->|<
%        +----------------+
% (BA+0) |      LINK      |
%        +----------------+
% (BA+8) |      KEY       |
%        +----------------+
%
% With the LINK being possibly:
% - #0 : denoting the null address
% - #1 : meaning that the current node is an empty node
% - >= #8 : a valid absolute address
%
% Notes about the hash function.
%
% The section didn't specify clearly how the hashes for EN,TO,...,SYV
% were generated; the keys are even changed for Program D, plus page
% suggests that independant hash functions may have been used for each
% character. Moreover, be aware that the character codes were not ASCII
% in MIX (see last page of any volume).
%

dLINK   IS 8*0  % 0 for NULL, 1 for empty node
dKEY    IS 8*1
dNODE   IS 8*2

NULL_LINK  IS 0
EMPTY_NODE IS 1

        PREFIX CHTSI:  % for Chained Hash Table Search and Insertion
inKey   IS $0
hash    IS $1
tt      IS $2 % table cursor
link    IS $3
test    IS $4
key     IS $5 % key in table
r       IS $6
rr      IS $7 % empty node cursor
:CHTSI  DIV hash,inKey,:M            % C1. Hash
        GET hash,:rR
        ADD hash,hash,1
        
        16ADDU tt,hash,:TABLE
        LDOU link,tt,:dLINK        % C2. Is there a list?
        CMP  test,link,:EMPTY_NODE
        BZ   test,3F            % no, create here
        
1H      LDOU key,tt,:dKEY         % C3. Search key in the current chain
        CMP test,inKey,key
        BZ  test,9F             % key already exists => done
        
        BZ  link,6F               % end of chain reached => add key
        SET tt,link
        LDOU link,tt,:dLINK
        JMP 1B
        
6H      SUB r,:R,1                 % C4 find empty node for new key
        SET :R,r
        BZ r,8F  % no more node available => OVERFLOW
        16ADDU rr,r,:TABLE
        LDOU link,rr,:dLINK
        CMP test,link,:EMPTY_NODE
        BZ test,7F       % empty node => create key
        JMP 6B
        
7H      CMP test,tt,rr                       % wire
        BZ test,3F
        STOU rr,tt,:dLINK
        SET tt,rr
3H      STOU inKey,tt,:dKEY    % C6. insert new key
        STCO :NULL_LINK,tt,:dLINK
        JMP 9F
        
8H      LDA $255,:ERROR:OVERFLOW
        TRAP 0,:Fputs,:StdOut
9H      POP 0,0
        PREFIX :