Handle-based entity manager (that stores entities contiguously)

Question

I've created a generic data structure intended for game development entity management. It has some interesting properties:

• Entities are stored contiguously in an std::vector.
• Stored entities can be in one of three states: alive, dead, unused.
• Upon entity creation, a lightweight Handle object is returned:
  • The user can check whether the entity is alive or not from the handle.
  • The user can access the entity from the handle.
  • The user can mark the entity as dead from the handle.
• Every frame (or every time the user desires), calling Manager::refresh() deals with dead entities:
  1. The internal contiguous storage is sorted using entity state as the sorting predicate. Alive entities are placed at the beginning of the storage, dead entities are placed at the end. Unused entities stay in between.
  2. Dead entities get destroyed and their handles get invalidated.
  3. The manager iterates over Alive entities to update their handles (and keep them valid).

Example diagram:

// Starting situation: we have 6 alive entities 


Entity storage:  | A00 | A01 | A02 | A03 | A04 | A05 |
Control storage: | 000 | 001 | 002 | 003 | 004 | 005 |  
Index storage:   | 000 | 001 | 002 | 003 | 004 | 005 |  
Counter storage: | 000 | 000 | 000 | 000 | 000 | 000 |



// Entity #04 is marked as `dead` (handle is still valid)

                                            X
Entity storage:  | A00 | A01 | A02 | A03 | A04 | A05 |  
Control storage: | 000 | 001 | 002 | 003 | 004 | 005 |  
Index storage:   | 000 | 001 | 002 | 003 | 004 | 005 |  
Counter storage: | 000 | 000 | 000 | 000 | 000 | 000 |



// User calls `refresh()` - at the beginning of the method entities are sorted
// along with their control indices

                                                  X
Entity storage:  | A00 | A01 | A02 | A03 | A05 | A04 |  
Control storage: | 000 | 001 | 002 | 003 | 005 | 004 |  
Index storage:   | 000 | 001 | 002 | 003 | 004 | 005 |  
Counter storage: | 000 | 000 | 000 | 000 | 000 | 000 |



// `refresh()` continues - dead entity data is destroyed, and dead entity 
// counters are incremented to invalidate existing handles
// Dead entities become unused entities now

                                                  U
Entity storage:  | A00 | A01 | A02 | A03 | A05 |     |  
Control storage: | 000 | 001 | 002 | 003 | 004 | 005 |  
Index storage:   | 000 | 001 | 002 | 003 | 004 | 005 |  
Counter storage: | 000 | 000 | 000 | 000 | 001 | 000 |

// If an user queries an handle with index 004 to check the status of the 
// entity, the incremented counter will make the user know the entity is now 
// dead



// `refresh()` continues - alive entities update their indices/controllers

                                                  U
Entity storage:  | A00 | A01 | A02 | A03 | A05 |     |  
Control storage: | 000 | 001 | 002 | 003 | 005 | 004 |  
Index storage:   | 000 | 001 | 002 | 003 | 004 | 005 |  
Counter storage: | 000 | 000 | 000 | 000 | 001 | 000 |

// Now, accessing an handle pointing to A05 will access the 6th control storage
// element, which contains 005, which is the new index of the A05 entity

---

#include <SSVUtils/SSVUtils.hpp>

using Idx = std::size_t;
using Ctr = int;

template<typename> class Manager;

namespace Internal
{
    template<typename T> class Uncertain
    {
        private:
            ssvu::AlignedStorageBasic<T> storage;

        public:
            template<typename... TArgs> inline void init(TArgs&&... mArgs) noexcept(ssvu::isNothrowConstructible<T>())
            {
                new (&storage) T(std::forward<TArgs>(mArgs)...);
            }
            inline void deinit() noexcept(ssvu::isNothrowDestructible<T>()) { get().~T(); }

            inline T& get() noexcept                { return reinterpret_cast<T&>(storage); }               
            inline const T& get() const noexcept    { return reinterpret_cast<const T&>(storage); }             
    };

    template<typename T> class Atom 
    {
        template<typename> friend class Manager;

        private:
            enum class State : int {Alive = 0, Unused = 1, Dead = 2};
            Idx ctrlIdx;
            State state{State::Unused};
            Uncertain<T> data;

            // Initializes the internal data
            template<typename... TArgs> inline void initData(TArgs&&... mArgs) noexcept(ssvu::isNothrowConstructible<T>())
            {
                SSVU_ASSERT(state == State::Unused);
                data.init(std::forward<TArgs>(mArgs)...);
            }

            // Deinitializes the internal data
            inline void deinitData() noexcept(ssvu::isNothrowDestructible<T>())
            { 
                SSVU_ASSERT(state != State::Unused);
                data.deinit();
            }

        public:
            inline Atom() = default;
            inline Atom(Atom&&) = default;
            inline Atom& operator=(Atom&&) = default;

            inline T& getData() noexcept                { SSVU_ASSERT(state != State::Unused); return data.get(); }             
            inline const T& getData() const noexcept    { SSVU_ASSERT(state != State::Unused); return data.get(); } 
            inline void setDead() noexcept              { state = State::Dead; }

            // Disallow copies
            inline Atom(const Atom&) = delete;
            inline Atom& operator=(const Atom&) = delete;
    };
}

template<typename T> class Handle
{
    template<typename> friend class Manager;

    private:
        using AtomType = typename Internal::Atom<T>;

        Manager<T>& manager;
        Idx ctrlIdx;
        Ctr ctr;

        inline Handle(Manager<T>& mManager, Idx mCtrlIdx, Ctr mCtr) noexcept 
            : manager(mManager), ctrlIdx{mCtrlIdx}, ctr{mCtr} { }       

        template<typename TT> inline TT getAtomImpl() noexcept
        {
            SSVU_ASSERT(isAlive());
            return manager.getAtomFromController(manager.controllers[ctrlIdx]);
        }

    public:
        inline AtomType& getAtom() noexcept             { return getAtomImpl<AtomType&>(); }
        inline const AtomType& getAtom() const noexcept { return getAtomImpl<const AtomType&>(); }
        inline T& get() noexcept                        { return getAtom().getData(); }
        inline const T& get() const noexcept            { return getAtom().getData(); }
        bool isAlive() const noexcept;
        void destroy() noexcept;
};

template<typename T> class Manager
{
    template<typename> friend class Handle;

    private:
        struct Controller { Idx idx; Ctr ctr; };
        using AtomType = typename Internal::Atom<T>;
        using AtomState = typename AtomType::State;

        std::vector<AtomType> atoms;
        std::vector<Controller> controllers;
        Idx size{0u};

        inline void growStorage(std::size_t mOldSize, std::size_t mNewSize)
        {
            SSVU_ASSERT(mNewSize >= 0 && mNewSize >= mOldSize);

            atoms.resize(mNewSize);
            controllers.resize(mNewSize);

            // Initialize resized storage
            for(; mOldSize < mNewSize; ++mOldSize)
            {
                atoms[mOldSize].ctrlIdx = mOldSize;                 
                controllers[mOldSize].idx = mOldSize;
            }
        }

        inline void growIfNeeded()
        {
            constexpr std::size_t resizeAmount{10};

            // If the first free index is valid, return
            auto oldSize(atoms.size());
            if(oldSize > size) return;

            // Calculate new size and grow storage
            growStorage(oldSize, oldSize + resizeAmount);
        }

        inline void destroy(Idx mCtrlIdx) noexcept
        {           
            getAtomFromController(controllers[mCtrlIdx]).setDead();
        }

        inline Controller& getControllerFromAtom(const AtomType& mAtom)         { return controllers[mAtom.ctrlIdx]; }
        inline AtomType& getAtomFromController(const Controller& mController)   { return atoms[mController.idx]; }

        inline void cleanUpMemory()
        {
            for(auto& a : atoms)                
                if(a.state != AtomState::Unused) 
                {
                    a.deinitData();
                    a.state = AtomState::Unused;
                }           
        }

    public:
        inline Manager() = default;
        inline ~Manager() { cleanUpMemory(); }

        inline void clear() noexcept
        {
            cleanUpMemory();
            atoms.clear();
            controllers.clear();
            size = 0;
        }

        inline void reserve(std::size_t mSize) 
        { 
            growStorage(atoms.size(), mSize); 
        }

        template<typename... TArgs> inline Handle<T> createAtom(TArgs&&... mArgs)
        {
            // `size` may be greater than the sizes of the vectors - resize vectors if needed 
            growIfNeeded();

            // `size` now is the first empty valid index - we create our atom there
            atoms[size].initData(std::forward<TArgs>(mArgs)...);
            atoms[size].state = AtomState::Alive;

            // Update the controller
            auto cIdx(atoms[size].ctrlIdx);
            auto& controller(controllers[cIdx]);
            controller.idx = size;
            ++controller.ctr;

            // Update current size
            ++size;

            return {*this, cIdx, controller.ctr};   
        }   

        inline void refresh()
        {
            // C++14: use polymorphic lambda
            ssvu::sortStable(atoms, [](const AtomType& mA, const AtomType& mB){ return mA.state < mB.state; });

            // Starting from the end, update dead entities and their controllers
            auto i(atoms.size() - 1);           
            for(; i > 0 && atoms[i].state == AtomState::Dead; --i)              
            {
                atoms[i].deinitData();
                atoms[i].state = AtomState::Unused;
                ++(getControllerFromAtom(atoms[i]).ctr);                
            }

            // Starting from the beginning, update alive entities and their controllers
            for(i = 0u; i <= atoms.size() && atoms[i].state == AtomState::Alive; ++i)           
                getControllerFromAtom(atoms[i]).idx = i;

            // Update current size
            size = i;
        }

        template<typename TFunc> inline void forEach(TFunc mFunc)
        {
            for(auto i(0u); i < size; ++i) mFunc(atoms[i].getData());
        }   
        template<typename TFunc> inline void forEachAtom(TFunc mFunc)
        {
            for(auto i(0u); i < size; ++i) mFunc(atoms[i]);
        }

        inline AtomType& getAtomAt(Idx mIdx) noexcept               { SSVU_ASSERT(mIdx < atoms.size()); return atoms[mIdx]; }
        inline const AtomType& getAtomAt(Idx mIdx) const noexcept   { SSVU_ASSERT(mIdx < atoms.size()); return atoms[mIdx]; }
        inline T& getDataAt(Idx mIdx) noexcept                      { return getAtomAt(mIdx).getData(); }
        inline const T& getDataAt(Idx mIdx) const noexcept          { return getAtomAt(mIdx).getData(); }

        inline std::size_t getSize() const noexcept { return size; }
};

template<typename T> inline bool Handle<T>::isAlive() const noexcept
{ 
    return manager.controllers[ctrlIdx].ctr == ctr;
}

template<typename T> inline void Handle<T>::destroy() noexcept
{ 
    return manager.destroy(ctrlIdx);
}

---

Example usage:

Manager<std::string> mgr;

assert(mgr.getSize() == 0);

auto h0 = mgr.createAtom("hi");
auto h1 = mgr.createAtom("bye");
auto h2 = mgr.createAtom("hello");
auto h3 = mgr.createAtom("goodbye");

assert(mgr.getSize() == 4);

h0.get() += " sir";
h1.destroy();
h2.get() += " madam;
h3.destroy();

mgr.refresh();

assert(!h1.isAlive());
assert(!h3.isAlive());
assert(h0.get() == "hi sir");
assert(h2.get() == "hello madam");
assert(mgr.getSize() == 2);

Answer 1

A few minor things I've found:

• This could be a maintenance issue:

  inline void cleanUpMemory()
  {
      for(auto& a : atoms)                
          if(a.state != AtomState::Unused) 
          {
              a.deinitData();
              a.state = AtomState::Unused;
          }           
  }
  

  There should still be curly braces with the for loop. You already use them elsewhere, so I don't need to go further into that.

  I also don't think this needs to be inline. Even when the keyword is needed, it's primarily done with single-line functionality. If the compiler decides to inline it anyway, then it will.

• This comment is useless:

  // Update current size
  ++size;
  

  size is clearly being updated, or specifically, incremented. Comments should be useful and not state the obvious.

• It may be a little more readable to have the template statement on a separate line from the class or function statement:

  template<typename T>
  class Uncertain
  

Answer 2

Overall, I like your liberal use of C++11 style. One minor nitpick about the use of inline that occurs all over the place:

class Bla
{
public:
    inline void fun() { /* implementation */ }
    ^^^^^^
};

the use of inline is superfluous here since anything defined in-class is implicitly inline, and furthermore, inline is only a compiler hint for actual inlining (the main use of inline is to prevent ODR violations in header files).