Fix #31: Entries can disappear when deleted key is reassigned during a migration

[junction.git] / junction / ConcurrentMap_Grampa.h

diff --git a/junction/ConcurrentMap_Grampa.h b/junction/ConcurrentMap_Grampa.h
index b0d6cec75b95cde1da4bed6912d2904cd1d37c81..dc4749cb60128095b9f508b1c3d07681dec9ea54 100644 (file)
--- a/junction/ConcurrentMap_Grampa.h
+++ b/junction/ConcurrentMap_Grampa.h
@@ -41,7 +41,7 @@ private:
         if (root & 1) {
             typename Details::FlatTree* flatTree = (typename Details::FlatTree*) (root & ~ureg(1));
             for (;;) {
-                ureg leafIdx = (hash >> flatTree->safeShift);
+                ureg leafIdx = ureg(hash >> flatTree->safeShift);
                 table = flatTree->getTables()[leafIdx].load(turf::Relaxed);
                 if (ureg(table) != Details::RedirectFlatTree) {
                     sizeMask = (Details::LeafSize - 1);
@@ -189,7 +189,7 @@ public:
                         // Retry the loop.
                     } else {
                         ureg repeat = ureg(1) << (migration->m_safeShift - flatTree->safeShift);
-                        ureg dstStartIndex = migration->m_baseHash >> flatTree->safeShift;
+                        ureg dstStartIndex = ureg(migration->m_baseHash >> flatTree->safeShift);
                         // The subtree we're about to publish fits inside the flattree.
                         TURF_ASSERT(dstStartIndex + migration->m_numDestinations * repeat - 1 <= Hash(-1) >> flatTree->safeShift);
                         // If a previous attempt to publish got redirected, resume publishing into the new flattree,
@@ -280,9 +280,12 @@ public:
                 m_cell = Details::find(hash, m_table, m_sizeMask);
                 if (!m_cell)
                     return;
-                m_value = m_cell->value.load(turf::Consume);
-                if (m_value != Value(ValueTraits::Redirect))
-                    return; // Found an existing value
+                Value value = m_cell->value.load(turf::Consume);
+                if (value != Value(ValueTraits::Redirect)) {
+                    // Found an existing value
+                    m_value = value;
+                    return;
+                }
                 // We've encountered a Redirect value. Help finish the migration.
                 TURF_TRACE(ConcurrentMap_Grampa, 11, "[Mutator] find was redirected", uptr(m_table), 0);
                 m_table->jobCoordinator.participate();
@@ -290,9 +293,9 @@ public:
             }
         }
 
-        // Constructor: Insert cell
+        // Constructor: Insert or find cell
         Mutator(ConcurrentMap_Grampa& map, Key key) : m_map(map), m_value(Value(ValueTraits::NullValue)) {
-            TURF_TRACE(ConcurrentMap_Grampa, 12, "[Mutator] insert constructor called", uptr(map.m_root.load(turf::Relaxed)),
+            TURF_TRACE(ConcurrentMap_Grampa, 12, "[Mutator] insertOrFind constructor called", uptr(map.m_root.load(turf::Relaxed)),
                        uptr(key));
             Hash hash = KeyTraits::hash(key);
             for (;;) {
@@ -300,20 +303,22 @@ public:
                     m_map.createInitialTable(Details::MinTableSize);
                 } else {
                     ureg overflowIdx;
-                    switch (Details::insert(hash, m_table, m_sizeMask, m_cell, overflowIdx)) { // Modifies m_cell
+                    switch (Details::insertOrFind(hash, m_table, m_sizeMask, m_cell, overflowIdx)) { // Modifies m_cell
                     case Details::InsertResult_InsertedNew: {
                         // We've inserted a new cell. Don't load m_cell->value.
                         return;
                     }
                     case Details::InsertResult_AlreadyFound: {
                         // The hash was already found in the table.
-                        m_value = m_cell->value.load(turf::Consume);
-                        if (m_value == Value(ValueTraits::Redirect)) {
+                        Value value = m_cell->value.load(turf::Consume);
+                        if (value == Value(ValueTraits::Redirect)) {
                             // We've encountered a Redirect value.
-                            TURF_TRACE(ConcurrentMap_Grampa, 13, "[Mutator] insert was redirected", uptr(m_table), uptr(m_value));
+                            TURF_TRACE(ConcurrentMap_Grampa, 13, "[Mutator] insertOrFind was redirected", uptr(m_table), uptr(m_value));
                             break; // Help finish the migration.
                         }
-                        return; // Found an existing value
+                        // Found an existing value
+                        m_value = value;
+                        return; 
                     }
                     case Details::InsertResult_Overflow: {
                         Details::beginTableMigration(m_map, m_table, overflowIdx);
@@ -335,6 +340,7 @@ public:
 
         Value exchangeValue(Value desired) {
             TURF_ASSERT(desired != Value(ValueTraits::NullValue));
+            TURF_ASSERT(desired != Value(ValueTraits::Redirect));
             TURF_ASSERT(m_cell); // Cell must have been found or inserted
             TURF_TRACE(ConcurrentMap_Grampa, 14, "[Mutator::exchangeValue] called", uptr(m_table), uptr(m_value));
             for (;;) {
@@ -373,7 +379,7 @@ public:
                     TURF_UNUSED(exists);
                     m_value = Value(ValueTraits::NullValue);
                     ureg overflowIdx;
-                    switch (Details::insert(hash, m_table, m_sizeMask, m_cell, overflowIdx)) { // Modifies m_cell
+                    switch (Details::insertOrFind(hash, m_table, m_sizeMask, m_cell, overflowIdx)) { // Modifies m_cell
                     case Details::InsertResult_AlreadyFound:
                         m_value = m_cell->value.load(turf::Consume);
                         if (m_value == Value(ValueTraits::Redirect)) {
@@ -397,7 +403,7 @@ public:
             }
         }
 
-        void setValue(Value desired) {
+        void assignValue(Value desired) {
             exchangeValue(desired);
         }
 
@@ -447,7 +453,7 @@ public:
         }
     };
 
-    Mutator insert(Key key) {
+    Mutator insertOrFind(Key key) {
         return Mutator(*this, key);
     }
 
@@ -477,7 +483,7 @@ public:
         }
     }
 
-    Value insert(Key key, Value desired) {
+    Value assign(Key key, Value desired) {
         Mutator iter(*this, key);
         return iter.exchangeValue(desired);
     }