+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 {
+// Local copy of folly::gen::Identity, to avoid heavy dependencies.
+class AHAIdentity {
+ public:
+ template<class Value>
+ auto operator()(Value&& value) const ->
+ decltype(std::forward<Value>(value)) {
+ return std::forward<Value>(value);
+ }
+};
+
+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
+