Hashing pointers by using their memory address as keys?

[EganSolo]

I need to build a hash of pointers. I thought the easiest way to achieve this is to use their mem address as a key like so:

Code: Pascal  [Select][+][-]

1. procedure HashPtr(const P: Pointer);
2. var aKey: String;
3. begin
4.    aKey := IntToHex(NativeUInt(P),8);
5.    Hash(aKey,P);
6. end;
7.  

Logically, that makes sense to me, but the compiler complains that NativeUInt(P) isn’t portable, which also makes sense. So, are there safe methods to convert between a pointer and a string? Something like PtrToStr and StrToPtr? Please don’t mention ToStr. That beast uses RTTI, and besides, I don’t know if it has an equivalent FromStr ...

Thanks for your feedback

[440bx]

It sounds like you could simply use the pointer value as the result of a "hash" then map it by applying a modulo operation based on the size of the hash array.

For instance, if your hash array is 101 (a prime number) then the hash key will be <pointer value> mod 101.  Simple and very fast.  Also, as long as the array has space for about 120% the number of elements as there are pointers you intend to "hash", the number of collisions should be small.

Lastly, to eliminate the non-portable message, if your hash function overlays a DWORD or qword on top of the pointer parameter, using an "absolute" clause (use a {$ifdef WIN32/64} to control the "absolute" then there won't be any warning message.

something along the lines of (pseudocode):

Code: Pascal  [Select][+][-]

1. function Hash(p : pointer) : DWORD;
2. {$ifdef WIN32}var v : DWORD absolute p; {$else} var v : qword absolute p; {$endif}
3. begin
4.   { NOTE: < the number of array elements> below could be a global, a constant or }
5.   {         another parameter, your choice }
6.  
7.    result := v mod <number of array elements>;  
8. end;
9.  

HTH.

ETA:

Actually you don't even need the {$ifdef}.  You could simply do:

Code: Pascal  [Select][+][-]

1. var
2.   v : ptruint absolute p;
3.  

Additionally, the hash function is so simple it could be made inline.

ETA2:

the above declaration of "v" will also work to eliminate the compiler message in the code snippet you presented.

i.e,

Code: Pascal  [Select][+][-]

1. aKey := IntToHex(v,8);
2.  

[Martin_fr]

Logically, that makes sense to me, but the compiler complains that NativeUInt(P) isn’t portable, which also makes sense. So, are there safe methods to convert between a pointer and a string? Something like PtrToStr and StrToPtr? Please don’t mention ToStr. That beast uses RTTI, and besides, I don’t know if it has an equivalent FromStr ...

Do you expect, that you need to support something where it wont be possible?

I don't actually know what that is. I could imagine maybe some embedded, or maybe cross compile to JS.... ?

It sounds like you could simply use the pointer value as the result of a "hash" then map it by applying a modulo operation based on the size of the hash array.

Maybe not the most efficient. On many targets data can be aligned (4, 8 or even 16 bit). Meaning the last few bit are always 0. If your modulo is power of 2 then you keep that, and you will have plenty of never-used buckets, and more clashes in the rest.

[440bx]

Maybe not the most efficient. On many targets data can be aligned (4, 8 or even 16 bit). Meaning the last few bit are always 0. If your modulo is power of 2 then you keep that, and you will have plenty of never-used buckets, and more clashes in the rest.

You just pointed out one of the reasons the modulo value should be a prime number. 

[BrunoK]

What unit contains the Hash(aKey,P); function ?

[ALLIGATOR]

How do you like this option?

Code: Pascal  [Select][+][-]

1. program app;
2. uses
3.   Generics.Hashes;
4.  
5. var
6.   P: Pointer;
7.   Hash: UInt32;
8.  
9. begin
10.   P := GetMem(1);
11.  
12.   Hash := Generics.Hashes.mORMotHasher(0, @P^, SizeOf(P));
13.  
14.   WriteLn(Hash);
15.   ReadLn;
16. end.

[jamie]

TFPHASHList class should do what you need ?

It already works with pointers.

Jamie

[cdbc]

Hi
What @jamie says   ...or you could take a 'looksee' at my 'IHashMap', there's also a /pointer-version/... It's located HERE.
Regards Benny

[EganSolo]

Thank you for the excellent feedback!
I should have mentioned that my request fits into a much larger context that relies on specific hashing functions and complex data structures, which is why I needed the PointerToStr and StrToPointer functions.

Here’s where I’ve landed. I don’t like using absolute, but it’s better than risking the other portability issue ...

Code: Pascal  [Select][+][-]

1. program Project1;
2. uses SysUtils;
3.  
4. Type
5.   pr = ^R;
6.   R  = Record N: string; I: integer; end;
7. var P1, P2: Pr;
8.     S : String;
9.  
10. function PointerToStr(const P: Pointer): String;
11. var I: Int64 absolute P;
12. begin
13.   Result := IntToStr(I);
14. end;
15.  
16. function StrToPointer(const Str: String): Pointer;
17. var anInt: Int64;
18.     pi   : PInteger  absolute anInt ;
19. begin
20.   anInt := StrToInt(str);
21.   Result := pi;
22. end;
23.  
24. begin
25.   New(P1);
26.   with P1^ do
27.   begin
28.     N := 'Name';
29.     I := 100   ;
30.   end;
31.   Writeln('p1^.N = ', p1^.N, ' & p1^.I = ', p1^.I);
32.   S := PointerToStr(P1);
33.   Writeln('p1''s address = ' , S);
34.   P2 := StrToPointer(S);
35.   Writeln('p2^.N = ', p2^.N, ' & p2^.I = ', p2^.I);
36.   Readln;
37.   Dispose(p1);
38. end.
39.  

[cdbc]

Hi
Hmmmm... This doesn't look right to me:

Code: Pascal  [Select][+][-]

1. function StrToPointer(const Str: String): Pointer;
2. var anInt: Int64;
3.     pi   : PInteger  absolute anInt ;
4. begin
5.   anInt := StrToInt(str);
6.   Result := pi; //<--HERE
7. end;

edit: Attached is the result of running your code "As Is"...
I'd say, that it should be:

Code: Pascal  [Select][+][-]

1. function StrToPointer(const Str: String): Pointer;
2. var anInt: PtrUInt; // NO negatives with pointers!
3.     p   : Pointer  absolute anInt ; //<--HERE
4. begin
5.   anInt := StrToInt64(str); //<-- we need 8 bytes
6.   Result := p;
7. end;

In your first code above, you'll get "a pointer to an integer" -- NOT "a pointer representation of an integer" and its the last one you need, to match the 'PointerToStr' function...
Just my 2 cent's worth... 
Regards Benny

[cdbc]

Hi again
Here's your code with my changes:

Code: Pascal  [Select][+][-]

1. program ptr2str;
2. {$mode objfpc}{$H+}
3. uses SysUtils;
4.  
5. Type
6.   pr = ^R;
7.   R  = Record N: string; I: integer; end;
8. var P1, P2: Pr;
9.     S : String;
10.  
11. function PointerToStr(const P: Pointer): String;
12. var I: Int64 absolute P;
13. begin
14.   Result := IntToStr(I);
15. end;
16.  
17. function StrToPointer(const Str: String): Pointer;
18. var anInt: PtrUInt; // NO negatives with pointers!
19.     p   : Pointer  absolute anInt ; //<--HERE
20. begin
21.   anInt := StrToInt64(str); //<-- we need 8 bytes
22.   Result := p;
23. end;
24.  
25. (**** HELL NO!!!
26. function StrToPointer(const Str: String): Pointer;
27. var anInt: Int64;
28.     pi   : PInteger  absolute anInt ;
29. begin
30.   anInt := StrToInt(str);
31.   Result := pi;
32. end;
33. ****)
34.  
35. begin
36.   New(P1);
37.   with P1^ do
38.   begin
39.     N := 'Name';
40.     I := 100   ;
41.   end;
42.   Writeln('p1^.N = ', p1^.N, ' & p1^.I = ', p1^.I);
43.   S := PointerToStr(P1);
44.   Writeln('p1''s address = ' , S);
45.   P2 := StrToPointer(S);
46.   Writeln('p2^.N = ', p2^.N, ' & p2^.I = ', p2^.I);
47.   Dispose(p1);
48.   {$ifdef win} Readln; {$endif}
49. end.
50.  

...And here's the result:

Code: Bash  [Select][+][-]

1. bc@red volapyk$ ./ptr2str
2. p1^.N = Name & p1^.I = 100
3. p1's address = 139960453034304
4. p2^.N = Name & p2^.I = 100
5. bc@red volapyk$
6.  

Regards Benny

[jamie]

Code: Pascal  [Select][+][-]

1. program Project1;
2.  
3. {$mode objfpc}{$H+}
4.  
5. uses
6.   {$IFDEF UNIX}
7.   cthreads,
8.   {$ENDIF}
9.   Classes,contnrs,sysutils
10.   { you can add units after this };
11. var
12.   TheList :TFPHashList;
13.   S:String;
14. begin
15. Writeln(' Not sure what you are after but here is some food for thought');
16. TheList := TFPHashList.create;
17. Thelist.Add('Entry_One',@TheList); //Just create a Pointer for test.
18. Writeln(TheList.NameOFIndex(Thelist.IndexOf(@TheList)));
19. Readln;
20. TheList.Free;
21. Writeln('And simple built in Helpers ');
22. S := UintPtr(@TheList).ToString;
23. WriteLn('The Address in String format :',S);
24. WriteLn(S.ToInt64);
25. Readln;
26. end.
27.  
28.  

I don't normally do console apps but in this case it was faster to present a test case.

AS you can see, you can use the hashlist class to store pointers with string names attached if you wish.
also, down at the end of code I show how you can simply generate these values using built in helpers !

Jamie

[EganSolo]

cdbc:

  Thanks for taking the time to test my code. It’s odd: it worked just fine on my system with no errors. Perhaps I made a mistake in copying.
  That said, I prefer your StrToPointer to mine, so thank you!

Jamie: I hear you; however, I have a complex structure with records and pointers only (no classes) that implements hashing, where the key is expected to be a string. That explains this.

[jamie]

Ok.

You know there the FPG (generics) that can pass complete records instead of pointers and with that, you can supply the comparator operators in the records to process whatever, all of those can be keyed with a string.

 Ok, have fun.

Jamie

[Martin_fr]

Here’s where I’ve landed. I don’t like using absolute, but it’s better than risking the other portability issue ...

absolute has far more risks. It just doesn't warn you.

Code: Pascal  [Select][+][-]

1. var anInt: Int64;
2.     pi   : PInteger  absolute anInt ;

compile that on a 32bit architecture, and it will compile. But your "PInteger" (or Pointer if you use that type) will only cover 32bit of teh 64 bits in your data...

If you instead had used the typecast, then you would have gotten an error. ... Well you could have gotten, may depend on how exactly you cast. PtrInt/PtrUInt probably silently truncate the data too. But "Pointer(anInt)" should fail (I haven't tested it), if anInt is 64 bit, but the pointer only 32bit.