|
<![CDATA[
procedure insert( key : typekey; var r : dataarray );
var i, inc, init, j : integer;
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;
begin
init := hashfunction( key );
inc := increment( key );
i := 0; j := -1;
while (i<=n) and (j<0) and (n<m) do begin
j := SearchMove( init, inc, i );
i := i+1
end;
if j>-1 then begin
{*** A hole was found, insert key ***}
r[j].k := key;
n := n+1
end
else Error {*** table is full ***};
end;
]]> |
Pascal source (3382.ins.p) 