Method
The job of a resource manager is to create resources on demand, hand them out to anyone who asks, and then eventually delete them. Handing out those resources as simple pointers is certainly easy and convenient, but it’s not a very safe way to do it. Pointers can “dangle” – one part of the system may tell the resource manager to delete a resource, which then immediately invalidates all other outstanding pointers. There’s no good way to prevent the dangling pointer problem from happening, and the only way we would find out that someone was attempting to dereference a deleted object is when the access violation dialog box comes up and the game crashes. The problem is that, with pointers, there’s no way to know how many references are outstanding, given that clients can copy the pointers as many times as they like without telling the manager about it.
Another problem is that the underlying data organization can’t change with pointers. Any reallocation of buffers would immediately invalidate all outstanding pointers. This becomes especially important with saving the game to disk. Pointers can’t be saved to disk because the next time the game is loaded, system memory will probably be configured differently or we may even be on a completely different machine. The pointers must be converted into a form that can be restored, which will probably be an offset or a unique identifier of some sort. Working around this problem isn’t exactly trivial and can require a lot of work to support in client code.
So it’s plainly not a good idea for a safe and flexible resource manager to be handing out pointers. Rather than using pointers, or attempting to write some kind of super-intelligent over-complicated “smart pointer”, we can add one layer of abstraction and use handles instead, and put the burden on the manager class. Handles are an ancient programming concept that API’s have been using with great success for decades. An example of this is the HANDLE type returned by the CreateFile() call in Win32’s file system. A file handle, representing an open file system object, is created through the CreateFile() call, passed to other functions such as ReadFile() and SetFilePointer() for manipulation, and then finally closed off with CloseHandle(). Attempting to call those functions with an invalid or closed handle will not cause a crash, but will instead return an error code. This method is efficient, safe, and easy to understand.
Handles almost always fit into a single CPU register for efficient storage in collections and passing as parameters to functions. They can be easily checked for validity and provide a level of indirection that allows the underlying data organization to change without invalidating any outstanding handles. This has significant advantages over passing around pointers. Handles can also be easily saved to disk, because the data structures they refer to can be reconstructed in the same order on a game restore. This allows the handles to be stored directly with no conversions necessary, because they are already natively in unique identifier form.
The Handle Class
A fast and safe way to represent handles is to use an unsigned integer composed of two bitfield components (this class appears in Listing 1). The first component (m_Index) is a unique identifier for fast dereferencing into the handle manager’s database. The handle manager can use this number however it likes, but perhaps the most efficient is as a simple index into an std::vector. The second component (m_Magic) is a “magic number” that can be used to validate the handle. Upon dereferencing, the handle manager can check to make sure that the magic number component of the handle matches up with its corresponding entry in the database.
The Handle class is very simple and really doesn’t do much except manage the magic number. Upon calling Init(), the handle will be given the next magic number, which auto increments and will wrap around if necessary. Note that the magic number is not intended to be a GUID. Its purpose is to serve as a very simple and fast validity check and is relying on the high improbability of a condition arising where one object happens to have the same index and magic number (via wrapping) as another. The magic number of zero is reserved for the “null handle” – where the handle’s data is zero. The default Handle constructor sets itself to null, a state that will return true on an IsNull() query. This is convenient to use for an error condition – a function that creates an object and returns a handle to it can just return a null handle to indicate an error occurred.
In most ways the Handle class will act as a read-only unsigned integer. It’s not intended to be modified after being created, though it can safely be assigned back to null to reset it. You’ll notice that it’s a parameterized class, taking a TAG type in order to fully define it. The template parameter TAG doesn’t do anything except differentiate among types of handles – an object of type TAG is never used anywhere in the system. The motivation here is type safety. Without parameterizing Handle, a handle meant for one type of resource could be passed to a function expecting a handle to a different type of resource without a complaint from the compiler. So to keep things safe, we create a new handle type, taking any unique symbol and using it for the parameter. The TAG type can really be anything so long as it’s unique across Handle types, but it’s convenient to define an empty struct and use that in the typedef for a handle, like this texture handle example:
typedef Handle <tagTexture> HTexture; |
Now we need a handle manager that is responsible for acquiring, dereferencing, and releasing objects (via handles) for a higher-level owner.
The HandleMgr Class
The HandleMgr class is a parameterized type composed of three main elements: a data store, a magic number store, and a free list (this class appears in Listing 2). The data store is simply a vector (or any other randomly accessible collection) of objects of type DATA. The DATA type, the first type parameter for HandleMgr, should be a very simple class that contains context information about the resource that it controls. For example, in a HandleMgr that manages files, the DATA type would probably just have the file handle and the name of the file:
HANDLE m_FileHandle; // OS file handle |
typedef Handle <tagFile> HFile; |
typedef HandleMgr <FileEntry, HFile> FileHandleMgr; |
This simple handle manager will maintain a set of context objects that correspond to all the open files that it knows about. The FileHandleMgr class will probably not be used directly by clients, but will instead be owned by another class (call it FileMgr) that handles the abstraction and knows about the problem domain (that is, what DATA is supposed to represent). This class might look something like this:
HFile OpenFile ( const char * name ); |
bool ReadFile ( HFile file, void * out, size_t bytes ); |
bool CloseFile( HFile file ); |
Upon calling any of these methods, FileMgr will ask its m_Mgr to dereference the handle to get at the actual FileEntry object. After verifying that the dereference succeeded (it will fail on an invalid handle), it will then perform the operation.
For our HandleMgr class, each handle will reference exactly one element within the object store, plus its corresponding element in the magic number store. Dereferencing the handles to get at the actual FileEntry object is as simple as using the m_Index component of the handle as an index into the object store (a very fast operation).
When dereferencing the handle, the code will also check the m_Magic component against the same index in the magic number store to make sure the handle is valid. As handles are freed and reacquired, corresponding entries in the magic number store are updated with the new handle magic numbers. This nearly guarantees that “dangling” handles on released objects won’t refer to unexpected objects when the slots are filled by a later handle acquisition, but will instead simply fail to work and return an error code. Obviously, the magic number store will always have the same number of elements as the object store.
As objects are released, the handle manager will add the indexes of the slots they occupy to the free list. This saves it the trouble of needing to search through the object store to find an open slot, which results in a tasty O(n) complexity for new handle acquisition. It’s important to note that the DATA type is not your typical C++ class. It shouldn’t have constructors and destructors that do anything important, such as acquire and release local resources. Objects contained within the object store are constructed, destroyed, and copied as the vector class sees fit. Note that the std::string used in the sample FileEntry is “simple” enough for our needs – it’s reference-counted, which minimizes the impact of its constructors and destructors and makes it nearly free for vector to copy.
When asked to acquire an object from the store, we’ll likely end up reusing an object that has already been constructed but is no longer in use, as indicated by its entry in the free list. It will need its members reinitialized before it can be used, because it won’t have had the constructor call to set it up. When an object is freed from the store, it will not get destroyed, but will instead have its index added to the free list, and as such will need its resources manually freed. These minor limitations arise from the fact that we’re embedding our DATA type directly in the vector, rather than using pointers and creating and destroying the objects with new and delete for each handle acquisition and release. The major advantage here is speed, in that the objects don’t have to be completely brought up and shut down each time. To make things more convenient, the initialize/shutdown code can be moved into member functions for easy callback by the HandleMgr owner.
The amount of handle validation necessary may depend on the application, and could even be chosen through an additional template parameter for HandleMgr. For example, the test for an invalid handle may be found to be unnecessary and could be removed (though the debug assertion should always remain). For a more robust system where error handling is important, the code could, upon detecting an invalid handle, set an error condition, and then abort the function call.
Sample Usage
In Listing 3 I provide a sample texture manager class. This class allows clients to ask it for textures by name and will construct them on demand. It automatically unloads the textures on deletion, and provides a set of query functions to use the textures. The textures are indexed by name for speedy lookup to make sure that the same texture is not added to the store twice. It would be a simple exercise to add reference counting to this example to make it safer, replacing DeleteTexture() with ReleaseTexture().
For another (larger) sample of file handle usage, see the sample code for my GDC 2000 talk, It’s Still Loading? Designing an Efficient File System.
Notes
The HandleMgr class is very simple and is meant to illustrate some basic concepts, but it can be expanded in a number of ways, either with the existing HandleMgr or separate classes:
- Create a HandleMgr that will work better with larger DATA objects, holding them indirectly through pointers. It would also allow hiding of the data structure to clients.
- Add automatic reference counting as standard functionality, rather than leaving it to be the responsibility of the owner of the HandleMgr.
- Add support for constant-time iteration over the potentially sparse object store by embedding a linked list within its elements. Use STL style iterator naming and operation for consistency.
- Many databases, such as a font manager or texture manager, will likely require indexes to access objects by name to retrieve handles. Build this in as a standard feature or as a separate (derivative) class.
- The HandleMgr system is especially effective when combined with the Singleton pattern (see “An Automatic Singleton Utility” elsewhere in this book). Many of a game’s databases are naturally singletons.
- Take the Singleton pattern a little further, and make the TAG type of Handle actually be the type that it corresponds to within the HandleMgr. Then the Handle could have an operator -> that would dereference itself into a TAG by directly accessing the Singleton that manages it.
- Save game functionality should be fairly easy to add, but it is necessarily specific to your game’s architecture. The handles can be saved out directly – just make sure that the HandleMgr stores the indexes for its objects along with the object data, and on restore, all handles will remain valid.
// sizes to use for bit fields |
// sizes to compare against for asserting dereferences |
MAX_INDEX = ( 1 << MAX_BITS_INDEX) - 1, |
MAX_MAGIC = ( 1 << MAX_BITS_MAGIC) - 1, |
unsigned m_Index : MAX_BITS_INDEX; // index into resource array |
unsigned m_Magic : MAX_BITS_MAGIC; // magic number to check |
Handle( void ) : m_Handle( 0 ) { } |
void Init( unsigned int index ); |
unsigned int GetIndex ( void ) const { return ( m_Index ); } |
unsigned int GetMagic ( void ) const { return ( m_Magic ); } |
unsigned int GetHandle( void ) const { return ( m_Handle ); } |
bool IsNull ( void ) const { return ( !m_Handle ); } |
operator unsigned int ( void ) const { return ( m_Handle ); } |
void Handle <TAG> :: Init( unsigned int index ) |
assert ( IsNull() ); // don't allow reassignment |
assert ( index <= MAX_INDEX ); // verify range |
static unsigned int s_AutoMagic = 0; |
if ( ++s_AutoMagic > MAX_MAGIC ) |
s_AutoMagic = 1; // 0 is used for "null handle" |
inline bool operator != ( Handle <TAG> l, Handle <TAG> r ) |
{ return ( l.GetHandle() != r.GetHandle() ); } |
inline bool operator == ( Handle <TAG> l, Handle <TAG> r ) |
{ return ( l.GetHandle() == r.GetHandle() ); } |
template < typename DATA, typename HANDLE > |
typedef std::vector <DATA> UserVec; |
typedef std::vector <unsigned int > MagicVec; |
typedef std::vector <unsigned int > FreeVec; |
UserVec m_UserData; // data we're going to get to |
MagicVec m_MagicNumbers; // corresponding magic numbers |
FreeVec m_FreeSlots; // keeps track of free slots in the db |
DATA* Acquire( HANDLE & handle ); |
void Release( HANDLE handle ); |
DATA* Dereference( HANDLE handle ); |
const DATA* Dereference( HANDLE handle ) const ; |
unsigned int GetUsedHandleCount( void ) const |
{ return ( m_MagicNumbers.size() - m_FreeSlots.size() ); } |
bool HasUsedHandles( void ) const |
{ return ( !!GetUsedHandleCount() ); } |
template < typename DATA, typename HANDLE > |
DATA* HandleMgr <DATA, HANDLE > :: Acquire( HANDLE & handle ) |
// if free list is empty, add a new one otherwise use first one found |
if ( m_FreeSlots.empty() ) |
index = m_MagicNumbers.size(); |
m_UserData.push_back( DATA() ); |
m_MagicNumbers.push_back( handle.GetMagic() ); |
index = m_FreeSlots.back(); |
m_MagicNumbers[ index ] = handle.GetMagic(); |
return ( m_UserData.begin() + index ); |
template < typename DATA, typename HANDLE > |
void HandleMgr <DATA, HANDLE > :: Release( HANDLE handle ) |
unsigned int index = handle.GetIndex(); |
assert ( index < m_UserData.size() ); |
assert ( m_MagicNumbers[ index ] == handle.GetMagic() ); |
// ok remove it - tag as unused and add to free list |
m_MagicNumbers[ index ] = 0; |
m_FreeSlots.push_back( index ); |
template < typename DATA, typename HANDLE > |
inline DATA* HandleMgr <DATA, HANDLE > |
:: Dereference( HANDLE handle ) |
if ( handle.IsNull() ) return ( 0 ); |
// check handle validity - $ this check can be removed for speed |
// if you can assume all handle references are always valid. |
unsigned int index = handle.GetIndex(); |
if ( ( index >= m_UserData.size() ) |
|| ( m_MagicNumbers[ index ] != handle.GetMagic() ) ) |
// no good! invalid handle == client programming error |
return ( m_UserData.begin() + index ); |
template < typename DATA, typename HANDLE > |
inline const DATA* HandleMgr <DATA, HANDLE > |
:: Dereference( HANDLE handle ) const |
// this lazy cast is ok - non-const version does not modify anything |
typedef HandleMgr <DATA, HANDLE > ThisType; |
return ( const_cast <ThisType*> ( this )->Dereference( handle ) ); |
// ... [ platform-specific surface handle type here ] |
typedef LPDIRECTDRAWSURFACE7 OsHandle; |
typedef Handle <tagTexture> HTexture; |
// Texture object data and db. |
typedef std::vector <OsHandle> HandleVec; |
std::string m_Name; // for reconstruction |
unsigned int m_Width; // mip 0 width |
unsigned int m_Height; // mip 1 width |
HandleVec m_Handles; // handles to mip surfaces |
OsHandle GetOsHandle( unsigned int mip ) const |
assert ( mip < m_Handles.size() ); |
return ( m_Handles[ mip ] ); |
bool Load ( const std::string& name ); |
typedef HandleMgr <Texture, HTexture> HTextureMgr; |
// Index by name into db. |
// case-insensitive string comparison predicate |
bool operator () ( const std::string& l, const std::string& r ) const |
{ return ( ::stricmp( l.c_str(), r.c_str() ) < 0 ); } |
typedef std::map <std::string, HTexture, istring_less > NameIndex; |
typedef std::pair <NameIndex::iterator, bool > NameIndexInsertRc; |
TextureMgr( void ) { /* ... */ } |
HTexture GetTexture ( const char * name ); |
void DeleteTexture( HTexture htex ); |
const std::string& GetName( HTexture htex ) const |
{ return ( m_Textures.Dereference( htex )->m_Name ); } |
int GetWidth( HTexture htex ) const |
{ return ( m_Textures.Dereference( htex )->m_Width ); } |
int GetHeight( HTexture htex ) const |
{ return ( m_Textures.Dereference( htex )->m_Height ); } |
OsHandle GetTexture( HTexture htex, unsigned int mip = 0 ) const |
{ return ( m_Textures.Dereference( htex )->GetOsHandle( mip ) ); } |
TextureMgr :: ~TextureMgr( void ) |
// release all our remaining textures before we go |
NameIndex::iterator i, begin = m_NameIndex.begin(), end = m_NameIndex.end(); |
for ( i = begin ; i != end ; ++i ) |
m_Textures.Dereference( i->second )->Unload(); |
HTexture TextureMgr :: GetTexture( const char * name ) |
m_NameIndex.insert( std::make_pair( name, HTexture() ) ); |
// this is a new insertion |
Texture* tex = m_Textures.Acquire( rc.first->second ); |
if ( !tex->Load( rc.first->first ) ) |
DeleteTexture( rc.first->second ); |
rc.first->second = HTexture(); |
return ( rc.first->second ); |
void TextureMgr :: DeleteTexture( HTexture htex ) |
Texture* tex = m_Textures.Dereference( htex ); |
m_NameIndex.erase( m_NameIndex.find( tex->m_Name ) ); |
m_Textures.Release( htex ); |
bool TextureMgr::Texture :: Load( const std::string& name ) |
// ... [ load texture from file system, return false on failure ] |
return ( true /* or false on error */ ); |
void TextureMgr::Texture :: Unload( void ) |
// ... [ free up mip surfaces ] |