Pointer to generic type

Question

In the process of transforming a given efficient pointer-based hash map implementation into a generic hash map implementation, I stumbled across the following problem:

I have a class representing a hash node (the hash map implementation uses a binary tree)

THashNode <KEY_TYPE, VALUE_TYPE> = class
public
  Key      : KEY_TYPE;
  Value    : VALUE_TYPE;
  Left     : THashNode <KEY_TYPE, VALUE_TYPE>;
  Right    : THashNode <KEY_TYPE, VALUE_TYPE>;
end;

In addition to that there is a function that should return a pointer to a hash node. I wanted to write

PHashNode = ^THashNode <KEY_TYPE, VALUE_TYPE>

but that doesn't compile (';' expected but '<' found).

How can I have a pointer to a generic type?

And adressed to Barry Kelly: if you read this: yes, this is based on your hash map implementation. You haven't written such a generic version of your implementation yourself, have you? That would save me some time :)

Answer 1

There's a generic hash map called TDictionary in the Generics.Collections unit. Unfortunately, it's badly broken at the moment, but it's apparently going to be fixed in update #3, which is due out within a matter of days, according to Nick Hodges.

Answer 2

To actually answer your question, you can't make a pointer to a generic type, because "generic types" don't exist. You have to make a pointer to a specific type, with the type parameters filled in.

Unfortunately, the compiler doesn't like finding angle brackets after a ^. But it will accept the following:

   TGeneric<T> = record
      value: T;
   end;

   TSpecific = TGeneric<string>;

   PGeneric = ^TSpecific;

But "PGeneric = ^TGeneric<string>;" gives a compiler error. Sounds like a glitch to me. I'd report that over at QC if I was you.

Why are you trying to make a pointer to an object, anyway? Delphi objects are a reference type, so they're pointers already. You can just cast your object reference to Pointer and you're good.

Answer 3

If Delphi supported generic pointer types at all, it would have to look like this:

type
  PHashNode<K, V> = ^THashNode<K, V>;

That is, mention the generic parameters on the left side where you declare the name of the type, and then use those parameters in constructing the type on the right.

However, Delphi does not support that. See QC 66584.

On the other hand, I'd also question the necessity of having a pointer to a class type at all. Generic or not. they are needed only very rarely.

Answer 4

Sorry, Smasher. Pointers to open generic types are not supported because generic pointer types are not supported, although it is possible (compiler bug) to create them in certain circumstances (particularly pointers to nested types inside a generic type); this "feature" can't be removed in an update in case we break someone's code. The limitation on generic pointer types ought to be removed in the future, but I can't make promises when.

If the type in question is the one in JclStrHashMap I wrote (or the ancient HashList unit), well, the easiest way to reproduce it would be to change the node type to be a class and pass around any double-pointers as Pointer with appropriate casting. However, if I were writing that unit again today, I would not implement buckets as binary trees. I got the opportunity to write the dictionary in the Generics.Collections unit, though with all the other Delphi compiler work time was too tight before shipping for solid QA, and generic feature support itself was in flux until fairly late.

I would prefer to implement the hash map buckets as one of double-hashing, per-bucket dynamic arrays or linked lists of cells from a contiguous array, whichever came out best from tests using representative data. The logic is that cache miss cost of following links in tree/list ought to dominate any difference in bucket search between tree and list with a good hash function. The current dictionary is implemented as straight linear probing primarily because it was relatively easy to implement and worked with the available set of primitive generic operations.

That said, the binary tree buckets should have been an effective hedge against poor hash functions; if they were balanced binary trees (=> even more modification cost), they would be O(1) on average and O(log n) worst case performance.