diff options
author | Arne H Juul <arnej27959@users.noreply.github.com> | 2021-02-27 22:06:44 +0100 |
---|---|---|
committer | GitHub <noreply@github.com> | 2021-02-27 22:06:44 +0100 |
commit | 0d3fe702a96f46b3a834bd77632049d32c2f86a9 (patch) | |
tree | 35b6aba2d716b7d0be53300a838956650e99e9c8 /vespalib | |
parent | a37e1b51351a92b084bbedf5c5225a6d01fc4a44 (diff) | |
parent | d50b2b9689469fe5f6d0d1e6f916e40e3ad3f670 (diff) |
Merge pull request #16701 from vespa-engine/havardpe/small-vector-convenience
added some extra convenience, mostly related to construction
Diffstat (limited to 'vespalib')
-rw-r--r-- | vespalib/src/tests/small_vector/small_vector_test.cpp | 82 | ||||
-rw-r--r-- | vespalib/src/vespa/vespalib/util/small_vector.h | 58 |
2 files changed, 137 insertions, 3 deletions
diff --git a/vespalib/src/tests/small_vector/small_vector_test.cpp b/vespalib/src/tests/small_vector/small_vector_test.cpp index 58779237fd4..808571acef6 100644 --- a/vespalib/src/tests/small_vector/small_vector_test.cpp +++ b/vespalib/src/tests/small_vector/small_vector_test.cpp @@ -2,6 +2,8 @@ #include <vespa/vespalib/util/small_vector.h> #include <vespa/vespalib/gtest/gtest.h> +#include <vector> +#include <map> using namespace vespalib; @@ -25,6 +27,18 @@ void verify(const SmallVector<T,N> &vec, std::vector<uint32_t> expect, size_t ex EXPECT_EQ(pos, end); } +template <typename T, size_t N, size_t M> +void verify_eq(const SmallVector<T,N> &a, const SmallVector<T,M> &b) { + EXPECT_TRUE(a == b); + EXPECT_TRUE(b == a); +} + +template <typename T, size_t N, size_t M> +void verify_not_eq(const SmallVector<T,N> &a, const SmallVector<T,M> &b) { + EXPECT_FALSE(a == b); + EXPECT_FALSE(b == a); +} + TEST(SmallVectorTest, basic_usage) { SmallVector<uint32_t,4> vec; EXPECT_EQ(sizeof(vec), 32); @@ -161,4 +175,72 @@ TEST(SmallVectorTest, create_with_unique_pointers) { EXPECT_TRUE(vec2[2].get() == nullptr); } +TEST(SmallVectorTest, create_with_initializer_list) { + SmallVector<uint32_t,4> vec1({1, 2}); + SmallVector<uint32_t,4> vec2({3, 4, 5, 6, 7, 8}); + verify(vec1, {1, 2}); + verify(vec2, {3, 4, 5, 6, 7, 8}); +} + +TEST(SmallVectorTest, create_with_pointer_range) { + SmallVector<uint32_t,4> vec1({1, 2}); + SmallVector<uint32_t,4> vec2({3, 4, 5, 6, 7, 8}); + SmallVector<uint32_t,4> vec3(&vec1[0], &vec1[0] + vec1.size()); + SmallVector<uint32_t,4> vec4(&vec2[0], &vec2[0] + vec2.size()); + verify(vec3, {1, 2}); + verify(vec4, {3, 4, 5, 6, 7, 8}); +} + +TEST(SmallVectorTest, create_with_random_access_iterator) { + std::vector<uint32_t> vec1({1, 2}); + std::vector<uint32_t> vec2({3, 4, 5, 6, 7, 8}); + SmallVector<uint32_t,4> vec3(vec1.begin(), vec1.end()); + SmallVector<uint32_t,4> vec4(vec2.begin(), vec2.end()); + verify(vec3, {1, 2}); + verify(vec4, {3, 4, 5, 6, 7, 8}); +} + +TEST(SmallVectorTest, create_with_akward_input_iterator_and_value_type) { + std::map<uint32_t,uint32_t> map; + map[1] = 2; + map[3] = 4; + map[5] = 6; + SmallVector<std::pair<const uint32_t, uint32_t>,2> vec(map.begin(), map.end()); + ASSERT_EQ(vec.size(), 3); + EXPECT_EQ(vec[0].first, 1); + EXPECT_EQ(vec[0].second, 2); + EXPECT_EQ(vec[1].first, 3); + EXPECT_EQ(vec[1].second, 4); + EXPECT_EQ(vec[2].first, 5); + EXPECT_EQ(vec[2].second, 6); +} + +TEST(SmallVectorTest, auto_select_N) { + SmallVector<uint32_t> vec1; + SmallVector<uint64_t> vec2; + SmallVector<MyStruct> vec3; + EXPECT_EQ(sizeof(vec1), 64); + EXPECT_EQ(sizeof(vec2), 64); + EXPECT_EQ(sizeof(vec3), 64); + EXPECT_EQ(vec1.capacity(), 12); + EXPECT_EQ(vec2.capacity(), 6); + EXPECT_EQ(vec3.capacity(), 4); +} + +struct EqOnly { + int value; + bool operator==(const EqOnly &rhs) const { return (value == rhs.value); } +}; + +TEST(SmallVectorTest, equal_operator) { + verify_eq(SmallVector<int,2>(), SmallVector<int,8>()); + verify_eq(SmallVector<int,2>({1,2,3}), SmallVector<int,8>({1,2,3})); + verify_eq(SmallVector<EqOnly>({EqOnly{1},EqOnly{2},EqOnly{3}}), + SmallVector<EqOnly>({EqOnly{1},EqOnly{2},EqOnly{3}})); + verify_not_eq(SmallVector<EqOnly>({EqOnly{1},EqOnly{2},EqOnly{3}}), + SmallVector<EqOnly>({EqOnly{1},EqOnly{2}})); + verify_not_eq(SmallVector<EqOnly>({EqOnly{1},EqOnly{2},EqOnly{3}}), + SmallVector<EqOnly>({EqOnly{1},EqOnly{5},EqOnly{3}})); +} + GTEST_MAIN_RUN_ALL_TESTS() diff --git a/vespalib/src/vespa/vespalib/util/small_vector.h b/vespalib/src/vespa/vespalib/util/small_vector.h index a0e2c621124..21a21fc2cbb 100644 --- a/vespalib/src/vespa/vespalib/util/small_vector.h +++ b/vespalib/src/vespa/vespalib/util/small_vector.h @@ -8,12 +8,24 @@ #include <cstdint> #include <cassert> #include <memory> +#include <iterator> namespace vespalib { namespace small_vector { -template<typename T, typename... Args> +template <typename T> +constexpr size_t select_N() { + if constexpr (sizeof(T) <= 16) { + return (48 / sizeof(T)); + } else { + static_assert(sizeof(T) <= 16, + "auto-selecting N is only supported for small objects (16 bytes or less)"); + return 1; + } +} + +template <typename T, typename... Args> void create_at(T *ptr, Args &&...args) { // https://en.cppreference.com/w/cpp/memory/construct_at ::new (const_cast<void*>(static_cast<const volatile void*>(ptr))) T(std::forward<Args>(args)...); @@ -22,7 +34,8 @@ void create_at(T *ptr, Args &&...args) { template <typename T> void move_objects(T *dst, T *src, uint32_t n) { if constexpr (std::is_trivially_copyable_v<T>) { - memcpy(dst, src, n * sizeof(T)); + // need to cast dst to void to avoid compiler warning caused by some trivially copyable objects not being copy assignable. + memcpy(static_cast<void *>(dst), src, n * sizeof(T)); } else { for (size_t i = 0; i < n; ++i) { create_at(dst + i, std::move(src[i])); @@ -72,7 +85,7 @@ std::pair<T*,size_t> alloc_objects(size_t wanted) { * inside the object itself. Intended use is to contain lists of * simple objects/values that are small in both size and number. **/ -template <typename T, size_t N> +template <typename T, size_t N = small_vector::select_N<T>()> class SmallVector { private: @@ -93,6 +106,19 @@ private: free(old_data); } } + template <typename InputIt> + void init(InputIt first, InputIt last, std::random_access_iterator_tag) { + reserve(last - first); + while (first != last) { + small_vector::create_at((_data + _size++), *first++); + } + } + template <typename InputIt> + void init(InputIt first, InputIt last, std::input_iterator_tag) { + while (first != last) { + emplace_back(*first++); + } + } public: constexpr SmallVector() noexcept : _data(local()), _size(0), _capacity(N) { static_assert(N > 0); @@ -107,6 +133,17 @@ public: small_vector::create_objects(_data, n, obj); _size = n; } + SmallVector(std::initializer_list<T> list) : SmallVector() { + reserve(list.size()); + for (const T &value: list) { + small_vector::create_at((_data + _size++), value); + } + } + template <typename InputIt, std::enable_if_t<std::is_base_of_v<std::input_iterator_tag, typename std::iterator_traits<InputIt>::iterator_category>, bool> = true> + SmallVector(InputIt first, InputIt last) : SmallVector() + { + init(first, last, typename std::iterator_traits<InputIt>::iterator_category()); + } SmallVector(SmallVector &&rhs) : SmallVector() { reserve(rhs._size); small_vector::move_objects(_data, rhs._data, rhs._size); @@ -171,4 +208,19 @@ public: } }; +template <typename T, size_t N, size_t M> +bool operator==(const SmallVector<T,N> &a, + const SmallVector<T,M> &b) +{ + if (a.size() != b.size()) { + return false; + } + for (size_t i = 0; i < a.size(); ++i) { + if (!(a[i] == b[i])) { + return false; + } + } + return true; +} + } // namespace |