Merge pull request #16701 from vespa-engine/havardpe/small-vector-convenience

added some extra convenience, mostly related to construction

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