Changes libcds library path

[junction.git] / junction / ConcurrentMap_Linear.h

diff --git a/junction/ConcurrentMap_Linear.h b/junction/ConcurrentMap_Linear.h
index bf6c1eaa305b9c3cab88808409c6224375ba0ce0..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,34 +95,38 @@ 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);
+                    Details::beginTableMigration(m_map, m_table, mustDouble);
                     break;
                 }
                 }
                 // A migration has been started (either by us, or another thread). Participate until it's complete.
                 m_table->jobCoordinator.participate();
+                // If we still overflow after this, avoid an infinite loop by forcing the next table to double.
+                mustDouble = true;
                 // Try again using the latest root.
             }
         }
@@ -132,8 +139,10 @@ 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_Linear, 4, "[Mutator::exchangeValue] called", uptr(m_table), uptr(m_value));
+            bool mustDouble = false;
             for (;;) {
                 Value oldValue = m_value;
                 if (m_cell->value.compareExchangeStrong(m_value, desired, turf::ConsumeRelease)) {
@@ -164,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)) {
@@ -177,9 +186,11 @@ public:
                         goto breakOuter;
                     case Details::InsertResult_Overflow:
                         TURF_TRACE(ConcurrentMap_Linear, 10, "[Mutator::exchangeValue] overflow after redirect", uptr(m_table), 0);
-                        Details::beginTableMigration(m_map, m_table);
+                        Details::beginTableMigration(m_map, m_table, mustDouble);
                         break;
                     }
+                    // If we still overflow after this, avoid an infinite loop by forcing the next table to double.
+                    mustDouble = true;
                     // We were redirected... again
                 }
             breakOuter:;
@@ -187,7 +198,7 @@ public:
             }
         }
 
-        void setValue(Value desired) {
+        void assignValue(Value desired) {
             exchangeValue(desired);
         }
 
@@ -237,7 +248,7 @@ public:
         }
     };
 
-    Mutator insert(Key key) {
+    Mutator insertOrFind(Key key) {
         return Mutator(*this, key);
     }
 
@@ -264,7 +275,7 @@ public:
         }
     }
 
-    Value insert(Key key, Value desired) {
+    Value assign(Key key, Value desired) {
         Mutator iter(*this, key);
         return iter.exchangeValue(desired);
     }
@@ -314,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 {