Fix MSVC warnings with u64 keys
[junction.git] / junction / ConcurrentMap_LeapFrog.h
1 /*------------------------------------------------------------------------
2   Junction: Concurrent data structures in C++
3   Copyright (c) 2016 Jeff Preshing
4
5   Distributed under the Simplified BSD License.
6   Original location: https://github.com/preshing/junction
7
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 ------------------------------------------------------------------------*/
12
13 #ifndef JUNCTION_CONCURRENTMAP_LEAPFROG_H
14 #define JUNCTION_CONCURRENTMAP_LEAPFROG_H
15
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>
21
22 namespace junction {
23
24 TURF_TRACE_DECLARE(ConcurrentMap_LeapFrog, 17)
25
26 template <typename K, typename V, class KT = DefaultKeyTraits<K>, class VT = DefaultValueTraits<V> >
27 class ConcurrentMap_LeapFrog {
28 public:
29     typedef K Key;
30     typedef V Value;
31     typedef KT KeyTraits;
32     typedef VT ValueTraits;
33     typedef typename turf::util::BestFit<Key>::Unsigned Hash;
34     typedef details::LeapFrog<ConcurrentMap_LeapFrog> Details;
35
36 private:
37     turf::Atomic<typename Details::Table*> m_root;
38
39 public:
40     ConcurrentMap_LeapFrog(ureg capacity = Details::InitialSize) : m_root(Details::Table::create(capacity)) {
41     }
42
43     ~ConcurrentMap_LeapFrog() {
44         typename Details::Table* table = m_root.loadNonatomic();
45         table->destroy();
46     }
47
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.
56     }
57
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.
66     class Mutator {
67     private:
68         friend class ConcurrentMap_LeapFrog;
69
70         ConcurrentMap_LeapFrog& m_map;
71         typename Details::Table* m_table;
72         typename Details::Cell* m_cell;
73         Value m_value;
74
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(m_table), uptr(key));
78             Hash hash = KeyTraits::hash(key);
79             for (;;) {
80                 m_table = m_map.m_root.load(turf::Consume);
81                 m_cell = Details::find(hash, m_table);
82                 if (!m_cell)
83                     return;
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.
91             }
92         }
93
94         // Constructor: Insert cell
95         Mutator(ConcurrentMap_LeapFrog& map, Key key)
96             : m_map(map), m_table(map.m_root.load(turf::Consume)), m_value(Value(ValueTraits::NullValue)) {
97             TURF_TRACE(ConcurrentMap_LeapFrog, 2, "[Mutator] insert constructor called", uptr(m_table), uptr(key));
98             Hash hash = KeyTraits::hash(key);
99             for (;;) {
100                 m_table = m_map.m_root.load(turf::Consume);
101                 ureg overflowIdx;
102                 switch (Details::insert(hash, m_table, m_cell, overflowIdx)) { // Modifies m_cell
103                 case Details::InsertResult_InsertedNew: {
104                     // We've inserted a new cell. Don't load m_cell->value.
105                     return;
106                 }
107                 case Details::InsertResult_AlreadyFound: {
108                     // The hash was already found in the table.
109                     m_value = m_cell->value.load(turf::Consume);
110                     if (m_value == Value(ValueTraits::Redirect)) {
111                         // We've encountered a Redirect value.
112                         TURF_TRACE(ConcurrentMap_LeapFrog, 3, "[Mutator] insert was redirected", uptr(m_table), uptr(m_value));
113                         break; // Help finish the migration.
114                     }
115                     return; // Found an existing value
116                 }
117                 case Details::InsertResult_Overflow: {
118                     Details::beginTableMigration(m_map, m_table, overflowIdx);
119                     break;
120                 }
121                 }
122                 // A migration has been started (either by us, or another thread). Participate until it's complete.
123                 m_table->jobCoordinator.participate();
124                 // Try again using the latest root.
125             }
126         }
127
128     public:
129         Value getValue() const {
130             // Return previously loaded value. Don't load it again.
131             return Value(m_value);
132         }
133
134         Value exchangeValue(Value desired) {
135             TURF_ASSERT(desired != Value(ValueTraits::NullValue));
136             TURF_ASSERT(m_cell); // Cell must have been found or inserted
137             TURF_TRACE(ConcurrentMap_LeapFrog, 4, "[Mutator::exchangeValue] called", uptr(m_table), uptr(m_value));
138             for (;;) {
139                 Value oldValue = m_value;
140                 if (m_cell->value.compareExchangeStrong(m_value, desired, turf::ConsumeRelease)) {
141                     // Exchange was successful. Return previous value.
142                     TURF_TRACE(ConcurrentMap_LeapFrog, 5, "[Mutator::exchangeValue] exchanged Value", uptr(m_value),
143                                uptr(desired));
144                     Value result = m_value;
145                     m_value = desired; // Leave the mutator in a valid state
146                     return result;
147                 }
148                 // The CAS failed and m_value has been updated with the latest value.
149                 if (m_value != Value(ValueTraits::Redirect)) {
150                     TURF_TRACE(ConcurrentMap_LeapFrog, 6, "[Mutator::exchangeValue] detected race to write value", uptr(m_table),
151                                uptr(m_value));
152                     if (oldValue == Value(ValueTraits::NullValue) && m_value != Value(ValueTraits::NullValue)) {
153                         TURF_TRACE(ConcurrentMap_LeapFrog, 7, "[Mutator::exchangeValue] racing write inserted new value",
154                                    uptr(m_table), uptr(m_value));
155                     }
156                     // There was a racing write (or erase) to this cell.
157                     // Pretend we exchanged with ourselves, and just let the racing write win.
158                     return desired;
159                 }
160                 // We've encountered a Redirect value. Help finish the migration.
161                 TURF_TRACE(ConcurrentMap_LeapFrog, 8, "[Mutator::exchangeValue] was redirected", uptr(m_table), uptr(m_value));
162                 Hash hash = m_cell->hash.load(turf::Relaxed);
163                 for (;;) {
164                     // Help complete the migration.
165                     m_table->jobCoordinator.participate();
166                     // Try again in the new table.
167                     m_table = m_map.m_root.load(turf::Consume);
168                     m_value = Value(ValueTraits::NullValue);
169                     ureg overflowIdx;
170                     switch (Details::insert(hash, m_table, m_cell, overflowIdx)) { // Modifies m_cell
171                     case Details::InsertResult_AlreadyFound:
172                         m_value = m_cell->value.load(turf::Consume);
173                         if (m_value == Value(ValueTraits::Redirect)) {
174                             TURF_TRACE(ConcurrentMap_LeapFrog, 9, "[Mutator::exchangeValue] was re-redirected", uptr(m_table),
175                                        uptr(m_value));
176                             break;
177                         }
178                         goto breakOuter;
179                     case Details::InsertResult_InsertedNew:
180                         goto breakOuter;
181                     case Details::InsertResult_Overflow:
182                         TURF_TRACE(ConcurrentMap_LeapFrog, 10, "[Mutator::exchangeValue] overflow after redirect", uptr(m_table),
183                                    overflowIdx);
184                         Details::beginTableMigration(m_map, m_table, overflowIdx);
185                         break;
186                     }
187                     // We were redirected... again
188                 }
189             breakOuter:;
190                 // Try again in the new table.
191             }
192         }
193
194         void setValue(Value desired) {
195             exchangeValue(desired);
196         }
197
198         Value eraseValue() {
199             TURF_ASSERT(m_cell); // Cell must have been found or inserted
200             TURF_TRACE(ConcurrentMap_LeapFrog, 11, "[Mutator::eraseValue] called", uptr(m_table), uptr(m_cell));
201             for (;;) {
202                 if (m_value == Value(ValueTraits::NullValue))
203                     return Value(m_value);
204                 TURF_ASSERT(m_cell); // m_value is non-NullValue, therefore cell must have been found or inserted.
205                 if (m_cell->value.compareExchangeStrong(m_value, Value(ValueTraits::NullValue), turf::Consume)) {
206                     // Exchange was successful and a non-NULL value was erased and returned by reference in m_value.
207                     TURF_ASSERT(m_value != ValueTraits::NullValue); // Implied by the test at the start of the loop.
208                     Value result = m_value;
209                     m_value = Value(ValueTraits::NullValue); // Leave the mutator in a valid state
210                     return result;
211                 }
212                 // The CAS failed and m_value has been updated with the latest value.
213                 TURF_TRACE(ConcurrentMap_LeapFrog, 12, "[Mutator::eraseValue] detected race to write value", uptr(m_table),
214                            uptr(m_cell));
215                 if (m_value != Value(ValueTraits::Redirect)) {
216                     // There was a racing write (or erase) to this cell.
217                     // Pretend we erased nothing, and just let the racing write win.
218                     return Value(ValueTraits::NullValue);
219                 }
220                 // We've been redirected to a new table.
221                 TURF_TRACE(ConcurrentMap_LeapFrog, 13, "[Mutator::eraseValue] was redirected", uptr(m_table), uptr(m_cell));
222                 Hash hash = m_cell->hash.load(turf::Relaxed); // Re-fetch hash
223                 for (;;) {
224                     // Help complete the migration.
225                     m_table->jobCoordinator.participate();
226                     // Try again in the new table.
227                     m_table = m_map.m_root.load(turf::Consume);
228                     m_cell = Details::find(hash, m_table);
229                     if (!m_cell) {
230                         m_value = Value(ValueTraits::NullValue);
231                         return m_value;
232                     }
233                     m_value = m_cell->value.load(turf::Relaxed);
234                     if (m_value != Value(ValueTraits::Redirect))
235                         break;
236                     TURF_TRACE(ConcurrentMap_LeapFrog, 14, "[Mutator::eraseValue] was re-redirected", uptr(m_table),
237                                uptr(m_cell));
238                 }
239             }
240         }
241     };
242
243     Mutator insert(Key key) {
244         return Mutator(*this, key);
245     }
246
247     Mutator find(Key key) {
248         return Mutator(*this, key, false);
249     }
250
251     // Lookup without creating a temporary Mutator.
252     Value get(Key key) {
253         Hash hash = KeyTraits::hash(key);
254         TURF_TRACE(ConcurrentMap_LeapFrog, 15, "[get] called", uptr(hash), 0);
255         for (;;) {
256             typename Details::Table* table = m_root.load(turf::Consume);
257             typename Details::Cell* cell = Details::find(hash, table);
258             if (!cell)
259                 return Value(ValueTraits::NullValue);
260             Value value = cell->value.load(turf::Consume);
261             if (value != Value(ValueTraits::Redirect))
262                 return value; // Found an existing value
263             // We've been redirected to a new table. Help with the migration.
264             TURF_TRACE(ConcurrentMap_LeapFrog, 16, "[get] was redirected", uptr(table), uptr(hash));
265             table->jobCoordinator.participate();
266             // Try again in the new table.
267         }
268     }
269
270     Value insert(Key key, Value desired) {
271         Mutator iter(*this, key);
272         return iter.exchangeValue(desired);
273     }
274
275     Value exchange(Key key, Value desired) {
276         Mutator iter(*this, key);
277         return iter.exchangeValue(desired);
278     }
279
280     Value erase(Key key) {
281         Mutator iter(*this, key, false);
282         return iter.eraseValue();
283     }
284
285     // The easiest way to implement an Iterator is to prevent all Redirects.
286     // The currrent Iterator does that by forbidding concurrent inserts.
287     // To make it work with concurrent inserts, we'd need a way to block TableMigrations.
288     class Iterator {
289     private:
290         typename Details::Table* m_table;
291         ureg m_idx;
292         Key m_hash;
293         Value m_value;
294
295     public:
296         Iterator(ConcurrentMap_LeapFrog& map) {
297             // Since we've forbidden concurrent inserts (for now), nonatomic would suffice here, but let's plan ahead:
298             m_table = map.m_root.load(turf::Consume);
299             m_idx = -1;
300             next();
301         }
302
303         void next() {
304             TURF_ASSERT(m_table);
305             TURF_ASSERT(isValid() || m_idx == -1); // Either the Iterator is already valid, or we've just started iterating.
306             while (++m_idx <= m_table->sizeMask) {
307                 // Index still inside range of table.
308                 typename Details::CellGroup* group = m_table->getCellGroups() + (m_idx >> 2);
309                 typename Details::Cell* cell = group->cells + (m_idx & 3);
310                 m_hash = cell->hash.load(turf::Relaxed);
311                 if (m_hash != KeyTraits::NullHash) {
312                     // Cell has been reserved.
313                     m_value = cell->value.load(turf::Relaxed);
314                     TURF_ASSERT(m_value != Value(ValueTraits::Redirect));
315                     if (m_value != Value(ValueTraits::NullValue))
316                         return; // Yield this cell.
317                 }
318             }
319             // That's the end of the map.
320             m_hash = KeyTraits::NullHash;
321             m_value = ValueTraits::NullValue;
322         }
323
324         bool isValid() const {
325             return m_value != Value(ValueTraits::NullValue);
326         }
327
328         Key getKey() const {
329             TURF_ASSERT(isValid());
330             // Since we've forbidden concurrent inserts (for now), nonatomic would suffice here, but let's plan ahead:
331             return KeyTraits::dehash(m_hash);
332         }
333
334         Value getValue() const {
335             TURF_ASSERT(isValid());
336             return m_value;
337         }
338     };
339 };
340
341 } // namespace junction
342
343 #endif // JUNCTION_CONCURRENTMAP_LEAPFROG_H