Krita Source Code Documentation
Loading...
Searching...
No Matches
Public Member Functions | Private Member Functions | Private Attributes | Friends | List of all members
ConcurrentMap< K, V, KT, VT >::Mutator Class Reference

#include <concurrent_map.h>

Public Member Functions

void assignValue (Value desired)
 
Value eraseValue ()
 
Value exchangeValue (Value desired)
 
Value getValue () const
 

Private Member Functions

 Mutator (ConcurrentMap &map, Key key)
 
 Mutator (ConcurrentMap &map, Key key, bool)
 

Private Attributes

Details::Cell * m_cell
 
ConcurrentMap & m_map
 
Details::Table * m_table
 
Value m_value
 

Friends

class ConcurrentMap
 

Detailed Description

template<typename K, typename V, class KT = DefaultKeyTraits<K>, class VT = DefaultValueTraits<V>>
class ConcurrentMap< K, V, KT, VT >::Mutator

Definition at line 70 of file concurrent_map.h.

Constructor & Destructor Documentation

◆ Mutator() [1/2]

template<typename K , typename V , class KT = DefaultKeyTraits<K>, class VT = DefaultValueTraits<V>>
ConcurrentMap< K, V, KT, VT >::Mutator::Mutator ( ConcurrentMap & map,
Key key,
bool  )
inlineprivate

Definition at line 81 of file concurrent_map.h.

81 : m_map(map), m_value(Value(ValueTraits::NullValue))
82 {
83 Hash hash = KeyTraits::hash(key);
84 for (;;) {
85 m_table = m_map.m_root.load(Consume);
86 m_cell = Details::find(hash, m_table);
87 if (!m_cell) {
88 return;
89 }
90
91 Value value = m_cell->value.load(Consume);
92 if (value != Value(ValueTraits::Redirect)) {
93 // Found an existing value
94 m_value = value;
95 return;
96 }
97 // We've encountered a Redirect value. Help finish the migration.
98 m_table->jobCoordinator.participate();
99 // Try again using the latest root.
100 }
101 }
value
float value(const T *src, size_t ch)
Definition JPEGXLImport.cpp:93
Consume
@ Consume
Definition atomic.h:58
Atomic::load
T load(MemoryOrder memoryOrder) const
Definition atomic.h:89
ConcurrentMap::Mutator::m_map
ConcurrentMap & m_map
Definition concurrent_map.h:75
ConcurrentMap::Mutator::m_table
Details::Table * m_table
Definition concurrent_map.h:76
ConcurrentMap::Mutator::m_cell
Details::Cell * m_cell
Definition concurrent_map.h:77
ConcurrentMap::m_root
Atomic< typename Details::Table * > m_root
Definition concurrent_map.h:29
Leapfrog::Cell::value
Atomic< Value > value
Definition leapfrog.h:37
Leapfrog::Table::jobCoordinator
SimpleJobCoordinator jobCoordinator
Definition leapfrog.h:54
Leapfrog::find
static Cell * find(Hash hash, Table *table)
Definition leapfrog.h:157

References Consume, Leapfrog< Map >::find(), Leapfrog< Map >::Table::jobCoordinator, Atomic< T >::load(), ConcurrentMap< K, V, KT, VT >::Mutator::m_cell, ConcurrentMap< K, V, KT, VT >::Mutator::m_map, ConcurrentMap< K, V, KT, VT >::m_root, ConcurrentMap< K, V, KT, VT >::Mutator::m_table, ConcurrentMap< K, V, KT, VT >::Mutator::m_value, SimpleJobCoordinator::participate(), Leapfrog< Map >::Cell::value, and value().

◆ Mutator() [2/2]

template<typename K , typename V , class KT = DefaultKeyTraits<K>, class VT = DefaultValueTraits<V>>
ConcurrentMap< K, V, KT, VT >::Mutator::Mutator ( ConcurrentMap & map,
Key key )
inlineprivate

Definition at line 104 of file concurrent_map.h.

104 : m_map(map), m_value(Value(ValueTraits::NullValue))
105 {
106 Hash hash = KeyTraits::hash(key);
107 for (;;) {
108 m_table = m_map.m_root.load(Consume);
109 quint64 overflowIdx;
110 switch (Details::insertOrFind(hash, m_table, m_cell, overflowIdx)) { // Modifies m_cell
111 case Details::InsertResult_InsertedNew: {
112 // We've inserted a new cell. Don't load m_cell->value.
113 return;
114 }
115 case Details::InsertResult_AlreadyFound: {
116 // The hash was already found in the table.
117 Value value = m_cell->value.load(Consume);
118 if (value == Value(ValueTraits::Redirect)) {
119 // We've encountered a Redirect value.
120 break; // Help finish the migration.
121 }
122 // Found an existing value
123 m_value = value;
124 return;
125 }
126 case Details::InsertResult_Overflow: {
127 // Unlike ConcurrentMap_Linear, we don't need to keep track of & pass a "mustDouble" flag.
128 // Passing overflowIdx is sufficient to prevent an infinite loop here.
129 // It defines the start of the range of cells to check while estimating total cells in use.
130 // After the first migration, deleted keys are purged, so if we hit this line during the
131 // second loop iteration, every cell in the range will be in use, thus the estimate will be 100%.
132 // (Concurrent deletes could result in further iterations, but it will eventually settle.)
133 Details::beginTableMigration(m_map, m_table, overflowIdx);
134 break;
135 }
136 }
137 // A migration has been started (either by us, or another thread). Participate until it's complete.
138 m_table->jobCoordinator.participate();
139 // Try again using the latest root.
140 }
141 }
Leapfrog::InsertResult_InsertedNew
@ InsertResult_InsertedNew
Definition leapfrog.h:194
Leapfrog::InsertResult_AlreadyFound
@ InsertResult_AlreadyFound
Definition leapfrog.h:194
Leapfrog::InsertResult_Overflow
@ InsertResult_Overflow
Definition leapfrog.h:194
Leapfrog::beginTableMigration
static void beginTableMigration(Map &map, Table *table, quint64 overflowIdx)
Definition leapfrog.h:332
Leapfrog::insertOrFind
static InsertResult insertOrFind(Hash hash, Table *table, Cell *&cell, quint64 &overflowIdx)
Definition leapfrog.h:195

References Leapfrog< Map >::beginTableMigration(), Consume, Leapfrog< Map >::insertOrFind(), Leapfrog< Map >::InsertResult_AlreadyFound, Leapfrog< Map >::InsertResult_InsertedNew, Leapfrog< Map >::InsertResult_Overflow, Leapfrog< Map >::Table::jobCoordinator, Atomic< T >::load(), ConcurrentMap< K, V, KT, VT >::Mutator::m_cell, ConcurrentMap< K, V, KT, VT >::Mutator::m_map, ConcurrentMap< K, V, KT, VT >::m_root, ConcurrentMap< K, V, KT, VT >::Mutator::m_table, ConcurrentMap< K, V, KT, VT >::Mutator::m_value, SimpleJobCoordinator::participate(), Leapfrog< Map >::Cell::value, and value().

Member Function Documentation

◆ assignValue()

template<typename K , typename V , class KT = DefaultKeyTraits<K>, class VT = DefaultValueTraits<V>>
void ConcurrentMap< K, V, KT, VT >::Mutator::assignValue ( Value desired)
inline

Definition at line 200 of file concurrent_map.h.

201 {
202 exchangeValue(desired);
203 }
ConcurrentMap::Mutator::exchangeValue
Value exchangeValue(Value desired)
Definition concurrent_map.h:150

References ConcurrentMap< K, V, KT, VT >::Mutator::exchangeValue().

◆ eraseValue()

template<typename K , typename V , class KT = DefaultKeyTraits<K>, class VT = DefaultValueTraits<V>>
Value ConcurrentMap< K, V, KT, VT >::Mutator::eraseValue ( )
inline

Definition at line 205 of file concurrent_map.h.

206 {
207 for (;;) {
208 if (m_value == Value(ValueTraits::NullValue)) {
209 return Value(m_value);
210 }
211
212 if (m_cell->value.compareExchangeStrong(m_value, Value(ValueTraits::NullValue), Consume)) {
213 // Exchange was successful and a non-NULL value was erased and returned by reference in m_value.
214 Value result = m_value;
215 m_value = Value(ValueTraits::NullValue); // Leave the mutator in a valid state
216 return result;
217 }
218
219 // The CAS failed and m_value has been updated with the latest value.
220 if (m_value != Value(ValueTraits::Redirect)) {
221 // There was a racing write (or erase) to this cell.
222 // Pretend we erased nothing, and just let the racing write win.
223 return Value(ValueTraits::NullValue);
224 }
225
226 // We've been redirected to a new table.
227 Hash hash = m_cell->hash.load(Relaxed); // Re-fetch hash
228 for (;;) {
229 // Help complete the migration.
230 m_table->jobCoordinator.participate();
231 // Try again in the new table.
232 m_table = m_map.m_root.load(Consume);
233 m_cell = Details::find(hash, m_table);
234 if (!m_cell) {
235 m_value = Value(ValueTraits::NullValue);
236 return m_value;
237 }
238
239 m_value = m_cell->value.load(Relaxed);
240 if (m_value != Value(ValueTraits::Redirect)) {
241 break;
242 }
243 }
244 }
245 }
Relaxed
@ Relaxed
Definition atomic.h:57
Atomic::compareExchangeStrong
bool compareExchangeStrong(T &expected, T desired, MemoryOrder memoryOrder)
Definition atomic.h:110
Leapfrog::Cell::hash
Atomic< Hash > hash
Definition leapfrog.h:36

References Atomic< T >::compareExchangeStrong(), Consume, Leapfrog< Map >::find(), Leapfrog< Map >::Cell::hash, Leapfrog< Map >::Table::jobCoordinator, Atomic< T >::load(), ConcurrentMap< K, V, KT, VT >::Mutator::m_cell, ConcurrentMap< K, V, KT, VT >::Mutator::m_map, ConcurrentMap< K, V, KT, VT >::m_root, ConcurrentMap< K, V, KT, VT >::Mutator::m_table, ConcurrentMap< K, V, KT, VT >::Mutator::m_value, SimpleJobCoordinator::participate(), Relaxed, and Leapfrog< Map >::Cell::value.

◆ exchangeValue()

template<typename K , typename V , class KT = DefaultKeyTraits<K>, class VT = DefaultValueTraits<V>>
Value ConcurrentMap< K, V, KT, VT >::Mutator::exchangeValue ( Value desired)
inline

Definition at line 150 of file concurrent_map.h.

151 {
152 for (;;) {
153 Value oldValue = m_value;
154 if (m_cell->value.compareExchangeStrong(m_value, desired, ConsumeRelease)) {
155 // Exchange was successful. Return previous value.
156 Value result = m_value;
157 m_value = desired; // Leave the mutator in a valid state
158 return result;
159 }
160 // The CAS failed and m_value has been updated with the latest value.
161 if (m_value != Value(ValueTraits::Redirect)) {
162 if (oldValue == Value(ValueTraits::NullValue) && m_value != Value(ValueTraits::NullValue)) {
163 // racing write inserted new value
164 }
165 // There was a racing write (or erase) to this cell.
166 // Pretend we exchanged with ourselves, and just let the racing write win.
167 return desired;
168 }
169
170 // We've encountered a Redirect value. Help finish the migration.
171 Hash hash = m_cell->hash.load(Relaxed);
172 for (;;) {
173 // Help complete the migration.
174 m_table->jobCoordinator.participate();
175 // Try again in the new table.
176 m_table = m_map.m_root.load(Consume);
177 m_value = Value(ValueTraits::NullValue);
178 quint64 overflowIdx;
179
180 switch (Details::insertOrFind(hash, m_table, m_cell, overflowIdx)) { // Modifies m_cell
181 case Details::InsertResult_AlreadyFound:
182 m_value = m_cell->value.load(Consume);
183 if (m_value == Value(ValueTraits::Redirect)) {
184 break;
185 }
186 goto breakOuter;
187 case Details::InsertResult_InsertedNew:
188 goto breakOuter;
189 case Details::InsertResult_Overflow:
190 Details::beginTableMigration(m_map, m_table, overflowIdx);
191 break;
192 }
193 // We were redirected... again
194 }
195 breakOuter:;
196 // Try again in the new table.
197 }
198 }
ConsumeRelease
@ ConsumeRelease
Definition atomic.h:61

References Leapfrog< Map >::beginTableMigration(), Atomic< T >::compareExchangeStrong(), Consume, ConsumeRelease, Leapfrog< Map >::Cell::hash, Leapfrog< Map >::insertOrFind(), Leapfrog< Map >::InsertResult_AlreadyFound, Leapfrog< Map >::InsertResult_InsertedNew, Leapfrog< Map >::InsertResult_Overflow, Leapfrog< Map >::Table::jobCoordinator, Atomic< T >::load(), ConcurrentMap< K, V, KT, VT >::Mutator::m_cell, ConcurrentMap< K, V, KT, VT >::Mutator::m_map, ConcurrentMap< K, V, KT, VT >::m_root, ConcurrentMap< K, V, KT, VT >::Mutator::m_table, ConcurrentMap< K, V, KT, VT >::Mutator::m_value, SimpleJobCoordinator::participate(), Relaxed, and Leapfrog< Map >::Cell::value.

◆ getValue()

template<typename K , typename V , class KT = DefaultKeyTraits<K>, class VT = DefaultValueTraits<V>>
Value ConcurrentMap< K, V, KT, VT >::Mutator::getValue ( ) const
inline

Definition at line 144 of file concurrent_map.h.

145 {
146 // Return previously loaded value. Don't load it again.
147 return Value(m_value);
148 }

References ConcurrentMap< K, V, KT, VT >::Mutator::m_value.

Friends And Related Symbol Documentation

◆ ConcurrentMap

template<typename K , typename V , class KT = DefaultKeyTraits<K>, class VT = DefaultValueTraits<V>>
friend class ConcurrentMap
friend

Definition at line 73 of file concurrent_map.h.

Member Data Documentation

◆ m_cell

template<typename K , typename V , class KT = DefaultKeyTraits<K>, class VT = DefaultValueTraits<V>>
Details::Cell* ConcurrentMap< K, V, KT, VT >::Mutator::m_cell
private

Definition at line 77 of file concurrent_map.h.

◆ m_map

template<typename K , typename V , class KT = DefaultKeyTraits<K>, class VT = DefaultValueTraits<V>>
ConcurrentMap& ConcurrentMap< K, V, KT, VT >::Mutator::m_map
private

Definition at line 75 of file concurrent_map.h.

◆ m_table

template<typename K , typename V , class KT = DefaultKeyTraits<K>, class VT = DefaultValueTraits<V>>
Details::Table* ConcurrentMap< K, V, KT, VT >::Mutator::m_table
private

Definition at line 76 of file concurrent_map.h.

◆ m_value

template<typename K , typename V , class KT = DefaultKeyTraits<K>, class VT = DefaultValueTraits<V>>
Value ConcurrentMap< K, V, KT, VT >::Mutator::m_value
private

Definition at line 78 of file concurrent_map.h.

The documentation for this class was generated from the following file: