Someone may find this useful. I wrote this class tonight because I wanted it for what I'm working on right now. It has some scary pointer manipulation in it, but don't worry. I don't know of any bugs in it (yet).
A dead/live list is a very fast way of allocating and releasing records of the same type. It pre-allocates a block of memory, then for each record within this block of memory it adds the record to a dead list. A call to Alloc() to get the next free record simply grabs the first record from the dead list. This record is then added to the live list. When a record is released, it is simply moved from the live list to the dead list, ready to be re-used.
So instead of allocating and deallocating memory for each instance of the record, this class allocates them in large blocks and then manages that block for you. If you use up that entire block, the next time you call Alloc() it will allocate another large block and manage that one for you.
constructor Create(RecordSize: Cardinal; Capacity: Cardinal);
Initializes all members and allocates the first block. RecordSize is the size of an individual record, eg. SizeOf(TMyRecord). Capacity is the number of records to be allocated in each block.
function Alloc: Pointer;
Returns a pointer to the next free record.
procedure Release(Data: Pointer);
Releases the record back to the dead list.
function GetNext(Data: Pointer): Pointer;
Used to iterate through all live records. Pass nil to get the first live record. Pass that pointer back in to get the next live record.
This unit uses DonkMem, which at the moment is just a wrapper around GetMem, ReallocMem and FreeMem, but will eventually be a replacement memory manager. I have included DonkMem at the end.
I hope someone finds it useful.
P.S. 'Donk' is the name of my engine.
DonkList.pas[pascal]unit DonkList;
interface
type
PDKDeadLiveChunk = ^TDKDeadLiveChunk;
TDKDeadLiveChunk = record
Next: PDKDeadLiveChunk;
end;
PDKDeadLiveNode = ^TDKDeadLiveNode;
TDKDeadLiveNode = record
Next, Prev: PDKDeadLiveNode;
end;
TDKDeadLiveList = class
private
FRecordSize: Cardinal;
FCapacity: Cardinal;
FLive: PDKDeadLiveNode;
FDead: PDKDeadLiveNode;
FChunk: PDKDeadLiveChunk;
procedure Grow;
public
constructor Create(RecordSize, Capacity: Cardinal);
destructor Destroy; override;
function Alloc: Pointer;
procedure Release(Data: Pointer);
function GetNext(Data: Pointer): Pointer;
end;
implementation
{
The dead/live list is composed of a series of chunks. These chunks are pre-
allocated to fit the capacity and record size given in the constructor. An
initial chunk is allocated, and when a new record is to be allocated and the
dead list is empty, another chunk is allocated.
A chunk is constructed like this:
Offset Size Description
0000 4 Pointer to the next chunk
0004 RecordSize + 8 A record plus the pointers for next/prev node
...
}
uses
DonkMem;
{ TDKDeadLiveList }
{
Grab a record from the dead list and add it to the live list. Return this
record to the caller.
}
function TDKDeadLiveList.Alloc: Pointer;
var
Node: PDKDeadLiveNode;
begin
{ No nodes left in the dead list, so allocate another chunk }
if FDead = nil then
Grow;
{ Grab the first node from the dead list }
Node := FDead;
{ Unlink the node from the dead list }
FDead := Node^.Next;
if FDead <> nil then
FDead^.Prev := nil;
{ Link the node to the live list }
Node^.Next := FLive;
if FLive <> nil then
FLive^.Prev := Node;
FLive := Node;
{ Return the pointer to the actual record }
Alloc := Pointer(Cardinal(Node) + SizeOf(TDKDeadLiveNode));
end;
{
Constructor for the list. Set the parameters for the list.
}
constructor TDKDeadLiveList.Create(RecordSize, Capacity: Cardinal);
begin
FRecordSize := RecordSize;
FCapacity := Capacity;
FLive := nil;
FDead := nil;
FChunk := nil;
{ Allocate the initial chunk }
Grow;
end;
{
Release a record back to the list. This will move it from the live list to
the dead list.
}
procedure TDKDeadLiveList.Release(Data: Pointer);
var
Node: PDKDeadLiveNode;
begin
Node := PDKDeadLiveNode(Cardinal(Data) - SizeOf(TDKDeadLiveNode));
{ Unlink the node from the live list }
if FLive <> Node then
begin
if Node^.Prev <> nil then
Node^.Prev^.Next := Node^.Next;
if Node^.Next <> nil then
Node^.Next^.Prev := Node^.Prev;
end
else
begin
FLive := FLive^.Next;
if FLive <> nil then
FLive^.Prev := nil;
Node^.Next := nil;
end;
{ Link the node to the dead list }
Node^.Next := FDead;
Node^.Prev := nil;
if FDead <> nil then
FDead^.Prev := Node;
FDead := Node;
end;
{
Free all memory allocated by the list
}
destructor TDKDeadLiveList.Destroy;
var
NextChunk: PDKDeadLiveChunk;
begin
// Assert(FLive = nil, 'Not all records were freed in the dead/live list');
{ Free all the chunks }
while FChunk <> nil do
begin
NextChunk := FChunk^.Next;
DKMem_Free(FChunk);
FChunk := NextChunk;
end;
inherited;
end;
{
Populate the dead list with another chunk
}
procedure TDKDeadLiveList.Grow;
var
NewChunk, PrevChunk: PDKDeadLiveChunk;
Node, NextNode, PrevNode: PDKDeadLiveNode;
Index: Integer;
begin
Assert(FDead = nil, 'Dead list is not empty');
NewChunk := PDKDeadLiveChunk(DKMem_Alloc((FRecordSize + SizeOf(TDKDeadLiveNode)) * FCapacity + SizeOf(TDKDeadLiveChunk)));
NewChunk^.Next := nil;
{ Add this chunk to the list of existing chunks }
if FChunk <> nil then
begin
PrevChunk := FChunk;
while FChunk^.Next <> nil do
PrevChunk := FChunk^.Next;
PrevChunk^.Next := NewChunk;
end
else
begin
FChunk := NewChunk;
end;
{ Set the dead list to point to the first node in the new chunk }
Node := PDKDeadLiveNode(Cardinal(FChunk) + SizeOf(TDKDeadLiveChunk));
FDead := Node;
{ Initialise the next/prev links for all the nodes }
PrevNode := nil;
for Index := 0 to FCapacity - 1 do
begin
NextNode := PDKDeadLiveNode(Cardinal(Node) + SizeOf(TDKDeadLiveNode) + FRecordSize);
Node^.Prev := PrevNode;
Node^.Next := NextNode;
PrevNode := Node;
Node := NextNode;
end;
Node^.Next := nil;
end;
{
Get the next record in the live list. If Data is nil, the first record in
the live list is returned.
}
function TDKDeadLiveList.GetNext(Data: Pointer): Pointer;
begin
if Data <> nil then
begin
GetNext := Pointer(Cardinal(PDKDeadLiveNode(Cardinal(Data) - SizeOf(TDKDeadLiveNode))^.Next) + SizeOf(TDKDeadLiveNode));
end
else
begin
GetNext := Pointer(Cardinal(FLive) + SizeOf(TDKDeadLiveNode));
end;
end;
end.[/pascal]
DonkMem.pas[pascal]unit DonkMem;
interface
function DKMem_Alloc(Size: Cardinal): Pointer;
function DKMem_Realloc(Block: Pointer; Size: Cardinal): Pointer;
procedure DKMem_Free(Block: Pointer);
implementation
uses
SysUtils;
function DKMem_Alloc(Size: Cardinal): Pointer;
var
Block: Pointer;
begin
GetMem(Block, Size);
DKMem_Alloc := Block;
end;
function DKMem_Realloc(Block: Pointer; Size: Cardinal): Pointer;
begin
ReallocMem(Block, Size);
DKMem_Realloc := Block;
end;
procedure DKMem_Free(Block: Pointer);
begin
FreeMem(Block);
end;
end.[/pascal]
Reply With Quote
Bookmarks