[fpc-devel] 2 Ideas for generic TDictionary and other hash containers

[Martin Frb]

There are 2 features, I am missing.

And I can't see a way to add them via subclassing, as the internal 
FItems array is private, and neither TItem, nor TPair can be gotten by 
the integer index into that array.

1) AddOrGetPointerToEmpty
This would actually just be to try and see if it gives any benefit in 
performance.

There is    TryAdd()
But, the caller must already have a new value, that it can pass for that 
key.

However, if the dictionary already has a value for that key, then the 
existing value may be enough,
So the caller ends up
    NewVal := CreaterNewValSpendingTime;
   if not Dictionary.TryAdd(TheKey, NewVal) then
     NewVal.Destroy;

Alternatively the caller can do
   If not Dictionary.ContainsKey(TheKey) then ...

But the latter then means, that "TheKey" need to be hashed twice, if a 
new value needs to be added (Even though the hash could already be known).

If there was a function
   GetItemPointer(AKey: TKey; out APtr: PValue): boolean;

which returns True, if Akey was found and therefore APtr points to 
existing Data, while otherwise APtr points to the empty slot, where the 
data can be copied to.



2) Key and Data to be the same.

Lets say I have lots of data, to which I have pointers (e.g. instances 
of some object).
Now when I have such a pointer, I want to know if I had a previous 
pointer to the same data. (even if the new pointer points to a copy of 
the data at a new location).

I could do TDictionary<TMyClass, TMClass>
I need to have my own IEqualityComparer, so I don't compare the 
pointers, but the data in the object. (That I can do).

But now I need to do
   MyDict.Add(val, val);
Which means the same value is stored as pointer and data => doubling mem 
requirements.

What I would need is
- set TData to "record end" (zero size)
- be able to retrieve the existing key, for another key that returns 
equal to the stored key

So instead of
   MyVal := Dict.Items[AKey];

I need
   ExsitingKey := Dict.Keys[ANewKey];

Obviously since the key is the data, my IEqualityComparer can do proper 
comparison, so even if the hash clashes, the pointed to data can be 
compared.