Recent

Author Topic: Using a custom record as a key in TDictionary (TOpenAddressingLP)  (Read 848 times)

ilowry

  • Newbie
  • Posts: 5
Hello friends!

I'm trying to figure out how to use the hashmap class from Generics.Collections with a record as the key and a custom hash function for it. At the moment, I have the following code:

Code: Pascal  [Select][+][-]
  1. program test_dict;
  2.  
  3. {$MODE delphi}{$H+}
  4. {$MODESWITCH advancedrecords}
  5. {$MODESWITCH typehelpers}
  6. {$MACRO on}
  7. {$POINTERMATH on}
  8. //{$RANGECHECKS on}
  9. {$GOTO ON}
  10. {$codePage UTF-8}
  11. //{$VarPropSetter+}
  12.  
  13. uses sysutils, generics.defaults, generics.collections, unix, typinfo;
  14.  
  15. type
  16.     TKey = record
  17.         pid  : pid_t;
  18.         path : String;
  19.     end;
  20.  
  21.     TKeyComparer = class (TEqualityComparer<TKey>)
  22.         function Equals (constref ALeft, ARight: TKey): Boolean; override;
  23.         function GetHashCode (constref akey: TKey): UInt32; override;
  24.     end;
  25.  
  26.     TKeyHashFactory = class (THashFactory)
  27.         class function GetHashService: THashServiceClass; override;
  28.         class function GetHashCode (AKey: Pointer; ASize: SizeInt; AInitVal: UInt32 = 0): UInt32; override;
  29.     end;
  30.  
  31.     TKeyHashService = class (THashService<TKeyHashFactory>)
  32.     type
  33.         class var comparer : TKeyComparer;
  34.         class function LookupEqualityComparer (ATypeInfo: PTypeInfo; ASize: SizeInt): Pointer; override;
  35.         class constructor Create;
  36.     end;
  37.  
  38.     TMyDictionary = TOpenAddressingLP<TKey, String, TKeyHashFactory>;
  39.  
  40.  
  41. function TKeyComparer.Equals (constref ALeft, ARight: TKey): Boolean;
  42. begin
  43.     result := (aleft.pid = aright.pid) and (aleft.path = aright.path);
  44. end;
  45.  
  46. function TKeyComparer.GetHashCode (constref akey: TKey): UInt32;
  47. begin
  48.     result := DWord (akey.pid) << 5 + akey.path.GetHashCode;
  49. end;
  50.  
  51. class function TKeyHashFactory.GetHashService: THashServiceClass;
  52. begin
  53.     result := TKeyHashService;
  54. end;
  55.  
  56. class function TKeyHashFactory.GetHashCode (AKey: Pointer; ASize: SizeInt; AInitVal: UInt32 = 0): UInt32;
  57. var
  58.     ptkey : ^TKey;
  59. begin
  60.     TKeyHashService (self.GetHashService).comparer.GetHashCode (TKey (akey^));
  61. end;
  62.  
  63. class constructor TKeyHashService.Create;
  64. begin
  65.     inherited;
  66.     comparer := TKeyComparer.Create;
  67. end;
  68.  
  69. class function TKeyHashService.LookupEqualityComparer (ATypeInfo: PTypeInfo; ASize: SizeInt): Pointer;
  70. begin
  71.     result := @comparer; { return a pointer to the comparer }
  72. end;
  73.  
  74. var
  75.     dict: TMyDictionary;
  76.     vals: array of string = ['a', 'b', 'c'];
  77.     keys: array of TKey = [ (pid: 111; path: 'aaa'), (pid: 222; path: 'bbb'), (pid: 333; path: 'ccc') ];
  78. begin
  79.     dict := TMyDictionary.Create (16);
  80.     dict.Add (keys[0],vals[0]);
  81. end.
  82.  


There is a problem with this code though: an exception occurs in the FPC_INTF_ASSIGN function when returning from a call to _LookupVtableInfoEx(giEqualityComparer,...) in the TEqualityComparer<T>.Default(…) method:

Code: Pascal  [Select][+][-]
  1. class function TEqualityComparer<T>.Default(AHashFactoryClass: THashFactoryClass): IEqualityComparer<T>;
  2. begin
  3.   if AHashFactoryClass.InheritsFrom(TExtendedHashFactory) then
  4.     Result := _LookupVtableInfoEx(giExtendedEqualityComparer, TypeInfo(T), SizeOf(T), AHashFactoryClass)
  5.   else if AHashFactoryClass.InheritsFrom(THashFactory) then
  6.     Result := _LookupVtableInfoEx(giEqualityComparer, TypeInfo(T), SizeOf(T), AHashFactoryClass);
  7. end;
  8.  


The error message displayed by Lazarus is 'Process stopped with reason: EXC_BAD_ACCESS (code=1, address=0x0)'. As far as vaguely understand, this has something to do with counting references to the TKeyComparer object returned from the TKeyHashService.LookupEqualityComparer(…) method, but I have no idea what is a reason for that and how to fix it (which is not surprising, considering that I have zero experience with Pascal and Delphi).

Could someone please help me figure out what I'm doing wrong? Or maybe this whole code is a conceptual mistake, and there is a much easier way to do the same thing?

« Last Edit: April 21, 2025, 07:50:18 am by ilowry »

TRon

  • Hero Member
  • *****
  • Posts: 4371
Re: Using a custom record as a key in TDictionary (TOpenAddressingLP)
« Reply #1 on: April 21, 2025, 01:13:39 pm »
I am unfamiliar with this specific generic.

However, when trying to compile with fixes (3.2.3) the compiler is unable to compile (3.2.2 seem to accept the code but crashes). Trunk (3.3.1) is even more explicit and generates other errors.

It is an indication that the example code you posted is either doing something wrong and/or the generics implementation has
progressed in such a way that it now renders the code as used by the example incompatible.

I seem unable to find any (user) documentation other than the source-code (the latter which unfortunately leaves me puzzled)
Today is tomorrow's yesterday.

Martin_fr

  • Administrator
  • Hero Member
  • *
  • Posts: 11171
  • Debugger - SynEdit - and more
    • wiki
Re: Using a custom record as a key in TDictionary (TOpenAddressingLP)
« Reply #2 on: April 21, 2025, 01:25:01 pm »
Not tested your code, but there may be another way

Code: Pascal  [Select][+][-]
  1.   IYourEqualityComparer = specialize IEqualityComparer<TYourKey>;
  2.  
  3.   TYourEqualityComparer = class(TInterfacedObject, IYourEqualityComparer)
  4.   public
  5.     {$IF FPC_Fullversion>30202}
  6.     function Equals(const ALeft, ARight: TYourKey): Boolean; reintroduce;
  7.     function GetHashCode(const AValue: TYourKey): UInt32; reintroduce;
  8.     {$ELSE}
  9.     function Equals(constref ALeft, ARight: TYourKey): Boolean; reintroduce;
  10.     function GetHashCode(constref AValue: TYourKey): UInt32; reintroduce;
  11.     {$ENDIF}
  12.   end;
  13.  

and then
Code: Pascal  [Select][+][-]
  1. TYourDictionary.Create(TYourEqualityComparer.Create)

Create your dictionary with on overridden constructor that makes the correct inherited call with the comparer.

Thaddy

  • Hero Member
  • *****
  • Posts: 16982
  • Ceterum censeo Trump esse delendam
Re: Using a custom record as a key in TDictionary (TOpenAddressingLP)
« Reply #3 on: April 21, 2025, 01:50:08 pm »
What I find disturbing and disappointing from all of you is that any TObject descedent alreay HAS a hashcode.
It is simple, yes, but it returns the address of the instance and that is good enough. You are trying to invent a wheel that looks like the 2d dimension of an easter egg...Which is a wobbly ride...

https://www.freepascal.org/docs-html/rtl/system/tobject.gethashcode.html

Note that it becomes more serious if storage is involved, but even then just override TObject.GetHashCode and use any of the hashes in the hash unit..
(TDictionary is a class...)

Disadvantage is you need a class instead of a record.
« Last Edit: April 22, 2025, 10:59:13 am by Thaddy »
Due to censorship, I changed this to "Nelly the Elephant". Keeps the message clear.

kapibara

  • Hero Member
  • *****
  • Posts: 649
Re: Using a custom record as a key in TDictionary (TOpenAddressingLP)
« Reply #4 on: April 21, 2025, 02:45:20 pm »
I remember vaguely from a while ago that some of the generic lists or datastructures has a limitation when it comes to storing records (that limitation doesn't affect objects).

Generics is handy, but some strange things made me switch back to classic datastructures if possible. For example, I saw "internal error" on compilation. Compiling the same code with another version of laz/fpc worked. And after that the first laz/fpc version worked again, a few times. There was also failure to compile due to a syntax error in interface section, when no such syntax error existed. All problems was resolved by removing all generics. Or compiling a second time. Except for the internal error. If you see these errors, be adviced where they come from.

Maybe these things can be worked around if you know how.

ChatGPT gave similar advice as Martin_fr:

I asked this: Does TDictionary in freepascal work well with both objects and records?

ChatGPT answer:
Great question — TDictionary in Free Pascal (FPC) can work with both objects and records, but there are some caveats and best practices you should be aware of, especially when using records as either keys or values.

Let’s go over the details:
TDictionary<TKey, TValue> Overview (FPC mode Delphi-compatible)

In FPC 3.2+ (and especially 3.2.2+), TDictionary (from fgl or Generics.Collections) supports:

    TKey and TValue can be primitive types, objects, records, strings, etc.

    You can use custom comparers for key types that require specific equality/hash logic (very relevant for records!).

Using Records as Values (TValue)

This is safe and works well, e.g.:

Code: Pascal  [Select][+][-]
  1. type
  2.   TMyData = record
  3.     A: Integer;
  4.     B: String;
  5.   end;
  6.  
  7. var
  8.   Dict: TDictionary<Integer, TMyData>;
  9.   Rec: TMyData;
  10. begin
  11.   Dict := TDictionary<Integer, TMyData>.Create;
  12.  
  13.   Rec.A := 42;
  14.   Rec.B := 'Hello';
  15.   Dict.Add(1, Rec);
  16.  
🔹 Internally, the record is copied by value when stored — so no problem there.
🔹 No need to manage memory unless the record holds managed types (e.g. dynamic arrays, strings, interfaces).
Using Records as Keys (TKey)

This works but you must be careful, because TDictionary uses:

    GetHashCode → for hashing

    Equals → for comparing keys

For simple records (no pointers, short strings, etc.), the default comparer does a bitwise compare, which may or may not match your logic.
Example:

Code: Pascal  [Select][+][-]
  1. type
  2.   TCoord = record
  3.     X, Y: Integer;
  4.   end;
  5.  
  6. var
  7.   Dict: TDictionary<TCoord, String>;
  8.   P: TCoord;
  9. begin
  10.   Dict := TDictionary<TCoord, String>.Create;
  11.  
  12.   P.X := 10;
  13.   P.Y := 20;
  14.   Dict.Add(P, 'Point A');
  15.  
This works as long as the record is bitwise comparable.
Best Practice: Use a Custom Comparer for Records as Keys

If your record is more complex (e.g., floating-point fields, strings, or requires tolerance for equality), define a custom IEqualityComparer<T>, like this:

Code: Pascal  [Select][+][-]
  1. type
  2.   TCoordComparer = class(TInterfacedObject, IEqualityComparer<TCoord>)
  3.     function Equals(const Left, Right: TCoord): Boolean;
  4.     function GetHashCode(const Value: TCoord): Integer;
  5.   end;
  6.  
  7. function TCoordComparer.Equals(const Left, Right: TCoord): Boolean;
  8. begin
  9.   Result := (Left.X = Right.X) and (Left.Y = Right.Y);
  10. end;
  11.  
  12. function TCoordComparer.GetHashCode(const Value: TCoord): Integer;
  13. begin
  14.   Result := Value.X * 31 + Value.Y;
  15. end;
  16.  
Then create the dictionary like this:

Code: Pascal  [Select][+][-]
  1. Dict := TDictionary<TCoord, String>.Create(TCoordComparer.Create);
  2.  
Now you're safe and clear on how comparisons and hashes are handled.
Lazarus trunk / fpc 3.2.2 / Kubuntu 24.04 - 64 bit

ilowry

  • Newbie
  • Posts: 5
Re: Using a custom record as a key in TDictionary (TOpenAddressingLP)
« Reply #5 on: April 21, 2025, 08:16:09 pm »
Then create the dictionary like this:

Code: Pascal  [Select][+][-]
  1. Dict := TDictionary<TCoord, String>.Create(TCoordComparer.Create);
  2.  
Now you're safe and clear on how comparisons and hashes are handled.

Oh! It turns out that you just had to pass the comparator object as an argument to the constructor method. And I was trying to specialize the generic  using a comparator class.
And now its works:

Code: Pascal  [Select][+][-]
  1. program test_dict;
  2.  
  3. {$MODE delphi}{$H+}
  4. {$MODESWITCH advancedrecords}
  5. {$MODESWITCH typehelpers}
  6. {$MACRO on}
  7. {$POINTERMATH on}
  8. //{$RANGECHECKS on}
  9. {$GOTO ON}
  10. {$codePage UTF-8}
  11. //{$VarPropSetter+}
  12.  
  13. uses sysutils, generics.defaults, generics.collections, unix, typinfo;
  14.  
  15. type
  16.     TKey = record
  17.         pid  : pid_t;
  18.         path : String;
  19.     end;
  20.  
  21.     TKeyComparer = class (TEqualityComparer<TKey>)
  22.       function Equals (constref ALeft, ARight: TKey): Boolean; override;
  23.       function GetHashCode (constref akey: TKey): UInt32; override;
  24.     end;
  25.  
  26.     TMyDictionary = TDictionary<TKey, String>;
  27.  
  28.  
  29. function TKeyComparer.Equals (constref ALeft, ARight: TKey): Boolean;
  30. begin
  31.     result := (aleft.pid = aright.pid) and (aleft.path = aright.path);
  32. end;
  33.  
  34. function TKeyComparer.GetHashCode (constref akey: TKey): UInt32;
  35. begin
  36.     result := DWord (akey.pid) << 5 + akey.path.GetHashCode;
  37. end;
  38.  
  39.  
  40. var
  41.     i: Cardinal;
  42.     keyval: TPair<TKey, String>;
  43.     dict: TMyDictionary;
  44.     vals: array of string = ['a', 'b', 'c'];
  45.     keys: array of TKey = [ (pid: 111; path: 'aaa'), (pid: 222; path: 'bbb'), (pid: 333; path: 'ccc')];
  46. begin
  47.     dict := TMyDictionary.create (TKeyComparer.create);
  48.     for i := 0 to 2 do
  49.         dict.add (keys[i], vals[i]);
  50.  
  51.     for keyval in dict do
  52.         writeln (keyval.key.pid, '-', keyval.key.path, ': ', keyval.value);
  53. end.
  54.  

Thanks a lot!

ilowry

  • Newbie
  • Posts: 5
Re: Using a custom record as a key in TDictionary (TOpenAddressingLP)
« Reply #6 on: April 21, 2025, 08:24:00 pm »
However, when trying to compile with fixes (3.2.3) the compiler is unable to compile (3.2.2 seem to accept the code but crashes). Trunk (3.3.1) is even more explicit and generates other errors.

It is an indication that the example code you posted is either doing something wrong and/or the generics implementation has
progressed in such a way that it now renders the code as used by the example incompatible.

Yes, and that was my question about what I did wrong. Actually, I haven't figured out what was wrong with my code yet, but now it's clear that there is a practical solution: just pass the comparer object as an argument to the dictionary constructor.

ilowry

  • Newbie
  • Posts: 5
Re: Using a custom record as a key in TDictionary (TOpenAddressingLP)
« Reply #7 on: April 21, 2025, 08:34:30 pm »
Not tested your code, but there may be another way

Code: Pascal  [Select][+][-]
  1.   IYourEqualityComparer = specialize IEqualityComparer<TYourKey>;
  2.  
  3.   TYourEqualityComparer = class(TInterfacedObject, IYourEqualityComparer)
  4.   public
  5.     {$IF FPC_Fullversion>30202}
  6.     function Equals(const ALeft, ARight: TYourKey): Boolean; reintroduce;
  7.     function GetHashCode(const AValue: TYourKey): UInt32; reintroduce;
  8.     {$ELSE}
  9.     function Equals(constref ALeft, ARight: TYourKey): Boolean; reintroduce;
  10.     function GetHashCode(constref AValue: TYourKey): UInt32; reintroduce;
  11.     {$ENDIF}
  12.   end;
  13.  

and then
Code: Pascal  [Select][+][-]
  1. TYourDictionary.Create(TYourEqualityComparer.Create)

Create your dictionary with on overridden constructor that makes the correct inherited call with the comparer.

Yes, thanks.  This is the solution. What I don't understand is why do we need a reintroduce modifier? The code seems to work without it.

ilowry

  • Newbie
  • Posts: 5
Re: Using a custom record as a key in TDictionary (TOpenAddressingLP)
« Reply #8 on: April 21, 2025, 09:13:00 pm »
Note that it becomes more serious if storage is involved, but even then just override TObject.GetHashCode and use any of the hashes in the hash unit..
(TDictionary is a class...)

It looks like TDictionary doesn't use the TObject.GetHashCode method, but instead just uses its own binary comparer, so we need to use our own comparer anyway. 

Thaddy

  • Hero Member
  • *****
  • Posts: 16982
  • Ceterum censeo Trump esse delendam
Re: Using a custom record as a key in TDictionary (TOpenAddressingLP)
« Reply #9 on: April 22, 2025, 10:29:31 am »
GetHashCode is virtual, so should be used as override, not reintroduce.
That is per the documentation of TObject.GetHashCode that describes exactly what I proposed.
Reintruduce has only validity/applicability in the case that you can't use override when a root method is not virtual.
It may be that Majieh, who wrote the bulk of generics.collections, was not aware of it. It may also be that the implementations clashed.
We need to check when generics.collections was written and when GetHashCode was added,
As it stands the correct way is to override GetHashCode if the pointer comparison is not enough. If you write an equality comparer that just uses the default implementation of GetHashCode that should be enough.
Its big O notation is O(1), it just returns a pointer to self, so it is fast.
« Last Edit: April 22, 2025, 10:43:48 am by Thaddy »
Due to censorship, I changed this to "Nelly the Elephant". Keeps the message clear.

Martin_fr

  • Administrator
  • Hero Member
  • *
  • Posts: 11171
  • Debugger - SynEdit - and more
    • wiki
Re: Using a custom record as a key in TDictionary (TOpenAddressingLP)
« Reply #10 on: April 22, 2025, 10:45:23 am »
What I don't understand is why do we need a reintroduce modifier? The code seems to work without it.

Just to silent the compiler message "is hiding a method"...

GetHashCode is virtual, so should be used as override, not reintroduce.
That is per the documentation of TObject.GetHashCode that describes exactly what I proposed.
Reintruduce has only validity/applicability in the case that you can't use override when a root method is not virtual.

In this case "reintroduce" is fine (and technically more effective / but in real life wont matter much).

The code will never have the need to go via the VMT. I.e. there will never be access through a variable of the base class' type.

Both methods are there only to be called via the interface. They could have had a new name in the class, and have been connected via "implements".
That there are methods of that name in the base class is just an inconvenience.

The dictionary only takes the interface (the constructor takes the interface as param). So the actual instance is only accessed via the interface.
And that points to the 2 non virtual methods.

So reintroduce is fine.

And reintroduce (without virtual) means that the interface can point directly to those 2 methods, and does not need to do the redirect via the VMT.

 

TinyPortal © 2005-2018