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;