Game Engine Architecture

235

template< typename ELEMENT >

struct Link

{

Link<ELEMENT>* m_pPrev;

Link<ELEMENT>* m_pNext;

ELEMENT* m_pElem;

};

Extrusive Lists

An extrusive list is a linked list in which the Link data structures are entirely
separate from the element data structures. Each Link contains a pointer to the
element, as shown in the example. Whenever an element is to be inserted into
a linked list, a link is allocated for it, and the pointers to the element and the
next and previous links are set up appropriately. When an element is removed
from a linked list, its link can be freed.
The benefi t of the extrusive design is that an element can reside in mul-
tiple linked lists simultaneously—all we need is one link per list. The down
side is that the Link objects must be dynamically allocated. Oft en a pool al-
locator (see Section 5.2.1.2) is used to allocate links, because they are always
exactly the same size (viz., 12 bytes on a machine with 32-bit pointers). A pool
allocator is an excellent choice due to its speed and its freedom from fragmen-
tation problems.

Intrusive Lists

An intrusive list is a linked list in which the Link data structure is embedded
in the target element itself. The big benefi t of this approach is that we no lon-
ger need to dynamically allocate the links—we get a link “for free” whenever
we allocate an element. For example, we might have:

classSomeElement

{

Link<SomeElement> m_link;

// other members...

};

We can also derive our element class from class Link. Using inheri-
tance like this is virtually identical to embedding a Link as the fi rst member
of the class, but it has the additional benefi t of allowing a pointer to a link
(Link) to be down-cast into a pointer to the element itself
(SomeElement). This means we can eliminate the back-pointer to the ele-
ment that would otherwise have to be embedded within the Link. Here’s how
such a design might be implemented in C++.

5.3. Containers