On the positive side, now that we've added an indirection (index to pointer, pointer to data), we could relocate the data, update the pointer in the array, and all the indices would still be valid. We could even delete the data and null the pointer out to indicate it is gone. Unfortunately, what we can't do is reuse a slot in the array since we don't know if there's any data out there using that particular index still referring to the old data.

Because of these drawbacks, indices into an array of pointers is usually not an effective way to keep references to data. It's usually better to stick with indices into an array of data, or extend the idea a bit further into a handle system, which is much safer and more versatile.

Handle-ing the Problem

Handles are small units of data (32 bits typically) that uniquely identify some other part of data. Unlike pointers, however, handles can be safely serialized and remain valid after they're restored. They also have the advantages of being updatable to refer to data that has been relocated or deleted, and being possible implement with minimal performance overhead.

The handle is used as a key into a handle manager, which associates handles with their data. The simplest possible implementation of a handle manager is a list of handle-pointer pairs and every lookup simply traverses the list looking for the handle. This would work but it's clearly very inefficient. Even sorting the handles and doing a binary search is slow and we can do much better than that.

An efficient implementation of a handle manager is available online at www.gdmag.com/resources/code.htm. The handle manager is implemented as an array of pointers, and handles are indices into that array. However, to get around the drawbacks of plain indices, handles are enhanced in a couple of ways.

Listing 1: The Handle Structure

struct Handle
{
Handle() : m_index(0), m_counter(0), m_type(0)
{}

Handle(uint32 index, uint32 counter, uint32 type)
: m_index(index), m_counter(counter), m_type(type)
{}

inline operator uint32() const;

uint32 m_index : 12;
uint32 m_counter : 15;
uint32 m_type : 5;
};

Handle::operator uint32() const
{
return m_type < < 27 | m_counter < < 12 | m_index;
}

In order to make handles more useful than pointers, we're going to use up different bits for different purposes (see Listing 1). We have a full 32 bits to play with, so this is how we're going to carve them out (see Figure 1):

Figure 1: 32 bit handle.

The index field. These bits will make up the actual index into the handle manager, so going from a handle to the pointer is a very fast operation. We should make this field as large as we need to, depending on how many handles we plan on having active at once. 14 bits give us over 16,000 handles, which seems plenty for most applications. But if you really need more, you can always use up a couple more bits and get up to 65,000 handles.

The counter field. This is the key to making this type of handle implementation work. We want to make sure we can delete handles and reuse their indices when we need to. But if some part of the game is holding on to a handle that gets deleted -- and eventually that slot gets reused with a new handle -- how can we detect that the old handle is invalid?

The counter field is the answer. This field contains a number that goes up every time the index slot is reused. Whenever the handle manager tries to convert a handle into a pointer, it first checks that the counter field matches with the stored entry. Otherwise, it knows the handle is expired and returns null.

The type field. This field indicates what type of data the pointer is pointing to. There are usually not that many different data types in the same handle manager, so 6-8 bits are usually enough. If you're storing homogeneous data, or all your data inherits from a common base class, then you might not need a type field at all.