// 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
/// Allocator for a lock free hash map
class LFHMAllocator : public NonCopyable
{
public:
/// Destructor
inline ~LFHMAllocator();
/// Initialize the allocator
/// @param inObjectStoreSizeBytes Number of bytes to reserve for all key value pairs
inline void Init(uint inObjectStoreSizeBytes);
/// Clear all allocations
inline void Clear();
/// Allocate a new block of data
/// @param inBlockSize Size of block to allocate (will potentially return a smaller block if memory is full).
/// @param ioBegin Should be the start of the first free byte in current memory block on input, will contain the start of the first free byte in allocated block on return.
/// @param ioEnd Should be the byte beyond the current memory block on input, will contain the byte beyond the allocated block on return.
inline void Allocate(uint32 inBlockSize, uint32 &ioBegin, uint32 &ioEnd);
/// Convert a pointer to an offset
template <class T>
inline uint32 ToOffset(const T *inData) const;
/// Convert an offset to a pointer
template <class T>
inline T * FromOffset(uint32 inOffset) const;
private:
uint8 * mObjectStore = nullptr; ///< This contains a contiguous list of objects (possibly of varying size)
uint32 mObjectStoreSizeBytes = 0; ///< The size of mObjectStore in bytes
atomic<uint32> mWriteOffset { 0 }; ///< Next offset to write to in mObjectStore
};
/// Allocator context object for a lock free hash map that allocates a larger memory block at once and hands it out in smaller portions.
/// This avoids contention on the atomic LFHMAllocator::mWriteOffset.
class LFHMAllocatorContext : public NonCopyable
{
public:
/// Construct a new allocator context
inline LFHMAllocatorContext(LFHMAllocator &inAllocator, uint32 inBlockSize);
/// @brief Allocate data block
/// @param inSize Size of block to allocate.
/// @param inAlignment Alignment of block to allocate.
/// @param outWriteOffset Offset in buffer where block is located
/// @return True if allocation succeeded
inline bool Allocate(uint32 inSize, uint32 inAlignment, uint32 &outWriteOffset);
private:
LFHMAllocator & mAllocator;
uint32 mBlockSize;
uint32 mBegin = 0;
uint32 mEnd = 0;
};
/// Very simple lock free hash map that only allows insertion, retrieval and provides a fixed amount of buckets and fixed storage.
/// Note: This class currently assumes key and value are simple types that need no calls to the destructor.
template <class Key, class Value>
class LockFreeHashMap : public NonCopyable
{
public:
using MapType = LockFreeHashMap<Key, Value>;
/// Destructor
explicit LockFreeHashMap(LFHMAllocator &inAllocator) : mAllocator(inAllocator) { }
~LockFreeHashMap();
/// Initialization
/// @param inMaxBuckets Max amount of buckets to use in the hashmap. Must be power of 2.
void Init(uint32 inMaxBuckets);
/// Remove all elements.
/// Note that this cannot happen simultaneously with adding new elements.
void Clear();
/// Get the current amount of buckets that the map is using
uint32 GetNumBuckets() const { return mNumBuckets; }
/// Get the maximum amount of buckets that this map supports
uint32 GetMaxBuckets() const { return mMaxBuckets; }
/// Update the number of buckets. This must be done after clearing the map and cannot be done concurrently with any other operations on the map.
/// Note that the number of buckets can never become bigger than the specified max buckets during initialization and that it must be a power of 2.
void SetNumBuckets(uint32 inNumBuckets);
/// A key / value pair that is inserted in the map
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; ///< Key for this entry
uint32 mNextOffset; ///< Offset in mObjectStore of next KeyValue entry with same hash
Value mValue; ///< Value for this entry + optionally extra bytes
};
/// Insert a new element, returns null if map full.
/// Multiple threads can be inserting in the map at the same time.
template <class... Params>
inline KeyValue * Create(LFHMAllocatorContext &ioContext, const Key &inKey, uint64 inKeyHash, int inExtraBytes, Params &&... inConstructorParams);
/// Find an element, returns null if not found
inline const KeyValue * Find(const Key &inKey, uint64 inKeyHash) const;
/// Value of an invalid handle
const static uint32 cInvalidHandle = uint32(-1);
/// Get convert key value pair to uint32 handle
inline uint32 ToHandle(const KeyValue *inKeyValue) const;
/// Convert uint32 handle back to key and value
inline const KeyValue * FromHandle(uint32 inHandle) const;
#ifdef JPH_ENABLE_ASSERTS
/// Get the number of key value pairs that this map currently contains.
/// Available only when asserts are enabled because adding elements creates contention on this atomic and negatively affects performance.
inline uint32 GetNumKeyValues() const { return mNumKeyValues; }
#endif // JPH_ENABLE_ASSERTS
/// Get all key/value pairs
inline void GetAllKeyValues(Array<const KeyValue *> &outAll) const;
/// Non-const iterator
struct Iterator
{
/// Comparison
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); }
/// Convert to key value pair
KeyValue & operator * ();
/// Next item
Iterator & operator ++ ();
MapType * mMap;
uint32 mBucket;
uint32 mOffset;
};
/// Iterate over the map, note that it is not safe to do this in parallel to Clear().
/// It is safe to do this while adding elements to the map, but newly added elements may or may not be returned by the iterator.
Iterator begin();
Iterator end();
#ifdef JPH_DEBUG
/// Output stats about this map to the log
void TraceStats() const;
#endif
private:
LFHMAllocator & mAllocator; ///< Allocator used to allocate key value pairs
#ifdef JPH_ENABLE_ASSERTS
atomic<uint32> mNumKeyValues = 0; ///< Number of key value pairs in the store
#endif // JPH_ENABLE_ASSERTS
atomic<uint32> * mBuckets = nullptr; ///< This contains the offset in mObjectStore of the first object with a particular hash
uint32 mNumBuckets = 0; ///< Current number of buckets
uint32 mMaxBuckets = 0; ///< Maximum number of buckets
};
JPH_NAMESPACE_END
#include "LockFreeHashMap.inl"