% Section 6.4, Algorithm D : Open Addressing with Double Hashing % Author Chan Vinh VONG % 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 :