4 replies to this topic

[bladder]

Heh, I was just going to show someone a technique for object management, but that person went offline and I had written the sample skeleton code, so here it is.

This is a pretty easy technique to use. People do know about it, but many do not. The object manager keeps track of all your objects and allows you to retrieve them with using constant speed. It also makes sure that unused indices get used again. And it allows for tree like searches for the object.

Each object is given a handle. The handle is essentially an index into the object array store. Each object can optionally have a name. If you dont have the handle, you can find it by giving the name in O(log n) time.

Searches are not really necesasary, and if you want them, the only problem is that the time to remove an object will increase from O(1) to O(n). If that's not a problem, then searches can come in quite handy - especially for script/console systems.

Anyway, here's the code, with seaching commented out (not really coded)

#include <map>
#include <vector>
#include <iostream>
#include <string>

template< class T > class GenericManager;

template< class T >
class GenericHandle
{
    friend class GenericManager<T>;
    int m_index;

    GenericHandle( int i )
        : m_index(i)
    {}

public:

    GenericHandle()
        : m_index(-1)
    {}

    bool IsValid() const
    {
        return m_index != -1;
    }
};

template< class T >
class GenericManager
{
public:

    typedef GenericHandle<T> Handle_t;

    ~GenericManager()
    {
        DestroyAll();
    }

    Handle_t Create( const T& prototype )
    {
        int idx = 0;
        T* p = new T(prototype);

        if( m_freeStore.size() )
        {
            idx = m_freeStore.back();
            m_freeStore.pop_back();
            m_objectStore[idx] = p;
        }
        else
        {
            idx = m_objectStore.size();
            m_objectStore.push_back( p );
        }
        
        // m_mapStore[name] = idx;
        // name would be an std::string parameter passed to this function as well

        return Handle_t(idx);
    }


    void Destroy( Handle_t& h )
    {
        T* p = m_objectStore[h.m_index];

        if( p )
        {
            delete p;
            m_objectStore[h.m_index] = 0;
            m_freeStore.push_back( h.m_index );
        }

        // Here's where things get slow if search capabilities are added
        /*
        iterator i = mapStore.begin()
        for each i in map
            if( i->second == h.m_index )
                erase iterator i and break.
        */

        h.m_index = -1;
    }    

    void DestroyAll()
    {
        m_freeStore.clear();

        for( std::size_t i = 0; i < m_objectStore.size(); ++i )
        {
            if( m_objectStore[i] )
            {
                delete m_objectStore[i];
            }
        }

        m_objectStore.clear();
    }

    T* GetObject( Handle_t h ) const
    {
        if( !h.IsValid() )
            return 0;

        return m_objectStore[h.m_index];
    }

/*  Can have this function with search capabilities
    Handle_t GetHandle( string name )
    {
        iterator i = map.find(name);
        if( i != end ) return Handle_t(i->second);
        return Handle_t(-1);
    }
*/

private:
    std::vector<int> m_freeStore;
    std::vector<T*> m_objectStore;

    // std::map<std::string, int> m_mapStore; // for searching
};


class SomeObject
{
    std::string m_name;

public:

    SomeObject( const std::string& name )
        : m_name(name)
    {}

    SomeObject( const SomeObject& o )
    {
        m_name = o.m_name;
    }

    void Work()
    {
        std::cout << "I am " << m_name << std::endl;
    }
};

int main()
{
    typedef GenericManager<SomeObject> ObjMgr_t;

    ObjMgr_t mgr;

    ObjMgr_t::Handle_t h1 = mgr.Create( SomeObject("one") );
    ObjMgr_t::Handle_t h2 = mgr.Create( SomeObject("two") );
    ObjMgr_t::Handle_t h3 = mgr.Create( SomeObject("three") );
    
    mgr.Destroy( h3 );

    ObjMgr_t::Handle_t h4 = mgr.Create( SomeObject("four") );

    if( mgr.GetObject( h1 ) )
        mgr.GetObject( h1 )->Work();
    if( mgr.GetObject( h2 ) )
        mgr.GetObject( h2 )->Work();
    if( mgr.GetObject( h3 ) )
        mgr.GetObject( h3 )->Work();
    if( mgr.GetObject( h4 ) )
        mgr.GetObject( h4 )->Work();

/*
    Seaching would allow for something like:
    Handle = Manager.getHandle( "my object" );
*/

    return 0;
}

Of course there is a lot that can and probably should be added to this class for official usage. First off, I've skipped error checking almost completley. Maybe there's a way to make the object deleting even faster. I've found ways that require the alteration of the GenericHandle structure, but I wanted to leave that the size of an int. IF anyone can see a different solution I'm all ears.

[anubis]

pretty much resembles scott bilas generic resource manager (and my own resouce system for my current project :)). i first saw that thing in game programming gems 1. with a little extension it can become really handy. one useful addition for example is overloading the -> operator for the handle

[john]

nice piece of code. One improvment you can make is add RTTI capability, which shouldn't be hard the way you designed it. You can also extend the resource manager to support garbage collection via smart pointers. nice job!

[bladder]

hey yeah you're right. Scott bilas's also uses that free stack thing. But going over his article, it seems like that magic number stuff he uses is pretty unnecessary. But a good read none the less. I have GPG 1, but I never actually read that article completely - just the first few paragraphs or so...

John: those are some nice suggestions. There's a lot of room for imporovement and additions here. I just coded up the basic skeleton really quickly specifically to show what I meant to someone.

Smart pointers is as always, a very good idea I use them as much as I can. And if you're willing to make the handle type a little bit more heavy, then you can have some kind of smart pointer within the handle itself, so that if the resource is ever destroyed, then all handles pointing to that resource are invalidated automagically.

Actually, instead of keeping an integer in the handle, you can probably keep a pointer to some form of information structure. The manager would create one of these info structures whenever a new resource is created. This info structure can store a list of all handles pointing to it, and invalidate all of them when the resource is destoryed.

You'd get auto handle invalidationg and you can keep the size of you handles stack happy.

[anubis]

yeah... i realized it might sound like i was acusing you of plagiarism, which i didn't intend to do. managing resources this way was obviously done before he wrote about it because it happens to be an intelligent way to do it :)