Container classes for Delphi Page
Michael Rynn
michrynn@ozemail.com.au
June 2000
The following units support container classes for pascal record based storage.
A manager object for records types is based on the TCCRecordMgr class.
Each class derived from TCCBase can use the same TCCRecordMgr class to allocate and deallocate storage, initialise and finalize data, and compare and assign records of the type managed by the descendent of the TCCRecordMgr class.
All the container classes can store the record in entirety, not just a pointer to it.
Lists and Tree classes reduce the memory overhead by allocating space for the record with each node.
Array classes store a single contigous block of records.
In Object-Pascal (Delphi) the lightweight objects corresponding to C++ struct type is the record type. Functions/Procedures are created to manage record types as objects, passing the record storage as const or var parameters, depending need to modify. For the purposes of the container classes, I have devised a record management object. It is a kind of customizable typeinfo object, but only contains information and methods as to what container classes can do with the record.
In order to make a container class for a new type of record object, it is necessary to create a record management object derived from TCCRecordMgr which overrides various methods. The most important are :-
TMyRecordMgr = class(TCCRecordMgr)
public
constructor create; override;
procedure ConstructItem(var item); override;
procedure DestructItem(var item); override;
procedure AssignItem(var dest;const src);
procedure SwapItems(var p1, p2); override;
function CompareItems(const p1, p2):integer; override;
function CompareKey(const item; data:Pointer):integer; override;
...
Not all of these need to be overridden. The most frequently overriden items would be the constructor and the CompareItems function. For the other workings of TCCRecordMgr, see the source code.
constructor Create;
In the constructor do whatever but the derived constructor must call the TCCRecordMgr method
InitRecordMgr.
procedure InitRecordMgr(itemSize : integer; initItems : Boolean);
InitRecordMgr specifies the record size and whether or not the records require calls to ConstructItem and DestructItem. Passing initItems as FALSE means that ConstructItem and DestructItem will not be called, even if they are overriden.
procedure ConstructItem;
To use this, InitRecordMgr must be called with initItems as TRUE.
Typically ConstructItem must be called if the record contains dynamically assigned pointer data types such as AnsiLongStrings,arrays or variants. The Delphi dynamic types are catered for by calls to initialize and finalize for the whole record or individual field type.
procedure DestructItem;
Usually paired with ConstructItem.
procedure AssignItem;
In order to copy the contents of one record to another, in order to achieve duplication of data.
For Delphi dynamic types, this requires a simple assignment between the individual fields of the record.
procedure SwapItems;
The TCCRecordMgr implementation of this does a record buffer swap using the TCCRecordMgr private record buffer, calling System.Move. Overriding this might achieve greater efficiency in array sorts.
function CompareItems;
This returns the result of the ordered comparison between p1 and p2. This function is most useful for sorting and ordered insertion.
The integer result should be defined so that
p1 < p2; Result < 0
p1 = p2; Result = 0
p1 > p2; Result > 0
function CompareKey;
When a container item is complex and inconvenient to construct for the sake of locating an item, the Container methods LocateKey and LocateKeyPtr become useful. They call the TCCRecordMgr method CompareKey, which is passed a container item, and a pointer to the key. The integer result should be defined so that :-
item < key; Result < 0
item = key; Result = 0
item > key; Result > 0
The base container class: TCCBase
In order to use raw container class, it must be passed a class type derived from the TCCRecordMgrClass. The container can then create its own instance of the record manager, in order to use the record managers properties and methods. For instance in order to use an container of records with the record type managed by TMyRecordMgr do:
myslist := TCCSList.CreateMgr( TMyRecordMgr );
mydlist := TCCDList.CreateMgr( TMyRecordMgr );
mytree := TCCTree.CreateMgr( TMyRecordMgr );
myarray := TCCArray.CreateMgr( TMyRecordMgr );
Insertion and deletion
Each derived container class supports the basic insertion and deletion functions.
A fully formed item supporting the CompareItems method must be passed for container classes supporting sorts and ordered insertion.
function AppendItem(const buf): TCCItemPtr; virtual;
function DeleteItem(const buf): boolean; virtual;
procedure FreeItem(var pitem : TCCItemPtr); virtual;
A bit about the TCCItemPtr. This is used a lot in these container classes, and because of the particular implementations used, it is always pointer to the items record data held in the container. The TCCItemPtr can safely be cast to a pointer to the record type stored in the container. Nodal based containers store the nodes information hidden in the same buffer just before the record data. The array container can increment or decrement the pointer in a C-style, and stores no extra non-record data. Nodal-based containers guarantee that the TCCItemPtr passed will remain valid even if other items are inserted or deleted. The array-based containers do not, since insertion or deletion will move memory, and may even relocate the whole array in memory.
For containers which are not sorted with ordered insertion the following are allowed.
procedure AppendFirst(const buf);virtual;
procedure AppendLast(const buf); virtual;
Access and navigation
Using a TCCItemPtr, iteration through the container is possible. In the case of arrays, insertion or deletion can invalidate a passed pointer. For example see the TCCBase methods CallActionMethod and CallActionProcedure. For Node-based containers, the passed TCCActionMethod or TCCActionProc can safely call FreeItem (if they can access the TCCBase object), which is not safe for array-based containers.
A copy of the container item is obtained with CopyItem, which uses the TCCRecordMgr method AssignItem.
function FirstItem : TCCItemPtr; virtual;
function LastItem : TCCItemPtr; virtual;
function NextItem(pitem : TCCItemPtr) : TCCItemPtr; virtual;
function PriorItem(pitem : TCCItemPtr) : TCCItemPtr; virtual;
procedure CopyItem(pitem : TCCItemPtr; var buf);
TCCActionMethod = procedure(:TCCItemPtr) of object;
TCCActionProc = procedure(item:TCCItemPtr);
TCCBase = class(TObject)
...
procedure CallActionMethod(method: TCCActionMethod);
procedure CallActionProcedure(proc: TCCActionProc);
...
Delphi array types support
For delphi 4 and above, a read-only single index dynamic array type property is provided by the Array-based containers. Its up to the derived class to provide the property. A psuedo reference count and array-size storage compatible with delphi is maintained before the beginning of the array. There is one serious potential error, in that if the Array object is freed in the same procedure or function that the dynamic array property is referenced, even in the last statement, then a memory access error will occur as Delphi attempts to dereference the array property during its own procedure exit code.