/* * 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. */ // // Docs: https://fburl.com/fbcref_f14nodeset // #pragma once /** * F14NodeSet, F14ValueSet, and F14VectorSet * * F14FastSet conditionally works like F14ValueSet or F14VectorSet * * See F14.md */ #include <cstddef> #include <initializer_list> #include <tuple> #include <folly/Portability.h> #include <folly/container/View.h> #include <folly/lang/SafeAssert.h> #include <folly/container/F14Set-fwd.h> #include <folly/container/Iterator.h> #include <folly/container/detail/F14Policy.h> #include <folly/container/detail/F14SetFallback.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 F14BasicSet { … }; } // namespace detail } // namespace f14 template <typename Key, typename Hasher, typename KeyEqual, typename Alloc> class F14ValueSet : public f14::detail::F14BasicSet<f14::detail::SetPolicyWithDefaults< f14::detail::ValueContainerPolicy, Key, Hasher, KeyEqual, Alloc>> { … }; #endif // FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE template < typename InputIt, typename Hasher = f14::DefaultHasher<iterator_value_type_t<InputIt>>, typename KeyEqual = f14::DefaultKeyEqual<iterator_value_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>> F14ValueSet( InputIt, InputIt, std::size_t = { … }; template < typename InputIt, typename Alloc, typename = detail::RequireInputIterator<InputIt>, typename = detail::RequireAllocator<Alloc>> F14ValueSet(InputIt, InputIt, std::size_t, Alloc) -> F14ValueSet< iterator_value_type_t<InputIt>, f14::DefaultHasher<iterator_value_type_t<InputIt>>, f14::DefaultKeyEqual<iterator_value_type_t<InputIt>>, Alloc>; template < typename InputIt, typename Hasher, typename Alloc, typename = detail::RequireInputIterator<InputIt>, typename = detail::RequireNotAllocator<Hasher>, typename = detail::RequireAllocator<Alloc>> F14ValueSet(InputIt, InputIt, std::size_t, Hasher, Alloc) -> F14ValueSet< iterator_value_type_t<InputIt>, Hasher, f14::DefaultKeyEqual<iterator_value_type_t<InputIt>>, Alloc>; template < typename Key, typename Hasher = f14::DefaultHasher<Key>, typename KeyEqual = f14::DefaultKeyEqual<Key>, typename Alloc = f14::DefaultAlloc<Key>, typename = detail::RequireNotAllocator<Hasher>, typename = detail::RequireNotAllocator<KeyEqual>, typename = detail::RequireAllocator<Alloc>> F14ValueSet( std::initializer_list<Key>, std::size_t = { … }; template < typename Key, typename Alloc, typename = detail::RequireAllocator<Alloc>> F14ValueSet(std::initializer_list<Key>, std::size_t, Alloc) -> F14ValueSet< Key, f14::DefaultHasher<Key>, f14::DefaultKeyEqual<Key>, Alloc>; template < typename Key, typename Hasher, typename Alloc, typename = detail::RequireAllocator<Alloc>> F14ValueSet(std::initializer_list<Key>, std::size_t, Hasher, Alloc) -> F14ValueSet<Key, Hasher, f14::DefaultKeyEqual<Key>, Alloc>; #if FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE template <typename Key, typename Hasher, typename KeyEqual, typename Alloc> class F14NodeSet : public f14::detail::F14BasicSet<f14::detail::SetPolicyWithDefaults< f14::detail::NodeContainerPolicy, Key, Hasher, KeyEqual, Alloc>> { … }; #endif // FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE template < typename InputIt, typename Hasher = f14::DefaultHasher<iterator_value_type_t<InputIt>>, typename KeyEqual = f14::DefaultKeyEqual<iterator_value_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>> F14NodeSet( InputIt, InputIt, std::size_t = { … }; template < typename InputIt, typename Alloc, typename = detail::RequireInputIterator<InputIt>, typename = detail::RequireAllocator<Alloc>> F14NodeSet(InputIt, InputIt, std::size_t, Alloc) -> F14NodeSet< iterator_value_type_t<InputIt>, f14::DefaultHasher<iterator_value_type_t<InputIt>>, f14::DefaultKeyEqual<iterator_value_type_t<InputIt>>, Alloc>; template < typename InputIt, typename Hasher, typename Alloc, typename = detail::RequireInputIterator<InputIt>, typename = detail::RequireNotAllocator<Hasher>, typename = detail::RequireAllocator<Alloc>> F14NodeSet(InputIt, InputIt, std::size_t, Hasher, Alloc) -> F14NodeSet< iterator_value_type_t<InputIt>, Hasher, f14::DefaultKeyEqual<iterator_value_type_t<InputIt>>, Alloc>; template < typename Key, typename Hasher = f14::DefaultHasher<Key>, typename KeyEqual = f14::DefaultKeyEqual<Key>, typename Alloc = f14::DefaultAlloc<Key>, typename = detail::RequireNotAllocator<Hasher>, typename = detail::RequireNotAllocator<KeyEqual>, typename = detail::RequireAllocator<Alloc>> F14NodeSet( std::initializer_list<Key>, std::size_t = { … }; template < typename Key, typename Alloc, typename = detail::RequireAllocator<Alloc>> F14NodeSet(std::initializer_list<Key>, std::size_t, Alloc) -> F14NodeSet< Key, f14::DefaultHasher<Key>, f14::DefaultKeyEqual<Key>, Alloc>; template < typename Key, typename Hasher, typename Alloc, typename = detail::RequireAllocator<Alloc>> F14NodeSet(std::initializer_list<Key>, std::size_t, Hasher, Alloc) -> F14NodeSet<Key, Hasher, f14::DefaultKeyEqual<Key>, Alloc>; #if FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE namespace f14 { namespace detail { template < typename Key, typename Hasher, typename KeyEqual, typename Alloc, typename EligibleForPerturbedInsertionOrder> class F14VectorSetImpl : public F14BasicSet<SetPolicyWithDefaults< VectorContainerPolicy, Key, Hasher, KeyEqual, Alloc, EligibleForPerturbedInsertionOrder>> { … }; } // namespace detail } // namespace f14 template <typename Key, typename Hasher, typename KeyEqual, typename Alloc> class F14VectorSet : public f14::detail:: F14VectorSetImpl<Key, Hasher, KeyEqual, Alloc, std::false_type> { … }; #endif // FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE template < typename InputIt, typename Hasher = f14::DefaultHasher<iterator_value_type_t<InputIt>>, typename KeyEqual = f14::DefaultKeyEqual<iterator_value_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>> F14VectorSet( InputIt, InputIt, std::size_t = { … }; template < typename InputIt, typename Alloc, typename = detail::RequireInputIterator<InputIt>, typename = detail::RequireAllocator<Alloc>> F14VectorSet(InputIt, InputIt, std::size_t, Alloc) -> F14VectorSet< iterator_value_type_t<InputIt>, f14::DefaultHasher<iterator_value_type_t<InputIt>>, f14::DefaultKeyEqual<iterator_value_type_t<InputIt>>, Alloc>; template < typename InputIt, typename Hasher, typename Alloc, typename = detail::RequireInputIterator<InputIt>, typename = detail::RequireNotAllocator<Hasher>, typename = detail::RequireAllocator<Alloc>> F14VectorSet(InputIt, InputIt, std::size_t, Hasher, Alloc) -> F14VectorSet< iterator_value_type_t<InputIt>, Hasher, f14::DefaultKeyEqual<iterator_value_type_t<InputIt>>, Alloc>; template < typename Key, typename Hasher = f14::DefaultHasher<Key>, typename KeyEqual = f14::DefaultKeyEqual<Key>, typename Alloc = f14::DefaultAlloc<Key>, typename = detail::RequireNotAllocator<Hasher>, typename = detail::RequireNotAllocator<KeyEqual>, typename = detail::RequireAllocator<Alloc>> F14VectorSet( std::initializer_list<Key>, std::size_t = { … }; template < typename Key, typename Alloc, typename = detail::RequireAllocator<Alloc>> F14VectorSet(std::initializer_list<Key>, std::size_t, Alloc) -> F14VectorSet< Key, f14::DefaultHasher<Key>, f14::DefaultKeyEqual<Key>, Alloc>; template < typename Key, typename Hasher, typename Alloc, typename = detail::RequireAllocator<Alloc>> F14VectorSet(std::initializer_list<Key>, std::size_t, Hasher, Alloc) -> F14VectorSet<Key, Hasher, f14::DefaultKeyEqual<Key>, Alloc>; #if FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE template <typename Key, typename Hasher, typename KeyEqual, typename Alloc> class F14FastSet : public std::conditional_t< sizeof(Key) < 24, F14ValueSet<Key, Hasher, KeyEqual, Alloc>, f14::detail:: F14VectorSetImpl<Key, Hasher, KeyEqual, Alloc, std::true_type>> { … }; #endif // FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE template < typename InputIt, typename Hasher = f14::DefaultHasher<iterator_value_type_t<InputIt>>, typename KeyEqual = f14::DefaultKeyEqual<iterator_value_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>> F14FastSet( InputIt, InputIt, std::size_t = { … }; template < typename InputIt, typename Alloc, typename = detail::RequireInputIterator<InputIt>, typename = detail::RequireAllocator<Alloc>> F14FastSet(InputIt, InputIt, std::size_t, Alloc) -> F14FastSet< iterator_value_type_t<InputIt>, f14::DefaultHasher<iterator_value_type_t<InputIt>>, f14::DefaultKeyEqual<iterator_value_type_t<InputIt>>, Alloc>; template < typename InputIt, typename Hasher, typename Alloc, typename = detail::RequireInputIterator<InputIt>, typename = detail::RequireNotAllocator<Hasher>, typename = detail::RequireAllocator<Alloc>> F14FastSet(InputIt, InputIt, std::size_t, Hasher, Alloc) -> F14FastSet< iterator_value_type_t<InputIt>, Hasher, f14::DefaultKeyEqual<iterator_value_type_t<InputIt>>, Alloc>; template < typename Key, typename Hasher = f14::DefaultHasher<Key>, typename KeyEqual = f14::DefaultKeyEqual<Key>, typename Alloc = f14::DefaultAlloc<Key>, typename = detail::RequireNotAllocator<Hasher>, typename = detail::RequireNotAllocator<KeyEqual>, typename = detail::RequireAllocator<Alloc>> F14FastSet( std::initializer_list<Key>, std::size_t = { … }; template < typename Key, typename Alloc, typename = detail::RequireAllocator<Alloc>> F14FastSet(std::initializer_list<Key>, std::size_t, Alloc) -> F14FastSet< Key, f14::DefaultHasher<Key>, f14::DefaultKeyEqual<Key>, Alloc>; template < typename Key, typename Hasher, typename Alloc, typename = detail::RequireAllocator<Alloc>> F14FastSet(std::initializer_list<Key>, std::size_t, Hasher, Alloc) -> F14FastSet<Key, Hasher, f14::DefaultKeyEqual<Key>, Alloc>; } // namespace folly namespace folly { namespace f14 { namespace detail { template <typename S> bool setsEqual(S const& lhs, S const& rhs) { … } } // namespace detail } // namespace f14 template <typename K, typename H, typename E, typename A> bool operator==( F14ValueSet<K, H, E, A> const& lhs, F14ValueSet<K, H, E, A> const& rhs) { … } template <typename K, typename H, typename E, typename A> bool operator!=( F14ValueSet<K, H, E, A> const& lhs, F14ValueSet<K, H, E, A> const& rhs) { … } template <typename K, typename H, typename E, typename A> bool operator==( F14NodeSet<K, H, E, A> const& lhs, F14NodeSet<K, H, E, A> const& rhs) { … } template <typename K, typename H, typename E, typename A> bool operator!=( F14NodeSet<K, H, E, A> const& lhs, F14NodeSet<K, H, E, A> const& rhs) { … } template <typename K, typename H, typename E, typename A> bool operator==( F14VectorSet<K, H, E, A> const& lhs, F14VectorSet<K, H, E, A> const& rhs) { … } template <typename K, typename H, typename E, typename A> bool operator!=( F14VectorSet<K, H, E, A> const& lhs, F14VectorSet<K, H, E, A> const& rhs) { … } template <typename K, typename H, typename E, typename A> bool operator==( F14FastSet<K, H, E, A> const& lhs, F14FastSet<K, H, E, A> const& rhs) { … } template <typename K, typename H, typename E, typename A> bool operator!=( F14FastSet<K, H, E, A> const& lhs, F14FastSet<K, H, E, A> const& rhs) { … } template <typename K, typename H, typename E, typename A> void swap(F14ValueSet<K, H, E, A>& lhs, F14ValueSet<K, H, E, A>& rhs) noexcept( noexcept(lhs.swap(rhs))) { … } template <typename K, typename H, typename E, typename A> void swap(F14NodeSet<K, H, E, A>& lhs, F14NodeSet<K, H, E, A>& rhs) noexcept( noexcept(lhs.swap(rhs))) { … } template <typename K, typename H, typename E, typename A> void swap( F14VectorSet<K, H, E, A>& lhs, F14VectorSet<K, H, E, A>& rhs) noexcept(noexcept(lhs.swap(rhs))) { … } template <typename K, typename H, typename E, typename A> void swap(F14FastSet<K, H, E, A>& lhs, F14FastSet<K, H, E, A>& rhs) noexcept( noexcept(lhs.swap(rhs))) { … } template <typename K, typename H, typename E, typename A, typename Pred> std::size_t erase_if(F14ValueSet<K, H, E, A>& c, Pred pred) { … } template <typename K, typename H, typename E, typename A, typename Pred> std::size_t erase_if(F14NodeSet<K, H, E, A>& c, Pred pred) { … } template <typename K, typename H, typename E, typename A, typename Pred> std::size_t erase_if(F14VectorSet<K, H, E, A>& c, Pred pred) { … } template <typename K, typename H, typename E, typename A, typename Pred> std::size_t erase_if(F14FastSet<K, H, E, A>& c, Pred pred) { … } } // namespace folly
Codebase Browser
folly