/* * 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 /** * F14NodeMap, F14ValueMap, and F14VectorMap * * F14FastMap conditionally works like F14ValueMap or F14VectorMap * * See F14.md */ #include <cstddef> #include <initializer_list> #include <stdexcept> #include <tuple> #include <folly/Portability.h> #include <folly/Range.h> #include <folly/Traits.h> #include <folly/container/View.h> #include <folly/lang/Exception.h> #include <folly/lang/SafeAssert.h> #include <folly/container/F14Map-fwd.h> #include <folly/container/Iterator.h> #include <folly/container/detail/F14MapFallback.h> #include <folly/container/detail/F14Policy.h> #include <folly/container/detail/F14Table.h> #include <folly/container/detail/Util.h> namespace folly { #if FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE //////// Common case for supported platforms namespace f14 { namespace detail { template <typename Policy> class F14BasicMap { … }; } // namespace detail } // namespace f14 template < typename Key, typename Mapped, typename Hasher, typename KeyEqual, typename Alloc> class F14ValueMap : public f14::detail::F14BasicMap<f14::detail::MapPolicyWithDefaults< f14::detail::ValueContainerPolicy, Key, Mapped, Hasher, KeyEqual, Alloc>> { … }; #endif // FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE template < typename InputIt, typename Hasher = f14::DefaultHasher<iterator_key_type_t<InputIt>>, typename KeyEqual = f14::DefaultKeyEqual<iterator_key_type_t<InputIt>>, typename Alloc = f14::DefaultAlloc<iterator_value_type_t<InputIt>>, typename = detail::RequireInputIterator<InputIt>, // Next two constraints are necessary to disambiguate from next constructor typename = detail::RequireNotAllocator<Hasher>, typename = detail::RequireNotAllocator<KeyEqual>, typename = detail::RequireAllocator<Alloc>> F14ValueMap( InputIt, InputIt, std::size_t = { … }; template < typename InputIt, typename Alloc, typename = detail::RequireInputIterator<InputIt>, typename = detail::RequireAllocator<Alloc>> F14ValueMap(InputIt, InputIt, std::size_t, Alloc) -> F14ValueMap< iterator_key_type_t<InputIt>, iterator_mapped_type_t<InputIt>, f14::DefaultHasher<iterator_key_type_t<InputIt>>, f14::DefaultKeyEqual<iterator_key_type_t<InputIt>>, Alloc>; template < typename InputIt, typename Hasher, typename Alloc, typename = detail::RequireInputIterator<InputIt>, typename = detail::RequireNotAllocator<Hasher>, typename = detail::RequireAllocator<Alloc>> F14ValueMap(InputIt, InputIt, std::size_t, Hasher, Alloc) -> F14ValueMap< iterator_key_type_t<InputIt>, iterator_mapped_type_t<InputIt>, Hasher, f14::DefaultKeyEqual<iterator_key_type_t<InputIt>>, Alloc>; template < typename Key, typename Mapped, typename Hasher = f14::DefaultHasher<Key>, typename KeyEqual = f14::DefaultKeyEqual<Key>, typename Alloc = f14::DefaultAlloc<std::pair<const Key, Mapped>>, typename = detail::RequireNotAllocator<Hasher>, typename = detail::RequireNotAllocator<KeyEqual>, typename = detail::RequireAllocator<Alloc>> F14ValueMap( std::initializer_list<std::pair<Key, Mapped>>, std::size_t = { … }; template < typename Key, typename Mapped, typename Alloc, typename = detail::RequireAllocator<Alloc>> F14ValueMap(std::initializer_list<std::pair<Key, Mapped>>, std::size_t, Alloc) -> F14ValueMap< Key, Mapped, f14::DefaultHasher<Key>, f14::DefaultKeyEqual<Key>, Alloc>; template < typename Key, typename Mapped, typename Hasher, typename Alloc, typename = detail::RequireAllocator<Alloc>> F14ValueMap( std::initializer_list<std::pair<Key, Mapped>>, std::size_t, Hasher, Alloc) -> F14ValueMap<Key, Mapped, Hasher, f14::DefaultKeyEqual<Key>, Alloc>; #if FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE template < typename Key, typename Mapped, typename Hasher, typename KeyEqual, typename Alloc> class F14NodeMap : public f14::detail::F14BasicMap<f14::detail::MapPolicyWithDefaults< f14::detail::NodeContainerPolicy, Key, Mapped, Hasher, KeyEqual, Alloc>> { … }; #endif // FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE template < typename InputIt, typename Hasher = f14::DefaultHasher<iterator_key_type_t<InputIt>>, typename KeyEqual = f14::DefaultKeyEqual<iterator_key_type_t<InputIt>>, typename Alloc = f14::DefaultAlloc<iterator_value_type_t<InputIt>>, typename = detail::RequireInputIterator<InputIt>, typename = detail::RequireNotAllocator<Hasher>, typename = detail::RequireNotAllocator<KeyEqual>, typename = detail::RequireAllocator<Alloc>> F14NodeMap( InputIt, InputIt, std::size_t = { … }; template < typename InputIt, typename Alloc, typename = detail::RequireInputIterator<InputIt>, typename = detail::RequireAllocator<Alloc>> F14NodeMap(InputIt, InputIt, std::size_t, Alloc) -> F14NodeMap< iterator_key_type_t<InputIt>, iterator_mapped_type_t<InputIt>, f14::DefaultHasher<iterator_key_type_t<InputIt>>, f14::DefaultKeyEqual<iterator_key_type_t<InputIt>>, Alloc>; template < typename InputIt, typename Hasher, typename Alloc, typename = detail::RequireInputIterator<InputIt>, typename = detail::RequireNotAllocator<Hasher>, typename = detail::RequireAllocator<Alloc>> F14NodeMap(InputIt, InputIt, std::size_t, Hasher, Alloc) -> F14NodeMap< iterator_key_type_t<InputIt>, iterator_mapped_type_t<InputIt>, Hasher, f14::DefaultKeyEqual<iterator_key_type_t<InputIt>>, Alloc>; template < typename Key, typename Mapped, typename Hasher = f14::DefaultHasher<Key>, typename KeyEqual = f14::DefaultKeyEqual<Key>, typename Alloc = f14::DefaultAlloc<std::pair<const Key, Mapped>>, typename = detail::RequireNotAllocator<Hasher>, typename = detail::RequireNotAllocator<KeyEqual>, typename = detail::RequireAllocator<Alloc>> F14NodeMap( std::initializer_list<std::pair<Key, Mapped>>, std::size_t = { … }; template < typename Key, typename Mapped, typename Alloc, typename = detail::RequireAllocator<Alloc>> F14NodeMap(std::initializer_list<std::pair<Key, Mapped>>, std::size_t, Alloc) -> F14NodeMap< Key, Mapped, f14::DefaultHasher<Key>, f14::DefaultKeyEqual<Key>, Alloc>; template < typename Key, typename Mapped, typename Hasher, typename Alloc, typename = detail::RequireAllocator<Alloc>> F14NodeMap( std::initializer_list<std::pair<Key, Mapped>>, std::size_t, Hasher, Alloc) -> F14NodeMap<Key, Mapped, Hasher, f14::DefaultKeyEqual<Key>, Alloc>; #if FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE namespace f14 { namespace detail { template < typename Key, typename Mapped, typename Hasher, typename KeyEqual, typename Alloc, typename EligibleForPerturbedInsertionOrder> class F14VectorMapImpl : public F14BasicMap<MapPolicyWithDefaults< VectorContainerPolicy, Key, Mapped, Hasher, KeyEqual, Alloc, EligibleForPerturbedInsertionOrder>> { … }; } // namespace detail } // namespace f14 template < typename Key, typename Mapped, typename Hasher, typename KeyEqual, typename Alloc> class F14VectorMap : public f14::detail::F14VectorMapImpl< Key, Mapped, Hasher, KeyEqual, Alloc, std::false_type> { … }; #endif // FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE template < typename InputIt, typename Hasher = f14::DefaultHasher<iterator_key_type_t<InputIt>>, typename KeyEqual = f14::DefaultKeyEqual<iterator_key_type_t<InputIt>>, typename Alloc = f14::DefaultAlloc<iterator_value_type_t<InputIt>>, typename = detail::RequireInputIterator<InputIt>, typename = detail::RequireNotAllocator<Hasher>, typename = detail::RequireNotAllocator<KeyEqual>, typename = detail::RequireAllocator<Alloc>> F14VectorMap( InputIt, InputIt, std::size_t = { … }; template < typename InputIt, typename Alloc, typename = detail::RequireInputIterator<InputIt>, typename = detail::RequireAllocator<Alloc>> F14VectorMap(InputIt, InputIt, std::size_t, Alloc) -> F14VectorMap< iterator_key_type_t<InputIt>, iterator_mapped_type_t<InputIt>, f14::DefaultHasher<iterator_key_type_t<InputIt>>, f14::DefaultKeyEqual<iterator_key_type_t<InputIt>>, Alloc>; template < typename InputIt, typename Hasher, typename Alloc, typename = detail::RequireInputIterator<InputIt>, typename = detail::RequireNotAllocator<Hasher>, typename = detail::RequireAllocator<Alloc>> F14VectorMap(InputIt, InputIt, std::size_t, Hasher, Alloc) -> F14VectorMap< iterator_key_type_t<InputIt>, iterator_mapped_type_t<InputIt>, Hasher, f14::DefaultKeyEqual<iterator_key_type_t<InputIt>>, Alloc>; template < typename Key, typename Mapped, typename Hasher = f14::DefaultHasher<Key>, typename KeyEqual = f14::DefaultKeyEqual<Key>, typename Alloc = f14::DefaultAlloc<std::pair<const Key, Mapped>>, typename = detail::RequireNotAllocator<Hasher>, typename = detail::RequireNotAllocator<KeyEqual>, typename = detail::RequireAllocator<Alloc>> F14VectorMap( std::initializer_list<std::pair<Key, Mapped>>, std::size_t = { … }; template < typename Key, typename Mapped, typename Alloc, typename = detail::RequireAllocator<Alloc>> F14VectorMap(std::initializer_list<std::pair<Key, Mapped>>, std::size_t, Alloc) -> F14VectorMap< Key, Mapped, f14::DefaultHasher<Key>, f14::DefaultKeyEqual<Key>, Alloc>; template < typename Key, typename Mapped, typename Hasher, typename Alloc, typename = detail::RequireAllocator<Alloc>> F14VectorMap( std::initializer_list<std::pair<Key, Mapped>>, std::size_t, Hasher, Alloc) -> F14VectorMap<Key, Mapped, Hasher, f14::DefaultKeyEqual<Key>, Alloc>; #if FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE /** * F14FastMap is, under the hood, either an F14ValueMap or an F14VectorMap. * F14FastMap chooses which of these two representations to use based on the * size of a node. */ template < typename Key, typename Mapped, typename Hasher, typename KeyEqual, typename Alloc> class F14FastMap : public std::conditional_t< (sizeof(std::pair<Key const, Mapped>) < 24), F14ValueMap<Key, Mapped, Hasher, KeyEqual, Alloc>, f14::detail::F14VectorMapImpl< Key, Mapped, Hasher, KeyEqual, Alloc, std::true_type>> { … }; #endif // if FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE template < typename InputIt, typename Hasher = f14::DefaultHasher<iterator_key_type_t<InputIt>>, typename KeyEqual = f14::DefaultKeyEqual<iterator_key_type_t<InputIt>>, typename Alloc = f14::DefaultAlloc<iterator_value_type_t<InputIt>>, typename = detail::RequireInputIterator<InputIt>, typename = detail::RequireNotAllocator<Hasher>, typename = detail::RequireNotAllocator<KeyEqual>, typename = detail::RequireAllocator<Alloc>> F14FastMap( InputIt, InputIt, std::size_t = { … }; template < typename InputIt, typename Alloc, typename = detail::RequireInputIterator<InputIt>, typename = detail::RequireAllocator<Alloc>> F14FastMap(InputIt, InputIt, std::size_t, Alloc) -> F14FastMap< iterator_key_type_t<InputIt>, iterator_mapped_type_t<InputIt>, f14::DefaultHasher<iterator_key_type_t<InputIt>>, f14::DefaultKeyEqual<iterator_key_type_t<InputIt>>, Alloc>; template < typename InputIt, typename Hasher, typename Alloc, typename = detail::RequireInputIterator<InputIt>, typename = detail::RequireNotAllocator<Hasher>, typename = detail::RequireAllocator<Alloc>> F14FastMap(InputIt, InputIt, std::size_t, Hasher, Alloc) -> F14FastMap< iterator_key_type_t<InputIt>, iterator_mapped_type_t<InputIt>, Hasher, f14::DefaultKeyEqual<iterator_key_type_t<InputIt>>, Alloc>; template < typename Key, typename Mapped, typename Hasher = f14::DefaultHasher<Key>, typename KeyEqual = f14::DefaultKeyEqual<Key>, typename Alloc = f14::DefaultAlloc<std::pair<const Key, Mapped>>, typename = detail::RequireNotAllocator<Hasher>, typename = detail::RequireNotAllocator<KeyEqual>, typename = detail::RequireAllocator<Alloc>> F14FastMap( std::initializer_list<std::pair<Key, Mapped>>, std::size_t = { … }; template < typename Key, typename Mapped, typename Alloc, typename = detail::RequireAllocator<Alloc>> F14FastMap(std::initializer_list<std::pair<Key, Mapped>>, std::size_t, Alloc) -> F14FastMap< Key, Mapped, f14::DefaultHasher<Key>, f14::DefaultKeyEqual<Key>, Alloc>; template < typename Key, typename Mapped, typename Hasher, typename Alloc, typename = detail::RequireAllocator<Alloc>> F14FastMap( std::initializer_list<std::pair<Key, Mapped>>, std::size_t, Hasher, Alloc) -> F14FastMap<Key, Mapped, Hasher, f14::DefaultKeyEqual<Key>, Alloc>; } // namespace folly namespace folly { namespace f14 { namespace detail { template <typename M> bool mapsEqual(M const& lhs, M const& rhs) { … } } // namespace detail } // namespace f14 template <typename K, typename M, typename H, typename E, typename A> bool operator==( F14ValueMap<K, M, H, E, A> const& lhs, F14ValueMap<K, M, H, E, A> const& rhs) { … } template <typename K, typename M, typename H, typename E, typename A> bool operator!=( F14ValueMap<K, M, H, E, A> const& lhs, F14ValueMap<K, M, H, E, A> const& rhs) { … } template <typename K, typename M, typename H, typename E, typename A> bool operator==( F14NodeMap<K, M, H, E, A> const& lhs, F14NodeMap<K, M, H, E, A> const& rhs) { … } template <typename K, typename M, typename H, typename E, typename A> bool operator!=( F14NodeMap<K, M, H, E, A> const& lhs, F14NodeMap<K, M, H, E, A> const& rhs) { … } template <typename K, typename M, typename H, typename E, typename A> bool operator==( F14VectorMap<K, M, H, E, A> const& lhs, F14VectorMap<K, M, H, E, A> const& rhs) { … } template <typename K, typename M, typename H, typename E, typename A> bool operator!=( F14VectorMap<K, M, H, E, A> const& lhs, F14VectorMap<K, M, H, E, A> const& rhs) { … } template <typename K, typename M, typename H, typename E, typename A> bool operator==( F14FastMap<K, M, H, E, A> const& lhs, F14FastMap<K, M, H, E, A> const& rhs) { … } template <typename K, typename M, typename H, typename E, typename A> bool operator!=( F14FastMap<K, M, H, E, A> const& lhs, F14FastMap<K, M, H, E, A> const& rhs) { … } template <typename K, typename M, typename H, typename E, typename A> void swap( F14ValueMap<K, M, H, E, A>& lhs, F14ValueMap<K, M, H, E, A>& rhs) noexcept(noexcept(lhs.swap(rhs))) { … } template <typename K, typename M, typename H, typename E, typename A> void swap( F14NodeMap<K, M, H, E, A>& lhs, F14NodeMap<K, M, H, E, A>& rhs) noexcept(noexcept(lhs.swap(rhs))) { … } template <typename K, typename M, typename H, typename E, typename A> void swap( F14VectorMap<K, M, H, E, A>& lhs, F14VectorMap<K, M, H, E, A>& rhs) noexcept(noexcept(lhs.swap(rhs))) { … } template <typename K, typename M, typename H, typename E, typename A> void swap( F14FastMap<K, M, H, E, A>& lhs, F14FastMap<K, M, H, E, A>& rhs) noexcept(noexcept(lhs.swap(rhs))) { … } template < typename K, typename M, typename H, typename E, typename A, typename Pred> std::size_t erase_if(F14ValueMap<K, M, H, E, A>& c, Pred pred) { … } template < typename K, typename M, typename H, typename E, typename A, typename Pred> std::size_t erase_if(F14NodeMap<K, M, H, E, A>& c, Pred pred) { … } template < typename K, typename M, typename H, typename E, typename A, typename Pred> std::size_t erase_if(F14VectorMap<K, M, H, E, A>& c, Pred pred) { … } template < typename K, typename M, typename H, typename E, typename A, typename Pred> std::size_t erase_if(F14FastMap<K, M, H, E, A>& c, Pred pred) { … } } // namespace folly
Codebase Browser
folly