-template <class KeyT, class ValueT,
- class HashFcn = std::hash<KeyT>,
- class EqualFcn = std::equal_to<KeyT>,
- class Allocator = std::allocator<char>>
+struct AtomicHashArrayLinearProbeFcn
+{
+ inline size_t operator()(size_t idx,
+ size_t /* numProbes */,
+ size_t capacity) const {
+ idx += 1; // linear probing
+
+ // Avoid modulus because it's slow
+ return LIKELY(idx < capacity) ? idx : (idx - capacity);
+ }
+};
+
+struct AtomicHashArrayQuadraticProbeFcn
+{
+ inline size_t operator()(size_t idx, size_t numProbes, size_t capacity) const{
+ idx += numProbes; // quadratic probing
+
+ // Avoid modulus because it's slow
+ return LIKELY(idx < capacity) ? idx : (idx - capacity);
+ }
+};
+
+// Enables specializing checkLegalKey without specializing its class.
+namespace detail {
+template <typename NotKeyT, typename KeyT>
+inline void checkLegalKeyIfKeyTImpl(NotKeyT /* ignored */,
+ KeyT /* emptyKey */,
+ KeyT /* lockedKey */,
+ KeyT /* erasedKey */) {}
+
+template <typename KeyT>
+inline void checkLegalKeyIfKeyTImpl(KeyT key_in, KeyT emptyKey,
+ KeyT lockedKey, KeyT erasedKey) {
+ DCHECK_NE(key_in, emptyKey);
+ DCHECK_NE(key_in, lockedKey);
+ DCHECK_NE(key_in, erasedKey);
+}
+} // namespace detail
+
+template <
+ class KeyT,
+ class ValueT,
+ class HashFcn = std::hash<KeyT>,
+ class EqualFcn = std::equal_to<KeyT>,
+ class Allocator = std::allocator<char>,
+ class ProbeFcn = AtomicHashArrayLinearProbeFcn,
+ class KeyConvertFcn = Identity>