Twitter  Facebook  YouTube  E-Mail  RSS
The One Man MMO Project
The story of a lone developer's quest to build an online world :: MMO programming, design, and industry commentary
Templates are Baffling No More
By Robert Basler on 2011-01-14 12:24:26
Homepage: www.onemanmmo.com email:one at onemanmmo dot com

I never learned about C++ templates in school. I mostly learned Pascal. Then I went on to C and never really understood the need for templates when I started using C++ features. When I was working at EA, templates were effectively banned for game code, but I was encouraged to read programming books featuring templates which enabled me to finally understand their appeal. And it is strong.

The problem with templates on console games is that the tools are crap. Yes, I'm looking at you SN and Codewarrior. Just try to use templates on older tools. It will make you very unhappy. The debugger will barf on them, and if you make an error implementing or using a template, you'll get the most spectacularly baffling error messages you've ever seen.

But this is why you want to learn templates: you will never have to code a linked list or circular queue, or map again. Evaaaaaaaar! The other night, I wrote the last circular queue I should ever have to write in C++, it goes like this:

// Copyright 2010 Robert Basler
//! file circularqueue.h

#ifndef CIRCULAR_QUEUE_H
#define CIRCULAR_QUEUE_H

#include "tasks/safespinlock.h"
#include "memory/memory.h"
#include "exceptions/exception.h"

// brief CircularQueue - circular queue template
namespace Lair
{
    static const fourcc CIRCULAR_QUEUE_POOL = 'cirp';
}

template < class T > class CircularQueue 
{
public:
    CLASS_MEMORY_OPERATORS( Lair::CIRCULAR_QUEUE_POOL );

    //! brief Create a circular queue with an optional spinlock.  Specify max entries in queue
    CircularQueue( unsigned int maxEntries, Lair::Spinlock* lock = NULL )
        : mMaxEntries( maxEntries + 1 ) // We lose one entry to 'full' status, so increase size by one.
        , mHead( 0 )
        , mTail( 0 )
        , mSpinLock( lock )
        , mData( new T[ mMaxEntries ] )
    {
        ASSERT( mMaxEntries > 0 );
    }

    virtual ~CircularQueue( void )
    {
        delete[] mData;
        mData = NULL;
    }

    //! brief Return true if queue is empty.
    bool Empty( void ) const
    {
        Lair::SafeSpinLock lock( mSpinLock, true );
        return mHead == mTail;
    }

    //! brief Return true if queue is full.
    bool Full( void ) const
    {
        Lair::SafeSpinLock lock( mSpinLock, true );
        return mTail == ( ( mHead + 1 ) % mMaxEntries );
    }

    //! brief Insert item into circular queue.
    void Insert( const T& item )
    {
        Lair::SafeSpinLock lock( mSpinLock, true );
        if ( mTail == ( ( mHead + 1 ) % mMaxEntries ) )
        {
            throw Lair::Exception( EXCEPTION_DEFAULT_INFO, L"Can't insert into full Circular Queue" );
        }
        mHead = ( mHead + 1 ) % mMaxEntries;
        mData[ mHead ] = item;
    }

    //! brief Remove item from circular queue.
    void Remove( T& item )
    {
        Lair::SafeSpinLock lock( mSpinLock, true );
        if ( mHead == mTail )
        {
            throw Lair::Exception( EXCEPTION_DEFAULT_INFO, L"Can't remove from empty Circular Queue" );
        }
        mTail = ( mTail + 1 ) % mMaxEntries;
        item = mData[ mTail ];
    }

    //! brief Clear all entries from the circular queue.
    void Clear( void )
    {
        Lair::SafeSpinLock lock( mSpinLock, true );
        mHead = mTail = 0;
    }

    //! brief Return size of queue (number of entries)
    unsigned int Size( void ) const
    {
        Lair::SafeSpinLock lock( mSpinLock, true );
        if ( mHead >= mTail )
        {
            return mHead - mTail;
        }
        return mMaxEntries - mTail + mHead;
    }
private:
    unsigned int mMaxEntries;       // Maximum number of entries in queue
    unsigned int mHead;             // Index of head of queue.
    unsigned int mTail;             // Index of tail of queue.
    T* mData;                       // Pointer to queue storage.
    Lair::Spinlock* mSpinLock;      // Spinlock, may be NULL if unused.
};

#endif

How cool is that?

To use it, I just do something like this:

CircularQueue< int >* intQueue = new CircularQueue< int >( 64 );
intQueue->Insert( 5 );
int x;
intQueue->Remove(x);
delete intQueue;

And I can do the same thing with any class so long as it implements operator =.

There are of course dangers in using templates. Because compilers implement functions for every type that you use with them, there is a danger that your program will bloat out with dozens or hundreds of copies of basically the same function for different types. This is known as template bloat. In most cases, template bloat can be minimized with careful design of your template. All that needs to be done is to use generic types (void*) internally for most things, with a few type-specific accessor functions which will be duplicated. In the circularqueue above, the constructor, destructor, Insert and Remove will be duplicated, all the rest of the functionality is generic. I could reduce the amount of code duplicated in insert and remove by pulling all but the first and last lines of each function into separate internal utility functions; although in this case, it isn't much code and probably isn't worth complicating the code, or the development effort.

In addition to template classes, template functions are another feature of C++ that are also über-cool and useful. Suppose you have a base class and a number of child classes, check out this handy little gem:

        static Asset* Get( const char * const assetName );

        //! brief Retrieve a correctly typed asset synchronously by name
        template < class AssetClass > static AssetClass* Get( const char * const assetName )
        {
            return static_cast< AssetClass* >( Get( assetName ) );
        };

You'll never have to return-type a call to Get again. The compiler will always return the correct type based on the type you are assigning the result of Get to. Nice!

I mentioned tools before as a huge problem with templates. I'm using Visual Studio 2010 (2005 works just as well in my experience) and while I still get the odd confusing template compile error, if I slow down and read the long mess of information the error gives, it is easy to figure out what the issue is. Debugging is no problem, it quite happily traces into template code.

Maybe even a bigger problem with templates than the tools is that people have abused them and created some godawful spaghetti code. Template code can be worse than the worst spaghetti you can create with the preparser. Combined with crap tools, that has really given templates a bad rep. But templates don't have to be evil. Look at the circular queue code above, it is pretty straightforward. You can parse it. Go write good template code.

I have to mention a couple of the better template libraries: STL (Standard Template Library) which comes with most compilers and Boost which has an amazing breadth of features. Both of these libraries are spectacular, and worthwhile learning more about. They will save you coding time. There is even EASTL which is open source from EA and aimed squarely at use in games. (You won't find a direct download link there, but EASTL is included in a number of the packages you can download.)

I will disclose that I don't use those libraries in my current project -- my template needs are fairly simple, and I prefer to minimize large library use, so I've written the few templates I use myself. (Granted I occasionally crib looks at how these libraries implement their templates.)

Learn templates. Go out and teach new programmers about them.

Want to learn more? Check out the free downloadable book Thinking in C++ (Chapter 16) or get Stroustrep's "The C++ Programming Language".

By Robert Basler on 2012-02-23 10:35:34
Homepage: www.onemanmmo.com email:one at onemanmmo dot com
Aw heck, I did someone's CS homework! :) Found this search in our web report:

write a template class circularqueue in c .

New Comment

Cookie Warning

We were unable to retrieve our cookie from your web browser. If pressing F5 once to reload this page does not get rid of this message, please read this to learn more.

You will not be able to post until you resolve this problem.

Comment (You can use HTML, but please double-check web link URLs and HTML tags!)
Your Name
Homepage (optional, don't include http://)
Email (optional, but automatically spam protected so please do)
Type boy. (What's this?)

  Admin Log In



[The Imperial Realm :: Miranda] [Blog] [Gallery] [About]
Terms Of Use & Privacy Policy