Rename insert() to set() to avoid confusion with std::map::insert()
authorJeff Preshing <filter-github@preshing.com>
Sun, 21 Feb 2016 18:38:01 +0000 (13:38 -0500)
committerJeff Preshing <filter-github@preshing.com>
Sun, 21 Feb 2016 18:38:01 +0000 (13:38 -0500)
std::map::insert() will only store the value if the key doesn't already exist.
junction::ConcurrentMap_xxx::set() stores the value unconditionally.

33 files changed:
README.md
junction/ConcurrentMap_Crude.h
junction/ConcurrentMap_Grampa.cpp
junction/ConcurrentMap_Grampa.h
junction/ConcurrentMap_LeapFrog.cpp
junction/ConcurrentMap_LeapFrog.h
junction/ConcurrentMap_Linear.cpp
junction/ConcurrentMap_Linear.h
junction/SingleMap_Linear.h
junction/details/Grampa.cpp
junction/details/Grampa.h
junction/details/LeapFrog.cpp
junction/details/LeapFrog.h
junction/details/Linear.cpp
junction/details/Linear.h
junction/extra/impl/MapAdapter_CDS_Cuckoo.h
junction/extra/impl/MapAdapter_CDS_Michael.h
junction/extra/impl/MapAdapter_Folly.h
junction/extra/impl/MapAdapter_LibCuckoo.h
junction/extra/impl/MapAdapter_Linear_Mutex.h
junction/extra/impl/MapAdapter_Linear_RWLock.h
junction/extra/impl/MapAdapter_NBDS.h
junction/extra/impl/MapAdapter_Null.h
junction/extra/impl/MapAdapter_StdMap.h
junction/extra/impl/MapAdapter_TBB.h
junction/extra/impl/MapAdapter_Tervel.h
samples/MallocTest/MallocTest.cpp
samples/MapCorrectnessTests/TestChurn.h
samples/MapCorrectnessTests/TestInsertDifferentKeys.h
samples/MapCorrectnessTests/TestInsertSameKeys.h
samples/MapLinearizabilityTest/MapLinearizabilityTest.cpp
samples/MapPerformanceTests/MapPerformanceTests.cpp
samples/MapScalabilityTests/MapScalabilityTests.cpp

index 195a747..96d4dd2 100644 (file)
--- a/README.md
+++ b/README.md
@@ -102,9 +102,9 @@ The `JUNCTION_USERCONFIG` variable works in a similar way. As an example, take a
 A Junction map is a lot like a big array of `std::atomic<>` variables, where the key is an index into the array. More precisely:
 
 * All of a Junction map's member functions, together with its `Mutator` member functions, are atomic with respect to each other, so you can safely call them from any thread without mutual exclusion.
-* If an `insert` [happens before](http://preshing.com/20130702/the-happens-before-relation/) a `get` with the same key, the `get` will return the value it inserted, except if another operation changes the value in between. Any [synchronizing operation](http://preshing.com/20130823/the-synchronizes-with-relation/) will establish this relationship.
-* For Linear, LeapFrog and Grampa maps, `insert` is a [release](http://preshing.com/20120913/acquire-and-release-semantics/) operation and `get` is a [consume](http://preshing.com/20140709/the-purpose-of-memory_order_consume-in-cpp11/) operation, so you can safely pass non-atomic information between threads using a pointer. For Crude maps, all operations are relaxed.
-* In the current version, you must not insert while concurrently using an `Iterator`.
+* If an `set` [happens before](http://preshing.com/20130702/the-happens-before-relation/) a `get` with the same key, the `get` will return the value set, except if another operation changes the value in between. Any [synchronizing operation](http://preshing.com/20130823/the-synchronizes-with-relation/) will establish this relationship.
+* For Linear, LeapFrog and Grampa maps, `set` is a [release](http://preshing.com/20120913/acquire-and-release-semantics/) operation and `get` is a [consume](http://preshing.com/20140709/the-purpose-of-memory_order_consume-in-cpp11/) operation, so you can safely pass non-atomic information between threads using a pointer. For Crude maps, all operations are relaxed.
+* In the current version, you must not set while concurrently using an `Iterator`.
 
 ## Feedback
 
index c78e4cf..d064a48 100644 (file)
@@ -49,7 +49,7 @@ public:
         delete[] m_cells;
     }
 
-    void insert(Key key, Value value) {
+    void set(Key key, Value value) {
         TURF_ASSERT(key != KeyTraits::NullKey);
         TURF_ASSERT(value != Value(ValueTraits::NullValue));
 
index 79b5b5b..902e613 100644 (file)
@@ -27,8 +27,8 @@ TURF_TRACE_DEFINE("[publishTableMigration] redirected")
 TURF_TRACE_DEFINE("[publishTableMigration] recovering from partial publish")
 TURF_TRACE_DEFINE("[Mutator] find constructor called")
 TURF_TRACE_DEFINE("[Mutator] find was redirected")
-TURF_TRACE_DEFINE("[Mutator] insert constructor called")
-TURF_TRACE_DEFINE("[Mutator] insert was redirected")
+TURF_TRACE_DEFINE("[Mutator] insertOrFind constructor called")
+TURF_TRACE_DEFINE("[Mutator] insertOrFind was redirected")
 TURF_TRACE_DEFINE("[Mutator::exchangeValue] called")
 TURF_TRACE_DEFINE("[Mutator::exchangeValue] exchanged Value")
 TURF_TRACE_DEFINE("[Mutator::exchangeValue] detected race to write value")
index 27e18ff..c8fdc8d 100644 (file)
@@ -290,9 +290,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,7 +300,7 @@ 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;
@@ -310,7 +310,7 @@ public:
                         m_value = m_cell->value.load(turf::Consume);
                         if (m_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
@@ -374,7 +374,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)) {
@@ -448,7 +448,7 @@ public:
         }
     };
 
-    Mutator insert(Key key) {
+    Mutator insertOrFind(Key key) {
         return Mutator(*this, key);
     }
 
@@ -478,7 +478,7 @@ public:
         }
     }
 
-    Value insert(Key key, Value desired) {
+    Value set(Key key, Value desired) {
         Mutator iter(*this, key);
         return iter.exchangeValue(desired);
     }
index 46ef668..67a39ad 100644 (file)
@@ -17,8 +17,8 @@ namespace junction {
 TURF_TRACE_DEFINE_BEGIN(ConcurrentMap_LeapFrog, 17) // autogenerated by TidySource.py
 TURF_TRACE_DEFINE("[Mutator] find constructor called")
 TURF_TRACE_DEFINE("[Mutator] find was redirected")
-TURF_TRACE_DEFINE("[Mutator] insert constructor called")
-TURF_TRACE_DEFINE("[Mutator] insert was redirected")
+TURF_TRACE_DEFINE("[Mutator] insertOrFind constructor called")
+TURF_TRACE_DEFINE("[Mutator] insertOrFind was redirected")
 TURF_TRACE_DEFINE("[Mutator::exchangeValue] called")
 TURF_TRACE_DEFINE("[Mutator::exchangeValue] exchanged Value")
 TURF_TRACE_DEFINE("[Mutator::exchangeValue] detected race to write value")
index bfbef61..2d0c0e2 100644 (file)
@@ -91,14 +91,14 @@ public:
             }
         }
 
-        // Constructor: Insert cell
+        // Constructor: Insert or find cell
         Mutator(ConcurrentMap_LeapFrog& map, Key key) : m_map(map), m_value(Value(ValueTraits::NullValue)) {
-            TURF_TRACE(ConcurrentMap_LeapFrog, 2, "[Mutator] insert constructor called", uptr(0), uptr(key));
+            TURF_TRACE(ConcurrentMap_LeapFrog, 2, "[Mutator] insertOrFind constructor called", uptr(0), uptr(key));
             Hash hash = KeyTraits::hash(key);
             for (;;) {
                 m_table = m_map.m_root.load(turf::Consume);
                 ureg overflowIdx;
-                switch (Details::insert(hash, m_table, m_cell, overflowIdx)) { // Modifies m_cell
+                switch (Details::insertOrFind(hash, m_table, m_cell, overflowIdx)) { // Modifies m_cell
                 case Details::InsertResult_InsertedNew: {
                     // We've inserted a new cell. Don't load m_cell->value.
                     return;
@@ -108,7 +108,7 @@ public:
                     m_value = m_cell->value.load(turf::Consume);
                     if (m_value == Value(ValueTraits::Redirect)) {
                         // We've encountered a Redirect value.
-                        TURF_TRACE(ConcurrentMap_LeapFrog, 3, "[Mutator] insert was redirected", uptr(m_table), uptr(m_value));
+                        TURF_TRACE(ConcurrentMap_LeapFrog, 3, "[Mutator] insertOrFind was redirected", uptr(m_table), uptr(m_value));
                         break; // Help finish the migration.
                     }
                     return; // Found an existing value
@@ -167,7 +167,7 @@ public:
                     m_table = m_map.m_root.load(turf::Consume);
                     m_value = Value(ValueTraits::NullValue);
                     ureg overflowIdx;
-                    switch (Details::insert(hash, m_table, m_cell, overflowIdx)) { // Modifies m_cell
+                    switch (Details::insertOrFind(hash, m_table, m_cell, overflowIdx)) { // Modifies m_cell
                     case Details::InsertResult_AlreadyFound:
                         m_value = m_cell->value.load(turf::Consume);
                         if (m_value == Value(ValueTraits::Redirect)) {
@@ -240,7 +240,7 @@ public:
         }
     };
 
-    Mutator insert(Key key) {
+    Mutator insertOrFind(Key key) {
         return Mutator(*this, key);
     }
 
@@ -267,7 +267,7 @@ public:
         }
     }
 
-    Value insert(Key key, Value desired) {
+    Value set(Key key, Value desired) {
         Mutator iter(*this, key);
         return iter.exchangeValue(desired);
     }
index 90819e2..1e732c4 100644 (file)
@@ -17,8 +17,8 @@ namespace junction {
 TURF_TRACE_DEFINE_BEGIN(ConcurrentMap_Linear, 17) // autogenerated by TidySource.py
 TURF_TRACE_DEFINE("[Mutator] find constructor called")
 TURF_TRACE_DEFINE("[Mutator] find was redirected")
-TURF_TRACE_DEFINE("[Mutator] insert constructor called")
-TURF_TRACE_DEFINE("[Mutator] insert was redirected")
+TURF_TRACE_DEFINE("[Mutator] insertOrFind constructor called")
+TURF_TRACE_DEFINE("[Mutator] insertOrFind was redirected")
 TURF_TRACE_DEFINE("[Mutator::exchangeValue] called")
 TURF_TRACE_DEFINE("[Mutator::exchangeValue] exchanged Value")
 TURF_TRACE_DEFINE("[Mutator::exchangeValue] detected race to write value")
index 387fb6c..7e268e5 100644 (file)
@@ -93,12 +93,12 @@ public:
 
         // Constructor: Insert cell
         Mutator(ConcurrentMap_Linear& map, Key key) : m_map(map), m_value(Value(ValueTraits::NullValue)) {
-            TURF_TRACE(ConcurrentMap_Linear, 2, "[Mutator] insert constructor called", uptr(0), uptr(key));
+            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;
@@ -108,7 +108,7 @@ public:
                     m_value = m_cell->value.load(turf::Consume);
                     if (m_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
@@ -168,7 +168,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)) {
@@ -243,7 +243,7 @@ public:
         }
     };
 
-    Mutator insert(Key key) {
+    Mutator insertOrFind(Key key) {
         return Mutator(*this, key);
     }
 
@@ -270,7 +270,7 @@ public:
         }
     }
 
-    Value insert(Key key, Value desired) {
+    Value set(Key key, Value desired) {
         Mutator iter(*this, key);
         return iter.exchangeValue(desired);
     }
index d347b5a..f68ec10 100644 (file)
@@ -189,7 +189,7 @@ public:
         return iter.isValid() ? iter.getValue() : NULL;
     }
 
-    Value insert(const Key& key, Value desired) {
+    Value set(const Key& key, Value desired) {
         Iterator iter(*this, key);
         return iter.exchangeValue(desired);
     }
index 3b33fa5..76ab6f0 100644 (file)
@@ -25,18 +25,18 @@ TURF_TRACE_DEFINE_BEGIN(Grampa, 37) // autogenerated by TidySource.py
 TURF_TRACE_DEFINE("[find] called")
 TURF_TRACE_DEFINE("[find] found existing cell optimistically")
 TURF_TRACE_DEFINE("[find] found existing cell")
-TURF_TRACE_DEFINE("[insert] called")
-TURF_TRACE_DEFINE("[insert] reserved first cell")
-TURF_TRACE_DEFINE("[insert] race to reserve first cell")
-TURF_TRACE_DEFINE("[insert] found in first cell")
-TURF_TRACE_DEFINE("[insert] race to read hash")
-TURF_TRACE_DEFINE("[insert] found in probe chain")
-TURF_TRACE_DEFINE("[insert] reserved cell")
-TURF_TRACE_DEFINE("[insert] race to reserve cell")
-TURF_TRACE_DEFINE("[insert] found outside probe chain")
-TURF_TRACE_DEFINE("[insert] found late-arriving cell in same bucket")
-TURF_TRACE_DEFINE("[insert] set link on behalf of late-arriving cell")
-TURF_TRACE_DEFINE("[insert] overflow")
+TURF_TRACE_DEFINE("[insertOrFind] called")
+TURF_TRACE_DEFINE("[insertOrFind] reserved first cell")
+TURF_TRACE_DEFINE("[insertOrFind] race to reserve first cell")
+TURF_TRACE_DEFINE("[insertOrFind] found in first cell")
+TURF_TRACE_DEFINE("[insertOrFind] race to read hash")
+TURF_TRACE_DEFINE("[insertOrFind] found in probe chain")
+TURF_TRACE_DEFINE("[insertOrFind] reserved cell")
+TURF_TRACE_DEFINE("[insertOrFind] race to reserve cell")
+TURF_TRACE_DEFINE("[insertOrFind] found outside probe chain")
+TURF_TRACE_DEFINE("[insertOrFind] found late-arriving cell in same bucket")
+TURF_TRACE_DEFINE("[insertOrFind] set link on behalf of late-arriving cell")
+TURF_TRACE_DEFINE("[insertOrFind] overflow")
 TURF_TRACE_DEFINE("[beginTableMigrationToSize] called")
 TURF_TRACE_DEFINE("[beginTableMigrationToSize] new migration already exists")
 TURF_TRACE_DEFINE("[beginTableMigrationToSize] new migration already exists (double-checked)")
index 2fe2cc2..2c74491 100644 (file)
@@ -358,8 +358,8 @@ struct Grampa {
 
     // FIXME: Possible optimization: Dedicated insert for migration? It wouldn't check for InsertResult_AlreadyFound.
     enum InsertResult { InsertResult_AlreadyFound, InsertResult_InsertedNew, InsertResult_Overflow };
-    static InsertResult insert(Hash hash, Table* table, ureg sizeMask, Cell*& cell, ureg& overflowIdx) {
-        TURF_TRACE(Grampa, 3, "[insert] called", uptr(table), hash);
+    static InsertResult insertOrFind(Hash hash, Table* table, ureg sizeMask, Cell*& cell, ureg& overflowIdx) {
+        TURF_TRACE(Grampa, 3, "[insertOrFind] called", uptr(table), hash);
         TURF_ASSERT(table);
         TURF_ASSERT(hash != KeyTraits::NullHash);
         ureg idx = ureg(hash);
@@ -370,16 +370,16 @@ struct Grampa {
         Hash probeHash = cell->hash.load(turf::Relaxed);
         if (probeHash == KeyTraits::NullHash) {
             if (cell->hash.compareExchangeStrong(probeHash, hash, turf::Relaxed)) {
-                TURF_TRACE(Grampa, 4, "[insert] reserved first cell", uptr(table), idx);
+                TURF_TRACE(Grampa, 4, "[insertOrFind] reserved first cell", uptr(table), idx);
                 // There are no links to set. We're done.
                 return InsertResult_InsertedNew;
             } else {
-                TURF_TRACE(Grampa, 5, "[insert] race to reserve first cell", uptr(table), idx);
+                TURF_TRACE(Grampa, 5, "[insertOrFind] race to reserve first cell", uptr(table), idx);
                 // Fall through to check if it was the same hash...
             }
         }
         if (probeHash == hash) {
-            TURF_TRACE(Grampa, 6, "[insert] found in first cell", uptr(table), idx);
+            TURF_TRACE(Grampa, 6, "[insertOrFind] found in first cell", uptr(table), idx);
             return InsertResult_AlreadyFound;
         }
 
@@ -402,14 +402,14 @@ struct Grampa {
                     // Cell was linked, but hash is not visible yet.
                     // We could avoid this case (and guarantee it's visible) using acquire & release, but instead,
                     // just poll until it becomes visible.
-                    TURF_TRACE(Grampa, 7, "[insert] race to read hash", uptr(table), idx);
+                    TURF_TRACE(Grampa, 7, "[insertOrFind] race to read hash", uptr(table), idx);
                     do {
                         probeHash = cell->hash.load(turf::Acquire);
                     } while (probeHash == KeyTraits::NullHash);
                 }
                 TURF_ASSERT(((probeHash ^ hash) & sizeMask) == 0); // Only hashes in same bucket can be linked
                 if (probeHash == hash) {
-                    TURF_TRACE(Grampa, 8, "[insert] found in probe chain", uptr(table), idx);
+                    TURF_TRACE(Grampa, 8, "[insertOrFind] found in probe chain", uptr(table), idx);
                     return InsertResult_AlreadyFound;
                 }
             } else {
@@ -427,7 +427,7 @@ struct Grampa {
                         // It's an empty cell. Try to reserve it.
                         if (cell->hash.compareExchangeStrong(probeHash, hash, turf::Relaxed)) {
                             // Success. We've reserved the cell. Link it to previous cell in same bucket.
-                            TURF_TRACE(Grampa, 9, "[insert] reserved cell", uptr(table), idx);
+                            TURF_TRACE(Grampa, 9, "[insertOrFind] reserved cell", uptr(table), idx);
                             TURF_ASSERT(probeDelta == 0);
                             u8 desiredDelta = idx - prevLinkIdx;
 #if TURF_WITH_ASSERTS
@@ -439,19 +439,19 @@ struct Grampa {
 #endif
                             return InsertResult_InsertedNew;
                         } else {
-                            TURF_TRACE(Grampa, 10, "[insert] race to reserve cell", uptr(table), idx);
+                            TURF_TRACE(Grampa, 10, "[insertOrFind] race to reserve cell", uptr(table), idx);
                             // Fall through to check if it's the same hash...
                         }
                     }
                     Hash x = (probeHash ^ hash);
                     // Check for same hash.
                     if (!x) {
-                        TURF_TRACE(Grampa, 11, "[insert] found outside probe chain", uptr(table), idx);
+                        TURF_TRACE(Grampa, 11, "[insertOrFind] found outside probe chain", uptr(table), idx);
                         return InsertResult_AlreadyFound;
                     }
                     // Check for same bucket.
                     if ((x & sizeMask) == 0) {
-                        TURF_TRACE(Grampa, 12, "[insert] found late-arriving cell in same bucket", uptr(table), idx);
+                        TURF_TRACE(Grampa, 12, "[insertOrFind] found late-arriving cell in same bucket", uptr(table), idx);
                         // Attempt to set the link on behalf of the late-arriving cell.
                         // This is usually redundant, but if we don't attempt to set the late-arriving cell's link here,
                         // there's no guarantee that our own link chain will be well-formed by the time this function returns.
@@ -461,7 +461,7 @@ struct Grampa {
                         probeDelta = prevLink->exchange(desiredDelta, turf::Relaxed);
                         TURF_ASSERT(probeDelta == 0 || probeDelta == desiredDelta);
                         if (probeDelta == 0)
-                            TURF_TRACE(Grampa, 13, "[insert] set link on behalf of late-arriving cell", uptr(table), idx);
+                            TURF_TRACE(Grampa, 13, "[insertOrFind] set link on behalf of late-arriving cell", uptr(table), idx);
 #else
                         prevLink->store(desiredDelta, turf::Relaxed);
 #endif
@@ -471,7 +471,7 @@ struct Grampa {
                 }
                 // Table is too full to insert.
                 overflowIdx = idx + 1;
-                TURF_TRACE(Grampa, 14, "[insert] overflow", uptr(table), overflowIdx);
+                TURF_TRACE(Grampa, 14, "[insertOrFind] overflow", uptr(table), overflowIdx);
                 return InsertResult_Overflow;
             }
         }
@@ -616,7 +616,7 @@ sreg Grampa<Map>::TableMigration::migrateRange(Table* srcTable, ureg startIdx) {
                 Table* dstLeaf = dstLeafs[destLeafIndex];
                 Cell* dstCell;
                 ureg overflowIdx;
-                InsertResult result = insert(srcHash, dstLeaf, dstLeaf->sizeMask, dstCell, overflowIdx);
+                InsertResult result = insertOrFind(srcHash, dstLeaf, dstLeaf->sizeMask, dstCell, overflowIdx);
                 // During migration, a hash can only exist in one place among all the source tables,
                 // and it is only migrated by one thread. Therefore, the hash will never already exist
                 // in the destination table:
index 3a7011e..7cb9452 100644 (file)
@@ -21,18 +21,18 @@ TURF_TRACE_DEFINE_BEGIN(LeapFrog, 33) // autogenerated by TidySource.py
 TURF_TRACE_DEFINE("[find] called")
 TURF_TRACE_DEFINE("[find] found existing cell optimistically")
 TURF_TRACE_DEFINE("[find] found existing cell")
-TURF_TRACE_DEFINE("[insert] called")
-TURF_TRACE_DEFINE("[insert] reserved first cell")
-TURF_TRACE_DEFINE("[insert] race to reserve first cell")
-TURF_TRACE_DEFINE("[insert] found in first cell")
-TURF_TRACE_DEFINE("[insert] race to read hash")
-TURF_TRACE_DEFINE("[insert] found in probe chain")
-TURF_TRACE_DEFINE("[insert] reserved cell")
-TURF_TRACE_DEFINE("[insert] race to reserve cell")
-TURF_TRACE_DEFINE("[insert] found outside probe chain")
-TURF_TRACE_DEFINE("[insert] found late-arriving cell in same bucket")
-TURF_TRACE_DEFINE("[insert] set link on behalf of late-arriving cell")
-TURF_TRACE_DEFINE("[insert] overflow")
+TURF_TRACE_DEFINE("[insertOrFind] called")
+TURF_TRACE_DEFINE("[insertOrFind] reserved first cell")
+TURF_TRACE_DEFINE("[insertOrFind] race to reserve first cell")
+TURF_TRACE_DEFINE("[insertOrFind] found in first cell")
+TURF_TRACE_DEFINE("[insertOrFind] race to read hash")
+TURF_TRACE_DEFINE("[insertOrFind] found in probe chain")
+TURF_TRACE_DEFINE("[insertOrFind] reserved cell")
+TURF_TRACE_DEFINE("[insertOrFind] race to reserve cell")
+TURF_TRACE_DEFINE("[insertOrFind] found outside probe chain")
+TURF_TRACE_DEFINE("[insertOrFind] found late-arriving cell in same bucket")
+TURF_TRACE_DEFINE("[insertOrFind] set link on behalf of late-arriving cell")
+TURF_TRACE_DEFINE("[insertOrFind] overflow")
 TURF_TRACE_DEFINE("[beginTableMigrationToSize] called")
 TURF_TRACE_DEFINE("[beginTableMigrationToSize] new migration already exists")
 TURF_TRACE_DEFINE("[beginTableMigrationToSize] new migration already exists (double-checked)")
index 75d91fb..bc184f9 100644 (file)
@@ -189,8 +189,8 @@ struct LeapFrog {
 
     // FIXME: Possible optimization: Dedicated insert for migration? It wouldn't check for InsertResult_AlreadyFound.
     enum InsertResult { InsertResult_AlreadyFound, InsertResult_InsertedNew, InsertResult_Overflow };
-    static InsertResult insert(Hash hash, Table* table, Cell*& cell, ureg& overflowIdx) {
-        TURF_TRACE(LeapFrog, 3, "[insert] called", uptr(table), hash);
+    static InsertResult insertOrFind(Hash hash, Table* table, Cell*& cell, ureg& overflowIdx) {
+        TURF_TRACE(LeapFrog, 3, "[insertOrFind] called", uptr(table), hash);
         TURF_ASSERT(table);
         TURF_ASSERT(hash != KeyTraits::NullHash);
         ureg sizeMask = table->sizeMask;
@@ -202,16 +202,16 @@ struct LeapFrog {
         Hash probeHash = cell->hash.load(turf::Relaxed);
         if (probeHash == KeyTraits::NullHash) {
             if (cell->hash.compareExchangeStrong(probeHash, hash, turf::Relaxed)) {
-                TURF_TRACE(LeapFrog, 4, "[insert] reserved first cell", uptr(table), idx);
+                TURF_TRACE(LeapFrog, 4, "[insertOrFind] reserved first cell", uptr(table), idx);
                 // There are no links to set. We're done.
                 return InsertResult_InsertedNew;
             } else {
-                TURF_TRACE(LeapFrog, 5, "[insert] race to reserve first cell", uptr(table), idx);
+                TURF_TRACE(LeapFrog, 5, "[insertOrFind] race to reserve first cell", uptr(table), idx);
                 // Fall through to check if it was the same hash...
             }
         }
         if (probeHash == hash) {
-            TURF_TRACE(LeapFrog, 6, "[insert] found in first cell", uptr(table), idx);
+            TURF_TRACE(LeapFrog, 6, "[insertOrFind] found in first cell", uptr(table), idx);
             return InsertResult_AlreadyFound;
         }
 
@@ -234,14 +234,14 @@ struct LeapFrog {
                     // Cell was linked, but hash is not visible yet.
                     // We could avoid this case (and guarantee it's visible) using acquire & release, but instead,
                     // just poll until it becomes visible.
-                    TURF_TRACE(LeapFrog, 7, "[insert] race to read hash", uptr(table), idx);
+                    TURF_TRACE(LeapFrog, 7, "[insertOrFind] race to read hash", uptr(table), idx);
                     do {
                         probeHash = cell->hash.load(turf::Acquire);
                     } while (probeHash == KeyTraits::NullHash);
                 }
                 TURF_ASSERT(((probeHash ^ hash) & sizeMask) == 0); // Only hashes in same bucket can be linked
                 if (probeHash == hash) {
-                    TURF_TRACE(LeapFrog, 8, "[insert] found in probe chain", uptr(table), idx);
+                    TURF_TRACE(LeapFrog, 8, "[insertOrFind] found in probe chain", uptr(table), idx);
                     return InsertResult_AlreadyFound;
                 }
             } else {
@@ -259,7 +259,7 @@ struct LeapFrog {
                         // It's an empty cell. Try to reserve it.
                         if (cell->hash.compareExchangeStrong(probeHash, hash, turf::Relaxed)) {
                             // Success. We've reserved the cell. Link it to previous cell in same bucket.
-                            TURF_TRACE(LeapFrog, 9, "[insert] reserved cell", uptr(table), idx);
+                            TURF_TRACE(LeapFrog, 9, "[insertOrFind] reserved cell", uptr(table), idx);
                             TURF_ASSERT(probeDelta == 0);
                             u8 desiredDelta = idx - prevLinkIdx;
 #if TURF_WITH_ASSERTS
@@ -270,19 +270,19 @@ struct LeapFrog {
 #endif
                             return InsertResult_InsertedNew;
                         } else {
-                            TURF_TRACE(LeapFrog, 10, "[insert] race to reserve cell", uptr(table), idx);
+                            TURF_TRACE(LeapFrog, 10, "[insertOrFind] race to reserve cell", uptr(table), idx);
                             // Fall through to check if it's the same hash...
                         }
                     }
                     Hash x = (probeHash ^ hash);
                     // Check for same hash.
                     if (!x) {
-                        TURF_TRACE(LeapFrog, 11, "[insert] found outside probe chain", uptr(table), idx);
+                        TURF_TRACE(LeapFrog, 11, "[insertOrFind] found outside probe chain", uptr(table), idx);
                         return InsertResult_AlreadyFound;
                     }
                     // Check for same bucket.
                     if ((x & sizeMask) == 0) {
-                        TURF_TRACE(LeapFrog, 12, "[insert] found late-arriving cell in same bucket", uptr(table), idx);
+                        TURF_TRACE(LeapFrog, 12, "[insertOrFind] found late-arriving cell in same bucket", uptr(table), idx);
                         // Attempt to set the link on behalf of the late-arriving cell.
                         // This is usually redundant, but if we don't attempt to set the late-arriving cell's link here,
                         // there's no guarantee that our own link chain will be well-formed by the time this function returns.
@@ -292,7 +292,7 @@ struct LeapFrog {
                         probeDelta = prevLink->exchange(desiredDelta, turf::Relaxed);
                         TURF_ASSERT(probeDelta == 0 || probeDelta == desiredDelta);
                         if (probeDelta == 0)
-                            TURF_TRACE(LeapFrog, 13, "[insert] set link on behalf of late-arriving cell", uptr(table), idx);
+                            TURF_TRACE(LeapFrog, 13, "[insertOrFind] set link on behalf of late-arriving cell", uptr(table), idx);
 #else
                         prevLink->store(desiredDelta, turf::Relaxed);
 #endif
@@ -302,7 +302,7 @@ struct LeapFrog {
                 }
                 // Table is too full to insert.
                 overflowIdx = idx + 1;
-                TURF_TRACE(LeapFrog, 14, "[insert] overflow", uptr(table), overflowIdx);
+                TURF_TRACE(LeapFrog, 14, "[insertOrFind] overflow", uptr(table), overflowIdx);
                 return InsertResult_Overflow;
             }
         }
@@ -417,7 +417,7 @@ bool LeapFrog<Map>::TableMigration::migrateRange(Table* srcTable, ureg startIdx)
                 TURF_ASSERT(srcValue != Value(ValueTraits::Redirect));
                 Cell* dstCell;
                 ureg overflowIdx;
-                InsertResult result = insert(srcHash, m_destination, dstCell, overflowIdx);
+                InsertResult result = insertOrFind(srcHash, m_destination, dstCell, overflowIdx);
                 // During migration, a hash can only exist in one place among all the source tables,
                 // and it is only migrated by one thread. Therefore, the hash will never already exist
                 // in the destination table:
index 739fc44..014316c 100644 (file)
@@ -20,12 +20,12 @@ namespace details {
 TURF_TRACE_DEFINE_BEGIN(Linear, 27) // autogenerated by TidySource.py
 TURF_TRACE_DEFINE("[find] called")
 TURF_TRACE_DEFINE("[find] found existing cell")
-TURF_TRACE_DEFINE("[insert] called")
-TURF_TRACE_DEFINE("[insert] found existing cell")
-TURF_TRACE_DEFINE("[insert] ran out of cellsRemaining")
-TURF_TRACE_DEFINE("[insert] reserved cell")
-TURF_TRACE_DEFINE("[insert] detected race to reserve cell")
-TURF_TRACE_DEFINE("[insert] race reserved same hash")
+TURF_TRACE_DEFINE("[insertOrFind] called")
+TURF_TRACE_DEFINE("[insertOrFind] found existing cell")
+TURF_TRACE_DEFINE("[insertOrFind] ran out of cellsRemaining")
+TURF_TRACE_DEFINE("[insertOrFind] reserved cell")
+TURF_TRACE_DEFINE("[insertOrFind] detected race to reserve cell")
+TURF_TRACE_DEFINE("[insertOrFind] race reserved same hash")
 TURF_TRACE_DEFINE("[beginTableMigrationToSize] called")
 TURF_TRACE_DEFINE("[beginTableMigrationToSize] new migration already exists")
 TURF_TRACE_DEFINE("[beginTableMigrationToSize] new migration already exists (double-checked)")
index 3e11a0e..6555fe3 100644 (file)
@@ -153,8 +153,8 @@ struct Linear {
 
     // FIXME: Possible optimization: Dedicated insert for migration? It wouldn't check for InsertResult_AlreadyFound.
     enum InsertResult { InsertResult_AlreadyFound, InsertResult_InsertedNew, InsertResult_Overflow };
-    static InsertResult insert(Hash hash, Table* table, Cell*& cell) {
-        TURF_TRACE(Linear, 2, "[insert] called", uptr(table), hash);
+    static InsertResult insertOrFind(Hash hash, Table* table, Cell*& cell) {
+        TURF_TRACE(Linear, 2, "[insertOrFind] called", uptr(table), hash);
         TURF_ASSERT(table);
         TURF_ASSERT(hash != KeyTraits::NullHash);
         ureg sizeMask = table->sizeMask;
@@ -165,7 +165,7 @@ struct Linear {
             // Load the existing hash.
             Hash probeHash = cell->hash.load(turf::Relaxed);
             if (probeHash == hash) {
-                TURF_TRACE(Linear, 3, "[insert] found existing cell", uptr(table), idx);
+                TURF_TRACE(Linear, 3, "[insertOrFind] found existing cell", uptr(table), idx);
                 return InsertResult_AlreadyFound; // Key found in table. Return the existing cell.
             }
             if (probeHash == KeyTraits::NullHash) {
@@ -174,7 +174,7 @@ struct Linear {
                 s32 prevCellsRemaining = table->cellsRemaining.fetchSub(1, turf::Relaxed);
                 if (prevCellsRemaining <= 0) {
                     // Table is overpopulated.
-                    TURF_TRACE(Linear, 4, "[insert] ran out of cellsRemaining", prevCellsRemaining, 0);
+                    TURF_TRACE(Linear, 4, "[insertOrFind] ran out of cellsRemaining", prevCellsRemaining, 0);
                     table->cellsRemaining.fetchAdd(1, turf::Relaxed); // Undo cellsRemaining decrement
                     return InsertResult_Overflow;
                 }
@@ -182,14 +182,14 @@ struct Linear {
                 Hash prevHash = cell->hash.compareExchange(KeyTraits::NullHash, hash, turf::Relaxed);
                 if (prevHash == KeyTraits::NullHash) {
                     // Success. We reserved a new cell.
-                    TURF_TRACE(Linear, 5, "[insert] reserved cell", prevCellsRemaining, idx);
+                    TURF_TRACE(Linear, 5, "[insertOrFind] reserved cell", prevCellsRemaining, idx);
                     return InsertResult_InsertedNew;
                 }
                 // There was a race and another thread reserved that cell from under us.
-                TURF_TRACE(Linear, 6, "[insert] detected race to reserve cell", ureg(hash), idx);
+                TURF_TRACE(Linear, 6, "[insertOrFind] detected race to reserve cell", ureg(hash), idx);
                 table->cellsRemaining.fetchAdd(1, turf::Relaxed); // Undo cellsRemaining decrement
                 if (prevHash == hash) {
-                    TURF_TRACE(Linear, 7, "[insert] race reserved same hash", ureg(hash), idx);
+                    TURF_TRACE(Linear, 7, "[insertOrFind] race reserved same hash", ureg(hash), idx);
                     return InsertResult_AlreadyFound; // They inserted the same key. Return the existing cell.
                 }
             }
@@ -308,7 +308,7 @@ bool Linear<Map>::TableMigration::migrateRange(Table* srcTable, ureg startIdx) {
                 TURF_ASSERT(srcValue != Value(ValueTraits::NullValue));
                 TURF_ASSERT(srcValue != Value(ValueTraits::Redirect));
                 Cell* dstCell;
-                InsertResult result = insert(srcHash, m_destination, dstCell);
+                InsertResult result = insertOrFind(srcHash, m_destination, dstCell);
                 // During migration, a hash can only exist in one place among all the source tables,
                 // and it is only migrated by one thread. Therefore, the hash will never already exist
                 // in the destination table:
index fd477f4..71fef30 100644 (file)
@@ -86,7 +86,7 @@ public:
         Map(ureg capacity) : m_map() {
         }
 
-        void insert(u32 key, void* value) {
+        void set(u32 key, void* value) {
             m_map.insert(key, value);
         }
 
index 44c34a2..bd6f1cd 100644 (file)
@@ -86,7 +86,7 @@ public:
         Map(ureg capacity) : m_map(capacity, 1) {
         }
 
-        void insert(u32 key, void* value) {
+        void set(u32 key, void* value) {
             m_map.insert(key, value);
         }
 
index 02d54a6..2cc8376 100644 (file)
@@ -54,7 +54,7 @@ public:
         Map(ureg capacity) : m_map(capacity) {
         }
 
-        void insert(u32 key, void* value) {
+        void set(u32 key, void* value) {
             m_map.insert(std::make_pair(key, value));
         }
 
index 76119ba..9e83817 100644 (file)
@@ -54,7 +54,7 @@ public:
         Map(ureg capacity) : m_map(capacity) {
         }
 
-        void insert(u32 key, void* value) {
+        void set(u32 key, void* value) {
             m_map.insert(key, value);
         }
 
index fbb21df..d383663 100644 (file)
@@ -52,9 +52,9 @@ public:
         Map(ureg capacity) : m_map(capacity) {
         }
 
-        void insert(u32 key, void* value) {
+        void set(u32 key, void* value) {
             turf::LockGuard<turf::Mutex> guard(m_mutex);
-            m_map.insert(key, value);
+            m_map.set(key, value);
         }
 
         void* get(u32 key) {
index e9414e3..8c08559 100644 (file)
@@ -52,9 +52,9 @@ public:
         Map(ureg capacity) : m_map(capacity) {
         }
 
-        void insert(u32 key, void* value) {
+        void set(u32 key, void* value) {
             turf::ExclusiveLockGuard<turf::RWLock> guard(m_rwLock);
-            m_map.insert(key, value);
+            m_map.set(key, value);
         }
 
         void* get(u32 key) {
index 43ed97b..bd2bc86 100644 (file)
@@ -69,7 +69,7 @@ public:
             ht_free(m_map);
         }
 
-        void insert(u32 key, void* value) {
+        void set(u32 key, void* value) {
             ht_cas(m_map, key, CAS_EXPECT_WHATEVER, (map_val_t) value);
         }
 
index 24254fc..af17120 100644 (file)
@@ -45,7 +45,7 @@ public:
         Map(ureg) {
         }
 
-        void insert(u32, void*) {
+        void set(u32, void*) {
         }
 
         void* get(u32) {
index fba38ae..8425936 100644 (file)
@@ -52,9 +52,9 @@ public:
         Map(ureg) {
         }
 
-        void insert(u32 key, void* value) {
+        void set(u32 key, void* value) {
             std::lock_guard<std::mutex> guard(m_mutex);
-            m_map.insert(std::make_pair(key, value));
+            m_map[key] = value;
         }
 
         void* get(u32 key) {
index a87a465..aa442ae 100644 (file)
@@ -54,7 +54,7 @@ public:
         Map(ureg capacity) : m_map(capacity) {
         }
 
-        void insert(u32 key, void* value) {
+        void set(u32 key, void* value) {
             m_map.insert(std::make_pair(key, value));
         }
 
index d00320d..d294278 100644 (file)
@@ -62,7 +62,7 @@ public:
         Map(ureg capacity) : m_map(capacity, 3) {
         }
 
-        void insert(u32 key, void* value) {
+        void set(u32 key, void* value) {
             m_map.insert(key, (u64) value);
         }
 
index 37efc77..a6695d2 100644 (file)
@@ -28,7 +28,7 @@ int main() {
         std::cout << "Population=" << population << ", inUse=" << TURF_HEAP.getInUseBytes() << std::endl;
 #endif
         for (; population < i * 5000; population++)
-            map.insert(population + 1, (void*) ((population << 2) | 3));
+            map.set(population + 1, (void*) ((population << 2) | 3));
     }
 
     return 0;
index 5ca48b8..ca2b321 100644 (file)
@@ -79,7 +79,7 @@ public:
             u32 key = thread.insertIndex * m_relativePrime;
             key = key ^ (key >> 16);
             if (key >= 2) {
-                m_map.insert(key, (void*) uptr(key));
+                m_map.set(key, (void*) uptr(key));
             }
             if (++thread.insertIndex >= thread.rangeHi)
                 thread.insertIndex = thread.rangeLo;
@@ -96,7 +96,7 @@ public:
                     u32 key = thread.insertIndex * m_relativePrime;
                     key = key ^ (key >> 16);
                     if (key >= 2) {
-                        m_map.insert(key, (void*) uptr(key));
+                        m_map.set(key, (void*) uptr(key));
                     }
                     if (++thread.insertIndex >= thread.rangeHi)
                         thread.insertIndex = thread.rangeLo;
index e545992..7e7bdaa 100644 (file)
@@ -36,7 +36,7 @@ public:
             u32 key = index * m_relativePrime;
             key = key ^ (key >> 16);
             if (key >= 2) { // Don't insert 0 or 1
-                m_map->insert(key, (void*) uptr(key));
+                m_map->set(key, (void*) uptr(key));
                 keysRemaining--;
             }
             index++;
index 9e87a23..8510d8c 100644 (file)
@@ -36,7 +36,7 @@ public:
             u32 key = index * m_relativePrime;
             key = key ^ (key >> 16);
             if (key >= 2) { // Don't insert 0 or 1
-                m_map->insert(key, (void*) uptr(key));
+                m_map->set(key, (void*) uptr(key));
                 keysRemaining--;
             }
             index++;
index 4523ae9..1532de5 100644 (file)
@@ -49,10 +49,10 @@ public:
         if (threadIndex == 0) {
             // We store 2 because Junction maps reserve 1 for the default Redirect value.
             // The default can be overridden, but this is easier.
-            m_map.insert(x, (void*) 2);
+            m_map.set(x, (void*) 2);
             m_r1 = (uptr) m_map.get(y);
         } else {
-            m_map.insert(y, (void*) 2);
+            m_map.set(y, (void*) 2);
             m_r2 = (uptr) m_map.get(x);
         }
     }
@@ -89,11 +89,11 @@ public:
         case 0:
             // We store 2 because Junction maps reserve 1 for the default Redirect value.
             // The default can be overridden, but this is easier.
-            m_map.insert(x, (void*) 2);
+            m_map.set(x, (void*) 2);
             break;
             
         case 1:
-            m_map.insert(y, (void*) 2);
+            m_map.set(y, (void*) 2);
             break;
             
         case 2:
index 806706b..d0a5e3d 100644 (file)
@@ -126,7 +126,7 @@ public:
         MapAdapter::Map* map = m_shared.map;
         for (ureg i = 0; i < m_shared.numKeysPerThread; i++) {
             u32 key = m_addIndex * Prime;
-            map->insert(key, (void*) (key & ~uptr(3)));
+            map->set(key, (void*) (key & ~uptr(3)));
             if (++m_addIndex == m_rangeHi)
                 m_addIndex = m_rangeLo;
         }
@@ -155,7 +155,7 @@ public:
                 break;
             u32 key = m_addIndex * Prime;
             if (key >= 2) {
-                map->insert(key, (void*) uptr(key));
+                map->set(key, (void*) uptr(key));
                 stats.mapOpsDone++;
             }
             if (++m_addIndex == m_rangeHi)
index db6d953..0841bdd 100644 (file)
@@ -103,7 +103,7 @@ public:
         for (ureg i = 0; i < m_shared.numKeysPerThread; i++) {
             u32 key = m_addIndex * Prime;
             if (key >= 2)
-                map->insert(key, (void*) uptr(key));
+                map->set(key, (void*) uptr(key));
             if (++m_addIndex == m_rangeHi)
                 m_addIndex = m_rangeLo;
         }
@@ -130,7 +130,7 @@ public:
                 break;
             u32 key = m_addIndex * Prime;
             if (key >= 2) {
-                map->insert(key, (void*) uptr(key));
+                map->set(key, (void*) uptr(key));
                 stats.mapOpsDone++;
             }
             if (++m_addIndex == m_rangeHi)