/* * 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. */ /* * For high-level documentation and usage examples see * folly/docs/small_vector.md */ #pragma once #include <algorithm> #include <cassert> #include <cstdlib> #include <cstring> #include <iterator> #include <memory> #include <stdexcept> #include <type_traits> #include <utility> #include <boost/operators.hpp> #include <folly/ConstexprMath.h> #include <folly/FormatTraits.h> #include <folly/Likely.h> #include <folly/Portability.h> #include <folly/ScopeGuard.h> #include <folly/Traits.h> #include <folly/functional/Invoke.h> #include <folly/hash/Hash.h> #include <folly/lang/Align.h> #include <folly/lang/Assume.h> #include <folly/lang/CheckedMath.h> #include <folly/lang/Exception.h> #include <folly/memory/Malloc.h> #include <folly/memory/SanitizeLeak.h> #include <folly/portability/Malloc.h> #if (FOLLY_X64 || FOLLY_PPC64 || FOLLY_AARCH64 || FOLLY_RISCV64) #define FOLLY_SV_PACK_ATTR … #define FOLLY_SV_PACK_PUSH … #define FOLLY_SV_PACK_POP … #else #define FOLLY_SV_PACK_ATTR #define FOLLY_SV_PACK_PUSH #define FOLLY_SV_PACK_POP #endif // Ignore shadowing warnings within this file, so includers can use -Wshadow. FOLLY_PUSH_WARNING FOLLY_GNU_DISABLE_WARNING(…) namespace folly { namespace small_vector_policy { namespace detail { struct item_size_type { … }; struct item_in_situ_only { … }; template <template <typename> class F, typename... T> constexpr size_t last_matching_() { … } template <size_t M, typename I, typename... P> struct merge_ // : I::template set<typename I::template get< type_pack_element_t<sizeof...(P) - M, P...>>> {}; merge_<0, I, P...>; merge; } // namespace detail template <typename... Policy> struct merge // : detail::merge<detail::item_size_type, Policy...>, detail::merge<detail::item_in_situ_only, Policy...> { … }; template <typename SizeType> struct policy_size_type { … }; template <bool Value> struct policy_in_situ_only { … }; } // namespace small_vector_policy ////////////////////////////////////////////////////////////////////// template <class T, std::size_t M, class P> class small_vector; ////////////////////////////////////////////////////////////////////// namespace detail { /* * Move objects in memory to the right into some uninitialized memory, where * the region overlaps. Then call create() for each hole in reverse order. * * This doesn't just use std::move_backward because move_backward only works * if all the memory is initialized to type T already. * * The create function should return a reference type, to avoid * extra copies and moves for non-trivial types. */ template <class T, class Create> typename std::enable_if<!std::is_trivially_copyable_v<T>>::type moveObjectsRightAndCreate( T* const first, T* const lastConstructed, T* const realLast, Create&& create) { … } // Specialization for trivially copyable types. The call to // std::move_backward here will just turn into a memmove. // This must only be used with trivially copyable types because some of the // memory may be uninitialized, and std::move_backward() won't work when it // can't memmove(). template <class T, class Create> typename std::enable_if<std::is_trivially_copyable_v<T>>::type moveObjectsRightAndCreate( T* const first, T* const lastConstructed, T* const realLast, Create&& create) { … } /* * Populate a region of memory using `op' to construct elements. If * anything throws, undo what we did. */ template <class T, class Function> void populateMemForward(T* mem, std::size_t n, Function const& op) { … } /* * Copies `fromSize` elements from `from' to `to', where `to' is only * initialized up to `toSize`, but has enough storage for `fromSize'. If * `toSize' > `fromSize', the extra elements are destructed. */ template <class Iterator1, class Iterator2> void partiallyUninitializedCopy( Iterator1 from, size_t fromSize, Iterator2 to, size_t toSize) { … } template <class SizeType, bool ShouldUseHeap, bool AlwaysUseHeap> struct IntegralSizePolicyBase { … }; template <class SizeType, bool ShouldUseHeap, bool AlwaysUseHeap> struct IntegralSizePolicy; IntegralSizePolicy<SizeType, true, AlwaysUseHeap>; IntegralSizePolicy<SizeType, false, AlwaysUseHeap>; /* * If you're just trying to use this class, ignore everything about * this next small_vector_base class thing. * * The purpose of this junk is to minimize sizeof(small_vector<>) * and allow specifying the template parameters in whatever order is * convenient for the user. There's a few extra steps here to try * to keep the error messages at least semi-reasonable. * * Apologies for all the black magic. */ template <class Value, std::size_t RequestedMaxInline, class InPolicy> struct small_vector_base { … }; inline void* unshiftPointer(void* p, size_t sizeBytes) { … } inline void* shiftPointer(void* p, size_t sizeBytes) { … } } // namespace detail ////////////////////////////////////////////////////////////////////// template <class Value, std::size_t RequestedMaxInline = 1, class Policy = void> class small_vector : public detail::small_vector_base<Value, RequestedMaxInline, Policy>:: type { … }; ////////////////////////////////////////////////////////////////////// // Basic guarantee only, or provides the nothrow guarantee iff T has a // nothrow move or copy constructor. template <class T, std::size_t MaxInline, class P> void swap(small_vector<T, MaxInline, P>& a, small_vector<T, MaxInline, P>& b) { … } template <class T, std::size_t MaxInline, class P, class U> void erase(small_vector<T, MaxInline, P>& v, U value) { … } template <class T, std::size_t MaxInline, class P, class Predicate> void erase_if(small_vector<T, MaxInline, P>& v, Predicate predicate) { … } ////////////////////////////////////////////////////////////////////// namespace detail { // Format support. IndexableTraits<small_vector<T, M, P>>; } // namespace detail } // namespace folly FOLLY_POP_WARNING #undef FOLLY_SV_PACK_ATTR #undef FOLLY_SV_PACK_PUSH #undef FOLLY_SV_PACK_POP namespace std { hash<folly::small_vector<T, M, P>>; } // namespace std
Codebase Browser
folly