Bug in TStringHashList.find()
Original Reporter info from Mantis: MaHan
-
Reporter name: Mattias Hansson
Original Reporter info from Mantis: MaHan
- Reporter name: Mattias Hansson
Description:
When 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 reproduce:
procedure 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 information:
Here 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;
Mantis conversion info:
- Mantis ID: 14551
- OS: Windows
- OS Build: XP
- Platform: Intel
- Version: 2.2.2
- Fixed in version: 0.9.29 (SVN)
- Fixed in revision: 23061 (#0fcd4927)
- Monitored by: » crossbuilder (Burkhard Carstens)
- Target version: 0.9.30