std::map::insert() will only store the value if the key doesn't already exist.
junction::ConcurrentMap_xxx::set() stores the value unconditionally.
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
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));
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")
}
}
- // 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 (;;) {
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;
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
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)) {
}
};
- Mutator insert(Key key) {
+ Mutator insertOrFind(Key key) {
return Mutator(*this, key);
}
}
}
- Value insert(Key key, Value desired) {
+ Value set(Key key, Value desired) {
Mutator iter(*this, key);
return iter.exchangeValue(desired);
}
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")
}
}
- // 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;
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
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)) {
}
};
- Mutator insert(Key key) {
+ Mutator insertOrFind(Key key) {
return Mutator(*this, key);
}
}
}
- Value insert(Key key, Value desired) {
+ Value set(Key key, Value desired) {
Mutator iter(*this, key);
return iter.exchangeValue(desired);
}
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")
// 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;
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
// 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)) {
}
};
- Mutator insert(Key key) {
+ Mutator insertOrFind(Key key) {
return Mutator(*this, key);
}
}
}
- Value insert(Key key, Value desired) {
+ Value set(Key key, Value desired) {
Mutator iter(*this, key);
return iter.exchangeValue(desired);
}
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);
}
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)")
// 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);
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;
}
// 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 {
// 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
#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.
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
}
// 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;
}
}
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:
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)")
// 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;
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;
}
// 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 {
// 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
#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.
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
}
// 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;
}
}
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:
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)")
// 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;
// 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) {
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;
}
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.
}
}
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:
Map(ureg capacity) : m_map() {
}
- void insert(u32 key, void* value) {
+ void set(u32 key, void* value) {
m_map.insert(key, value);
}
Map(ureg capacity) : m_map(capacity, 1) {
}
- void insert(u32 key, void* value) {
+ void set(u32 key, void* value) {
m_map.insert(key, value);
}
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));
}
Map(ureg capacity) : m_map(capacity) {
}
- void insert(u32 key, void* value) {
+ void set(u32 key, void* value) {
m_map.insert(key, value);
}
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) {
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) {
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);
}
Map(ureg) {
}
- void insert(u32, void*) {
+ void set(u32, void*) {
}
void* get(u32) {
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) {
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));
}
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);
}
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;
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;
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;
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++;
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++;
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);
}
}
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:
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;
}
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)
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;
}
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)
projects / junction.git / commitdiff