F14Table.h | Explore in Territory

/*
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#pragma once

#include <cstddef>
#include <cstdint>
#include <cstring>

#include <array>
#include <iterator>
#include <limits>
#include <memory>
#include <new>
#include <string_view>
#include <type_traits>
#include <utility>
#include <vector>

#include <folly/Bits.h>
#include <folly/ConstexprMath.h>
#include <folly/Likely.h>
#include <folly/Portability.h>
#include <folly/ScopeGuard.h>
#include <folly/Traits.h>
#include <folly/functional/Invoke.h>
#include <folly/lang/Align.h>
#include <folly/lang/Assume.h>
#include <folly/lang/Exception.h>
#include <folly/lang/Pretty.h>
#include <folly/lang/SafeAssert.h>
#include <folly/portability/Builtins.h>

#include <folly/container/HeterogeneousAccess.h>
#include <folly/container/detail/F14Defaults.h>
#include <folly/container/detail/F14IntrinsicsAvailability.h>
#include <folly/container/detail/F14Mask.h>

#if __has_include(<concepts>)
#include <concepts>
#endif

#if FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE

#if FOLLY_F14_CRC_INTRINSIC_AVAILABLE
#if FOLLY_NEON
#include <arm_acle.h> // __crc32cd
#else
#include <nmmintrin.h> // _mm_crc32_u64
#endif
#else
#ifdef _WIN32
#include <intrin.h> // _mul128 in fallback bit mixer
#endif
#endif

#if FOLLY_NEON
#include <arm_neon.h> // uint8x16t intrinsics
#elif FOLLY_SSE >= 2 // SSE2
#include <emmintrin.h> // _mm_set1_epi8
#include <immintrin.h> // __m128i intrinsics
#include <xmmintrin.h> // _mm_prefetch
#endif

#ifndef FOLLY_F14_PERTURB_INSERTION_ORDER
#define FOLLY_F14_PERTURB_INSERTION_ORDER …
#endif

#else // FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE

#ifndef FOLLY_F14_PERTURB_INSERTION_ORDER
#define FOLLY_F14_PERTURB_INSERTION_ORDER …
#endif

#endif // FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE

namespace folly {

struct F14TableStats { … };

namespace f14 {
namespace detail {

template <F14IntrinsicsMode>
struct F14LinkCheck { … };

template <>
struct F14LinkCheck<getF14IntrinsicsMode()> { … };

bool tlsPendingSafeInserts(std::ptrdiff_t delta = 0);
std::size_t tlsMinstdRand(std::size_t n);

#if defined(_LIBCPP_VERSION)

template <typename K, typename V, typename H>
struct StdNodeReplica { … };

#else

template <typename H>
struct StdIsFastHash : std::true_type {};
template <>
struct StdIsFastHash<std::hash<long double>> : std::false_type {};
template <typename... Args>
struct StdIsFastHash<std::hash<std::basic_string<Args...>>> : std::false_type {
};
template <typename... Args>
struct StdIsFastHash<std::hash<std::basic_string_view<Args...>>>
    : std::false_type {};

// mimic internal node of unordered containers in STL to estimate the size
template <typename K, typename V, typename H, typename Enable = void>
struct StdNodeReplica {
  void* next;
  V value;
};
template <typename K, typename V, typename H>
struct StdNodeReplica<
    K,
    V,
    H,
    std::enable_if_t<
        !StdIsFastHash<H>::value || !is_nothrow_invocable_v<H, K>>> {
  void* next;
  V value;
  std::size_t hash;
};

#endif

template <class Container, class Predicate>
typename Container::size_type erase_if_impl(
    Container& c, Predicate& predicate) { … }

} // namespace detail
} // namespace f14

#if FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE
namespace f14 {
namespace detail {
template <typename Policy>
class F14Table;
} // namespace detail
} // namespace f14

class F14HashToken final { … };

#else
class F14HashToken final {
  friend constexpr bool operator==(
      F14HashToken const&, F14HashToken const&) noexcept {
    return true;
  }
  friend constexpr bool operator!=(
      F14HashToken const&, F14HashToken const&) noexcept {
    return false;
  }
};
#endif

#if __cpp_concepts && __has_include(<concepts>)
static_assert(std::regular<F14HashToken>);
#endif

namespace f14 {
namespace detail {

// Detection for folly_assume_32bit_hash

template <typename Hasher, typename Void = void>
struct ShouldAssume32BitHash : std::bool_constant<!require_sizeof<Hasher>> { … };

ShouldAssume32BitHash<Hasher, void_t<typename Hasher::folly_assume_32bit_hash>>;

//////// hash helpers

// Hash values are used to compute the desired position, which is the
// chunk index at which we would like to place a value (if there is no
// overflow), and the tag, which is an additional 7 bits of entropy.
//
// The standard's definition of hash function quality only refers to
// the probability of collisions of the entire hash value, not to the
// probability of collisions of the results of shifting or masking the
// hash value.  Some hash functions, however, provide this stronger
// guarantee (not quite the same as the definition of avalanching,
// but similar).
//
// If the user-supplied hasher is an avalanching one (each bit of the
// hash value has a 50% chance of being the same for differing hash
// inputs), then we can just take 7 bits of the hash value for the tag
// and the rest for the desired position.  Avalanching hashers also
// let us map hash value to array index position with just a bitmask
// without risking clumping.  (Many hash tables just accept the risk
// and do it regardless.)
//
// std::hash<std::string> avalanches in all implementations we've
// examined: libstdc++-v3 uses MurmurHash2, and libc++ uses CityHash
// or MurmurHash2.  The other std::hash specializations, however, do not
// have this property.  std::hash for integral and pointer values is the
// identity function on libstdc++-v3 and libc++, in particular.  In our
// experience it is also fairly common for user-defined specializations
// of std::hash to combine fields in an ad-hoc way that does not evenly
// distribute entropy among the bits of the result (a + 37 * b, for
// example, where a and b are integer fields).
//
// For hash functions we don't trust to avalanche, we repair things by
// applying a bit mixer to the user-supplied hash.

#if FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE
#if FOLLY_X64 || FOLLY_AARCH64 || FOLLY_RISCV64
// 64-bit
template <typename Hasher, typename Key>
std::pair<std::size_t, std::size_t> splitHashImpl(std::size_t hash) { … }
#else
// 32-bit
template <typename Hasher, typename Key>
std::pair<std::size_t, std::size_t> splitHashImpl(std::size_t hash) {
  static_assert(sizeof(std::size_t) == sizeof(uint32_t), "");
  uint8_t tag;
  if (!IsAvalanchingHasher<Hasher, Key>::value) {
#if FOLLY_F14_CRC_INTRINSIC_AVAILABLE
#if FOLLY_SSE_PREREQ(4, 2)
    // SSE4.2 CRC
    auto c = _mm_crc32_u32(0, hash);
    tag = static_cast<uint8_t>(~(c >> 25));
    hash += c;
#else
    auto c = __crc32cw(0, hash);
    tag = static_cast<uint8_t>(~(c >> 25));
    hash += c;
#endif
#else
    // finalizer for 32-bit murmur2
    hash ^= hash >> 13;
    hash *= 0x5bd1e995;
    hash ^= hash >> 15;
    tag = static_cast<uint8_t>(~(hash >> 25));
#endif
  } else {
    // we don't trust the top bit
    tag = (hash >> 24) | 0x80;
  }
  return std::make_pair(hash, tag);
}
#endif
#endif
} // namespace detail
} // namespace f14

template <typename TKeyType, typename Hasher = f14::DefaultHasher<TKeyType>>
class F14HashedKey final {
 public:
#if FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE
  template <typename... Args>
  explicit F14HashedKey(Args&&... args)
      : key_(std::forward<Args>(args)...),
        hash_(f14::detail::splitHashImpl<Hasher, TKeyType>(Hasher{ … }
#else
  F14HashedKey() = delete;
#endif

  const TKeyType& getKey() const { … }
  const F14HashToken& getHashToken() const { … }
  // We want the conversion to the key to be implicit - the hashed key should
  // seamlessly behave as the key itself.
  /* implicit */ operator const TKeyType&() const { return key_; }
  explicit operator const F14HashToken&() const { return hash_; }

  bool operator==(const F14HashedKey& other) const { … }
  bool operator==(const TKeyType& other) const { … }

 private:
  TKeyType key_;
  F14HashToken hash_;
};

#if FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE
namespace f14 {
namespace detail {

//// Defaults should be selected using void
VoidDefault;

Defaulted;

////////////////

/// Prefetch the first cache line of the object at ptr.
template <typename T>
FOLLY_ALWAYS_INLINE static void prefetchAddr(T const* ptr) { … }

#if FOLLY_NEON
TagVector;
#elif FOLLY_SSE >= 2
using TagVector = __m128i;
#elif FOLLY_HAVE_INT128_T
using TagVector = __uint128_t;
#endif

// We could use unaligned loads to relax this requirement, but that
// would be both a performance penalty and require a bulkier packed
// ItemIter format
constexpr std::size_t kRequiredVectorAlignment = …;

EmptyTagVectorType;

FOLLY_EXPORT extern EmptyTagVectorType kEmptyTagVector;

template <typename ItemType>
struct alignas(kRequiredVectorAlignment) F14Chunk { … };

////////////////

// PackedChunkItemPtr points to an Item in an F14Chunk, allowing both the
// Item& and its index to be recovered.  It sorts by the address of the
// item, and it only works for items that are in a properly-aligned chunk.

// generic form, not actually packed
template <typename Ptr>
class PackedChunkItemPtr { … };

// Bare pointer form, packed into a uintptr_t.  Uses only bits wasted by
// alignment, so it works on 32-bit and 64-bit platforms
PackedChunkItemPtr<T *>;

template <typename ChunkPtr>
class F14ItemIter { … };

////////////////

struct PackedSizeAndChunkShift { … };

struct UnpackedSizeAndChunkShift { … };

SizeAndChunkShift;

template <typename ItemIter, bool EnablePackedItemIter>
struct SizeAndChunkShiftAndPackedBegin { … };

SizeAndChunkShiftAndPackedBegin<ItemIter, false>;

template <typename Policy>
class F14Table : public Policy { … };
} // namespace detail
} // namespace f14

#endif // FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE

namespace f14 {
namespace test {
inline void disableInsertOrderRandomization() { … }
} // namespace test
} // namespace f14
} // namespace folly
folly/folly/container/detail/F14Table.h
