Dead/live list data structure

[Sly]

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.pasunit 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.

DonkMem.pasunit 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.

[cairnswm]

Just add a SaveToFile and a Load from File and you have an in memory database :)

[Sly]

That could be done, but there are some caveats that would need to be properly handled. For example, the next/prev links between records and the link to the next block. Pointers can not be simply written to disk and retrieved. They would have to converted to pointers to offsets when written, and then converted from offsets to pointers when read. If the records themselves contained pointers, how would they be handled?

I was thinking about the replacement routines for memory management while in the shower this morning (why is it that the best ideas come about while either in the shower or just as you are going to sleep?) and realised that I was going about it the wrong way. In the System unit there is a function to replace the memory manager, and there are also better memory managers out there already, such as FastMM. I'll fix that when I get home tonight.

[cairnswm]

My best ideas always come when I am not near a PC - on holiday where there is no power, or driving in rush hour traffic.

My bath time is the only really quiet time I have in a day - I usually spend it thinking about my family instead of work/game dev :)

[Sly]

Here's an improved version. Replaced the calls to DKMem with the standard memory allocation calls (now it has zero external dependencies), and fixed a bug in GetNext (it was not checking properly for the end of the list).

I forgot to mention in the original post that it should also work out-of-the-box in FPC, so I tried it and found that because it used the 'class' type, it required Delphi mode to be enabled. So I added that too.

Edit: Fixed the GetNext function again. It couldn't handle the case where no records had been allocated yet. One day I will learn to test these things more fully.

unit DonkList;

{$IFDEF FPC}
{$MODE DELPHI}
{$ENDIF FPC}

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
...
}

{ 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;
FreeMem(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');
GetMem(NewChunk, (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;
var
Node: PDKDeadLiveNode;
begin
if Data <> nil then
begin
Node := PDKDeadLiveNode(Cardinal(Data) - SizeOf(TDKDeadLiveNode));
if Node^.Next <> nil then
GetNext := Pointer(Cardinal(Node^.Next) + SizeOf(TDKDeadLiveNode))
else
GetNext := nil;
end
else if FLive <> nil then
begin
Result := Pointer(Cardinal(FLive) + SizeOf(TDKDeadLiveNode));
end
else
begin
Result := nil;
end;
end;

end.

[Sly]

Ewww... had an off-by-one bug in there that caused the obscure 'Invalid pointer operation' exception. In the Grow method, replace for Index := 0 to FCapacity - 1 do
with for Index := 0 to FCapacity - 2 do
and add Node^.Prev := PrevNode;
after the for loop.