Binary tree reorganization hashing: movement of entries


function SearchMove ( init, inc, level : integer ) : integer; {*** Find the first hole (empty location) at the given depth in the binary tree spanned by a key ***} label 999; var i, inc1, j, k : integer; begin i := (init + inc*level) mod m; if empty(r[i]) or deleted(r[i]) then SearchMove := i else begin for j:=level-1 downto 0 do begin i := (init + inc*j) mod m; inc1 := increment( r[i].k ); k := SearchMove( (i+inc1) mod m, inc1, level-j-1 ); if k>-1 then begin {*** A hole was found, move forward ***} r[k] := r[i]; SearchMove := i; goto 999 {*** return ***} end end; {*** Could not find hole ***} SearchMove := -1; end; 999: end;

Pascal source (3382.move.p)



© Addison-Wesley Publishing Co. Inc.