View Issue Details
ID | Project | Category | View Status | Date Submitted | Last Update |
---|---|---|---|---|---|
0031704 | FPC | RTL | public | 2017-04-24 16:42 | 2017-04-24 22:53 |
Reporter | Denis Kozlov | Assigned To | Michael Van Canneyt | ||
Priority | normal | Severity | minor | Reproducibility | always |
Status | resolved | Resolution | fixed | ||
Product Version | 3.1.1 | Product Build | |||
Target Version | 3.2.0 | Fixed in Version | 3.1.1 | ||
Summary | 0031704: TFPGMap.TryGetData fails when Sorted=False | ||||
Description | TFPGMap.TryGetData uses binary search on unsorted keys by calling Find method blindly, which of course produces wrong results if keys are not sorted. Patch is trivial. Use IndexOf instead of Find, which already uses either linear or binary search depending on the Sorted state. Patch also makes TFPSMap.Find raise an exception if keys are not sorted, instead of silently producing wrong results - same fix was applied to TStringList.Find some time ago. | ||||
Additional Information | Patch and sample project are attached. | ||||
Tags | patch | ||||
Fixed in Revision | 35942 | ||||
FPCOldBugId | |||||
FPCTarget | |||||
Attached Files |
|
|
fgl.pp.patch (597 bytes)
Index: rtl/objpas/fgl.pp =================================================================== --- rtl/objpas/fgl.pp (revision 35934) +++ rtl/objpas/fgl.pp (working copy) @@ -1317,6 +1317,9 @@ I,L,R,Dir: Integer; begin Result := false; + Index := -1; + if not Sorted then + raise EListError.Create(SErrFindNeedsSortedList); // Use binary search. L := 0; R := FCount-1; @@ -1550,7 +1553,8 @@ var I: Integer; begin - Result := inherited Find(@AKey, I); + I := IndexOf(AKey); + Result := (I >= 0); if Result then AData := TData(inherited GetData(I)^) else |
|
project.pas (588 bytes)
program project; {$mode objfpc}{$H+} uses Classes, FGL; type TStringMap = specialize TFPGMap<string, string>; procedure TestStringMap(const Strings: array of String; const FindString: String); var List: TStringMap; S: String; begin List := TStringMap.Create; try //List.Sorted := True; for S in Strings do List.Add(S, S); if List.TryGetData(FindString, S) then WriteLn('FOUND ' + S) else WriteLn('NOT FOUND ' + S); finally List.Free; end; end; begin TestStringMap(['ZZZ', 'AAA'], 'AAA'); end. |
|
Please backport to FPC 3.0 fixes if possible. |
|
TFPGMapObject.TryGetData and TFPGMapInterfacedObjectData.TryGetData also suffer from the same condition. I will upload an updated patch shortly which also fixes these two methods. |
|
fgl-2.pp.patch (1,005 bytes)
Index: rtl/objpas/fgl.pp =================================================================== --- rtl/objpas/fgl.pp (revision 35934) +++ rtl/objpas/fgl.pp (working copy) @@ -1317,6 +1317,9 @@ I,L,R,Dir: Integer; begin Result := false; + Index := -1; + if not Sorted then + raise EListError.Create(SErrFindNeedsSortedList); // Use binary search. L := 0; R := FCount-1; @@ -1550,7 +1553,8 @@ var I: Integer; begin - Result := inherited Find(@AKey, I); + I := IndexOf(AKey); + Result := (I >= 0); if Result then AData := TData(inherited GetData(I)^) else @@ -1735,7 +1739,8 @@ var I: Integer; begin - Result := inherited Find(@AKey, I); + I := IndexOf(AKey); + Result := (I >= 0); if Result then AData := TData(inherited GetData(I)^) else @@ -1916,7 +1921,8 @@ var I: Integer; begin - Result := inherited Find(@AKey, I); + I := IndexOf(AKey); + Result := (I >= 0); if Result then AData := TData(inherited GetData(I)^) else |
|
New patch uploaded: fgl-2.pp.patch |
|
Checked and applied the patch, thank you very much! |
Date Modified | Username | Field | Change |
---|---|---|---|
2017-04-24 16:42 | Denis Kozlov | New Issue | |
2017-04-24 16:42 | Denis Kozlov | Tag Attached: patch | |
2017-04-24 16:43 | Denis Kozlov | File Added: fgl.pp.patch | |
2017-04-24 16:44 | Denis Kozlov | File Added: project.pas | |
2017-04-24 16:46 | Denis Kozlov | Note Added: 0099864 | |
2017-04-24 16:59 | Denis Kozlov | Note Added: 0099865 | |
2017-04-24 17:03 | Denis Kozlov | File Added: fgl-2.pp.patch | |
2017-04-24 17:04 | Denis Kozlov | Note Added: 0099866 | |
2017-04-24 22:50 | Michael Van Canneyt | Assigned To | => Michael Van Canneyt |
2017-04-24 22:50 | Michael Van Canneyt | Status | new => assigned |
2017-04-24 22:53 | Michael Van Canneyt | Fixed in Revision | => 35942 |
2017-04-24 22:53 | Michael Van Canneyt | Note Added: 0099885 | |
2017-04-24 22:53 | Michael Van Canneyt | Status | assigned => resolved |
2017-04-24 22:53 | Michael Van Canneyt | Fixed in Version | => 3.1.1 |
2017-04-24 22:53 | Michael Van Canneyt | Resolution | open => fixed |
2017-04-24 22:53 | Michael Van Canneyt | Target Version | => 3.2.0 |