LockFreeHashMap.h

Go to the documentation of this file.

// Jolt Physics Library (https://github.com/jrouwe/JoltPhysics)
// SPDX-FileCopyrightText: 2021 Jorrit Rouwe
// SPDX-License-Identifier: MIT
 
#pragma once
 
#include <Jolt/Core/NonCopyable.h>
#include <Jolt/Core/Atomics.h>
 
JPH_NAMESPACE_BEGIN
 
class LFHMAllocator : public NonCopyable
{
public:
    inline                  ~LFHMAllocator();
 
    inline void             Init(uint inObjectStoreSizeBytes);
 
    inline void             Clear();
 
    inline void             Allocate(uint32 inBlockSize, uint32 &ioBegin, uint32 &ioEnd);
 
    template <class T>
    inline uint32           ToOffset(const T *inData) const;
 
    template <class T>
    inline T *              FromOffset(uint32 inOffset) const;
 
private:
    uint8 *                 mObjectStore = nullptr;         
    uint32                  mObjectStoreSizeBytes = 0;      
    atomic<uint32>          mWriteOffset { 0 };             
};
 
class LFHMAllocatorContext : public NonCopyable
{
public:
    inline                  LFHMAllocatorContext(LFHMAllocator &inAllocator, uint32 inBlockSize);
 
    inline bool             Allocate(uint32 inSize, uint32 inAlignment, uint32 &outWriteOffset);
 
private:
    LFHMAllocator &         mAllocator;
    uint32                  mBlockSize;
    uint32                  mBegin = 0;
    uint32                  mEnd = 0;
};
 
template <class Key, class Value>
class LockFreeHashMap : public NonCopyable
{
public:
    using MapType = LockFreeHashMap<Key, Value>;
 
    explicit                LockFreeHashMap(LFHMAllocator &inAllocator) : mAllocator(inAllocator) { }
                            ~LockFreeHashMap();
 
    void                    Init(uint32 inMaxBuckets);
 
    void                    Clear();
    
    uint32                  GetNumBuckets() const           { return mNumBuckets; }
 
    uint32                  GetMaxBuckets() const           { return mMaxBuckets; }
 
    void                    SetNumBuckets(uint32 inNumBuckets);
 
    class KeyValue
    {
    public:
        const Key &         GetKey() const                  { return mKey; }
        Value &             GetValue()                      { return mValue; }
        const Value &       GetValue() const                { return mValue; }
 
    private:
        template <class K, class V> friend class LockFreeHashMap;
 
        Key                 mKey;                           
        uint32              mNextOffset;                    
        Value               mValue;                         
    };
 
    template <class... Params>
    inline KeyValue *       Create(LFHMAllocatorContext &ioContext, const Key &inKey, uint64 inKeyHash, int inExtraBytes, Params &&... inConstructorParams);
    
    inline const KeyValue * Find(const Key &inKey, uint64 inKeyHash) const;
 
    const static uint32     cInvalidHandle = uint32(-1);
 
    inline uint32           ToHandle(const KeyValue *inKeyValue) const;
 
    inline const KeyValue * FromHandle(uint32 inHandle) const;
 
#ifdef JPH_ENABLE_ASSERTS
    inline uint32           GetNumKeyValues() const         { return mNumKeyValues; }
#endif // JPH_ENABLE_ASSERTS
 
    inline void             GetAllKeyValues(Array<const KeyValue *> &outAll) const;
 
    struct Iterator
    {
        bool                operator == (const Iterator &inRHS) const   { return mMap == inRHS.mMap && mBucket == inRHS.mBucket && mOffset == inRHS.mOffset; }
        bool                operator != (const Iterator &inRHS) const   { return !(*this == inRHS); }
 
        KeyValue &          operator * ();
 
        Iterator &          operator ++ ();
 
        MapType *           mMap;       
        uint32              mBucket;
        uint32              mOffset;
    };
 
    Iterator                begin();
    Iterator                end();
 
#ifdef _DEBUG
    void                    TraceStats() const;
#endif
 
private:
    LFHMAllocator &         mAllocator;                     
 
#ifdef JPH_ENABLE_ASSERTS
    atomic<uint32>          mNumKeyValues = 0;              
#endif // JPH_ENABLE_ASSERTS
 
    atomic<uint32> *        mBuckets = nullptr;             
    uint32                  mNumBuckets = 0;                
    uint32                  mMaxBuckets = 0;                
};
 
JPH_NAMESPACE_END
 
#include "LockFreeHashMap.inl"