justPhukit! Delphi Wiki

Dynamic Arrays

More often than not, when you are programming some routine that requires an array, you don't know how many elements you want in that array. It may be ten, one hundred, or a thousand, but certainly it's only at run time that you can come up with the answer. Furthermore, because you don't know, it's hard to declare the array as a local variable (declaring the maximum size you may encounter might put strains on the stack, especially in Delphi 1); it certainly makes sense to allocate it on the heap.

This still leaves something to be desired. Suppose you decide that, really, you would never require more than 100 elements. Never say never, because one day the application would require 101 elements, and it would crash with a sudden mysterious memory overwrite or an access violation (unless, of course, you added an assertion in your code to check for that eventuality). And of course, you could also guarantee that that would only happen with your best customer.

One technique, which dates from pre-object-oriented Pascal days, is to create an array type with just one element, and a pointer to that array:

type

PMyArray : ^TMyArray;

When you need an array of TMyType, you allocate the required number of elements:

MyArray : PMyArray; begin

GetMem(MyArray, 42*sizeof(TMyType)); .. use MyArray ..

FreeMem(MyArray, 42*sizeof(TMyType));

It is only Delphi 1 that requires the size of the allocated block with a call to FreeMem. All 32-bit versions of Delphi and Kylix store the size of an allocated block with the block itself. It appears just before the block you get back from GetMem, and they ignore any size value you pass into FreeMem and use the hidden value instead.

Until you free the memory, MyArray points to an array of 42 TMyType elements. Although this technique is quick and easy, it suffers from some problems of which you must be aware. The first is that you cannot compile your code with range checking enabled ($R+) since the compiler thinks that the array should only have one element and therefore that the only index you can use is 0.

(You can get around this by sizing the upper bound of the the array type to some large number instead. This solution has the opposite problem: any index becomes valid up to the upper limit of the range. An example would be allocating a 42-element array based on a type with 1000 elements: any index from 42 to 999 is valid as far as the compiler's range checking goes.)

The second problem is that the allocated variable has no record of how many elements are in the array. Generally, you have to store this as a variable and keep track of the variable alongside the allocated array. That way you can do your own range checking, possibly with assertions.

Nevertheless, this technique is used a lot in everyday programming tasks. For example, the SysUtils unit has an extremely flexible array type called TByteArray, with the pointer to this type being PByteArray. Using this type (or rather the pointer to it) you can easily typecast an untyped buffer parameter to an array of bytes. There are other array types as well; you should be able to find a longint array type, a word array type, and so on.

The solution to the second problem discussed above shows the way to go. The best idea is to create an array class that would allow you to allocate as many elements as you wanted and that would enable you to access and set individual elements, even grow or shrink the array in size (i.e., increase or decrease the number of elements). Other methods, like the ability to sort the elements, and delete or insert a new element, might come in handy as well. Basically you would create an instance of the array class, declaring the size of each element with the constructor, and let the object deal with memory allocation issues.

Note that I am not talking about the TList class here. TList, which we'll discuss in a moment, is an array of pointers. In essence, if you were to use a TList, you'd have to allocate the individual elements on the heap and then manipulate an array of pointers to your elements.

What we will do instead is write a record array class, called TtdRecordList, that mimics a TList in its operations, but which is responsible for allocating the space for the elements themselves. The array class we will discuss has the interface shown in Listing 2.1.

Listing 2.1: Declaration of the TtdRecordList class

TtdRecordList = class private

FActElemSize : integer;| FArray : PAnsiChar;

FCount : integer;

FCapacity : integer; FElementSize : integer; FMaxElemCount: integer; FName : TtdNameString;

protected function rlGetItem(aIndex : integer) : pointer; procedure rlSetCapacity(aCapacity : integer); procedure rlSetCount(aCount : integer); procedure rlError(aErrorCode : integer;

const aMethodName : TtdNameString; aIndex : integer); procedure rlExpand; public constructor Create(aElementSize : integer); destructor Destroy; override; function Add(aItem : pointer) : integer; procedure Clear;

procedure Delete(aIndex : integer); procedure Exchange(aIndex1, aIndex2 : integer); function First : pointer; function Index0f(aItem : pointer;

aCompare : TtdCompareFunc) : integer; procedure Insert(aIndex : integer; aItem : pointer); function Last : pointer;

procedure Move(aCurIndex, aNewIndex : integer); function Remove(aItem : pointer;

aCompare : TtdCompareFunc) : integer; procedure Sort(aCompare : TtdCompareFunc);

property Capacity : integer read FCapacity write rlSetCapacity;

property Count : integer read FCount write rlSetCount;

property ElementSize : integer read FActElemSize;

property Items[aIndex : integer] : pointer read rlGetItem; default;

property MaxCount : integer read FMaxElemCount;

property Name : TtdNameString read FName write FName;

end;

If you are familiar with the interface to TList, you'll see that the TtdRecordList class mimics it with similarly named methods and properties. So, for example, Add will append an element onto the end of the list, whereas Insert will add the element at the index given. Both methods will extend the internal structure if necessary and increment the count of elements. The Sort method won't be discussed here; we'll leave this implementation until Chapter 5.

The Create constructor saves the passed element size and also calculates the size of an element, rounded up to the nearest four bytes. This ensures that, for speed reasons, elements always start on a 4-byte boundary. As a final step, the constructor calculates the maximum number of elements the class could hold with the given element size. This is only really required for Delphi 1 since the maximum allocation from the heap is a shade less than 64 KB, and it will be used to check that the array doesn't grow beyond the maximum limit.

Listing 2.2: The constructor for TtdRecordList constructor TtdRecordList.Create(aElementSize : integer); begin inherited Create;

{save the actual element size}

FActElemSize := aElementSize;

{round the actual size to the nearest 4 bytes}

FElementSize := ((aElementSize + 3) shr 2) shl 2;

• calculate the maximum number of elements}
• IFDEF Delphi1}

FMaxElemCount := 65535 div FElementSize; {$ELSE}

FMaxElemCount := MaxInt div FElementSize; {$ENDIF} end;

Note that the class does not allocate any memory for the elements. This allocation is deferred until an element is actually added; in other words, until the class instance is actually used.

(Listing 2.2 uses a non-standard compiler define, Delphi1. This compiler define is declared in an include file, TDDefine.inc, that is included in all the units for this book. I find it easier to remember a compiler define named Delphi1 than the more official VER80, and this gets easier the more Delphi versions there are. For example, VER100 is for Delphi 3, whereas VER120 is for Delphi 4, but either way it's easier to remember Delphi3 and Delphi4.)

The Destroy destructor is equally simple. We just set the capacity of the instance to zero (we'll discuss what this does in a moment) and the ancestor Destroy destructor is called.

Listing 2.3: The destructor for TtdRecordList destructor TtdRecordList.Destroy; begin Capacity := 0; inherited Destroy; end;

Let's see something more interesting: adding or inserting a new element. The Add method is simple; it just calls Insert to insert a new element at the end of the internal array. Insert accepts an index value indicating where to insert the element. The element itself is defined as a pointer (there is another way of defining the element to insert (as a typeless var parameter) but if we stick with pointers, it makes other methods easier to implement and understand, and also provides consistency). When we call the method, we can use Delphi's @ operator to pass the address of our item as the pointer value.

As the new item is a pointer, it could be nil, so the first thing is to make sure that it isn't. Then the method validates the index; it must be between 0 and the current count of elements in the array, inclusive. Now we can do some work. If the number of elements equals the current capacity of the array, the array must be grown with a call to rlExpand. We now move the elements from aIndex to the end of the array along by one element to open up a "hole" for the new element, and then we copy the new element into the hole. We increment the count of elements as the final step.

Listing 2.4: Adding and inserting a new element function TtdRecordList.Add(aItem : pointer) : integer; begin

procedure TtdRecordList.Insert(aIndex : integer; altem : pointer); begin if (aItem = nil) then rlError(tdeNilItem, 'Insert', aIndex); if (aIndex < 0) or (aIndex > Count) then rlError(tdeIndexOutOfBounds, 'Insert', aIndex); if (Count = Capacity) then rlExpand; if (aIndex < Count) then System.Move((FArray + (aIndex * FElementSize))^,

• FArray + (succ(aIndex) * FElementSize))^, (Count - aIndex) * FElementSize); System.Move(aIterrT,
• FArray + (aIndex * FElementSize))^, FActElemSize);

inc(FCount); end;

Having seen Insert, Listing 2.5 shows Delete for deleting an element from the array. Again, we check the index we're given, and if it's acceptable, we move the elements from aIndex to the end of the array over the element we're asked to delete. We have one less element now, so we decrement the count.

Listing 2.5: Deleting an element from the array procedure TtdRecordList.Delete(aIndex : integer); begin if (aIndex < 0) or (aIndex >= Count) then rlError(tdeIndexOutOfBounds, 'Delete', aIndex); dec(FCount);

if (aIndex < Count) then System.Move((FArray + (succ(aIndex) * FElementSize))^, (FArray + (aIndex * FElementSize))^, (Count - aIndex) * FElementSize);

end;

Allied to Delete is the Remove method where we want to delete a particular element, but we don't necessarily know where it is in the array. We find the item by means of the IndexOf method and a helper comparison routine that we have to write externally to the class. So Remove requires not only the element we wish to delete, but also a routine which will help identify the element that needs removing inside the array. This routine is of type TtdCompareFunc and will be called for every element in the array by the IndexOf method until the routine returns 0 (i.e., equal) for an element. If no element does so, IndexOf returns tdc_ItemNotPresent.

Listing 2.6: Remove and IndexOf methods

function TtdRecordList.Remove(aItem :	pointer;
aCompare	: TtdCompareFunc)	integer;
begin
Result := IndexOf(aItem, aCompare);
if (Result<>tdc_ItemNotPresent) then
Delete(Result);
end;
function TtdRecordList.IndexOf(aItem	: pointer;
aCompare	: TtdCompareFunc)	integer;
var
ElementPtr : PAnsiChar;
i : integer;
begin
ElementPtr := FArray;
for i := 0 to pred(Count) do begin
if (aCompare(aItem, ElementPtr) = 0)	then begin
Result := i;
Exit;
end;
inc(ElementPtr, FElementSize);
end;
Result := tdc ItemNotPresent;
end;

To expand the array (i.e., to allow more elements to be stored in it), you set the Capacity property. Setting Capacity causes the protected rlSetCapacity method to be called. rlSetCapacity looks more complicated than it need be because the Delphi 1 ReAllocMem routine doesn't do everything that the 32-bit version does.

A related method is the protected rlExpand method, which uses a simple algorithm to set the Capacity property based on its current value. rlExpand is called automatically by the Insert method to grow the array, if that method determines that the current array is full (i.e., the capacity of the array is equal to the number of elements in the array).

Listing 2.7: Expanding the array procedure TtdRecordList.rlExpand; var

NewCapacity : integer; begin

• if current capacity is 0, make new capacity 4 elements} if (Capacity = 0) then NewCapacity := 4
• if current capacity is less than 64, increase it by 16 elements} else if (Capacity < 64) then

NewCapacity := Capacity + 16 {if current capacity is 64 or more, increase it by a quarter} else

NewCapacity := Capacity + (Capacity div 4); {make sure we don't grow beyond the array's upper limit} if (NewCapacity > FMaxElemCount) then begin NewCapacity := FMaxElemCount; if (NewCapacity = Capacity) then rlError(tdeAtMaxCapacity, 'rlExpand', 0);

end;

{set the new capacity} Capacity := NewCapacity; end;

procedure TtdRecordList.rlSetCapacity(aCapacity : integer); begin if (aCapacity<>FCapacity) then begin

• don't go over the maximum number of elements possible} if (aCapacity > FMaxElemCount) then rlError(tdeCapacityTooLarge, 'rlSetCapacity', 0); {reallocate the array, or free it if the capacity is being reduced to zero}
• IFDEF Delphi1} if (aCapacity = 0) then begin FreeMem(FArray, word(FCapacity) * FElementSize); FArray := nil;

end else begin if (FCapacity = 0) then

GetMem(FArray, word(aCapacity) * FElementSize) else

FArray := ReallocMem(FArray, word(FCapacity) * FElementSize, word(aCapacity) * FElementSize);

end;

ReallocMem(FArray, aCapacity * FElementSize); {$ENDIF}

{are we shrinking the capacity? if so check the count} if (aCapacity < FCapacity) then begin if (Count > aCapacity) then Count := aCapacity;

end;

{save the new capacity} FCapacity := aCapacity; end; end;

Of course, an array class wouldn't be very useful if we couldn't get at the elements stored in the array. The TtdRecordList class makes use of an array property called Items. The only accessor for this property is the read method: rlGetItem. To avoid excessive copying of the data in an element, the rlGetItem method returns a pointer to the element in the array. This makes it easy to alter a particular element in the array as well, which is why we do not expose a write accessor method for the Items property. Since the Items property is marked with the default keyword it's easy to access individual elements with code like this, MyArray[i], rather than MyArray.Items[i].

Listing 2.8: Accessing an element in the array function TtdRecordList.rlGetItem(aIndex : integer) : pointer; begin if (aIndex < 0) or (aIndex >= Count) then rlError(tdeIndexOutOfBounds, 'rlGetItem', aIndex); Result := pointer(FArray + (aIndex * FElementSize)); end;

The final method we shall discuss is the one called by setting the Count property: rlSetCount. Setting the Count property makes it easy to preallocate the space for an array and use it in a similar fashion to standard Delphi arrays. Note that the Insert and Delete methods will maintain the count properly when you insert or delete an element. Setting the Count property explicitly will ensure that the Capacity property is properly set as well (Insert takes care of this automatically). If the new value for Count is greater than the current value, the newly accessible elements will automatically be set to binary zeros; if it is less than, the elements at indexes greater than or equal to the new count will no longer be accessible (essentially, you can view them as having been deleted).

Listing 2.9: Setting the number of elements in the array procedure TtdRecordList.rlSetCount(aCount : integer); begin if (aCount<>FCount) then begin

{if the new count is greater than the capacity, grow the array} if (aCount > Capacity) then

Capacity := aCount; {if the new count is greater than the old count, set new elements to binary zeros} if (aCount > FCount) then FillChar((FArray + (FCount * FElementSize))~, (aCount - FCount) * FElementSize, 0);

The code for the TtdRecordList class is on the accompanying CD in the TDRecLst.pas source file. It also includes other standard methods like First, Last, Move, and Exchange.

0 0