1 /*------------------------------------------------------------------------
2 Junction: Concurrent data structures in C++
3 Copyright (c) 2016 Jeff Preshing
5 Distributed under the Simplified BSD License.
6 Original location: https://github.com/preshing/junction
8 This software is distributed WITHOUT ANY WARRANTY; without even the
9 implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
10 See the LICENSE file for more information.
11 ------------------------------------------------------------------------*/
13 #ifndef JUNCTION_CONCURRENTMAP_LEAPFROG_H
14 #define JUNCTION_CONCURRENTMAP_LEAPFROG_H
16 #include <junction/Core.h>
17 #include <junction/details/Leapfrog.h>
18 #include <junction/QSBR.h>
19 #include <turf/Heap.h>
20 #include <turf/Trace.h>
24 TURF_TRACE_DECLARE(ConcurrentMap_Leapfrog, 17)
26 template <typename K, typename V, class KT = DefaultKeyTraits<K>, class VT = DefaultValueTraits<V> >
27 class ConcurrentMap_Leapfrog {
32 typedef VT ValueTraits;
33 typedef typename turf::util::BestFit<Key>::Unsigned Hash;
34 typedef details::Leapfrog<ConcurrentMap_Leapfrog> Details;
37 turf::Atomic<typename Details::Table*> m_root;
40 ConcurrentMap_Leapfrog(ureg capacity = Details::InitialSize) : m_root(Details::Table::create(capacity)) {
43 ~ConcurrentMap_Leapfrog() {
44 typename Details::Table* table = m_root.loadNonatomic();
48 // publishTableMigration() is called by exactly one thread from Details::TableMigration::run()
49 // after all the threads participating in the migration have completed their work.
50 void publishTableMigration(typename Details::TableMigration* migration) {
51 // There are no racing calls to this function.
52 typename Details::Table* oldRoot = m_root.loadNonatomic();
53 m_root.store(migration->m_destination, turf::Release);
54 TURF_ASSERT(oldRoot == migration->getSources()[0].table);
55 // Caller will GC the TableMigration and the source table.
58 // A Mutator represents a known cell in the hash table.
59 // It's meant for manipulations within a temporary function scope.
60 // Obviously you must not call QSBR::Update while holding a Mutator.
61 // Any operation that modifies the table (exchangeValue, eraseValue)
62 // may be forced to follow a redirected cell, which changes the Mutator itself.
63 // Note that even if the Mutator was constructed from an existing cell,
64 // exchangeValue() can still trigger a resize if the existing cell was previously marked deleted,
65 // or if another thread deletes the key between the two steps.
68 friend class ConcurrentMap_Leapfrog;
70 ConcurrentMap_Leapfrog& m_map;
71 typename Details::Table* m_table;
72 typename Details::Cell* m_cell;
75 // Constructor: Find existing cell
76 Mutator(ConcurrentMap_Leapfrog& map, Key key, bool) : m_map(map), m_value(Value(ValueTraits::NullValue)) {
77 TURF_TRACE(ConcurrentMap_Leapfrog, 0, "[Mutator] find constructor called", uptr(0), uptr(key));
78 Hash hash = KeyTraits::hash(key);
80 m_table = m_map.m_root.load(turf::Consume);
81 m_cell = Details::find(hash, m_table);
84 m_value = m_cell->value.load(turf::Consume);
85 if (m_value != Value(ValueTraits::Redirect))
86 return; // Found an existing value
87 // We've encountered a Redirect value. Help finish the migration.
88 TURF_TRACE(ConcurrentMap_Leapfrog, 1, "[Mutator] find was redirected", uptr(m_table), 0);
89 m_table->jobCoordinator.participate();
90 // Try again using the latest root.
94 // Constructor: Insert or find cell
95 Mutator(ConcurrentMap_Leapfrog& map, Key key) : m_map(map), m_value(Value(ValueTraits::NullValue)) {
96 TURF_TRACE(ConcurrentMap_Leapfrog, 2, "[Mutator] insertOrFind constructor called", uptr(0), uptr(key));
97 Hash hash = KeyTraits::hash(key);
99 m_table = m_map.m_root.load(turf::Consume);
101 switch (Details::insertOrFind(hash, m_table, m_cell, overflowIdx)) { // Modifies m_cell
102 case Details::InsertResult_InsertedNew: {
103 // We've inserted a new cell. Don't load m_cell->value.
106 case Details::InsertResult_AlreadyFound: {
107 // The hash was already found in the table.
108 m_value = m_cell->value.load(turf::Consume);
109 if (m_value == Value(ValueTraits::Redirect)) {
110 // We've encountered a Redirect value.
111 TURF_TRACE(ConcurrentMap_Leapfrog, 3, "[Mutator] insertOrFind was redirected", uptr(m_table), uptr(m_value));
112 break; // Help finish the migration.
114 return; // Found an existing value
116 case Details::InsertResult_Overflow: {
117 // Unlike ConcurrentMap_Linear, we don't need to keep track of & pass a "mustDouble" flag.
118 // Passing overflowIdx is sufficient to prevent an infinite loop here.
119 // It defines the start of the range of cells to check while estimating total cells in use.
120 // After the first migration, deleted keys are purged, so if we hit this line during the
121 // second loop iteration, every cell in the range will be in use, thus the estimate will be 100%.
122 // (Concurrent deletes could result in further iterations, but it will eventually settle.)
123 Details::beginTableMigration(m_map, m_table, overflowIdx);
127 // A migration has been started (either by us, or another thread). Participate until it's complete.
128 m_table->jobCoordinator.participate();
129 // Try again using the latest root.
134 Value getValue() const {
135 // Return previously loaded value. Don't load it again.
136 return Value(m_value);
139 Value exchangeValue(Value desired) {
140 TURF_ASSERT(desired != Value(ValueTraits::NullValue));
141 TURF_ASSERT(desired != Value(ValueTraits::Redirect));
142 TURF_ASSERT(m_cell); // Cell must have been found or inserted
143 TURF_TRACE(ConcurrentMap_Leapfrog, 4, "[Mutator::exchangeValue] called", uptr(m_table), uptr(m_value));
145 Value oldValue = m_value;
146 if (m_cell->value.compareExchangeStrong(m_value, desired, turf::ConsumeRelease)) {
147 // Exchange was successful. Return previous value.
148 TURF_TRACE(ConcurrentMap_Leapfrog, 5, "[Mutator::exchangeValue] exchanged Value", uptr(m_value),
150 Value result = m_value;
151 m_value = desired; // Leave the mutator in a valid state
154 // The CAS failed and m_value has been updated with the latest value.
155 if (m_value != Value(ValueTraits::Redirect)) {
156 TURF_TRACE(ConcurrentMap_Leapfrog, 6, "[Mutator::exchangeValue] detected race to write value", uptr(m_table),
158 if (oldValue == Value(ValueTraits::NullValue) && m_value != Value(ValueTraits::NullValue)) {
159 TURF_TRACE(ConcurrentMap_Leapfrog, 7, "[Mutator::exchangeValue] racing write inserted new value",
160 uptr(m_table), uptr(m_value));
162 // There was a racing write (or erase) to this cell.
163 // Pretend we exchanged with ourselves, and just let the racing write win.
166 // We've encountered a Redirect value. Help finish the migration.
167 TURF_TRACE(ConcurrentMap_Leapfrog, 8, "[Mutator::exchangeValue] was redirected", uptr(m_table), uptr(m_value));
168 Hash hash = m_cell->hash.load(turf::Relaxed);
170 // Help complete the migration.
171 m_table->jobCoordinator.participate();
172 // Try again in the new table.
173 m_table = m_map.m_root.load(turf::Consume);
174 m_value = Value(ValueTraits::NullValue);
176 switch (Details::insertOrFind(hash, m_table, m_cell, overflowIdx)) { // Modifies m_cell
177 case Details::InsertResult_AlreadyFound:
178 m_value = m_cell->value.load(turf::Consume);
179 if (m_value == Value(ValueTraits::Redirect)) {
180 TURF_TRACE(ConcurrentMap_Leapfrog, 9, "[Mutator::exchangeValue] was re-redirected", uptr(m_table),
185 case Details::InsertResult_InsertedNew:
187 case Details::InsertResult_Overflow:
188 TURF_TRACE(ConcurrentMap_Leapfrog, 10, "[Mutator::exchangeValue] overflow after redirect", uptr(m_table),
190 Details::beginTableMigration(m_map, m_table, overflowIdx);
193 // We were redirected... again
196 // Try again in the new table.
200 void assignValue(Value desired) {
201 exchangeValue(desired);
205 TURF_ASSERT(m_cell); // Cell must have been found or inserted
206 TURF_TRACE(ConcurrentMap_Leapfrog, 11, "[Mutator::eraseValue] called", uptr(m_table), uptr(m_cell));
208 if (m_value == Value(ValueTraits::NullValue))
209 return Value(m_value);
210 TURF_ASSERT(m_cell); // m_value is non-NullValue, therefore cell must have been found or inserted.
211 if (m_cell->value.compareExchangeStrong(m_value, Value(ValueTraits::NullValue), turf::Consume)) {
212 // Exchange was successful and a non-NULL value was erased and returned by reference in m_value.
213 TURF_ASSERT(m_value != ValueTraits::NullValue); // Implied by the test at the start of the loop.
214 Value result = m_value;
215 m_value = Value(ValueTraits::NullValue); // Leave the mutator in a valid state
218 // The CAS failed and m_value has been updated with the latest value.
219 TURF_TRACE(ConcurrentMap_Leapfrog, 12, "[Mutator::eraseValue] detected race to write value", uptr(m_table),
221 if (m_value != Value(ValueTraits::Redirect)) {
222 // There was a racing write (or erase) to this cell.
223 // Pretend we erased nothing, and just let the racing write win.
224 return Value(ValueTraits::NullValue);
226 // We've been redirected to a new table.
227 TURF_TRACE(ConcurrentMap_Leapfrog, 13, "[Mutator::eraseValue] was redirected", uptr(m_table), uptr(m_cell));
228 Hash hash = m_cell->hash.load(turf::Relaxed); // Re-fetch hash
230 // Help complete the migration.
231 m_table->jobCoordinator.participate();
232 // Try again in the new table.
233 m_table = m_map.m_root.load(turf::Consume);
234 m_cell = Details::find(hash, m_table);
236 m_value = Value(ValueTraits::NullValue);
239 m_value = m_cell->value.load(turf::Relaxed);
240 if (m_value != Value(ValueTraits::Redirect))
242 TURF_TRACE(ConcurrentMap_Leapfrog, 14, "[Mutator::eraseValue] was re-redirected", uptr(m_table),
249 Mutator insertOrFind(Key key) {
250 return Mutator(*this, key);
253 Mutator find(Key key) {
254 return Mutator(*this, key, false);
257 // Lookup without creating a temporary Mutator.
259 Hash hash = KeyTraits::hash(key);
260 TURF_TRACE(ConcurrentMap_Leapfrog, 15, "[get] called", uptr(this), uptr(hash));
262 typename Details::Table* table = m_root.load(turf::Consume);
263 typename Details::Cell* cell = Details::find(hash, table);
265 return Value(ValueTraits::NullValue);
266 Value value = cell->value.load(turf::Consume);
267 if (value != Value(ValueTraits::Redirect))
268 return value; // Found an existing value
269 // We've been redirected to a new table. Help with the migration.
270 TURF_TRACE(ConcurrentMap_Leapfrog, 16, "[get] was redirected", uptr(table), uptr(hash));
271 table->jobCoordinator.participate();
272 // Try again in the new table.
276 Value assign(Key key, Value desired) {
277 Mutator iter(*this, key);
278 return iter.exchangeValue(desired);
281 Value exchange(Key key, Value desired) {
282 Mutator iter(*this, key);
283 return iter.exchangeValue(desired);
286 Value erase(Key key) {
287 Mutator iter(*this, key, false);
288 return iter.eraseValue();
291 // The easiest way to implement an Iterator is to prevent all Redirects.
292 // The currrent Iterator does that by forbidding concurrent inserts.
293 // To make it work with concurrent inserts, we'd need a way to block TableMigrations.
296 typename Details::Table* m_table;
302 Iterator(ConcurrentMap_Leapfrog& map) {
303 // Since we've forbidden concurrent inserts (for now), nonatomic would suffice here, but let's plan ahead:
304 m_table = map.m_root.load(turf::Consume);
310 TURF_ASSERT(m_table);
311 TURF_ASSERT(isValid() || m_idx == -1); // Either the Iterator is already valid, or we've just started iterating.
312 while (++m_idx <= m_table->sizeMask) {
313 // Index still inside range of table.
314 typename Details::CellGroup* group = m_table->getCellGroups() + (m_idx >> 2);
315 typename Details::Cell* cell = group->cells + (m_idx & 3);
316 m_hash = cell->hash.load(turf::Relaxed);
317 if (m_hash != KeyTraits::NullHash) {
318 // Cell has been reserved.
319 m_value = cell->value.load(turf::Relaxed);
320 TURF_ASSERT(m_value != Value(ValueTraits::Redirect));
321 if (m_value != Value(ValueTraits::NullValue))
322 return; // Yield this cell.
325 // That's the end of the map.
326 m_hash = KeyTraits::NullHash;
327 m_value = Value(ValueTraits::NullValue);
330 bool isValid() const {
331 return m_value != Value(ValueTraits::NullValue);
335 TURF_ASSERT(isValid());
336 // Since we've forbidden concurrent inserts (for now), nonatomic would suffice here, but let's plan ahead:
337 return KeyTraits::dehash(m_hash);
340 Value getValue() const {
341 TURF_ASSERT(isValid());
347 } // namespace junction
349 #endif // JUNCTION_CONCURRENTMAP_LEAPFROG_H