Jolt Physics
A multi core friendly Game Physics Engine
Loading...
Searching...
No Matches
LockFreeHashMap.h
Go to the documentation of this file.
1// Jolt Physics Library (https://github.com/jrouwe/JoltPhysics)
2// SPDX-FileCopyrightText: 2021 Jorrit Rouwe
3// SPDX-License-Identifier: MIT
4
5#pragma once
6
8#include <Jolt/Core/Atomics.h>
9
11
14{
15public:
17 inline ~LFHMAllocator();
18
21 inline void Init(uint inObjectStoreSizeBytes);
22
24 inline void Clear();
25
30 inline void Allocate(uint32 inBlockSize, uint32 &ioBegin, uint32 &ioEnd);
31
33 template <class T>
34 inline uint32 ToOffset(const T *inData) const;
35
37 template <class T>
38 inline T * FromOffset(uint32 inOffset) const;
39
40private:
41 uint8 * mObjectStore = nullptr;
42 uint32 mObjectStoreSizeBytes = 0;
43 atomic<uint32> mWriteOffset { 0 };
44};
45
49{
50public:
52 inline LFHMAllocatorContext(LFHMAllocator &inAllocator, uint32 inBlockSize);
53
59 inline bool Allocate(uint32 inSize, uint32 inAlignment, uint32 &outWriteOffset);
60
61private:
62 LFHMAllocator & mAllocator;
63 uint32 mBlockSize;
64 uint32 mBegin = 0;
65 uint32 mEnd = 0;
66};
67
70template <class Key, class Value>
72{
73public:
75
77 explicit LockFreeHashMap(LFHMAllocator &inAllocator) : mAllocator(inAllocator) { }
79
82 void Init(uint32 inMaxBuckets);
83
86 void Clear();
87
89 uint32 GetNumBuckets() const { return mNumBuckets; }
90
92 uint32 GetMaxBuckets() const { return mMaxBuckets; }
93
96 void SetNumBuckets(uint32 inNumBuckets);
97
100 {
101 public:
102 const Key & GetKey() const { return mKey; }
103 Value & GetValue() { return mValue; }
104 const Value & GetValue() const { return mValue; }
105
106 private:
107 template <class K, class V> friend class LockFreeHashMap;
108
109 Key mKey;
110 uint32 mNextOffset;
111 Value mValue;
112 };
113
116 template <class... Params>
117 inline KeyValue * Create(LFHMAllocatorContext &ioContext, const Key &inKey, uint64 inKeyHash, int inExtraBytes, Params &&... inConstructorParams);
118
120 inline const KeyValue * Find(const Key &inKey, uint64 inKeyHash) const;
121
123 const static uint32 cInvalidHandle = uint32(-1);
124
126 inline uint32 ToHandle(const KeyValue *inKeyValue) const;
127
129 inline const KeyValue * FromHandle(uint32 inHandle) const;
130
131#ifdef JPH_ENABLE_ASSERTS
134 inline uint32 GetNumKeyValues() const { return mNumKeyValues; }
135#endif // JPH_ENABLE_ASSERTS
136
138 inline void GetAllKeyValues(Array<const KeyValue *> &outAll) const;
139
141 struct Iterator
142 {
144 bool operator == (const Iterator &inRHS) const { return mMap == inRHS.mMap && mBucket == inRHS.mBucket && mOffset == inRHS.mOffset; }
145 bool operator != (const Iterator &inRHS) const { return !(*this == inRHS); }
146
149
152
156 };
157
160 Iterator begin();
161 Iterator end();
162
163#ifdef _DEBUG
165 void TraceStats() const;
166#endif
167
168private:
169 LFHMAllocator & mAllocator;
170
171#ifdef JPH_ENABLE_ASSERTS
172 atomic<uint32> mNumKeyValues = 0;
173#endif // JPH_ENABLE_ASSERTS
174
175 atomic<uint32> * mBuckets = nullptr;
176 uint32 mNumBuckets = 0;
177 uint32 mMaxBuckets = 0;
178};
179
181
182#include "LockFreeHashMap.inl"
std::uint8_t uint8
Definition: Core.h:440
std::uint64_t uint64
Definition: Core.h:443
unsigned int uint
Definition: Core.h:439
#define JPH_NAMESPACE_END
Definition: Core.h:367
std::uint32_t uint32
Definition: Core.h:442
#define JPH_NAMESPACE_BEGIN
Definition: Core.h:361
AllocateFunction Allocate
Definition: Memory.cpp:59
std::vector< T, STLAllocator< T > > Array
Definition: STLAllocator.h:81
Definition: LockFreeHashMap.h:49
Allocator for a lock free hash map.
Definition: LockFreeHashMap.h:14
uint32 ToOffset(const T *inData) const
Convert a pointer to an offset.
Definition: LockFreeHashMap.inl:62
~LFHMAllocator()
Destructor.
Definition: LockFreeHashMap.inl:13
void Init(uint inObjectStoreSizeBytes)
Definition: LockFreeHashMap.inl:18
T * FromOffset(uint32 inOffset) const
Convert an offset to a pointer.
Definition: LockFreeHashMap.inl:70
void Clear()
Clear all allocations.
Definition: LockFreeHashMap.inl:26
A key / value pair that is inserted in the map.
Definition: LockFreeHashMap.h:100
const Key & GetKey() const
Definition: LockFreeHashMap.h:102
Value & GetValue()
Definition: LockFreeHashMap.h:103
const Value & GetValue() const
Definition: LockFreeHashMap.h:104
Definition: LockFreeHashMap.h:72
const KeyValue * FromHandle(uint32 inHandle) const
Convert uint32 handle back to key and value.
Definition: LockFreeHashMap.inl:238
Iterator begin()
Definition: LockFreeHashMap.inl:259
void GetAllKeyValues(Array< const KeyValue * > &outAll) const
Get all key/value pairs.
Definition: LockFreeHashMap.inl:244
void Init(uint32 inMaxBuckets)
Definition: LockFreeHashMap.inl:119
void SetNumBuckets(uint32 inNumBuckets)
Definition: LockFreeHashMap.inl:160
uint32 GetMaxBuckets() const
Get the maximum amount of buckets that this map supports.
Definition: LockFreeHashMap.h:92
LockFreeHashMap(LFHMAllocator &inAllocator)
Destructor.
Definition: LockFreeHashMap.h:77
KeyValue * Create(LFHMAllocatorContext &ioContext, const Key &inKey, uint64 inKeyHash, int inExtraBytes, Params &&... inConstructorParams)
Definition: LockFreeHashMap.inl:171
~LockFreeHashMap()
Definition: LockFreeHashMap.inl:133
uint32 GetNumBuckets() const
Get the current amount of buckets that the map is using.
Definition: LockFreeHashMap.h:89
const KeyValue * Find(const Key &inKey, uint64 inKeyHash) const
Find an element, returns null if not found.
Definition: LockFreeHashMap.inl:214
uint32 ToHandle(const KeyValue *inKeyValue) const
Get convert key value pair to uint32 handle.
Definition: LockFreeHashMap.inl:232
Iterator end()
Definition: LockFreeHashMap.inl:272
static const uint32 cInvalidHandle
Value of an invalid handle.
Definition: LockFreeHashMap.h:123
void Clear()
Definition: LockFreeHashMap.inl:139
Class that makes another class non-copyable. Usage: Inherit from NonCopyable.
Definition: NonCopyable.h:11
Non-const iterator.
Definition: LockFreeHashMap.h:142
bool operator==(const Iterator &inRHS) const
Comparison.
Definition: LockFreeHashMap.h:144
uint32 mOffset
Definition: LockFreeHashMap.h:155
Iterator & operator++()
Next item.
Definition: LockFreeHashMap.inl:286
uint32 mBucket
Definition: LockFreeHashMap.h:154
bool operator!=(const Iterator &inRHS) const
Definition: LockFreeHashMap.h:145
MapType * mMap
Definition: LockFreeHashMap.h:153
KeyValue & operator*()
Convert to key value pair.
Definition: LockFreeHashMap.inl:278