// AtomicHashArray private constructor --
template <class KeyT, class ValueT,
- class HashFcn, class EqualFcn, class Allocator>
-AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+ class HashFcn, class EqualFcn, class Allocator, class ProbeFcn>
+AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
AtomicHashArray(size_t capacity, KeyT emptyKey, KeyT lockedKey,
KeyT erasedKey, double _maxLoadFactor, size_t cacheSize)
: capacity_(capacity),
* ret.index is set to capacity_.
*/
template <class KeyT, class ValueT,
- class HashFcn, class EqualFcn, class Allocator>
+ class HashFcn, class EqualFcn, class Allocator, class ProbeFcn>
typename AtomicHashArray<KeyT, ValueT,
- HashFcn, EqualFcn, Allocator>::SimpleRetT
-AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+ HashFcn, EqualFcn, Allocator, ProbeFcn>::SimpleRetT
+AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
findInternal(const KeyT key_in) {
DCHECK_NE(key_in, kEmptyKey_);
DCHECK_NE(key_in, kLockedKey_);
DCHECK_NE(key_in, kErasedKey_);
for (size_t idx = keyToAnchorIdx(key_in), numProbes = 0;
;
- idx = probeNext(idx, numProbes)) {
+ idx = ProbeFcn()(idx, numProbes, capacity_)) {
const KeyT key = acquireLoadKey(cells_[idx]);
if (LIKELY(EqualFcn()(key, key_in))) {
return SimpleRetT(idx, true);
// if we hit an empty element, this key does not exist
return SimpleRetT(capacity_, false);
}
+ // NOTE: the way we count numProbes must be same in find(), insert(),
+ // and erase(). Otherwise it may break probing.
++numProbes;
if (UNLIKELY(numProbes >= capacity_)) {
// probed every cell...fail
* default.
*/
template <class KeyT, class ValueT,
- class HashFcn, class EqualFcn, class Allocator>
-template <class T>
+ class HashFcn, class EqualFcn, class Allocator, class ProbeFcn>
+template <typename... ArgTs>
typename AtomicHashArray<KeyT, ValueT,
- HashFcn, EqualFcn, Allocator>::SimpleRetT
-AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
-insertInternal(KeyT key_in, T&& value) {
+ HashFcn, EqualFcn, Allocator, ProbeFcn>::SimpleRetT
+AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
+insertInternal(KeyT key_in, ArgTs&&... vCtorArgs) {
const short NO_NEW_INSERTS = 1;
const short NO_PENDING_INSERTS = 2;
CHECK_NE(key_in, kEmptyKey_);
// another thread now does ++numPendingEntries_, we expect it
// to pass the isFull_.load() test above. (It shouldn't insert
// a new entry.)
- FOLLY_SPIN_WAIT(
- isFull_.load(std::memory_order_acquire) != NO_PENDING_INSERTS
- && numPendingEntries_.readFull() != 0
- );
+ detail::atomic_hash_spin_wait([&] {
+ return
+ (isFull_.load(std::memory_order_acquire) != NO_PENDING_INSERTS) &&
+ (numPendingEntries_.readFull() != 0);
+ });
isFull_.store(NO_PENDING_INSERTS, std::memory_order_release);
if (relaxedLoadKey(*cell) == kEmptyKey_) {
// Write the value - done before unlocking
try {
DCHECK(relaxedLoadKey(*cell) == kLockedKey_);
- /*
- * This happens using the copy constructor because we won't have
- * constructed a lhs to use an assignment operator on when
- * values are being set.
- */
- new (&cell->second) ValueT(std::forward<T>(value));
+ new (&cell->second) ValueT(std::forward<ArgTs>(vCtorArgs)...);
unlockCell(cell, key_in); // Sets the new key
} catch (...) {
// Transition back to empty key---requires handling
--numPendingEntries_;
throw;
}
+ // An erase() can race here and delete right after our insertion
// Direct comparison rather than EqualFcn ok here
// (we just inserted it)
- DCHECK(relaxedLoadKey(*cell) == key_in);
+ DCHECK(relaxedLoadKey(*cell) == key_in ||
+ relaxedLoadKey(*cell) == kErasedKey_);
--numPendingEntries_;
++numEntries_; // This is a thread cached atomic increment :)
if (numEntries_.readFast() >= maxEntries_) {
}
DCHECK(relaxedLoadKey(*cell) != kEmptyKey_);
if (kLockedKey_ == acquireLoadKey(*cell)) {
- FOLLY_SPIN_WAIT(
- kLockedKey_ == acquireLoadKey(*cell)
- );
+ detail::atomic_hash_spin_wait([&] {
+ return kLockedKey_ == acquireLoadKey(*cell);
+ });
}
const KeyT thisKey = acquireLoadKey(*cell);
continue;
}
+
+ // NOTE: the way we count numProbes must be same in find(),
+ // insert(), and erase(). Otherwise it may break probing.
++numProbes;
if (UNLIKELY(numProbes >= capacity_)) {
// probed every cell...fail
return SimpleRetT(capacity_, false);
}
- idx = probeNext(idx, numProbes);
+ idx = ProbeFcn()(idx, numProbes, capacity_);
}
}
* touch it either.
*/
template <class KeyT, class ValueT,
- class HashFcn, class EqualFcn, class Allocator>
-size_t AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+ class HashFcn, class EqualFcn, class Allocator, class ProbeFcn>
+size_t AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
erase(KeyT key_in) {
CHECK_NE(key_in, kEmptyKey_);
CHECK_NE(key_in, kLockedKey_);
CHECK_NE(key_in, kErasedKey_);
+
for (size_t idx = keyToAnchorIdx(key_in), numProbes = 0;
;
- idx = probeNext(idx, numProbes)) {
+ idx = ProbeFcn()(idx, numProbes, capacity_)) {
DCHECK_LT(idx, capacity_);
value_type* cell = &cells_[idx];
KeyT currentKey = acquireLoadKey(*cell);
// If another thread succeeds in erasing our key, we'll stop our search.
return 0;
}
+
+ // NOTE: the way we count numProbes must be same in find(), insert(),
+ // and erase(). Otherwise it may break probing.
++numProbes;
if (UNLIKELY(numProbes >= capacity_)) {
// probed every cell...fail
}
template <class KeyT, class ValueT,
- class HashFcn, class EqualFcn, class Allocator>
-const typename AtomicHashArray<KeyT, ValueT,
- HashFcn, EqualFcn, Allocator>::Config
-AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::defaultConfig;
-
-template <class KeyT, class ValueT,
- class HashFcn, class EqualFcn, class Allocator>
+ class HashFcn, class EqualFcn, class Allocator, class ProbeFcn>
typename AtomicHashArray<KeyT, ValueT,
- HashFcn, EqualFcn, Allocator>::SmartPtr
-AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+ HashFcn, EqualFcn, Allocator, ProbeFcn>::SmartPtr
+AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
create(size_t maxSize, const Config& c) {
CHECK_LE(c.maxLoadFactor, 1.0);
CHECK_GT(c.maxLoadFactor, 0.0);
}
template <class KeyT, class ValueT,
- class HashFcn, class EqualFcn, class Allocator>
-void AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+ class HashFcn, class EqualFcn, class Allocator, class ProbeFcn>
+void AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
destroy(AtomicHashArray* p) {
assert(p);
// clear -- clears all keys and values in the map and resets all counters
template <class KeyT, class ValueT,
- class HashFcn, class EqualFcn, class Allocator>
-void AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+ class HashFcn, class EqualFcn, class Allocator, class ProbeFcn>
+void AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
clear() {
FOR_EACH_RANGE(i, 0, capacity_) {
if (cells_[i].first != kEmptyKey_) {
// Iterator implementation
template <class KeyT, class ValueT,
- class HashFcn, class EqualFcn, class Allocator>
+ class HashFcn, class EqualFcn, class Allocator, class ProbeFcn>
template <class ContT, class IterVal>
-struct AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::aha_iterator
+struct AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
+ aha_iterator
: boost::iterator_facade<aha_iterator<ContT,IterVal>,
IterVal,
boost::forward_traversal_tag>
}; // aha_iterator
} // namespace folly
-
-#undef FOLLY_SPIN_WAIT