pool.h

Go to the documentation of this file.

/*
* Copyright 2016 Autodesk, Inc. All rights reserved.
* Use of this software is subject to the terms of the Autodesk license agreement and any attachments or Appendices thereto provided at the time of installation or download,
* or which otherwise accompanies this software in either electronic or hard copy form, or which is signed by you and accepted by Autodesk.
*/

#pragma once

#include "gwnavruntime/containers/poolchunk.h"
#include "gwnavruntime/containers/kyarray.h"
#include "gwnavruntime/containers/kyarray.h"
#include "gwnavruntime/kernel/SF_Debug.h"

namespace Kaim
{


// PoolHandle
// - allows Delete(Handle handle) in O(1)
// - has sizeof() = 8 on 32 bits
// - has sizeof() = 16 on 64 bits
// - points directly to the value
template <typename T>
class PoolHandle
{
    KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)

public:
    KY_INLINE PoolHandle() : m_chunkIdx(KyUInt32MAXVAL), m_ptr(nullptr) {}
    KY_INLINE PoolHandle(KyUInt32 chunkIdx, T* value) : m_chunkIdx(chunkIdx), m_ptr(value) {}
    KY_INLINE PoolHandle(const PoolHandle& rhs) : m_chunkIdx(rhs.m_chunkIdx), m_ptr(rhs.m_ptr) {}

    KY_INLINE PoolHandle& operator=(const PoolHandle& rhs) { m_chunkIdx = rhs.m_chunkIdx; m_ptr = rhs.m_ptr; return *this; }

    KY_INLINE T& Get() const  { return *m_ptr; }
    KY_INLINE T& operator*()  { return *m_ptr; }
    KY_INLINE T* operator->() { return  m_ptr; }

    KY_INLINE void Invalidate() { m_chunkIdx = KyUInt32MAXVAL; m_ptr = nullptr; }
    KY_INLINE bool IsValid() const { return m_ptr != nullptr; }

    KY_INLINE bool operator==(const PoolHandle& rhs) const { return m_ptr == rhs.m_ptr; }
    KY_INLINE bool operator!=(const PoolHandle& rhs) const { return m_ptr != rhs.m_ptr; }

public:
    KyUInt32 m_chunkIdx;
    T* m_ptr;
};


// PoolKey
// - allows Delete(Key compactKey) in O(1)
// - has sizeof() = 4
// - requires 2 indirections to get the value
class PoolKey
{
    KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)

public:
    KY_INLINE PoolKey() : m_chunkIdx(KyUInt16MAXVAL), m_idxInChunk(KyUInt16MAXVAL) {}

    KY_INLINE PoolKey(KyUInt32 chunkIdx, KyUInt32 idxInChunk) : m_chunkIdx(KyUInt16(chunkIdx)), m_idxInChunk(KyUInt16(idxInChunk)) {}

    KY_INLINE PoolKey(const PoolKey& rhs) : m_chunkIdx(rhs.m_chunkIdx), m_idxInChunk(rhs.m_idxInChunk) {}

    KY_INLINE PoolKey& operator=(const PoolKey& rhs) { m_chunkIdx = rhs.m_chunkIdx; m_idxInChunk = rhs.m_idxInChunk; return *this; }

    KY_INLINE void Invalidate() { m_chunkIdx = KyUInt16MAXVAL; m_idxInChunk = KyUInt16MAXVAL; }
    KY_INLINE bool IsValid() const { return m_chunkIdx != KyUInt16MAXVAL && m_idxInChunk != KyUInt16MAXVAL; }

    KY_INLINE bool operator==(const PoolKey& rhs) const { return m_chunkIdx == rhs.m_chunkIdx && m_idxInChunk == rhs.m_idxInChunk; }
    KY_INLINE bool operator!=(const PoolKey& rhs) const { return !(*this == rhs); }

public:
    KyUInt16 m_chunkIdx;
    KyUInt16 m_idxInChunk;
};


struct PoolChunkSize
{
    enum Mode { ByteSize, SlotCount, WaitInit };
};

template <typename T>
struct PoolChunkElement
{
    PoolChunkElement() : m_chunk(nullptr), m_next(KyUInt32MAXVAL) {}
    PoolChunkElement(PoolChunk<T>* chunk) : m_chunk(chunk), m_next(KyUInt32MAXVAL) {}
    PoolChunk<T>* m_chunk;
    KyUInt32 m_next; // next non full chunk
};


template <typename T>
class Pool
{
    KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
    KY_CLASS_WITHOUT_COPY(Pool)
    typedef PoolChunk<T> ChunkT;
    typedef PoolChunkElement<T> ChunkElemT;

public:
    typedef PoolHandle<T> Handle;
    typedef PoolKey       Key;

public:
    explicit Pool(MemoryHeap* heap, KyInt32 memStat, PoolChunkSize::Mode chunkSizeMode = PoolChunkSize::ByteSize, KyUInt32 byteOrSlotCount = 256);

    void Init(PoolChunkSize::Mode chunkSizeMode, KyUInt32 byteOrSlotCount);

    ~Pool();

    KY_INLINE KyUInt32 GetCount() const { return m_count; }

    // -------- Key access --------
    KY_INLINE Key New_CompactKey();
    KY_INLINE Key New_CompactKey(const T& data);

    KY_INLINE void New_CompactKeyAndPtr(Key& key, T*& ptr);

    KY_INLINE const T& Get(Key key) const { return *GetChunk(key).Get(key.m_idxInChunk); }
    KY_INLINE T&       Get(Key key)       { return *GetChunk(key).Get(key.m_idxInChunk); }

    KY_INLINE void Delete(Key key) { Delete(key.m_chunkIdx, key.m_idxInChunk); }

    // -------- Handle access --------
    KY_INLINE Handle New_Handle();
    KY_INLINE Handle New_Handle(const T& data);
    KY_INLINE void Delete(const Handle& handle) { Delete(handle.m_chunkIdx, GetChunk(handle).GetIdxInChunk(handle.m_ptr)); }

    // -------- ptr access Delete() is in O(nbChunks) --------
    KY_INLINE T* New_Ptr();
    KY_INLINE T* New_Ptr(const T& data);
    KY_INLINE void Delete(T* ptr)
    {
        KyUInt32 chunkIdx = Ptr2ChunkIdx(ptr);
        Delete(chunkIdx, GetChunk(chunkIdx).GetIdxInChunk(ptr));
    }

    // --------
    KY_INLINE Key Handle2CompactKey(const Handle& h) const { return Key(h.m_chunkIdx, Ptr2IdxInChunk(h.m_chunkIdx, h.m_ptr)); }
    KY_INLINE Handle CompactKey2Handle(Key key) const { return Handle(key.m_chunkIdx, GetChunk(key).Get(key.m_idxInChunk)); }

    KY_INLINE KyUInt32 GetChunkCount() const { return m_chunkElems.GetCount(); }
    KY_INLINE KyUInt32 GetNbSlotsByChunk() const { return m_nbSlotsByChunk; }

    KyUInt32 Ptr2ChunkIdx(T* ptr) const; // O(NbChunks)
    KY_INLINE KyUInt32 Ptr2IdxInChunk(KyUInt32 chunkIdx, T* ptr) const { return GetChunk(chunkIdx).GetIdxInChunk(ptr); }

    KY_INLINE T& Get(KyUInt32 chunkIdx, KyUInt32 idxInChunk) const { return *GetChunk(chunkIdx).Get(idxInChunk); }

    KY_INLINE KyUInt32 GetGlobalIdx(const Handle& handle) { return handle.m_chunkIdx  * m_nbSlotsByChunk + Ptr2IdxInChunk(handle.m_chunkIdx, handle.m_ptr); }
    KY_INLINE KyUInt32 GetGlobalIdx(Key key)              { return key.m_chunkIdx     * m_nbSlotsByChunk + key.m_idxInChunk; }
    KY_INLINE KyUInt32 GetGlobalIdx(T* ptr)               { KyUInt32 chunkIdx = Ptr2ChunkIdx(ptr); return chunkIdx * m_nbSlotsByChunk + Ptr2IdxInChunk(chunkIdx, ptr); }

private:
    void PushBackNewChunk();

    struct Slot
    {
        void Set(KyUInt32 chunkIdx, ChunkT* chunk, KyUInt32 idxInChunk) { m_chunkIdx = chunkIdx; m_idxInchunk = idxInChunk; m_chunk = chunk; m_value = chunk->Get(idxInChunk); }
        KyUInt32 m_chunkIdx; KyUInt32 m_idxInchunk; ChunkT* m_chunk; T* m_value;
    };

    void NewSlot(Slot& slot);
    void Delete(KyUInt32 chunkIdx, KyUInt32 idxInChunk);

    void Slot2CompactKey(const Slot& slot, Key& key);

    ChunkT& GetChunk(const Handle& handle) { return *m_chunkElems[handle.m_chunkIdx].m_chunk; }
    ChunkT& GetChunk(Key key)              { return *m_chunkElems[key.m_chunkIdx].m_chunk; }
    ChunkT& GetChunk(Key key) const        { return *m_chunkElems[key.m_chunkIdx].m_chunk; }
    ChunkT& GetChunk(T* ptr)               { return *m_chunkElems[Ptr2ChunkIdx(ptr)].m_chunk; }
    ChunkT& GetChunk(KyUInt32 idx)         { return *m_chunkElems[idx].m_chunk; }
    ChunkT& GetChunk(KyUInt32 idx) const   { return *m_chunkElems[idx].m_chunk; }

private:
    KyArrayDH_POD<ChunkElemT> m_chunkElems;
    KyUInt32 m_first; // first non full chunk, if KyUInt32MAXVAL, then
    KyUInt32 m_chunkByteSize;
    KyUInt32 m_nbSlotsByChunk;
    KyUInt32 m_count;
    PoolChunkSize::Mode m_chunkSizeMode;
    MemoryHeap* m_heap;
    KyInt32 m_memStat;
};

} // namespace Kaim

#include "gwnavruntime/containers/pool.inl"