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

[junction.git] / junction / ConcurrentMap_Linear.h

diff --git a/junction/ConcurrentMap_Linear.h b/junction/ConcurrentMap_Linear.h
index b93d86e342be2ac1a5ab526d7cfafe8dd683eb49..6799c916e557aaf2a16e70b0b5c8c887e2a0764b 100644 (file)
--- a/junction/ConcurrentMap_Linear.h
+++ b/junction/ConcurrentMap_Linear.h
@@ -74,16 +74,19 @@ public:
 
         // Constructor: Find existing cell
         Mutator(ConcurrentMap_Linear& map, Key key, bool) : m_map(map), m_value(Value(ValueTraits::NullValue)) {
-            TURF_TRACE(ConcurrentMap_Linear, 0, "[Mutator] find constructor called", uptr(m_table), uptr(key));
+            TURF_TRACE(ConcurrentMap_Linear, 0, "[Mutator] find constructor called", uptr(0), uptr(key));
             Hash hash = KeyTraits::hash(key);
             for (;;) {
                 m_table = m_map.m_root.load(turf::Consume);
                 m_cell = Details::find(hash, m_table);
                 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_Linear, 1, "[Mutator] find was redirected", uptr(m_table), 0);
                 m_table->jobCoordinator.participate();
@@ -92,27 +95,28 @@ public:
         }
 
         // Constructor: Insert cell
-        Mutator(ConcurrentMap_Linear& map, Key key)
-            : m_map(map), m_table(map.m_root.load(turf::Consume)), m_value(Value(ValueTraits::NullValue)) {
-            TURF_TRACE(ConcurrentMap_Linear, 2, "[Mutator] insert constructor called", uptr(m_table), uptr(key));
+        Mutator(ConcurrentMap_Linear& map, Key key) : m_map(map), m_value(Value(ValueTraits::NullValue)) {
+            TURF_TRACE(ConcurrentMap_Linear, 2, "[Mutator] insertOrFind constructor called", uptr(0), uptr(key));
             Hash hash = KeyTraits::hash(key);
             bool mustDouble = false;
             for (;;) {
                 m_table = m_map.m_root.load(turf::Consume);
-                switch (Details::insert(hash, m_table, m_cell)) { // Modifies m_cell
+                switch (Details::insertOrFind(hash, m_table, m_cell)) { // 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_Linear, 3, "[Mutator] insert was redirected", uptr(m_table), uptr(m_value));
+                        TURF_TRACE(ConcurrentMap_Linear, 3, "[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, mustDouble);
@@ -169,7 +173,7 @@ public:
                     // Try again in the new table.
                     m_table = m_map.m_root.load(turf::Consume);
                     m_value = Value(ValueTraits::NullValue);
-                    switch (Details::insert(hash, m_table, m_cell)) { // Modifies m_cell
+                    switch (Details::insertOrFind(hash, m_table, m_cell)) { // Modifies m_cell
                     case Details::InsertResult_AlreadyFound:
                         m_value = m_cell->value.load(turf::Consume);
                         if (m_value == Value(ValueTraits::Redirect)) {
@@ -194,7 +198,7 @@ public:
             }
         }
 
-        void setValue(Value desired) {
+        void assignValue(Value desired) {
             exchangeValue(desired);
         }
 
@@ -244,7 +248,7 @@ public:
         }
     };
 
-    Mutator insert(Key key) {
+    Mutator insertOrFind(Key key) {
         return Mutator(*this, key);
     }
 
@@ -271,7 +275,7 @@ public:
         }
     }
 
-    Value insert(Key key, Value desired) {
+    Value assign(Key key, Value desired) {
         Mutator iter(*this, key);
         return iter.exchangeValue(desired);
     }
@@ -321,7 +325,7 @@ public:
             }
             // That's the end of the map.
             m_hash = KeyTraits::NullHash;
-            m_value = ValueTraits::NullValue;
+            m_value = Value(ValueTraits::NullValue);
         }
 
         bool isValid() const {