[fpc-devel] crash with TCuckooD2<string, string>

[Martin Frb]

is TCuckooD2<string, string> allowed?

See the code below. It's brute force testing some of the dictionaries.

Testing with 2.2.3 and 3.3.1 (both from early this year) I get a crash for
    TCuckooD2<string, string>
   (not tested any of those that follow later in the list).

The crash happens after "Run2" did
   Dict.clear;

when it attempts to add a new element.





program test_dict;
{$mode objfpc}{$H+}

uses Generics.Collections, SysUtils;

generic procedure Run<T>;
var
   Dict: T;
   i: Integer;
   GotExcept: Boolean;

   procedure Add(ATestVal: integer);
   begin
     Dict.Add(IntToStr(ATestVal), 'Val'+IntToStr(ATestVal));
   end;
   function TryAdd(ATestVal: integer): boolean;
   begin
     result := Dict.TryAdd(IntToStr(ATestVal), 'Val'+IntToStr(ATestVal));
   end;
   procedure Del(ATestVal: integer);
   begin
     Dict.Remove(IntToStr(ATestVal));
   end;
   procedure Check(ATestVal: integer);
   var
     ValGotten: string;
   begin
     if not Dict.ContainsKey(IntToStr(ATestVal)) then
       raise Exception.Create('missing key');
     if Dict[IntToStr(ATestVal)] <> 'Val'+IntToStr(ATestVal) then
       raise Exception.Create('wrong value');
     if not Dict.TryGetValue(IntToStr(ATestVal), ValGotten) then
       raise Exception.Create('TryGetValue failed');
     if ValGotten <> 'Val'+IntToStr(ATestVal) then
       raise Exception.Create('wrong tried value');
   end;
   procedure CheckNot(ATestVal: integer);
   var
     ValGotten: string;
   begin
     if  Dict.ContainsKey(IntToStr(ATestVal)) then
       raise Exception.Create('unexpected key');
     if Dict.TryGetValue(IntToStr(ATestVal), ValGotten) then
       raise Exception.Create('TryGetValue unexpected');
   end;
   procedure CheckCount(AnExp: integer);
   begin
     if not Dict.Count = AnExp then
       raise Exception.Create('wrong count');
   end;

begin
   RandSeed := 1; // make the test reproducible

   Dict := T.Create;

   CheckNot(0);
   CheckNot(1);
   CheckCount(0);

   Add(-999);
   Check(-999);
   CheckNot(0);
   CheckNot(1);
   CheckCount(1);

   Del(-999);
   CheckNot(-999);
   CheckNot(0);
   CheckNot(1);
   CheckCount(0);

   // re-add
   Add(-999);
   Check(-999);
   CheckNot(0);
   CheckNot(1);
   CheckCount(1);

   if not TryAdd(-998) then raise Exception.Create('try add failed');
   Check(-998);
   Check(-999);
   CheckCount(2);
   if TryAdd(-999) then raise Exception.Create('try add unexpected');
   if TryAdd(-998) then raise Exception.Create('try add unexpected');
   Check(-998);
   Check(-999);
   CheckCount(2);


   for i :=   0 to  99 do Add(i);
   for i :=   0 to  99 do Check(i);
   for i := 100 to 199 do CheckNot(i);
   for i := -99 to  -1 do CheckNot(i);
   CheckCount(102);
   Del(99);
   CheckCount(101);

   for i := 200 to 999 do Add(i);
   for i := 200 to 999 do Check(i);
   for i :=   0 to  98 do Check(i);
   for i :=  99 to 199 do CheckNot(i);
   for i := -99 to  -1 do CheckNot(i);

   for i :=1000 to 9999 do Add(i);
   for i := 200 to 9999 do Check(i);
   for i :=   0 to  98 do Check(i);
   for i :=  99 to 199 do CheckNot(i);
   for i := -99 to  -1 do CheckNot(i);

   Dict.TrimExcess;

   for i := 200 to 9999 do Check(i);
   for i :=   0 to  98 do Check(i);
   for i :=  99 to 199 do CheckNot(i);
   for i := -99 to  -1 do CheckNot(i);

   Dict.Clear;
   CheckCount(101);
   for i :=   0 to  999 do CheckNot(i);


   GotExcept := False;
   Add(-999);
   try
     Add(-999);
   except
     GotExcept := True;
   end;
   if not GotExcept then
     raise exception.Create('did not reject dup');
   Check(-999);
   CheckNot(0);
   CheckNot(1);
   CheckCount(1);

   Dict.AddOrSetValue('998', 'B');
   if Dict['998'] <> 'B' then
     raise Exception.Create('TryOrSet failed');
   Check(-999);
   CheckCount(2);

   Dict.AddOrSetValue('999', 'A');
   if Dict['999'] <> 'A' then
     raise Exception.Create('TryOrSet failed');
   if Dict['998'] <> 'B' then
     raise Exception.Create('TryOrSet failed');
   CheckCount(2);

   Dict.Destroy;
end;


generic procedure Run2<T>;
var
   Dict: T;
   i: Integer;
   GotExcept: Boolean;

   procedure Add(ATestVal: integer);
   begin
     Dict.Add(IntToStr(ATestVal), 'Val'+IntToStr(ATestVal));
   end;
   procedure Del(ATestVal: integer);
   begin
     Dict.Remove(IntToStr(ATestVal));
   end;
   procedure Check(ATestVal: integer);
   var
     ValGotten: string;
   begin
     if not Dict.ContainsKey(IntToStr(ATestVal)) then
       raise Exception.Create('missing key');
     if Dict[IntToStr(ATestVal)] <> 'Val'+IntToStr(ATestVal) then
       raise Exception.Create('wrong value');
     if not Dict.TryGetValue(IntToStr(ATestVal), ValGotten) then
       raise Exception.Create('TryGetValue failed');
     if ValGotten <> 'Val'+IntToStr(ATestVal) then
       raise Exception.Create('wrong tried value');
   end;
   procedure CheckNot(ATestVal: integer);
   var
     ValGotten: string;
   begin
     if  Dict.ContainsKey(IntToStr(ATestVal)) then
       raise Exception.Create('unexpected key');
     if Dict.TryGetValue(IntToStr(ATestVal), ValGotten) then
       raise Exception.Create('TryGetValue unexpected');
   end;
   procedure CheckCount(AnExp: integer);
   begin
     if not Dict.Count = AnExp then
       raise Exception.Create('wrong count');
   end;

begin
   RandSeed := 1; // make the test reproducible

   Dict := T.Create;

   CheckNot(0);
   CheckNot(1);
   CheckCount(0);

   Add(-999);
   Check(-999);
   CheckNot(0);
   CheckNot(1);
   CheckCount(1);

   Del(-999);
   CheckNot(-999);
   CheckNot(0);
   CheckNot(1);
   CheckCount(0);

   // re-add
   Add(-999);
   Check(-999);
   CheckNot(0);
   CheckNot(1);
   CheckCount(1);

   Add(-998); // TryAdd not avail
   Check(-998);
   Check(-999);
   CheckCount(2);


   for i :=   0 to  99 do Add(i);
   for i :=   0 to  99 do Check(i);
   for i := 100 to 199 do CheckNot(i);
   for i := -99 to  -1 do CheckNot(i);
   CheckCount(102);
   Del(99);
   CheckCount(101);

   for i := 200 to 999 do Add(i);
   for i := 200 to 999 do Check(i);
   for i :=   0 to  98 do Check(i);
   for i :=  99 to 199 do CheckNot(i);
   for i := -99 to  -1 do CheckNot(i);

   for i :=1000 to 9999 do Add(i);
   for i := 200 to 9999 do Check(i);
   for i :=   0 to  98 do Check(i);
   for i :=  99 to 199 do CheckNot(i);
   for i := -99 to  -1 do CheckNot(i);

   Dict.TrimExcess;

   for i := 200 to 9999 do Check(i);
   for i :=   0 to  98 do Check(i);
   for i :=  99 to 199 do CheckNot(i);
   for i := -99 to  -1 do CheckNot(i);

   Dict.Clear;
   CheckCount(101);
   for i :=   0 to  999 do CheckNot(i);

   GotExcept := False;
//exit; // //////////////////////////////// NEXT LINE CRASH
   Add(-999);  // fails for TCuckooD2
   try
     Add(-999);
   except
     GotExcept := True;
   end;
   if not GotExcept then
     raise exception.Create('did not reject dup');
   Check(-999);
   CheckNot(0);
   CheckNot(1);
   CheckCount(1);

   Dict.AddOrSetValue('998', 'B');
   if Dict['998'] <> 'B' then
     raise Exception.Create('TryOrSet failed');
   Check(-999);
   CheckCount(2);

   Dict.AddOrSetValue('999', 'A');
   if Dict['999'] <> 'A' then
     raise Exception.Create('TryOrSet failed');
   if Dict['998'] <> 'B' then
     raise Exception.Create('TryOrSet failed');
   CheckCount(2);

   Dict.Destroy;
end;



begin
   specialize Run<specialize TDictionary<string, string> >();
   specialize Run<specialize TObjectOpenAddressingLP<string, string> >();
   specialize Run<specialize TOpenAddressingLPT<string, string> >();
   specialize Run<specialize TOpenAddressingQP<string, string> >();
   specialize Run<specialize TOpenAddressingDH<string, string> >();
   specialize Run2<specialize TCuckooD2<string, string> >();
   specialize Run2<specialize TCuckooD4<string, string> >();
   specialize Run2<specialize TCuckooD6<string, string> >();
   specialize Run2<specialize TFastHashMap<string, string> >();
   specialize Run2<specialize THashMap<string, string> >();

end.