58 class KeyHash = std::hash<KeyT>,
59 class KeyEqual = std::equal_to<KeyT>,
60 class ProbeFcn = AtomicHashSetLinearProbeFcn>
62 static_assert((std::is_convertible_v<KeyT, int32_t> || std::is_convertible_v<KeyT, int64_t> ||
63 std::is_convertible_v<KeyT, const void *>),
64 "You are trying to use AtomicHashSet with disallowed key "
65 "types. You must use atomically compare-and-swappable integer "
66 "keys, or a different container class.");
78 using cell_type = std::conditional_t<isAtomic, std::atomic<KeyT>, KeyT>;
79 std::vector<cell_type> cells_;
98 KeyHash hasher = KeyHash(),
99 KeyEqual equalityChecker = KeyEqual(),
101 :
capacity_(size_t(double(maxSize) / c.maxLoadFactor) + 1),
119 std::fill(
reinterpret_cast<KeyT *
>(cells_.data()),
120 reinterpret_cast<KeyT *
>(cells_.data()) +
capacity_,
132 if (*cell == existingKey) {
143 return cell->compare_exchange_strong(existingKey, newKey, std::memory_order_acq_rel);
148 size_t idx = keyToAnchorIdx(key);
149 size_t numProbes = 0;
151 cell_type *cell = &cells_[idx];
156 return std::make_pair(key,
true);
162 return std::make_pair(existingKey,
false);
173 idx = ProbeFcn()(idx, numProbes,
capacity_);
178 size_t keyToAnchorIdx(
const KeyT k)
const
180 const size_t hashVal =
hasher_(k);
181 const size_t probe = hashVal & kAnchorMask_;
AtomicHashSet & operator=(const AtomicHashSet &)=delete
AtomicHashSet(size_t maxSize, KeyHash hasher=KeyHash(), KeyEqual equalityChecker=KeyEqual(), const Config &c=Config())
bool tryUpdateCell(std::atomic< KeyT > *cell, KeyT &existingKey, KeyT newKey)
bool tryUpdateCell(KeyT *cell, KeyT &existingKey, KeyT newKey)
std::pair< KeyT, bool > emplace(KeyT key)
KeyEqual equalityChecker_
AtomicHashSet(const AtomicHashSet &)=delete
#define assert(assertion)
size_t operator()(size_t idx, size_t, size_t capacity) const
size_t operator()(size_t idx, size_t numProbes, size_t capacity) const