One important part of any generic collection classes are the “type support” functions. And what I mean are the functions specific to each type that perform:

1. Comparison – will return a value indicating if A > B or A <B or A = B. It’s usually a function that has this prototype: function Compare(const A, B : T) : Integer. The result value is less than 0 is A ie less than B, bigger than 0 is A is greater than B, and is 0 if the values match.
2. Equality – will return a Boolean value of True if A and B are equal. The usual prototype is: function AreEqual(const A, B : T) : Boolean.
3. Hash – the hash function is used by Dictionaries and Hash Sets. The usual prototype is function GetHashCode(const A : T) : Integer. Result is an integer that is supposed to be as unique as possible.

Now, in .NET or Java these functions are a part of any type (be it Integer, Object or etc.). This makes the development of generic collections easier because you can expect any type you’re operating on to have those functions exposed. It may be a little more work in some cases but anyway it’s always pretty simple.

In languages like C++ or Delphi there is a clear distinction between “value types” and “objects” which makes it quite impossible to operate on all data types with the same generic code. That’s why STL (C++) classes require you to provide support functions for each data type you want to use in your collection.

When I started working on HelperLib I designed a type called HTypeSupport which would provide all three support functions for all collections I create:

  MyDictionary := HDictionary<String, Integer>.Create(
                HStringTypeSupport.Create(), 
                HIntegerTypeSupport.Create());

So, as you can see in the example above, you’d have to supply your “type support” object each time you create an instance of the collection class.

Later on I discovered that Delphi provides Collections.Generic and Collections.Defaults units. Which made me interested is the fact that you could create a List without specifically giving it the support functions:

  MyList := TList<Integer>.Create();

After some digging I found out how are the pulling it off – RTTI. Yes RTTI seemed to work for generic types! Hooray! You can write a piece of code like this actually:

function GenericClass<T>.NameOfType() : String
begin
  Result := TypeInfo(T)^.Name;
end;

which will actually return you the name of the type you’re operating at run-time (note that TypeInfo can also return nil in the cases when T doesn’t have RTTI attached – like for records.)

If you look deeper in Generics.Defaults you will notice that RTL developers are doing some weird stuff – they are creating instances of objects building them by-hand. It’s very very ugly and I wanted to avoid this.

My HelperLib.TypeSupport unit does the same thing as Generics.Defaults just that it does it in a more cleaner way. The way to use it is simple – if you need a “type support” for your “unknown-yet” type you just call:

  HTypeSupport<T>.Default;

It will take into account all the possible types you can throw at it. The generic “binary type support” will be selected in all the cases when a type doesn’t have RTTI attached or where it makes sense to be used.

The development of these classes took quite a lot – mostly debugging with CPU window enabled. The problem appeared when developing the HBinaryTypeSupport – there is no possibility to know the size of the input parameters in those support functions at compile time. The only information at the time you create a HBinaryTypeSupport is the size of the arguments to come:

{ Binary Support }
HBinaryTypeSupport = class(HTypeSupport<Pointer>)
private
  FSize : Cardinal;

public
  { Constructor }
  constructor Create(const Size: Cardinal);

  { Comparator }
  function Compare(const AValue1, AValue2 : Pointer) : Integer;

  { Equality Comparator }
  function AreEqual(const AValue1, AValue2 : Pointer) : Boolean;

  { Hash code provider }
  function GenerateHashCode(const AValue : Pointer) : Integer;
end;

The Pointer arguments are actually, in a sense, bogus, because AValue can be of any given size (depending on the Type it was created for). The fun starts at knowing how the compiler will put the values onto the stack/registers when trying to call any of these functions. Example:

  TMyRec = packed record
    I1, I2, I3, I4, I5, I6 : Integer;
  end;

  procedure TestRecord;
  var
    DefaultSupport : ITypeSupport<TMyRec>;
    v1, v2         : TMyRec;
  begin
    DefaultSupport := HTypeSupport<TMyRec>.Default;
    DefaultSupport.Compare(v1, v2)
  end;

In this case the size of AValue1, and AValue2 will be 24 bytes, while the HBinaryTypeSupport.Compare function expects 2 pointers! It will actually work because the compiler will pass v1 and v2 as addresses to the Compare function. This happens because AValue1 and AValue2 are expected to be const – which ensures that the compiler will pass the address of the variables when their size is bigger than the platform register size (in this case 32 bits). Also the compiler will put those addresses to ECX/EDX registers – these two will be mapped to AValue1 and AValue2 resulting in me having 2 valid pointers to the structures I need to compare.

Of course this happens only if the size of the structure passed is bigger than 4 (size of the 32 bit register) – but HBinaryTypeSupport class is only instantiated for sizes which are bigger than 4 bytes anyway so there is no problem. (Note: See the implementation of HTypeSupport.Default to see what particular classes are selected for any given type.)

Another interesting effect is related to structures/arrays which are of 3 bytes length. Those are not passed as pointers and are not even passed by value in EDX/ECX. Compiler will actually push those onto stack (as 32 bit values). This meant that I had to create a special H3BytesTypeSupport class which would be instantiated for all types who’s sizes are 3 bytes (ex. packed array[0..2] of Byte). Using a HIntegerTypeSupport would not help because in that case the compiler will pass the integers using EDX/ECX.

There are also other interesting bits out there – like the comparison for dynamic arrays. This is done in a more logical way (expecting Pointers as AValue1 and AValue2) and exploiting the internal structure of dynamic arrays.

If you want to read more info on the calling convention used by Delphi by default, read this.