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                 Value value = m_cell->value.load(turf::Consume);
 284                 if (value != Value(ValueTraits::Redirect)) {
 285                     // Found an existing value
 286                     m_value = value;
 287                     return;
 288                 }
 289                 // We've encountered a Redirect value. Help finish the migration.
 290                 TURF_TRACE(ConcurrentMap_Grampa, 11, "[Mutator] find was redirected", uptr(m_table), 0);
 291                 m_table->jobCoordinator.participate();
 292                 // Try again using the latest root.
 293             }
 294         }
 295
 296         // Constructor: Insert or find cell
 297         Mutator(ConcurrentMap_Grampa& map, Key key) : m_map(map), m_value(Value(ValueTraits::NullValue)) {
 298             TURF_TRACE(ConcurrentMap_Grampa, 12, "[Mutator] insertOrFind constructor called", uptr(map.m_root.load(turf::Relaxed)),
 299                        uptr(key));
 300             Hash hash = KeyTraits::hash(key);
 301             for (;;) {
 302                 if (!m_map.locateTable(m_table, m_sizeMask, hash)) {
 303                     m_map.createInitialTable(Details::MinTableSize);
 304                 } else {
 305                     ureg overflowIdx;
 306                     switch (Details::insertOrFind(hash, m_table, m_sizeMask, m_cell, overflowIdx)) { // Modifies m_cell
 307                     case Details::InsertResult_InsertedNew: {
 308                         // We've inserted a new cell. Don't load m_cell->value.
 309                         return;
 310                     }
 311                     case Details::InsertResult_AlreadyFound: {
 312                         // The hash was already found in the table.
 313                         Value value = m_cell->value.load(turf::Consume);
 314                         if (value == Value(ValueTraits::Redirect)) {
 315                             // We've encountered a Redirect value.
 316                             TURF_TRACE(ConcurrentMap_Grampa, 13, "[Mutator] insertOrFind was redirected", uptr(m_table), uptr(m_value));
 317                             break; // Help finish the migration.
 318                         }
 319                         // Found an existing value
 320                         m_value = value;
 321                         return;
 322                     }
 323                     case Details::InsertResult_Overflow: {
 324                         Details::beginTableMigration(m_map, m_table, overflowIdx);
 325                         break;
 326                     }
 327                     }
 328                     // A migration has been started (either by us, or another thread). Participate until it's complete.
 329                     m_table->jobCoordinator.participate();
 330                 }
 331                 // Try again using the latest root.
 332             }
 333         }
 334
 335     public:
 336         Value getValue() const {
 337             // Return previously loaded value. Don't load it again.
 338             return m_value;
 339         }
 340
 341         Value exchangeValue(Value desired) {
 342             TURF_ASSERT(desired != Value(ValueTraits::NullValue));
 343             TURF_ASSERT(desired != Value(ValueTraits::Redirect));
 344             TURF_ASSERT(m_cell); // Cell must have been found or inserted
 345             TURF_TRACE(ConcurrentMap_Grampa, 14, "[Mutator::exchangeValue] called", uptr(m_table), uptr(m_value));
 346             for (;;) {
 347                 Value oldValue = m_value;
 348                 if (m_cell->value.compareExchangeStrong(m_value, desired, turf::ConsumeRelease)) {
 349                     // Exchange was successful. Return previous value.
 350                     TURF_TRACE(ConcurrentMap_Grampa, 15, "[Mutator::exchangeValue] exchanged Value", uptr(m_value),
 351                                uptr(desired));
 352                     Value result = m_value;
 353                     m_value = desired; // Leave the mutator in a valid state
 354                     return result;
 355                 }
 356                 // The CAS failed and m_value has been updated with the latest value.
 357                 if (m_value != Value(ValueTraits::Redirect)) {
 358                     TURF_TRACE(ConcurrentMap_Grampa, 16, "[Mutator::exchangeValue] detected race to write value", uptr(m_table),
 359                                uptr(m_value));
 360                     if (oldValue == Value(ValueTraits::NullValue) && m_value != Value(ValueTraits::NullValue)) {
 361                         TURF_TRACE(ConcurrentMap_Grampa, 17, "[Mutator::exchangeValue] racing write inserted new value",
 362                                    uptr(m_table), uptr(m_value));
 363                     }
 364                     // There was a racing write (or erase) to this cell.
 365                     // Pretend we exchanged with ourselves, and just let the racing write win.
 366                     return desired;
 367                 }
 368                 // We've encountered a Redirect value. Help finish the migration.
 369                 TURF_TRACE(ConcurrentMap_Grampa, 18, "[Mutator::exchangeValue] was redirected", uptr(m_table), uptr(m_value));
 370                 Hash hash = m_cell->hash.load(turf::Relaxed);
 371                 for (;;) {
 372                     // Help complete the migration.
 373                     m_table->jobCoordinator.participate();
 374                     // Try again in the latest table.
 375                     // FIXME: locateTable() could return false if the map is concurrently cleared (m_root set to 0).
 376                     // This is not concern yet since clear() is not implemented.
 377                     bool exists = m_map.locateTable(m_table, m_sizeMask, hash);
 378                     TURF_ASSERT(exists);
 379                     TURF_UNUSED(exists);
 380                     m_value = Value(ValueTraits::NullValue);
 381                     ureg overflowIdx;
 382                     switch (Details::insertOrFind(hash, m_table, m_sizeMask, m_cell, overflowIdx)) { // Modifies m_cell
 383                     case Details::InsertResult_AlreadyFound:
 384                         m_value = m_cell->value.load(turf::Consume);
 385                         if (m_value == Value(ValueTraits::Redirect)) {
 386                             TURF_TRACE(ConcurrentMap_Grampa, 19, "[Mutator::exchangeValue] was re-redirected", uptr(m_table),
 387                                        uptr(m_value));
 388                             break;
 389                         }
 390                         goto breakOuter;
 391                     case Details::InsertResult_InsertedNew:
 392                         goto breakOuter;
 393                     case Details::InsertResult_Overflow:
 394                         TURF_TRACE(ConcurrentMap_Grampa, 20, "[Mutator::exchangeValue] overflow after redirect", uptr(m_table),
 395                                    overflowIdx);
 396                         Details::beginTableMigration(m_map, m_table, overflowIdx);
 397                         break;
 398                     }
 399                     // We were redirected... again
 400                 }
 401             breakOuter:;
 402                 // Try again in the new table.
 403             }
 404         }
 405
 406         void assignValue(Value desired) {
 407             exchangeValue(desired);
 408         }
 409
 410         Value eraseValue() {
 411             TURF_ASSERT(m_cell); // Cell must have been found or inserted
 412             TURF_TRACE(ConcurrentMap_Grampa, 21, "[Mutator::eraseValue] called", uptr(m_table), uptr(m_value));
 413             for (;;) {
 414                 if (m_value == Value(ValueTraits::NullValue))
 415                     return m_value;
 416                 TURF_ASSERT(m_cell); // m_value is non-NullValue, therefore cell must have been found or inserted.
 417                 if (m_cell->value.compareExchangeStrong(m_value, Value(ValueTraits::NullValue), turf::Consume)) {
 418                     // Exchange was successful and a non-NullValue value was erased and returned by reference in m_value.
 419                     TURF_ASSERT(m_value != Value(ValueTraits::NullValue)); // Implied by the test at the start of the loop.
 420                     Value result = m_value;
 421                     m_value = Value(ValueTraits::NullValue); // Leave the mutator in a valid state
 422                     return result;
 423                 }
 424                 // The CAS failed and m_value has been updated with the latest value.
 425                 TURF_TRACE(ConcurrentMap_Grampa, 22, "[Mutator::eraseValue] detected race to write value", uptr(m_table),
 426                            uptr(m_value));
 427                 if (m_value != Value(ValueTraits::Redirect)) {
 428                     // There was a racing write (or erase) to this cell.
 429                     // Pretend we erased nothing, and just let the racing write win.
 430                     return Value(ValueTraits::NullValue);
 431                 }
 432                 // We've been redirected to a new table.
 433                 TURF_TRACE(ConcurrentMap_Grampa, 23, "[Mutator::eraseValue] was redirected", uptr(m_table), uptr(m_cell));
 434                 Hash hash = m_cell->hash.load(turf::Relaxed); // Re-fetch hash
 435                 for (;;) {
 436                     // Help complete the migration.
 437                     m_table->jobCoordinator.participate();
 438                     // Try again in the latest table.
 439                     if (!m_map.locateTable(m_table, m_sizeMask, hash))
 440                         m_cell = NULL;
 441                     else
 442                         m_cell = Details::find(hash, m_table, m_sizeMask);
 443                     if (!m_cell) {
 444                         m_value = Value(ValueTraits::NullValue);
 445                         return m_value;
 446                     }
 447                     m_value = m_cell->value.load(turf::Relaxed);
 448                     if (m_value != Value(ValueTraits::Redirect))
 449                         break;
 450                     TURF_TRACE(ConcurrentMap_Grampa, 24, "[Mutator::eraseValue] was re-redirected", uptr(m_table), uptr(m_cell));
 451                 }
 452             }
 453         }
 454     };
 455
 456     Mutator insertOrFind(Key key) {
 457         return Mutator(*this, key);
 458     }
 459
 460     Mutator find(Key key) {
 461         return Mutator(*this, key, false);
 462     }
 463
 464     // Lookup without creating a temporary Mutator.
 465     Value get(Key key) {
 466         Hash hash = KeyTraits::hash(key);
 467         TURF_TRACE(ConcurrentMap_Grampa, 25, "[get] called", uptr(this), uptr(hash));
 468         for (;;) {
 469             typename Details::Table* table;
 470             ureg sizeMask;
 471             if (!locateTable(table, sizeMask, hash))
 472                 return Value(ValueTraits::NullValue);
 473             typename Details::Cell* cell = Details::find(hash, table, sizeMask);
 474             if (!cell)
 475                 return Value(ValueTraits::NullValue);
 476             Value value = cell->value.load(turf::Consume);
 477             if (value != Value(ValueTraits::Redirect))
 478                 return value; // Found an existing value
 479             // We've been redirected to a new table. Help with the migration.
 480             TURF_TRACE(ConcurrentMap_Grampa, 26, "[get] was redirected", uptr(table), 0);
 481             table->jobCoordinator.participate();
 482             // Try again in the new table.
 483         }
 484     }
 485
 486     Value assign(Key key, Value desired) {
 487         Mutator iter(*this, key);
 488         return iter.exchangeValue(desired);
 489     }
 490
 491     Value exchange(Key key, Value desired) {
 492         Mutator iter(*this, key);
 493         return iter.exchangeValue(desired);
 494     }
 495
 496     Value erase(Key key) {
 497         Mutator iter(*this, key, false);
 498         return iter.eraseValue();
 499     }
 500
 501     // The easiest way to implement an Iterator is to prevent all Redirects.
 502     // The currrent Iterator does that by forbidding concurrent inserts.
 503     // To make it work with concurrent inserts, we'd need a way to block TableMigrations as the Iterator visits each table.
 504     // FlatTreeMigrations, too.
 505     class Iterator {
 506     private:
 507         typename Details::FlatTree* m_flatTree;
 508         ureg m_flatTreeIdx;
 509         typename Details::Table* m_table;
 510         ureg m_idx;
 511         Key m_hash;
 512         Value m_value;
 513
 514     public:
 515         Iterator(ConcurrentMap_Grampa& map) {
 516             // Since we've forbidden concurrent inserts (for now), nonatomic would suffice here, but let's plan ahead:
 517             ureg root = map.m_root.load(turf::Consume);
 518             if (root & 1) {
 519                 m_flatTree = (typename Details::FlatTree*) (root & ~ureg(1));
 520                 TURF_ASSERT(m_flatTree->getSize() > 0);
 521                 m_flatTreeIdx = 0;
 522                 m_table = m_flatTree->getTables()[0].load(turf::Consume);
 523                 TURF_ASSERT(m_table);
 524                 m_idx = -1;
 525             } else {
 526                 m_flatTree = NULL;
 527                 m_flatTreeIdx = 0;
 528                 m_table = (typename Details::Table*) root;
 529                 m_idx = -1;
 530             }
 531             if (m_table) {
 532                 next();
 533             } else {
 534                 m_hash = KeyTraits::NullHash;
 535                 m_value = Value(ValueTraits::NullValue);
 536             }
 537         }
 538
 539         void next() {
 540             TURF_ASSERT(m_table);
 541             TURF_ASSERT(isValid() || m_idx == -1); // Either the Iterator is already valid, or we've just started iterating.
 542             for (;;) {
 543             searchInTable:
 544                 m_idx++;
 545                 if (m_idx <= m_table->sizeMask) {
 546                     // Index still inside range of table.
 547                     typename Details::CellGroup* group = m_table->getCellGroups() + (m_idx >> 2);
 548                     typename Details::Cell* cell = group->cells + (m_idx & 3);
 549                     m_hash = cell->hash.load(turf::Relaxed);
 550                     if (m_hash != KeyTraits::NullHash) {
 551                         // Cell has been reserved.
 552                         m_value = cell->value.load(turf::Relaxed);
 553                         TURF_ASSERT(m_value != Value(ValueTraits::Redirect));
 554                         if (m_value != Value(ValueTraits::NullValue))
 555                             return; // Yield this cell.
 556                     }
 557                 } else {
 558                     // We've advanced past the end of this table.
 559                     if (m_flatTree) {
 560                         // Scan for the next unique table in the flattree.
 561                         while (++m_flatTreeIdx < m_flatTree->getSize()) {
 562                             typename Details::Table* nextTable = m_flatTree->getTables()[m_flatTreeIdx].load(turf::Consume);
 563                             if (nextTable != m_table) {
 564                                 // Found the next table.
 565                                 m_table = nextTable;
 566                                 m_idx = -1;
 567                                 goto searchInTable; // Continue iterating in this table.
 568                             }
 569                         }
 570                     }
 571                     // That's the end of the entire map.
 572                     m_hash = KeyTraits::NullHash;
 573                     m_value = Value(ValueTraits::NullValue);
 574                     return;
 575                 }
 576             }
 577         }
 578
 579         bool isValid() const {
 580             return m_value != Value(ValueTraits::NullValue);
 581         }
 582
 583         Key getKey() const {
 584             TURF_ASSERT(isValid());
 585             // Since we've forbidden concurrent inserts (for now), nonatomic would suffice here, but let's plan ahead:
 586             return KeyTraits::dehash(m_hash);
 587         }
 588
 589         Value getValue() const {
 590             TURF_ASSERT(isValid());
 591             return m_value;
 592         }
 593     };
 594 };
 595
 596 } // namespace junction
 597
 598 #endif // JUNCTION_CONCURRENTMAP_GRAMPA_H