View Issue Details

IDProjectCategoryView StatusLast Update
0014551LazarusFCLpublic2011-12-01 11:22
ReporterMattias HanssonAssigned ToPaul Ishenin 
PrioritynormalSeveritymajorReproducibilityalways
Status closedResolutionfixed 
PlatformIntelOSWindowsOS VersionXP
Product VersionProduct Build 
Target Version0.9.30Fixed in Version0.9.29 (SVN) 
Summary0014551: Bug in TStringHashList.find()
DescriptionWhen the hashvalue of a string is not unique so that the find method goes to its second phase where it tries to match the correct string from several and these hashvalues are at the end of the hashlist, it can't find the string, even if it is there!

Look at my reproduction example, how the TStringHashList.Remove() call fails precisely by this effect. (Fails in the notion that it does not remove the string it's asked to remove).

Steps To Reproduceprocedure showStringHashListProblem;
//Must add this to compiler path: "$(LazarusDir)\lcl\units\$(TargetCPU)-$(TargetOS)\"
const
  ARR_COUNT = 10;
  STRARR: array[0..ARR_COUNT-1] of string =
  (
  'MoveDist: 1534',
  'getTileYForScreenY(): 9',
  'getTileXForScreenX(): 17',
  'fps: 59|line break|demo',
  'getBottomTileYonScreen(): 49',
  'getTopTileYonScreen(): 35',
  'Screen center!|Several lines|Game Over!',
  'getLeftMostTileXonScreen(): -1',
  'getRightMostTileXonScreen(): 19',
  'getRightMostTileXonScreen(): 38'
  );
var
  hl: TStringHashList;
  i: integer;
  removeResult: integer;
begin
  hl := TStringHashList.Create(false);

  for i := ARR_COUNT-1 downto 0 do
    hl.add(STRARR[i]);

  writeln('Count: ' + IntToStr(hl.Count));

  removeResult := hl.Remove(STRARR[ARR_COUNT-1]);

  if removeResult = -1 then
    Writeln('Huh? Cannot remove "' + STRARR[ARR_COUNT-1] + '"? It''s right there!');

  writeln('Count: ' + IntToStr(hl.Count));

  hl.free;
  readln;
end;
Additional InformationHere is my suggested fix of TStringHashList.find():
Note: The old code is still there, but commented. (for removal)

function TStringHashList.Find(const S: String): Integer;
var
  Value: Cardinal;
  First, Last, Temp, I: Integer;
begin
  Value:= HashOf(s);
  Result:= -1;
  First:= 0;
  Last:= Count -1;
  while First <= Last do
  begin
    Temp:= (First + Last) div 2;
    case CompareValue(Value, FList[Temp]^.HashValue) of
     1: First:= Temp + 1;
     0:
       begin
         Result:= Temp;
         if CompareString(S, FList[Temp]^.Key) then
           exit
         else
           break;
       end;
     -1: Last:= Temp-1;
    end;
    end;
  if Result <> -1 then
  begin
    Result:= -1;
    First:= Temp -1;
    //Serious bug here!
    {if First > 0 then
    while CompareValue(Value, FList[First]^.HashValue) = 0 do
      dec(First);
    inc(First);
    }
    //Find first matching hash index. My take:
    while (First >= 0) and (CompareValue(Value, FList[First]^.HashValue) = 0) do
      dec(First);
    if (First < 0) or ((CompareValue(Value, FList[First]^.HashValue) <> 0)) then
      inc(First);
    {end of my mod}


    Last:= Temp +1;
    //Serious bug here!
    {
    if Last < Count -1 then
    while CompareValue(Value, FList[Last]^.HashValue) = 0 do
      inc(Last);
    dec(Last);
    }
    //Find last matching hash index. My take:
    while (Last <= (FCount-1)) and (CompareValue(Value, FList[Last]^.HashValue) = 0) do
      inc(Last);
    if (Last > (FCount-1)) or (CompareValue(Value, FList[Last]^.HashValue) <> 0) then
      dec(Last);
    {end of my mod}
    for I:= First to Last do
      if CompareString(S, FList[I]^.Key) then
      begin
        Result:= I;
        Exit;
      end;
  end;
end;


TagsNo tags attached.
Fixed in Revision23061
LazTarget0.9.30
Widgetset
Attached Files

Activities

Paul Ishenin

2009-12-10 09:36

manager   ~0032888

Thanks, applied.

Issue History

Date Modified Username Field Change
2009-09-09 20:28 Mattias Hansson New Issue
2009-09-09 21:23 Marco van de Voort Project FPC => Lazarus
2009-09-09 21:35 Vincent Snijders LazTarget => 0.9.30
2009-09-09 21:35 Vincent Snijders Status new => acknowledged
2009-09-09 21:35 Vincent Snijders Target Version => 0.9.30
2009-12-10 09:36 Paul Ishenin Fixed in Revision => 23061
2009-12-10 09:36 Paul Ishenin Status acknowledged => resolved
2009-12-10 09:36 Paul Ishenin Fixed in Version => 0.9.29 (SVN)
2009-12-10 09:36 Paul Ishenin Resolution open => fixed
2009-12-10 09:36 Paul Ishenin Assigned To => Paul Ishenin
2009-12-10 09:36 Paul Ishenin Note Added: 0032888
2011-12-01 11:22 Marc Weustink Status resolved => closed