[Home]
[Chapter]
[Contents]
[Previous Algorithm]
[Next Algorithm]


Brent's reorganization scheme: insertion


procedure insert( key : typekey; var r : dataarray ); label 999; var i, ii, inc, init, j, jj : integer; begin init := hashfunction( key ); inc := increment( key ); for i:=0 to n do for j:=i downto 0 do begin jj := (init + inc*j) mod m; ii := (jj + increment(r[jj].k) * (i-j)) mod m; if empty(r[ii]) or deleted(r[ii]) then begin {*** move record forward ***} r[ii] := r[jj]; {*** insert new in r[jj] ***} r[jj].k := key; n := n+1; goto 999 {*** return ***} end end; Error {*** table full ***}; 999: end;

C source (3381.ins.c) Pascal source (3381.ins.p)



© Addison-Wesley Publishing Co. Inc.