27e18ff3a5b4f1297f4f6b53835f8d3ce72a00cd
[junction.git] / junction / ConcurrentMap_Grampa.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_GRAMPA_H
14 #define JUNCTION_CONCURRENTMAP_GRAMPA_H
15
16 #include <junction/Core.h>
17 #include <junction/details/Grampa.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_Grampa, 27)
25
26 template <typename K, typename V, class KT = DefaultKeyTraits<K>, class VT = DefaultValueTraits<V> >
27 class ConcurrentMap_Grampa {
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::Grampa<ConcurrentMap_Grampa> Details;
35
36 private:
37     turf::Atomic<uptr> m_root;
38
39     bool locateTable(typename Details::Table*& table, ureg& sizeMask, Hash hash) {
40         ureg root = m_root.load(turf::Consume);
41         if (root & 1) {
42             typename Details::FlatTree* flatTree = (typename Details::FlatTree*) (root & ~ureg(1));
43             for (;;) {
44                 ureg leafIdx = ureg(hash >> flatTree->safeShift);
45                 table = flatTree->getTables()[leafIdx].load(turf::Relaxed);
46                 if (ureg(table) != Details::RedirectFlatTree) {
47                     sizeMask = (Details::LeafSize - 1);
48                     return true;
49                 }
50                 TURF_TRACE(ConcurrentMap_Grampa, 0, "[locateTable] flattree lookup redirected", uptr(flatTree), uptr(leafIdx));
51                 typename Details::FlatTreeMigration* migration = Details::getExistingFlatTreeMigration(flatTree);
52                 migration->run();
53                 migration->m_completed.wait();
54                 flatTree = migration->m_destination;
55             }
56         } else {
57             if (!root)
58                 return false;
59             table = (typename Details::Table*) root;
60             sizeMask = table->sizeMask;
61             return true;
62         }
63     }
64
65     void createInitialTable(ureg initialSize) {
66         if (!m_root.load(turf::Relaxed)) {
67             // This could perform DCLI, but let's avoid needing a mutex instead.
68             typename Details::Table* table = Details::Table::create(initialSize, 0, sizeof(Hash) * 8);
69             if (m_root.compareExchange(uptr(NULL), uptr(table), turf::Release)) {
70                 TURF_TRACE(ConcurrentMap_Grampa, 1, "[createInitialTable] race to create initial table", uptr(this), 0);
71                 table->destroy();
72             }
73         }
74     }
75
76 public:
77     ConcurrentMap_Grampa(ureg initialSize = 0) : m_root(uptr(NULL)) {
78         // FIXME: Support initialSize argument
79         TURF_UNUSED(initialSize);
80     }
81
82     ~ConcurrentMap_Grampa() {
83         ureg root = m_root.loadNonatomic();
84         if (root & 1) {
85             typename Details::FlatTree* flatTree = (typename Details::FlatTree*) (root & ~ureg(1));
86             ureg size = (Hash(-1) >> flatTree->safeShift) + 1;
87             typename Details::Table* lastTableGCed = NULL;
88             for (ureg i = 0; i < size; i++) {
89                 typename Details::Table* t = flatTree->getTables()[i].loadNonatomic();
90                 TURF_ASSERT(ureg(t) != Details::RedirectFlatTree);
91                 if (t != lastTableGCed) {
92                     t->destroy();
93                     lastTableGCed = t;
94                 }
95             }
96             flatTree->destroy();
97         } else if (root) {
98             typename Details::Table* t = (typename Details::Table*) root;
99             t->destroy();
100         }
101     }
102
103     // publishTableMigration() is called by exactly one thread from Details::TableMigration::run()
104     // after all the threads participating in the migration have completed their work.
105     // There are no racing writes to the same range of hashes.
106     void publishTableMigration(typename Details::TableMigration* migration) {
107         TURF_TRACE(ConcurrentMap_Grampa, 2, "[publishTableMigration] called", uptr(migration), 0);
108         if (migration->m_safeShift == 0) {
109             // This TableMigration replaces the entire map with a single table.
110             TURF_ASSERT(migration->m_baseHash == 0);
111             TURF_ASSERT(migration->m_numDestinations == 1);
112             ureg oldRoot = m_root.loadNonatomic(); // There are no racing writes to m_root.
113             // Store the single table in m_root directly.
114             typename Details::Table* newTable = migration->getDestinations()[0];
115             m_root.store(uptr(newTable), turf::Release); // Make table contents visible
116             newTable->isPublished.signal();
117             if ((oldRoot & 1) == 0) {
118                 TURF_TRACE(ConcurrentMap_Grampa, 3, "[publishTableMigration] replacing single root with single root",
119                            uptr(migration), 0);
120                 // If oldRoot is a table, it must be the original source of the migration.
121                 TURF_ASSERT((typename Details::Table*) oldRoot == migration->getSources()[0].table);
122                 // Don't GC it here. The caller will GC it since it's a source of the TableMigration.
123             } else {
124                 TURF_TRACE(ConcurrentMap_Grampa, 4, "[publishTableMigration] replacing flattree with single root",
125                            uptr(migration), 0);
126                 // The entire previous flattree is being replaced.
127                 Details::garbageCollectFlatTree((typename Details::FlatTree*) (oldRoot & ~ureg(1)));
128             }
129             // Caller will GC the TableMigration.
130         } else {
131             // We are either publishing a subtree of one or more tables, or replacing the entire map with multiple tables.
132             // In either case, there will be a flattree after this function returns.
133             TURF_ASSERT(migration->m_safeShift <
134                         sizeof(Hash) * 8); // If m_numDestinations > 1, some index bits must remain after shifting
135             ureg oldRoot = m_root.load(turf::Consume);
136             if ((oldRoot & 1) == 0) {
137                 // There's no flattree yet. This means the TableMigration is publishing the full range of hashes.
138                 TURF_ASSERT(migration->m_baseHash == 0);
139                 TURF_ASSERT((Hash(-1) >> migration->m_safeShift) == (migration->m_numDestinations - 1));
140                 // The oldRoot should be the original source of the migration.
141                 TURF_ASSERT((typename Details::Table*) oldRoot == migration->getSources()[0].table);
142                 // Furthermore, it is guaranteed that there are no racing writes to m_root.
143                 // Create a new flattree and store it to m_root.
144                 TURF_TRACE(ConcurrentMap_Grampa, 5, "[publishTableMigration] replacing single root with flattree",
145                            uptr(migration), 0);
146                 typename Details::FlatTree* flatTree = Details::FlatTree::create(migration->m_safeShift);
147                 typename Details::Table* prevTable = NULL;
148                 for (ureg i = 0; i < migration->m_numDestinations; i++) {
149                     typename Details::Table* newTable = migration->getDestinations()[i];
150                     flatTree->getTables()[i].storeNonatomic(newTable);
151                     if (newTable != prevTable) {
152                         newTable->isPublished.signal();
153                         prevTable = newTable;
154                     }
155                 }
156                 m_root.store(uptr(flatTree) | 1, turf::Release); // Ensure visibility of flatTree->tables
157                 // Caller will GC the TableMigration.
158                 // Caller will also GC the old oldRoot since it's a source of the TableMigration.
159             } else {
160                 // There is an existing flattree, and we are publishing one or more tables to it.
161                 // Attempt to publish the subtree in a loop.
162                 // The loop is necessary because we might get redirected in the middle of publishing.
163                 TURF_TRACE(ConcurrentMap_Grampa, 6, "[publishTableMigration] publishing subtree to existing flattree",
164                            uptr(migration), 0);
165                 typename Details::FlatTree* flatTree = (typename Details::FlatTree*) (oldRoot & ~ureg(1));
166                 ureg subTreeEntriesPublished = 0;
167                 typename Details::Table* tableToReplace = migration->getSources()[0].table;
168                 // Wait here so that we only replace tables that are fully published.
169                 // Otherwise, there will be a race between a subtree and its own children.
170                 // (If all ManualResetEvent objects supported isPublished(), we could add a TURF_TRACE counter for this.
171                 // In previous tests, such a counter does in fact get hit.)
172                 tableToReplace->isPublished.wait();
173                 typename Details::Table* prevTable = NULL;
174                 for (;;) {
175                 publishLoop:
176                     if (migration->m_safeShift < flatTree->safeShift) {
177                         // We'll need to migrate to larger flattree before publishing our new subtree.
178                         // First, try to create a FlatTreeMigration with the necessary properties.
179                         // This will fail if an existing FlatTreeMigration has already been created using the same source.
180                         // In that case, we'll help complete the existing FlatTreeMigration, then we'll retry the loop.
181                         TURF_TRACE(ConcurrentMap_Grampa, 7, "[publishTableMigration] existing flattree too small",
182                                    uptr(migration), 0);
183                         typename Details::FlatTreeMigration* flatTreeMigration =
184                             Details::createFlatTreeMigration(*this, flatTree, migration->m_safeShift);
185                         tableToReplace->jobCoordinator.runOne(flatTreeMigration);
186                         flatTreeMigration->m_completed.wait(); // flatTreeMigration->m_destination becomes entirely visible
187                         flatTree = flatTreeMigration->m_destination;
188                         // The FlatTreeMigration has already been GC'ed by the last worker.
189                         // Retry the loop.
190                     } else {
191                         ureg repeat = ureg(1) << (migration->m_safeShift - flatTree->safeShift);
192                         ureg dstStartIndex = ureg(migration->m_baseHash >> flatTree->safeShift);
193                         // The subtree we're about to publish fits inside the flattree.
194                         TURF_ASSERT(dstStartIndex + migration->m_numDestinations * repeat - 1 <= Hash(-1) >> flatTree->safeShift);
195                         // If a previous attempt to publish got redirected, resume publishing into the new flattree,
196                         // starting with the first subtree entry that has not yet been fully published, as given by
197                         // subTreeEntriesPublished.
198                         // (Note: We could, in fact, restart the publish operation starting at entry 0. That would be valid too.
199                         // We are the only thread that can modify this particular range of the flattree at this time.)
200                         turf::Atomic<typename Details::Table*>* dstLeaf =
201                             flatTree->getTables() + dstStartIndex + (subTreeEntriesPublished * repeat);
202                         typename Details::Table** subFlatTree = migration->getDestinations();
203                         while (subTreeEntriesPublished < migration->m_numDestinations) {
204                             typename Details::Table* srcTable = subFlatTree[subTreeEntriesPublished];
205                             for (ureg r = repeat; r > 0; r--) {
206                                 typename Details::Table* probeTable = tableToReplace;
207                                 while (!dstLeaf->compareExchangeStrong(probeTable, srcTable, turf::Relaxed)) {
208                                     if (ureg(probeTable) == Details::RedirectFlatTree) {
209                                         // We've been redirected.
210                                         // Help with the FlatTreeMigration, then try again.
211                                         TURF_TRACE(ConcurrentMap_Grampa, 8, "[publishTableMigration] redirected", uptr(migration),
212                                                    uptr(dstLeaf));
213                                         typename Details::FlatTreeMigration* flatTreeMigration =
214                                             Details::getExistingFlatTreeMigration(flatTree);
215                                         tableToReplace->jobCoordinator.runOne(flatTreeMigration);
216                                         flatTreeMigration->m_completed.wait();
217                                         // flatTreeMigration->m_destination becomes entirely visible
218                                         flatTree = flatTreeMigration->m_destination;
219                                         goto publishLoop;
220                                     }
221                                     // The only other possibility is that we were previously redirected, and the subtree entry got
222                                     // partially published.
223                                     TURF_TRACE(ConcurrentMap_Grampa, 9, "[publishTableMigration] recovering from partial publish",
224                                                uptr(migration), 0);
225                                     TURF_ASSERT(probeTable == srcTable);
226                                 }
227                                 // The caller will GC the table) being replaced them since it's a source of the TableMigration.
228                                 dstLeaf++;
229                             }
230                             if (prevTable != srcTable) {
231                                 srcTable->isPublished.signal();
232                                 prevTable = srcTable;
233                             }
234                             subTreeEntriesPublished++;
235                         }
236                         // We've successfully published the migrated sub-flattree.
237                         // Caller will GC the TableMigration.
238                         break;
239                     }
240                 }
241             }
242         }
243     }
244
245     void publishFlatTreeMigration(typename Details::FlatTreeMigration* migration) {
246         // There are no racing writes.
247         // Old root must be the migration source (a flattree).
248         TURF_ASSERT(m_root.loadNonatomic() == (ureg(migration->m_source) | 1));
249         // Publish the new flattree, making entire table contents visible.
250         m_root.store(uptr(migration->m_destination) | 1, turf::Release);
251         // Don't GC the old flattree. The FlatTreeMigration will do that, since it's a source.
252     }
253
254     // A Mutator represents a known cell in the hash table.
255     // It's meant for manipulations within a temporary function scope.
256     // Obviously you must not call QSBR::Update while holding a Mutator.
257     // Any operation that modifies the table (exchangeValue, eraseValue)
258     // may be forced to follow a redirected cell, which changes the Mutator itself.
259     // Note that even if the Mutator was constructed from an existing cell,
260     // exchangeValue() can still trigger a resize if the existing cell was previously marked deleted,
261     // or if another thread deletes the key between the two steps.
262     class Mutator {
263     private:
264         friend class ConcurrentMap_Grampa;
265
266         ConcurrentMap_Grampa& m_map;
267         typename Details::Table* m_table;
268         ureg m_sizeMask;
269         typename Details::Cell* m_cell;
270         Value m_value;
271
272         // Constructor: Find existing cell
273         Mutator(ConcurrentMap_Grampa& map, Key key, bool) : m_map(map), m_value(Value(ValueTraits::NullValue)) {
274             TURF_TRACE(ConcurrentMap_Grampa, 10, "[Mutator] find constructor called", uptr(map.m_root.load(turf::Relaxed)),
275                        uptr(key));
276             Hash hash = KeyTraits::hash(key);
277             for (;;) {
278                 if (!m_map.locateTable(m_table, m_sizeMask, hash))
279                     return;
280                 m_cell = Details::find(hash, m_table, m_sizeMask);
281                 if (!m_cell)
282                     return;
283                 m_value = m_cell->value.load(turf::Consume);
284                 if (m_value != Value(ValueTraits::Redirect))
285                     return; // Found an existing value
286                 // We've encountered a Redirect value. Help finish the migration.
287                 TURF_TRACE(ConcurrentMap_Grampa, 11, "[Mutator] find was redirected", uptr(m_table), 0);
288                 m_table->jobCoordinator.participate();
289                 // Try again using the latest root.
290             }
291         }
292
293         // Constructor: Insert cell
294         Mutator(ConcurrentMap_Grampa& map, Key key) : m_map(map), m_value(Value(ValueTraits::NullValue)) {
295             TURF_TRACE(ConcurrentMap_Grampa, 12, "[Mutator] insert constructor called", uptr(map.m_root.load(turf::Relaxed)),
296                        uptr(key));
297             Hash hash = KeyTraits::hash(key);
298             for (;;) {
299                 if (!m_map.locateTable(m_table, m_sizeMask, hash)) {
300                     m_map.createInitialTable(Details::MinTableSize);
301                 } else {
302                     ureg overflowIdx;
303                     switch (Details::insert(hash, m_table, m_sizeMask, m_cell, overflowIdx)) { // Modifies m_cell
304                     case Details::InsertResult_InsertedNew: {
305                         // We've inserted a new cell. Don't load m_cell->value.
306                         return;
307                     }
308                     case Details::InsertResult_AlreadyFound: {
309                         // The hash was already found in the table.
310                         m_value = m_cell->value.load(turf::Consume);
311                         if (m_value == Value(ValueTraits::Redirect)) {
312                             // We've encountered a Redirect value.
313                             TURF_TRACE(ConcurrentMap_Grampa, 13, "[Mutator] insert was redirected", uptr(m_table), uptr(m_value));
314                             break; // Help finish the migration.
315                         }
316                         return; // Found an existing value
317                     }
318                     case Details::InsertResult_Overflow: {
319                         Details::beginTableMigration(m_map, m_table, overflowIdx);
320                         break;
321                     }
322                     }
323                     // A migration has been started (either by us, or another thread). Participate until it's complete.
324                     m_table->jobCoordinator.participate();
325                 }
326                 // Try again using the latest root.
327             }
328         }
329
330     public:
331         Value getValue() const {
332             // Return previously loaded value. Don't load it again.
333             return m_value;
334         }
335
336         Value exchangeValue(Value desired) {
337             TURF_ASSERT(desired != Value(ValueTraits::NullValue));
338             TURF_ASSERT(desired != Value(ValueTraits::Redirect));
339             TURF_ASSERT(m_cell); // Cell must have been found or inserted
340             TURF_TRACE(ConcurrentMap_Grampa, 14, "[Mutator::exchangeValue] called", uptr(m_table), uptr(m_value));
341             for (;;) {
342                 Value oldValue = m_value;
343                 if (m_cell->value.compareExchangeStrong(m_value, desired, turf::ConsumeRelease)) {
344                     // Exchange was successful. Return previous value.
345                     TURF_TRACE(ConcurrentMap_Grampa, 15, "[Mutator::exchangeValue] exchanged Value", uptr(m_value),
346                                uptr(desired));
347                     Value result = m_value;
348                     m_value = desired; // Leave the mutator in a valid state
349                     return result;
350                 }
351                 // The CAS failed and m_value has been updated with the latest value.
352                 if (m_value != Value(ValueTraits::Redirect)) {
353                     TURF_TRACE(ConcurrentMap_Grampa, 16, "[Mutator::exchangeValue] detected race to write value", uptr(m_table),
354                                uptr(m_value));
355                     if (oldValue == Value(ValueTraits::NullValue) && m_value != Value(ValueTraits::NullValue)) {
356                         TURF_TRACE(ConcurrentMap_Grampa, 17, "[Mutator::exchangeValue] racing write inserted new value",
357                                    uptr(m_table), uptr(m_value));
358                     }
359                     // There was a racing write (or erase) to this cell.
360                     // Pretend we exchanged with ourselves, and just let the racing write win.
361                     return desired;
362                 }
363                 // We've encountered a Redirect value. Help finish the migration.
364                 TURF_TRACE(ConcurrentMap_Grampa, 18, "[Mutator::exchangeValue] was redirected", uptr(m_table), uptr(m_value));
365                 Hash hash = m_cell->hash.load(turf::Relaxed);
366                 for (;;) {
367                     // Help complete the migration.
368                     m_table->jobCoordinator.participate();
369                     // Try again in the latest table.
370                     // FIXME: locateTable() could return false if the map is concurrently cleared (m_root set to 0).
371                     // This is not concern yet since clear() is not implemented.
372                     bool exists = m_map.locateTable(m_table, m_sizeMask, hash);
373                     TURF_ASSERT(exists);
374                     TURF_UNUSED(exists);
375                     m_value = Value(ValueTraits::NullValue);
376                     ureg overflowIdx;
377                     switch (Details::insert(hash, m_table, m_sizeMask, m_cell, overflowIdx)) { // Modifies m_cell
378                     case Details::InsertResult_AlreadyFound:
379                         m_value = m_cell->value.load(turf::Consume);
380                         if (m_value == Value(ValueTraits::Redirect)) {
381                             TURF_TRACE(ConcurrentMap_Grampa, 19, "[Mutator::exchangeValue] was re-redirected", uptr(m_table),
382                                        uptr(m_value));
383                             break;
384                         }
385                         goto breakOuter;
386                     case Details::InsertResult_InsertedNew:
387                         goto breakOuter;
388                     case Details::InsertResult_Overflow:
389                         TURF_TRACE(ConcurrentMap_Grampa, 20, "[Mutator::exchangeValue] overflow after redirect", uptr(m_table),
390                                    overflowIdx);
391                         Details::beginTableMigration(m_map, m_table, overflowIdx);
392                         break;
393                     }
394                     // We were redirected... again
395                 }
396             breakOuter:;
397                 // Try again in the new table.
398             }
399         }
400
401         void setValue(Value desired) {
402             exchangeValue(desired);
403         }
404
405         Value eraseValue() {
406             TURF_ASSERT(m_cell); // Cell must have been found or inserted
407             TURF_TRACE(ConcurrentMap_Grampa, 21, "[Mutator::eraseValue] called", uptr(m_table), uptr(m_value));
408             for (;;) {
409                 if (m_value == Value(ValueTraits::NullValue))
410                     return m_value;
411                 TURF_ASSERT(m_cell); // m_value is non-NullValue, therefore cell must have been found or inserted.
412                 if (m_cell->value.compareExchangeStrong(m_value, Value(ValueTraits::NullValue), turf::Consume)) {
413                     // Exchange was successful and a non-NullValue value was erased and returned by reference in m_value.
414                     TURF_ASSERT(m_value != Value(ValueTraits::NullValue)); // Implied by the test at the start of the loop.
415                     Value result = m_value;
416                     m_value = Value(ValueTraits::NullValue); // Leave the mutator in a valid state
417                     return result;
418                 }
419                 // The CAS failed and m_value has been updated with the latest value.
420                 TURF_TRACE(ConcurrentMap_Grampa, 22, "[Mutator::eraseValue] detected race to write value", uptr(m_table),
421                            uptr(m_value));
422                 if (m_value != Value(ValueTraits::Redirect)) {
423                     // There was a racing write (or erase) to this cell.
424                     // Pretend we erased nothing, and just let the racing write win.
425                     return Value(ValueTraits::NullValue);
426                 }
427                 // We've been redirected to a new table.
428                 TURF_TRACE(ConcurrentMap_Grampa, 23, "[Mutator::eraseValue] was redirected", uptr(m_table), uptr(m_cell));
429                 Hash hash = m_cell->hash.load(turf::Relaxed); // Re-fetch hash
430                 for (;;) {
431                     // Help complete the migration.
432                     m_table->jobCoordinator.participate();
433                     // Try again in the latest table.
434                     if (!m_map.locateTable(m_table, m_sizeMask, hash))
435                         m_cell = NULL;
436                     else
437                         m_cell = Details::find(hash, m_table, m_sizeMask);
438                     if (!m_cell) {
439                         m_value = Value(ValueTraits::NullValue);
440                         return m_value;
441                     }
442                     m_value = m_cell->value.load(turf::Relaxed);
443                     if (m_value != Value(ValueTraits::Redirect))
444                         break;
445                     TURF_TRACE(ConcurrentMap_Grampa, 24, "[Mutator::eraseValue] was re-redirected", uptr(m_table), uptr(m_cell));
446                 }
447             }
448         }
449     };
450
451     Mutator insert(Key key) {
452         return Mutator(*this, key);
453     }
454
455     Mutator find(Key key) {
456         return Mutator(*this, key, false);
457     }
458
459     // Lookup without creating a temporary Mutator.
460     Value get(Key key) {
461         Hash hash = KeyTraits::hash(key);
462         TURF_TRACE(ConcurrentMap_Grampa, 25, "[get] called", uptr(this), uptr(hash));
463         for (;;) {
464             typename Details::Table* table;
465             ureg sizeMask;
466             if (!locateTable(table, sizeMask, hash))
467                 return Value(ValueTraits::NullValue);
468             typename Details::Cell* cell = Details::find(hash, table, sizeMask);
469             if (!cell)
470                 return Value(ValueTraits::NullValue);
471             Value value = cell->value.load(turf::Consume);
472             if (value != Value(ValueTraits::Redirect))
473                 return value; // Found an existing value
474             // We've been redirected to a new table. Help with the migration.
475             TURF_TRACE(ConcurrentMap_Grampa, 26, "[get] was redirected", uptr(table), 0);
476             table->jobCoordinator.participate();
477             // Try again in the new table.
478         }
479     }
480
481     Value insert(Key key, Value desired) {
482         Mutator iter(*this, key);
483         return iter.exchangeValue(desired);
484     }
485
486     Value exchange(Key key, Value desired) {
487         Mutator iter(*this, key);
488         return iter.exchangeValue(desired);
489     }
490
491     Value erase(Key key) {
492         Mutator iter(*this, key, false);
493         return iter.eraseValue();
494     }
495
496     // The easiest way to implement an Iterator is to prevent all Redirects.
497     // The currrent Iterator does that by forbidding concurrent inserts.
498     // To make it work with concurrent inserts, we'd need a way to block TableMigrations as the Iterator visits each table.
499     // FlatTreeMigrations, too.
500     class Iterator {
501     private:
502         typename Details::FlatTree* m_flatTree;
503         ureg m_flatTreeIdx;
504         typename Details::Table* m_table;
505         ureg m_idx;
506         Key m_hash;
507         Value m_value;
508
509     public:
510         Iterator(ConcurrentMap_Grampa& map) {
511             // Since we've forbidden concurrent inserts (for now), nonatomic would suffice here, but let's plan ahead:
512             ureg root = map.m_root.load(turf::Consume);
513             if (root & 1) {
514                 m_flatTree = (typename Details::FlatTree*) (root & ~ureg(1));
515                 TURF_ASSERT(m_flatTree->getSize() > 0);
516                 m_flatTreeIdx = 0;
517                 m_table = m_flatTree->getTables()[0].load(turf::Consume);
518                 TURF_ASSERT(m_table);
519                 m_idx = -1;
520             } else {
521                 m_flatTree = NULL;
522                 m_flatTreeIdx = 0;
523                 m_table = (typename Details::Table*) root;
524                 m_idx = -1;
525             }
526             if (m_table) {
527                 next();
528             } else {
529                 m_hash = KeyTraits::NullHash;
530                 m_value = Value(ValueTraits::NullValue);
531             }
532         }
533
534         void next() {
535             TURF_ASSERT(m_table);
536             TURF_ASSERT(isValid() || m_idx == -1); // Either the Iterator is already valid, or we've just started iterating.
537             for (;;) {
538             searchInTable:
539                 m_idx++;
540                 if (m_idx <= m_table->sizeMask) {
541                     // Index still inside range of table.
542                     typename Details::CellGroup* group = m_table->getCellGroups() + (m_idx >> 2);
543                     typename Details::Cell* cell = group->cells + (m_idx & 3);
544                     m_hash = cell->hash.load(turf::Relaxed);
545                     if (m_hash != KeyTraits::NullHash) {
546                         // Cell has been reserved.
547                         m_value = cell->value.load(turf::Relaxed);
548                         TURF_ASSERT(m_value != Value(ValueTraits::Redirect));
549                         if (m_value != Value(ValueTraits::NullValue))
550                             return; // Yield this cell.
551                     }
552                 } else {
553                     // We've advanced past the end of this table.
554                     if (m_flatTree) {
555                         // Scan for the next unique table in the flattree.
556                         while (++m_flatTreeIdx < m_flatTree->getSize()) {
557                             typename Details::Table* nextTable = m_flatTree->getTables()[m_flatTreeIdx].load(turf::Consume);
558                             if (nextTable != m_table) {
559                                 // Found the next table.
560                                 m_table = nextTable;
561                                 m_idx = -1;
562                                 goto searchInTable; // Continue iterating in this table.
563                             }
564                         }
565                     }
566                     // That's the end of the entire map.
567                     m_hash = KeyTraits::NullHash;
568                     m_value = Value(ValueTraits::NullValue);
569                     return;
570                 }
571             }
572         }
573
574         bool isValid() const {
575             return m_value != Value(ValueTraits::NullValue);
576         }
577
578         Key getKey() const {
579             TURF_ASSERT(isValid());
580             // Since we've forbidden concurrent inserts (for now), nonatomic would suffice here, but let's plan ahead:
581             return KeyTraits::dehash(m_hash);
582         }
583
584         Value getValue() const {
585             TURF_ASSERT(isValid());
586             return m_value;
587         }
588     };
589 };
590
591 } // namespace junction
592
593 #endif // JUNCTION_CONCURRENTMAP_GRAMPA_H