From 76328b6ed4e32235858e312d34b7abaed994584b Mon Sep 17 00:00:00 2001 From: Benny Chen Date: Wed, 15 Nov 2017 14:03:27 -0800 Subject: [PATCH] allow small vector to be storage for sorted_vector_map Summary: this is to allow small_vector to be a storage option for sorted_vector_map. Reas on I want to do this is because in ads there are a lot of small maps where we wo uld have to allocate separately. Reviewed By: yfeldblum Differential Revision: D6318811 fbshipit-source-id: b145d1bef2cbbeb946995aa66b55aaadeb6c54f5 --- folly/small_vector.h | 4 ++ folly/sorted_vector_types.h | 72 +++++++++++++------------- folly/test/small_vector_test.cpp | 86 ++++++++++++++++++++++++++++++++ 3 files changed, 124 insertions(+), 38 deletions(-) diff --git a/folly/small_vector.h b/folly/small_vector.h index 7287585a..67f18108 100644 --- a/folly/small_vector.h +++ b/folly/small_vector.h @@ -413,6 +413,7 @@ class small_vector : public detail::small_vector_base< typedef value_type& reference; typedef value_type const& const_reference; typedef value_type* iterator; + typedef value_type* pointer; typedef value_type const* const_iterator; typedef std::ptrdiff_t difference_type; @@ -420,6 +421,9 @@ class small_vector : public detail::small_vector_base< typedef std::reverse_iterator const_reverse_iterator; small_vector() = default; + // Allocator is unused here. It is taken in for compatibility with std::vector + // interface, but it will be ignored. + small_vector(const std::allocator&) {} small_vector(small_vector const& o) { auto n = o.size(); diff --git a/folly/sorted_vector_types.h b/folly/sorted_vector_types.h index 2cff300f..432b9411 100644 --- a/folly/sorted_vector_types.h +++ b/folly/sorted_vector_types.h @@ -215,14 +215,12 @@ template < class T, class Compare = std::less, class Allocator = std::allocator, - class GrowthPolicy = void> + class GrowthPolicy = void, + class Container = std::vector> class sorted_vector_set - : boost::totally_ordered1< - sorted_vector_set - , detail::growth_policy_wrapper > -{ - typedef std::vector ContainerT; - + : boost::totally_ordered1< + sorted_vector_set, + detail::growth_policy_wrapper> { detail::growth_policy_wrapper& get_growth_policy() { return *this; } @@ -236,20 +234,20 @@ class sorted_vector_set typedef Compare key_compare; typedef Compare value_compare; - typedef typename ContainerT::pointer pointer; - typedef typename ContainerT::reference reference; - typedef typename ContainerT::const_reference const_reference; + typedef typename Container::pointer pointer; + typedef typename Container::reference reference; + typedef typename Container::const_reference const_reference; /* * XXX: Our normal iterator ought to also be a constant iterator * (cf. Defect Report 103 for std::set), but this is a bit more of a * pain. */ - typedef typename ContainerT::iterator iterator; - typedef typename ContainerT::const_iterator const_iterator; - typedef typename ContainerT::difference_type difference_type; - typedef typename ContainerT::size_type size_type; - typedef typename ContainerT::reverse_iterator reverse_iterator; - typedef typename ContainerT::const_reverse_iterator const_reverse_iterator; + typedef typename Container::iterator iterator; + typedef typename Container::const_iterator const_iterator; + typedef typename Container::difference_type difference_type; + typedef typename Container::size_type size_type; + typedef typename Container::reverse_iterator reverse_iterator; + typedef typename Container::const_reverse_iterator const_reverse_iterator; explicit sorted_vector_set(const Compare& comp = Compare(), const Allocator& alloc = Allocator()) @@ -284,10 +282,10 @@ class sorted_vector_set // those performed by the caller. (The iterator range constructor performs at // least one allocation). // - // Note that `sorted_vector_set(const ContainerT& container)` is not provided, + // Note that `sorted_vector_set(const Container& container)` is not provided, // since the purpose of this constructor is to avoid an unnecessary copy. explicit sorted_vector_set( - ContainerT&& container, + Container&& container, const Compare& comp = Compare()) : m_(comp, container.get_allocator()) { std::sort(container.begin(), container.end(), value_comp()); @@ -478,7 +476,7 @@ class sorted_vector_set : Compare(c) , cont_(alloc) {} - ContainerT cont_; + Container cont_; } m_; template @@ -525,14 +523,12 @@ template < class Value, class Compare = std::less, class Allocator = std::allocator>, - class GrowthPolicy = void> + class GrowthPolicy = void, + class Container = std::vector, Allocator>> class sorted_vector_map - : boost::totally_ordered1< - sorted_vector_map - , detail::growth_policy_wrapper > -{ - typedef std::vector,Allocator> ContainerT; - + : boost::totally_ordered1< + sorted_vector_map, + detail::growth_policy_wrapper> { detail::growth_policy_wrapper& get_growth_policy() { return *this; } @@ -556,15 +552,15 @@ class sorted_vector_map explicit value_compare(const Compare& c) : Compare(c) {} }; - typedef typename ContainerT::pointer pointer; - typedef typename ContainerT::reference reference; - typedef typename ContainerT::const_reference const_reference; - typedef typename ContainerT::iterator iterator; - typedef typename ContainerT::const_iterator const_iterator; - typedef typename ContainerT::difference_type difference_type; - typedef typename ContainerT::size_type size_type; - typedef typename ContainerT::reverse_iterator reverse_iterator; - typedef typename ContainerT::const_reverse_iterator const_reverse_iterator; + typedef typename Container::pointer pointer; + typedef typename Container::reference reference; + typedef typename Container::const_reference const_reference; + typedef typename Container::iterator iterator; + typedef typename Container::const_iterator const_iterator; + typedef typename Container::difference_type difference_type; + typedef typename Container::size_type size_type; + typedef typename Container::reverse_iterator reverse_iterator; + typedef typename Container::const_reverse_iterator const_reverse_iterator; explicit sorted_vector_map(const Compare& comp = Compare(), const Allocator& alloc = Allocator()) @@ -597,10 +593,10 @@ class sorted_vector_map // those performed by the caller. (The iterator range constructor performs at // least one allocation). // - // Note that `sorted_vector_map(const ContainerT& container)` is not provided, + // Note that `sorted_vector_map(const Container& container)` is not provided, // since the purpose of this constructor is to avoid an unnecessary copy. explicit sorted_vector_map( - ContainerT&& container, + Container&& container, const Compare& comp = Compare()) : m_(value_compare(comp), container.get_allocator()) { std::sort(container.begin(), container.end(), value_comp()); @@ -806,7 +802,7 @@ class sorted_vector_map : value_compare(c) , cont_(alloc) {} - ContainerT cont_; + Container cont_; } m_; template diff --git a/folly/test/small_vector_test.cpp b/folly/test/small_vector_test.cpp index 618af54e..d01b60fa 100644 --- a/folly/test/small_vector_test.cpp +++ b/folly/test/small_vector_test.cpp @@ -15,6 +15,7 @@ */ #include +#include #include #include @@ -64,6 +65,43 @@ static_assert(!FOLLY_IS_TRIVIALLY_COPYABLE(std::unique_ptr), namespace { +template +using small_sorted_vector_map = folly::sorted_vector_map< + Key, + Value, + std::less, + std::allocator>, + void, + folly::small_vector, N>>; + +template +using noheap_sorted_vector_map = folly::sorted_vector_map< + Key, + Value, + std::less, + std::allocator>, + void, + folly::small_vector< + std::pair, + N, + folly::small_vector_policy::NoHeap>>; + +template +using small_sorted_vector_set = folly::sorted_vector_set< + T, + std::less, + std::allocator, + void, + folly::small_vector>; + +template +using noheap_sorted_vector_set = folly::sorted_vector_set< + T, + std::less, + std::allocator, + void, + folly::small_vector>; + struct NontrivialType { static int ctored; explicit NontrivialType() : a(0) {} @@ -996,3 +1034,51 @@ TEST(small_vector, CLVPushBackEfficiency) { EXPECT_EQ(test.size() - 1, counts.moveCount); EXPECT_LT(test.size(), test.capacity()); } + +TEST(small_vector, StorageForSortedVectorMap) { + small_sorted_vector_map test; + test.insert(std::make_pair(10, 10)); + EXPECT_EQ(test.size(), 1); + test.insert(std::make_pair(10, 10)); + EXPECT_EQ(test.size(), 1); + test.insert(std::make_pair(20, 10)); + EXPECT_EQ(test.size(), 2); + test.insert(std::make_pair(30, 10)); + EXPECT_EQ(test.size(), 3); +} + +TEST(small_vector, NoHeapStorageForSortedVectorMap) { + noheap_sorted_vector_map test; + test.insert(std::make_pair(10, 10)); + EXPECT_EQ(test.size(), 1); + test.insert(std::make_pair(10, 10)); + EXPECT_EQ(test.size(), 1); + test.insert(std::make_pair(20, 10)); + EXPECT_EQ(test.size(), 2); + EXPECT_THROW(test.insert(std::make_pair(30, 10)), std::length_error); + EXPECT_EQ(test.size(), 2); +} + +TEST(small_vector, StorageForSortedVectorSet) { + small_sorted_vector_set test; + test.insert(10); + EXPECT_EQ(test.size(), 1); + test.insert(10); + EXPECT_EQ(test.size(), 1); + test.insert(20); + EXPECT_EQ(test.size(), 2); + test.insert(30); + EXPECT_EQ(test.size(), 3); +} + +TEST(small_vector, NoHeapStorageForSortedVectorSet) { + noheap_sorted_vector_set test; + test.insert(10); + EXPECT_EQ(test.size(), 1); + test.insert(10); + EXPECT_EQ(test.size(), 1); + test.insert(20); + EXPECT_EQ(test.size(), 2); + EXPECT_THROW(test.insert(30), std::length_error); + EXPECT_EQ(test.size(), 2); +} -- 2.34.1