https://github.com/ro-i updated https://github.com/llvm/llvm-project/pull/176163
>From a68c43a28c09a53a715fbff8c04dca8e72fc6902 Mon Sep 17 00:00:00 2001 From: Robert Imschweiler <[email protected]> Date: Thu, 15 Jan 2026 04:46:16 -0600 Subject: [PATCH 1/3] [libomp] Add kmp_vector (ADT 2/2) See rationale in the commit adding kmp_str_ref. This commit introduces kmp_vector, a class intended primarily for small vectors. It currently only includes methods I need at the moment, but it's easily extensible. --- openmp/runtime/src/kmp_adt.h | 182 ++++++ openmp/runtime/unittests/ADT/CMakeLists.txt | 1 + openmp/runtime/unittests/ADT/TestVector.cpp | 580 ++++++++++++++++++++ 3 files changed, 763 insertions(+) create mode 100644 openmp/runtime/unittests/ADT/TestVector.cpp diff --git a/openmp/runtime/src/kmp_adt.h b/openmp/runtime/src/kmp_adt.h index c546e13412322..8e1a133cb235e 100644 --- a/openmp/runtime/src/kmp_adt.h +++ b/openmp/runtime/src/kmp_adt.h @@ -26,6 +26,7 @@ #include <cstring> #include <functional> #include <string_view> +#include <utility> #include "kmp.h" @@ -154,4 +155,185 @@ class kmp_str_ref final { const char *end() const { return sv.data() + length(); } }; +/// kmp_vector is a vector class for managing small vectors. +/// inline_threshold: Number of elements in the inline array. If exceeded, the +/// vector will grow dynamically. +template <typename T, size_t inline_threshold = 8> class kmp_vector final { + static_assert(std::is_copy_constructible_v<T>, + "T must be copy constructible"); + static_assert(std::is_destructible_v<T>, "T must be destructible"); + + T inline_data[inline_threshold]; + T *data = inline_data; + size_t count = 0; + size_t capacity = inline_threshold; + + void copy_data(T *dst, const T *src, size_t num_elements) { + if constexpr (std::is_trivially_copyable_v<T>) { + memcpy(dst, src, num_elements * sizeof(T)); + } else { + for (size_t i = 0; i < num_elements; i++) + new (&dst[i]) T(src[i]); // copy-construct to memory + } + } + + void grow() { + size_t new_capacity = capacity + (capacity / 2) + 1; + resize(new_capacity); + } + + void init(size_t new_capacity, const T *init_data, size_t new_count) { + assert(new_capacity >= new_count); + if (new_capacity > inline_threshold) + resize(new_capacity); + if (init_data) + copy_data(data, init_data, new_count); + count = new_count; + } + + void move_from(kmp_vector &&other) { + if (other.data == other.inline_data) { + // Cannot move inline data, must copy. + init(other.capacity, other.data, other.count); + } else { + // Steal dynamic data. + data = other.data; + count = other.count; + capacity = other.capacity; + } + other.reset(false); + } + + void reset(bool free_data) { + if (free_data && data != inline_data) { + clear(); + KMP_INTERNAL_FREE(data); + } + data = inline_data; + count = 0; + capacity = inline_threshold; + } + + // resize only changes the capacity, not the size (i.e., the number of + // actually used elements) + void resize(size_t new_capacity) { + // Currently only supports growing the capacity. (Consequently, doesn't need + // to worry about going from a dynamic array back to an inline array.) + assert(new_capacity > capacity && "resize() only supports growing"); + capacity = new_capacity; + T *old_data = data != inline_data ? data : nullptr; + data = + static_cast<T *>(KMP_INTERNAL_REALLOC(old_data, capacity * sizeof(T))); + assert(data); + // Copy the data to the new array if we didn't use a dynamic array before. + if (!old_data) + copy_data(data, inline_data, count); + } + +public: + ~kmp_vector() { reset(true); } + + explicit kmp_vector(size_t capacity = 0) { init(capacity, nullptr, 0); } + + kmp_vector(size_t capacity, const T *init_data, size_t count) { + init(capacity, init_data, count); + } + + kmp_vector(const kmp_vector &other) { + init(other.capacity, other.data, other.count); + } + + kmp_vector(kmp_vector &&other) noexcept { move_from(std::move(other)); } + + kmp_vector &operator=(const kmp_vector &other) { + if (this != &other) { + reset(true); + init(other.capacity, other.data, other.count); + } + return *this; + } + + kmp_vector &operator=(kmp_vector &&other) noexcept { + if (this != &other) { + reset(true); + move_from(std::move(other)); + } + return *this; + } + + // Destroy all elements in the vector. Doesn't free the memory. + void clear() { + if constexpr (!std::is_trivially_destructible_v<T>) { + for (size_t i = 0; i < count; i++) + data[i].~T(); + } + count = 0; + } + + // Check if the vector contains the given value. + // If a comparator is provided, it will be used to compare the values. + // Otherwise, the equality operator will be used. + bool contains(const T &value, + bool (*comp)(const T &, const T &) = nullptr) const { + for (size_t i = 0; i < count; i++) { + if (comp ? comp(data[i], value) : data[i] == value) + return true; + } + return false; + } + + bool empty() const { return !count; } + + // Check if the two vectors are equal with set semantics. + // Current implementation is naive O(n^2) and not optimized for performance. + // Handles duplicates correctly. + bool is_set_equal(const kmp_vector &other, + bool (*comp)(const T &, const T &) = nullptr) const { + for (const T &val : *this) { + if (!other.contains(val, comp)) + return false; + } + for (const T &val : other) { + if (!contains(val, comp)) + return false; + } + return true; + } + + // Add a new element to the end of the vector. + void push_back(const T &value) { + if (count == capacity) + grow(); + if constexpr (std::is_trivially_copyable_v<T>) { + data[count++] = value; + } else { + new (&data[count++]) T(value); + } + } + + // Reserve space for the given number of elements. + // (Note: does not shrink the vector.) + void reserve(size_t new_capacity) { + if (new_capacity > capacity) + resize(new_capacity); + } + + size_t size() const { return count; } + + T &operator[](size_t index) { + assert(index < count && "Index out of bounds"); + return data[index]; + } + const T &operator[](size_t index) const { + assert(index < count && "Index out of bounds"); + return data[index]; + } + + // Iterator support (raw pointers work as iterators for contiguous storage) + T *begin() { return data; } + T *end() { return data + count; } + const T *begin() const { return data; } + const T *end() const { return data + count; } +}; + #endif // __KMP_ADT_H__ diff --git a/openmp/runtime/unittests/ADT/CMakeLists.txt b/openmp/runtime/unittests/ADT/CMakeLists.txt index a29e70afe6df6..ea3a32271b8fc 100644 --- a/openmp/runtime/unittests/ADT/CMakeLists.txt +++ b/openmp/runtime/unittests/ADT/CMakeLists.txt @@ -1,4 +1,5 @@ add_openmp_unittest(ADTTests TestStringRef.cpp + TestVector.cpp ) diff --git a/openmp/runtime/unittests/ADT/TestVector.cpp b/openmp/runtime/unittests/ADT/TestVector.cpp new file mode 100644 index 0000000000000..3b2d5ec0e040a --- /dev/null +++ b/openmp/runtime/unittests/ADT/TestVector.cpp @@ -0,0 +1,580 @@ +//===- TestVector.cpp - Tests for kmp_vector class -----------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "kmp_adt.h" +#include "gtest/gtest.h" + +namespace { + +//===----------------------------------------------------------------------===// +// Construction +//===----------------------------------------------------------------------===// + +TEST(kmp_vector_test, DefaultConstruction) { + kmp_vector<int> v; + EXPECT_EQ(v.size(), 0u); + EXPECT_TRUE(v.empty()); +} + +TEST(kmp_vector_test, ConstructWithCapacity) { + kmp_vector<int> v(10); + EXPECT_EQ(v.size(), 0u); + EXPECT_TRUE(v.empty()); +} + +TEST(kmp_vector_test, ConstructWithData) { + int data[] = {1, 2, 3, 4, 5}; + kmp_vector<int> v(5, data, 5); + + EXPECT_EQ(v.size(), 5u); + EXPECT_EQ(v[0], 1); + EXPECT_EQ(v[1], 2); + EXPECT_EQ(v[2], 3); + EXPECT_EQ(v[3], 4); + EXPECT_EQ(v[4], 5); +} + +TEST(kmp_vector_test, ConstructWithCapacityLargerThanSize) { + int data[] = {1, 2, 3}; + kmp_vector<int> v(10, data, 3); + + EXPECT_EQ(v.size(), 3u); + EXPECT_EQ(v[0], 1); + EXPECT_EQ(v[1], 2); + EXPECT_EQ(v[2], 3); +} + +//===----------------------------------------------------------------------===// +// Copy Semantics +//===----------------------------------------------------------------------===// + +TEST(kmp_vector_test, CopyConstruction) { + int data[] = {1, 2, 3}; + kmp_vector<int> v1(3, data, 3); + kmp_vector<int> v2(v1); + + EXPECT_EQ(v2.size(), 3u); + EXPECT_EQ(v2[0], 1); + EXPECT_EQ(v2[1], 2); + EXPECT_EQ(v2[2], 3); + + // Modify v1, v2 should be unchanged + v1[0] = 100; + EXPECT_EQ(v2[0], 1); +} + +TEST(kmp_vector_test, CopyAssignment) { + int data1[] = {1, 2, 3}; + int data2[] = {4, 5}; + kmp_vector<int> v1(3, data1, 3); + kmp_vector<int> v2(2, data2, 2); + + v2 = v1; + + EXPECT_EQ(v2.size(), 3u); + EXPECT_EQ(v2[0], 1); + EXPECT_EQ(v2[1], 2); + EXPECT_EQ(v2[2], 3); +} + +TEST(kmp_vector_test, SelfCopyAssignment) { + int data[] = {1, 2, 3}; + kmp_vector<int> v(3, data, 3); + + kmp_vector<int> &v_ref = v; + v = v_ref; // Avoid self-assignment warning + + EXPECT_EQ(v.size(), 3u); + EXPECT_EQ(v[0], 1); +} + +//===----------------------------------------------------------------------===// +// Move Semantics +//===----------------------------------------------------------------------===// + +TEST(kmp_vector_test, MoveConstruction) { + int data[] = {1, 2, 3}; + kmp_vector<int> v1(3, data, 3); + kmp_vector<int> v2(std::move(v1)); + + EXPECT_EQ(v2.size(), 3u); + EXPECT_EQ(v2[0], 1); + EXPECT_EQ(v2[1], 2); + EXPECT_EQ(v2[2], 3); + + // v1 should be empty after move + EXPECT_EQ(v1.size(), 0u); +} + +TEST(kmp_vector_test, MoveAssignment) { + int data1[] = {1, 2, 3}; + int data2[] = {4, 5}; + kmp_vector<int> v1(3, data1, 3); + kmp_vector<int> v2(2, data2, 2); + + v2 = std::move(v1); + + EXPECT_EQ(v2.size(), 3u); + EXPECT_EQ(v2[0], 1); + EXPECT_EQ(v1.size(), 0u); +} + +TEST(kmp_vector_test, SelfMoveAssignment) { + int data[] = {1, 2, 3}; + kmp_vector<int> v(3, data, 3); + + kmp_vector<int> &v_ref = v; + v = std::move(v_ref); // Avoid self-move warning + + // Self-move should leave object in valid state + EXPECT_EQ(v.size(), 3u); + EXPECT_EQ(v[0], 1); +} + +//===----------------------------------------------------------------------===// +// push_back +//===----------------------------------------------------------------------===// + +TEST(kmp_vector_test, PushBackToEmpty) { + kmp_vector<int> v; + + v.push_back(42); + + EXPECT_EQ(v.size(), 1u); + EXPECT_EQ(v[0], 42); +} + +TEST(kmp_vector_test, PushBackMultiple) { + kmp_vector<int> v; + + v.push_back(1); + v.push_back(2); + v.push_back(3); + v.push_back(4); + v.push_back(5); + + EXPECT_EQ(v.size(), 5u); + EXPECT_EQ(v[0], 1); + EXPECT_EQ(v[1], 2); + EXPECT_EQ(v[2], 3); + EXPECT_EQ(v[3], 4); + EXPECT_EQ(v[4], 5); +} + +TEST(kmp_vector_test, PushBackGrowth) { + kmp_vector<int> v; + + // Push many elements to trigger multiple resizes + for (int i = 0; i < 100; ++i) { + v.push_back(i); + } + + EXPECT_EQ(v.size(), 100u); + for (int i = 0; i < 100; ++i) { + EXPECT_EQ(v[i], i); + } +} + +//===----------------------------------------------------------------------===// +// clear +//===----------------------------------------------------------------------===// + +TEST(kmp_vector_test, Clear) { + int data[] = {1, 2, 3}; + kmp_vector<int> v(3, data, 3); + + EXPECT_EQ(v.size(), 3u); + + v.clear(); + + EXPECT_EQ(v.size(), 0u); + EXPECT_TRUE(v.empty()); +} + +TEST(kmp_vector_test, ClearEmpty) { + kmp_vector<int> v; + + v.clear(); + + EXPECT_EQ(v.size(), 0u); + EXPECT_TRUE(v.empty()); +} + +TEST(kmp_vector_test, PushBackAfterClear) { + int data[] = {1, 2, 3}; + kmp_vector<int> v(3, data, 3); + + v.clear(); + v.push_back(42); + + EXPECT_EQ(v.size(), 1u); + EXPECT_EQ(v[0], 42); +} + +//===----------------------------------------------------------------------===// +// empty +//===----------------------------------------------------------------------===// + +TEST(kmp_vector_test, EmptyOnDefault) { + kmp_vector<int> v; + EXPECT_TRUE(v.empty()); +} + +TEST(kmp_vector_test, NotEmptyAfterPush) { + kmp_vector<int> v; + v.push_back(1); + EXPECT_FALSE(v.empty()); +} + +TEST(kmp_vector_test, EmptyAfterClear) { + kmp_vector<int> v; + v.push_back(1); + v.clear(); + EXPECT_TRUE(v.empty()); +} + +//===----------------------------------------------------------------------===// +// contains +//===----------------------------------------------------------------------===// + +TEST(kmp_vector_test, ContainsFound) { + int data[] = {1, 2, 3, 4, 5}; + kmp_vector<int> v(5, data, 5); + + EXPECT_TRUE(v.contains(1)); + EXPECT_TRUE(v.contains(3)); + EXPECT_TRUE(v.contains(5)); +} + +TEST(kmp_vector_test, ContainsNotFound) { + int data[] = {1, 2, 3, 4, 5}; + kmp_vector<int> v(5, data, 5); + + EXPECT_FALSE(v.contains(0)); + EXPECT_FALSE(v.contains(6)); + EXPECT_FALSE(v.contains(-1)); +} + +TEST(kmp_vector_test, ContainsEmpty) { + kmp_vector<int> v; + + EXPECT_FALSE(v.contains(0)); + EXPECT_FALSE(v.contains(1)); +} + +//===----------------------------------------------------------------------===// +// is_set_equal +//===----------------------------------------------------------------------===// + +TEST(kmp_vector_test, IsSetEqualSameOrder) { + int data[] = {1, 2, 3}; + kmp_vector<int> v1(3, data, 3); + kmp_vector<int> v2(3, data, 3); + + EXPECT_TRUE(v1.is_set_equal(v2)); + EXPECT_TRUE(v2.is_set_equal(v1)); +} + +TEST(kmp_vector_test, IsSetEqualDifferentOrder) { + int data1[] = {1, 2, 3}; + int data2[] = {3, 1, 2}; + kmp_vector<int> v1(3, data1, 3); + kmp_vector<int> v2(3, data2, 3); + + EXPECT_TRUE(v1.is_set_equal(v2)); + EXPECT_TRUE(v2.is_set_equal(v1)); +} + +TEST(kmp_vector_test, IsSetEqualDifferentSize) { + int data1[] = {1, 2, 3}; + int data2[] = {1, 2}; + kmp_vector<int> v1(3, data1, 3); + kmp_vector<int> v2(2, data2, 2); + + EXPECT_FALSE(v1.is_set_equal(v2)); + EXPECT_FALSE(v2.is_set_equal(v1)); +} + +TEST(kmp_vector_test, IsSetEqualDifferentElements) { + int data1[] = {1, 2, 3}; + int data2[] = {1, 2, 4}; + kmp_vector<int> v1(3, data1, 3); + kmp_vector<int> v2(3, data2, 3); + + EXPECT_FALSE(v1.is_set_equal(v2)); +} + +TEST(kmp_vector_test, IsSetEqualEmpty) { + kmp_vector<int> v1; + kmp_vector<int> v2; + + EXPECT_TRUE(v1.is_set_equal(v2)); +} + +TEST(kmp_vector_test, IsSetEqualWithDuplicates) { + int data1[] = {1, 1}; + int data2[] = {1, 2}; + kmp_vector<int> v1(2, data1, 2); + kmp_vector<int> v2(2, data2, 2); + + EXPECT_FALSE(v1.is_set_equal(v2)); + EXPECT_FALSE(v2.is_set_equal(v1)); +} + +TEST(kmp_vector_test, IsSetEqualWithDuplicatesSame) { + int data1[] = {1, 1}; + int data2[] = {1}; + kmp_vector<int> v1(2, data1, 2); + kmp_vector<int> v2(1, data2, 1); + + EXPECT_TRUE(v1.is_set_equal(v2)); + EXPECT_TRUE(v2.is_set_equal(v1)); +} + +//===----------------------------------------------------------------------===// +// contains with Comparator +//===----------------------------------------------------------------------===// + +TEST(kmp_vector_test, ContainsWithComparator) { + int data[] = {10, 20, 30}; + kmp_vector<int> v(3, data, 3); + + // Compare by tens digit + auto same_tens = [](const int &a, const int &b) { + return (a / 10) == (b / 10); + }; + + EXPECT_TRUE(v.contains(15, same_tens)); // 15/10 == 1, matches 10/10 == 1 + EXPECT_TRUE(v.contains(25, same_tens)); // 25/10 == 2, matches 20/10 == 2 + EXPECT_FALSE(v.contains(45, same_tens)); // 45/10 == 4, no match +} + +TEST(kmp_vector_test, ContainsPointerWithComparator) { + int a = 100, b = 200, c = 300; + int *data[] = {&a, &b, &c}; + kmp_vector<int *> v(3, data, 3); + + // Comparator that compares pointed-to values + auto deref_comp = [](int *const &pa, int *const &pb) { return *pa == *pb; }; + + int x = 200; + int *px = &x; + + // Without comparator: comparing pointers (different addresses) + EXPECT_FALSE(v.contains(px)); + + // With comparator: comparing values (200 == 200) + EXPECT_TRUE(v.contains(px, deref_comp)); +} + +//===----------------------------------------------------------------------===// +// is_set_equal with Comparator +//===----------------------------------------------------------------------===// + +TEST(kmp_vector_test, IsSetEqualWithComparator) { + int data1[] = {10, 20, 30}; + int data2[] = {35, 15, 25}; // Same tens digits as data1, different order + kmp_vector<int> v1(3, data1, 3); + kmp_vector<int> v2(3, data2, 3); + + auto same_tens = [](const int &a, const int &b) { + return (a / 10) == (b / 10); + }; + + // Without comparator: not equal + EXPECT_FALSE(v1.is_set_equal(v2)); + + // With comparator: equal (same tens digits) + EXPECT_TRUE(v1.is_set_equal(v2, same_tens)); +} + +TEST(kmp_vector_test, IsSetEqualPointerWithComparator) { + int a1 = 100, b1 = 200, c1 = 300; + int a2 = 100, b2 = 200, c2 = 300; + int *data1[] = {&a1, &b1, &c1}; + int *data2[] = {&c2, &a2, &b2}; // Same values, different order and addresses + kmp_vector<int *> v1(3, data1, 3); + kmp_vector<int *> v2(3, data2, 3); + + auto deref_comp = [](int *const &pa, int *const &pb) { return *pa == *pb; }; + + // Without comparator: not equal (different pointers) + EXPECT_FALSE(v1.is_set_equal(v2)); + + // With comparator: equal (same pointed-to values) + EXPECT_TRUE(v1.is_set_equal(v2, deref_comp)); +} + +//===----------------------------------------------------------------------===// +// Indexing +//===----------------------------------------------------------------------===// + +TEST(kmp_vector_test, IndexOperator) { + int data[] = {10, 20, 30}; + kmp_vector<int> v(3, data, 3); + + EXPECT_EQ(v[0], 10); + EXPECT_EQ(v[1], 20); + EXPECT_EQ(v[2], 30); +} + +TEST(kmp_vector_test, IndexOperatorModify) { + int data[] = {10, 20, 30}; + kmp_vector<int> v(3, data, 3); + + v[1] = 200; + + EXPECT_EQ(v[1], 200); +} + +TEST(kmp_vector_test, ConstIndexOperator) { + int data[] = {10, 20, 30}; + const kmp_vector<int> v(3, data, 3); + + EXPECT_EQ(v[0], 10); + EXPECT_EQ(v[1], 20); + EXPECT_EQ(v[2], 30); +} + +//===----------------------------------------------------------------------===// +// Iterators +//===----------------------------------------------------------------------===// + +TEST(kmp_vector_test, BeginEnd) { + int data[] = {1, 2, 3}; + kmp_vector<int> v(3, data, 3); + + int *begin = v.begin(); + int *end = v.end(); + + EXPECT_EQ(end - begin, 3); + EXPECT_EQ(*begin, 1); + EXPECT_EQ(*(end - 1), 3); +} + +TEST(kmp_vector_test, ConstBeginEnd) { + int data[] = {1, 2, 3}; + const kmp_vector<int> v(3, data, 3); + + const int *begin = v.begin(); + const int *end = v.end(); + + EXPECT_EQ(end - begin, 3); + EXPECT_EQ(*begin, 1); +} + +TEST(kmp_vector_test, RangeBasedFor) { + int data[] = {1, 2, 3, 4, 5}; + kmp_vector<int> v(5, data, 5); + + int sum = 0; + for (int x : v) { + sum += x; + } + + EXPECT_EQ(sum, 15); +} + +TEST(kmp_vector_test, RangeBasedForModify) { + int data[] = {1, 2, 3}; + kmp_vector<int> v(3, data, 3); + + for (int &x : v) { + x *= 2; + } + + EXPECT_EQ(v[0], 2); + EXPECT_EQ(v[1], 4); + EXPECT_EQ(v[2], 6); +} + +TEST(kmp_vector_test, RangeBasedForEmpty) { + kmp_vector<int> v; + + int count = 0; + for (int x : v) { + (void)x; + count++; + } + + EXPECT_EQ(count, 0); +} + +//===----------------------------------------------------------------------===// +// Edge Cases +//===----------------------------------------------------------------------===// + +TEST(kmp_vector_test, EmptyVector) { + kmp_vector<int> v; + + EXPECT_EQ(v.size(), 0u); + EXPECT_EQ(v.begin(), v.end()); + EXPECT_FALSE(v.contains(0)); +} + +TEST(kmp_vector_test, SingleElement) { + kmp_vector<int> v; + v.push_back(42); + + EXPECT_EQ(v.size(), 1u); + EXPECT_EQ(v[0], 42); + EXPECT_TRUE(v.contains(42)); + EXPECT_EQ(v.end() - v.begin(), 1); +} + +//===----------------------------------------------------------------------===// +// Different Types +//===----------------------------------------------------------------------===// + +TEST(kmp_vector_test, PointerType) { + int a = 1, b = 2, c = 3; + int *data[] = {&a, &b, &c}; + kmp_vector<int *> v(3, data, 3); + + EXPECT_EQ(v.size(), 3u); + EXPECT_EQ(*v[0], 1); + EXPECT_EQ(*v[1], 2); + EXPECT_EQ(*v[2], 3); +} + +TEST(kmp_vector_test, SizeTType) { + size_t data[] = {100, 200, 300}; + kmp_vector<size_t> v(3, data, 3); + + EXPECT_EQ(v[0], 100u); + EXPECT_EQ(v[1], 200u); + EXPECT_EQ(v[2], 300u); +} + +//===----------------------------------------------------------------------===// +// Reserve +//===----------------------------------------------------------------------===// + +TEST(kmp_vector_test, Reserve) { + kmp_vector<int> v; + v.reserve(100); + + EXPECT_EQ(v.size(), 0u); + + // Push one element to get a valid data pointer + v.push_back(0); + const int *data_ptr = v.begin(); + + // Should be able to push without reallocation + for (int i = 1; i < 100; ++i) { + v.push_back(i); + } + + EXPECT_EQ(v.size(), 100u); + EXPECT_EQ(v.begin(), data_ptr) << "Reallocation occurred despite reserve()"; + for (int i = 0; i < 100; ++i) { + EXPECT_EQ(v[i], i); + } +} + +} // namespace >From 211187faa301c5e5c00b85a9b0245d75b216e3c3 Mon Sep 17 00:00:00 2001 From: Robert Imschweiler <[email protected]> Date: Thu, 9 Apr 2026 08:26:52 -0500 Subject: [PATCH 2/3] add free_data parameter comment --- openmp/runtime/src/kmp_adt.h | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/openmp/runtime/src/kmp_adt.h b/openmp/runtime/src/kmp_adt.h index 8e1a133cb235e..fe4c30aa669ac 100644 --- a/openmp/runtime/src/kmp_adt.h +++ b/openmp/runtime/src/kmp_adt.h @@ -201,7 +201,7 @@ template <typename T, size_t inline_threshold = 8> class kmp_vector final { count = other.count; capacity = other.capacity; } - other.reset(false); + other.reset(/*free_data=*/false); } void reset(bool free_data) { @@ -231,7 +231,7 @@ template <typename T, size_t inline_threshold = 8> class kmp_vector final { } public: - ~kmp_vector() { reset(true); } + ~kmp_vector() { reset(/*free_data=*/true); } explicit kmp_vector(size_t capacity = 0) { init(capacity, nullptr, 0); } @@ -247,7 +247,7 @@ template <typename T, size_t inline_threshold = 8> class kmp_vector final { kmp_vector &operator=(const kmp_vector &other) { if (this != &other) { - reset(true); + reset(/*free_data=*/true); init(other.capacity, other.data, other.count); } return *this; @@ -255,7 +255,7 @@ template <typename T, size_t inline_threshold = 8> class kmp_vector final { kmp_vector &operator=(kmp_vector &&other) noexcept { if (this != &other) { - reset(true); + reset(/*free_data=*/true); move_from(std::move(other)); } return *this; >From e629ad7be290a455215e6a11a80b83a26b31fe98 Mon Sep 17 00:00:00 2001 From: Robert Imschweiler <[email protected]> Date: Tue, 2 Jun 2026 09:02:21 -0500 Subject: [PATCH 3/3] implement feedback --- openmp/runtime/src/kmp_adt.h | 49 ++-- openmp/runtime/unittests/ADT/TestVector.cpp | 246 ++++++++++---------- 2 files changed, 153 insertions(+), 142 deletions(-) diff --git a/openmp/runtime/src/kmp_adt.h b/openmp/runtime/src/kmp_adt.h index fe4c30aa669ac..ca53f6601c2b5 100644 --- a/openmp/runtime/src/kmp_adt.h +++ b/openmp/runtime/src/kmp_adt.h @@ -156,17 +156,17 @@ class kmp_str_ref final { }; /// kmp_vector is a vector class for managing small vectors. -/// inline_threshold: Number of elements in the inline array. If exceeded, the +/// INLINE_THRESHOLD: Number of elements in the inline array. If exceeded, the /// vector will grow dynamically. -template <typename T, size_t inline_threshold = 8> class kmp_vector final { +template <typename T, size_t INLINE_THRESHOLD = 8> class kmp_vector final { static_assert(std::is_copy_constructible_v<T>, "T must be copy constructible"); static_assert(std::is_destructible_v<T>, "T must be destructible"); - T inline_data[inline_threshold]; + T inline_data[INLINE_THRESHOLD]; T *data = inline_data; size_t count = 0; - size_t capacity = inline_threshold; + size_t capacity = INLINE_THRESHOLD; void copy_data(T *dst, const T *src, size_t num_elements) { if constexpr (std::is_trivially_copyable_v<T>) { @@ -177,21 +177,25 @@ template <typename T, size_t inline_threshold = 8> class kmp_vector final { } } + /// Grow by ~1.5x void grow() { size_t new_capacity = capacity + (capacity / 2) + 1; resize(new_capacity); } void init(size_t new_capacity, const T *init_data, size_t new_count) { - assert(new_capacity >= new_count); - if (new_capacity > inline_threshold) + assert(new_capacity >= new_count && + "more elements requested than capacity"); + if (new_capacity > INLINE_THRESHOLD) resize(new_capacity); if (init_data) copy_data(data, init_data, new_count); count = new_count; } + /// Move data from other vector to this vector (which must be emptied before) void move_from(kmp_vector &&other) { + assert(empty() && "must be empty before overwriting"); if (other.data == other.inline_data) { // Cannot move inline data, must copy. init(other.capacity, other.data, other.count); @@ -211,11 +215,11 @@ template <typename T, size_t inline_threshold = 8> class kmp_vector final { } data = inline_data; count = 0; - capacity = inline_threshold; + capacity = INLINE_THRESHOLD; } - // resize only changes the capacity, not the size (i.e., the number of - // actually used elements) + /// resize only changes the capacity, not the size (i.e., the number of + /// actually used elements) void resize(size_t new_capacity) { // Currently only supports growing the capacity. (Consequently, doesn't need // to worry about going from a dynamic array back to an inline array.) @@ -261,7 +265,7 @@ template <typename T, size_t inline_threshold = 8> class kmp_vector final { return *this; } - // Destroy all elements in the vector. Doesn't free the memory. + /// Destroy all elements in the vector. Doesn't free the memory. void clear() { if constexpr (!std::is_trivially_destructible_v<T>) { for (size_t i = 0; i < count; i++) @@ -270,9 +274,9 @@ template <typename T, size_t inline_threshold = 8> class kmp_vector final { count = 0; } - // Check if the vector contains the given value. - // If a comparator is provided, it will be used to compare the values. - // Otherwise, the equality operator will be used. + /// Check if the vector contains the given value. + /// If a comparator is provided, it will be used to compare the values. + /// Otherwise, the equality operator will be used. bool contains(const T &value, bool (*comp)(const T &, const T &) = nullptr) const { for (size_t i = 0; i < count; i++) { @@ -284,9 +288,9 @@ template <typename T, size_t inline_threshold = 8> class kmp_vector final { bool empty() const { return !count; } - // Check if the two vectors are equal with set semantics. - // Current implementation is naive O(n^2) and not optimized for performance. - // Handles duplicates correctly. + /// Check if the two vectors are equal with set semantics. + /// Current implementation is naive O(n^2) and not optimized for performance. + /// Handles duplicates correctly. bool is_set_equal(const kmp_vector &other, bool (*comp)(const T &, const T &) = nullptr) const { for (const T &val : *this) { @@ -300,19 +304,18 @@ template <typename T, size_t inline_threshold = 8> class kmp_vector final { return true; } - // Add a new element to the end of the vector. + /// Add a new element to the end of the vector. void push_back(const T &value) { if (count == capacity) grow(); - if constexpr (std::is_trivially_copyable_v<T>) { + if constexpr (std::is_trivially_copyable_v<T>) data[count++] = value; - } else { + else new (&data[count++]) T(value); - } } - // Reserve space for the given number of elements. - // (Note: does not shrink the vector.) + /// Reserve space for the given number of elements. + /// (Note: does not shrink the vector.) void reserve(size_t new_capacity) { if (new_capacity > capacity) resize(new_capacity); @@ -329,7 +332,7 @@ template <typename T, size_t inline_threshold = 8> class kmp_vector final { return data[index]; } - // Iterator support (raw pointers work as iterators for contiguous storage) + /// Iterator support (raw pointers work as iterators for contiguous storage) T *begin() { return data; } T *end() { return data + count; } const T *begin() const { return data; } diff --git a/openmp/runtime/unittests/ADT/TestVector.cpp b/openmp/runtime/unittests/ADT/TestVector.cpp index 3b2d5ec0e040a..7a58bea3abb2a 100644 --- a/openmp/runtime/unittests/ADT/TestVector.cpp +++ b/openmp/runtime/unittests/ADT/TestVector.cpp @@ -11,25 +11,39 @@ namespace { +/// Type-parameterized test fixture so each test runs against multiple +/// INLINE_THRESHOLD values, exercising both the inline and dynamic paths. +template <typename Config> class kmp_vector_test : public ::testing::Test {}; + +template <size_t N> struct InlineThreshold { + template <typename T> using Vec = kmp_vector<T, N>; + static constexpr size_t value = N; +}; + +using InlineThresholds = + ::testing::Types<InlineThreshold<0>, InlineThreshold<1>, InlineThreshold<8>, + InlineThreshold<16>>; +TYPED_TEST_SUITE(kmp_vector_test, InlineThresholds); + //===----------------------------------------------------------------------===// // Construction //===----------------------------------------------------------------------===// -TEST(kmp_vector_test, DefaultConstruction) { - kmp_vector<int> v; +TYPED_TEST(kmp_vector_test, DefaultConstruction) { + typename TypeParam::template Vec<int> v; EXPECT_EQ(v.size(), 0u); EXPECT_TRUE(v.empty()); } -TEST(kmp_vector_test, ConstructWithCapacity) { - kmp_vector<int> v(10); +TYPED_TEST(kmp_vector_test, ConstructWithCapacity) { + typename TypeParam::template Vec<int> v(10); EXPECT_EQ(v.size(), 0u); EXPECT_TRUE(v.empty()); } -TEST(kmp_vector_test, ConstructWithData) { +TYPED_TEST(kmp_vector_test, ConstructWithData) { int data[] = {1, 2, 3, 4, 5}; - kmp_vector<int> v(5, data, 5); + typename TypeParam::template Vec<int> v(5, data, 5); EXPECT_EQ(v.size(), 5u); EXPECT_EQ(v[0], 1); @@ -39,9 +53,9 @@ TEST(kmp_vector_test, ConstructWithData) { EXPECT_EQ(v[4], 5); } -TEST(kmp_vector_test, ConstructWithCapacityLargerThanSize) { +TYPED_TEST(kmp_vector_test, ConstructWithCapacityLargerThanSize) { int data[] = {1, 2, 3}; - kmp_vector<int> v(10, data, 3); + typename TypeParam::template Vec<int> v(10, data, 3); EXPECT_EQ(v.size(), 3u); EXPECT_EQ(v[0], 1); @@ -53,10 +67,10 @@ TEST(kmp_vector_test, ConstructWithCapacityLargerThanSize) { // Copy Semantics //===----------------------------------------------------------------------===// -TEST(kmp_vector_test, CopyConstruction) { +TYPED_TEST(kmp_vector_test, CopyConstruction) { int data[] = {1, 2, 3}; - kmp_vector<int> v1(3, data, 3); - kmp_vector<int> v2(v1); + typename TypeParam::template Vec<int> v1(3, data, 3); + typename TypeParam::template Vec<int> v2(v1); EXPECT_EQ(v2.size(), 3u); EXPECT_EQ(v2[0], 1); @@ -68,11 +82,11 @@ TEST(kmp_vector_test, CopyConstruction) { EXPECT_EQ(v2[0], 1); } -TEST(kmp_vector_test, CopyAssignment) { +TYPED_TEST(kmp_vector_test, CopyAssignment) { int data1[] = {1, 2, 3}; int data2[] = {4, 5}; - kmp_vector<int> v1(3, data1, 3); - kmp_vector<int> v2(2, data2, 2); + typename TypeParam::template Vec<int> v1(3, data1, 3); + typename TypeParam::template Vec<int> v2(2, data2, 2); v2 = v1; @@ -82,11 +96,11 @@ TEST(kmp_vector_test, CopyAssignment) { EXPECT_EQ(v2[2], 3); } -TEST(kmp_vector_test, SelfCopyAssignment) { +TYPED_TEST(kmp_vector_test, SelfCopyAssignment) { int data[] = {1, 2, 3}; - kmp_vector<int> v(3, data, 3); + typename TypeParam::template Vec<int> v(3, data, 3); - kmp_vector<int> &v_ref = v; + typename TypeParam::template Vec<int> &v_ref = v; v = v_ref; // Avoid self-assignment warning EXPECT_EQ(v.size(), 3u); @@ -97,10 +111,10 @@ TEST(kmp_vector_test, SelfCopyAssignment) { // Move Semantics //===----------------------------------------------------------------------===// -TEST(kmp_vector_test, MoveConstruction) { +TYPED_TEST(kmp_vector_test, MoveConstruction) { int data[] = {1, 2, 3}; - kmp_vector<int> v1(3, data, 3); - kmp_vector<int> v2(std::move(v1)); + typename TypeParam::template Vec<int> v1(3, data, 3); + typename TypeParam::template Vec<int> v2(std::move(v1)); EXPECT_EQ(v2.size(), 3u); EXPECT_EQ(v2[0], 1); @@ -111,11 +125,11 @@ TEST(kmp_vector_test, MoveConstruction) { EXPECT_EQ(v1.size(), 0u); } -TEST(kmp_vector_test, MoveAssignment) { +TYPED_TEST(kmp_vector_test, MoveAssignment) { int data1[] = {1, 2, 3}; int data2[] = {4, 5}; - kmp_vector<int> v1(3, data1, 3); - kmp_vector<int> v2(2, data2, 2); + typename TypeParam::template Vec<int> v1(3, data1, 3); + typename TypeParam::template Vec<int> v2(2, data2, 2); v2 = std::move(v1); @@ -124,11 +138,11 @@ TEST(kmp_vector_test, MoveAssignment) { EXPECT_EQ(v1.size(), 0u); } -TEST(kmp_vector_test, SelfMoveAssignment) { +TYPED_TEST(kmp_vector_test, SelfMoveAssignment) { int data[] = {1, 2, 3}; - kmp_vector<int> v(3, data, 3); + typename TypeParam::template Vec<int> v(3, data, 3); - kmp_vector<int> &v_ref = v; + typename TypeParam::template Vec<int> &v_ref = v; v = std::move(v_ref); // Avoid self-move warning // Self-move should leave object in valid state @@ -140,8 +154,8 @@ TEST(kmp_vector_test, SelfMoveAssignment) { // push_back //===----------------------------------------------------------------------===// -TEST(kmp_vector_test, PushBackToEmpty) { - kmp_vector<int> v; +TYPED_TEST(kmp_vector_test, PushBackToEmpty) { + typename TypeParam::template Vec<int> v; v.push_back(42); @@ -149,8 +163,8 @@ TEST(kmp_vector_test, PushBackToEmpty) { EXPECT_EQ(v[0], 42); } -TEST(kmp_vector_test, PushBackMultiple) { - kmp_vector<int> v; +TYPED_TEST(kmp_vector_test, PushBackMultiple) { + typename TypeParam::template Vec<int> v; v.push_back(1); v.push_back(2); @@ -166,27 +180,25 @@ TEST(kmp_vector_test, PushBackMultiple) { EXPECT_EQ(v[4], 5); } -TEST(kmp_vector_test, PushBackGrowth) { - kmp_vector<int> v; +TYPED_TEST(kmp_vector_test, PushBackGrowth) { + typename TypeParam::template Vec<int> v; // Push many elements to trigger multiple resizes - for (int i = 0; i < 100; ++i) { + for (int i = 0; i < 100; ++i) v.push_back(i); - } EXPECT_EQ(v.size(), 100u); - for (int i = 0; i < 100; ++i) { + for (int i = 0; i < 100; ++i) EXPECT_EQ(v[i], i); - } } //===----------------------------------------------------------------------===// // clear //===----------------------------------------------------------------------===// -TEST(kmp_vector_test, Clear) { +TYPED_TEST(kmp_vector_test, Clear) { int data[] = {1, 2, 3}; - kmp_vector<int> v(3, data, 3); + typename TypeParam::template Vec<int> v(3, data, 3); EXPECT_EQ(v.size(), 3u); @@ -196,8 +208,8 @@ TEST(kmp_vector_test, Clear) { EXPECT_TRUE(v.empty()); } -TEST(kmp_vector_test, ClearEmpty) { - kmp_vector<int> v; +TYPED_TEST(kmp_vector_test, ClearEmpty) { + typename TypeParam::template Vec<int> v; v.clear(); @@ -205,9 +217,9 @@ TEST(kmp_vector_test, ClearEmpty) { EXPECT_TRUE(v.empty()); } -TEST(kmp_vector_test, PushBackAfterClear) { +TYPED_TEST(kmp_vector_test, PushBackAfterClear) { int data[] = {1, 2, 3}; - kmp_vector<int> v(3, data, 3); + typename TypeParam::template Vec<int> v(3, data, 3); v.clear(); v.push_back(42); @@ -220,19 +232,19 @@ TEST(kmp_vector_test, PushBackAfterClear) { // empty //===----------------------------------------------------------------------===// -TEST(kmp_vector_test, EmptyOnDefault) { - kmp_vector<int> v; +TYPED_TEST(kmp_vector_test, EmptyOnDefault) { + typename TypeParam::template Vec<int> v; EXPECT_TRUE(v.empty()); } -TEST(kmp_vector_test, NotEmptyAfterPush) { - kmp_vector<int> v; +TYPED_TEST(kmp_vector_test, NotEmptyAfterPush) { + typename TypeParam::template Vec<int> v; v.push_back(1); EXPECT_FALSE(v.empty()); } -TEST(kmp_vector_test, EmptyAfterClear) { - kmp_vector<int> v; +TYPED_TEST(kmp_vector_test, EmptyAfterClear) { + typename TypeParam::template Vec<int> v; v.push_back(1); v.clear(); EXPECT_TRUE(v.empty()); @@ -242,26 +254,26 @@ TEST(kmp_vector_test, EmptyAfterClear) { // contains //===----------------------------------------------------------------------===// -TEST(kmp_vector_test, ContainsFound) { +TYPED_TEST(kmp_vector_test, ContainsFound) { int data[] = {1, 2, 3, 4, 5}; - kmp_vector<int> v(5, data, 5); + typename TypeParam::template Vec<int> v(5, data, 5); EXPECT_TRUE(v.contains(1)); EXPECT_TRUE(v.contains(3)); EXPECT_TRUE(v.contains(5)); } -TEST(kmp_vector_test, ContainsNotFound) { +TYPED_TEST(kmp_vector_test, ContainsNotFound) { int data[] = {1, 2, 3, 4, 5}; - kmp_vector<int> v(5, data, 5); + typename TypeParam::template Vec<int> v(5, data, 5); EXPECT_FALSE(v.contains(0)); EXPECT_FALSE(v.contains(6)); EXPECT_FALSE(v.contains(-1)); } -TEST(kmp_vector_test, ContainsEmpty) { - kmp_vector<int> v; +TYPED_TEST(kmp_vector_test, ContainsEmpty) { + typename TypeParam::template Vec<int> v; EXPECT_FALSE(v.contains(0)); EXPECT_FALSE(v.contains(1)); @@ -271,66 +283,66 @@ TEST(kmp_vector_test, ContainsEmpty) { // is_set_equal //===----------------------------------------------------------------------===// -TEST(kmp_vector_test, IsSetEqualSameOrder) { +TYPED_TEST(kmp_vector_test, IsSetEqualSameOrder) { int data[] = {1, 2, 3}; - kmp_vector<int> v1(3, data, 3); - kmp_vector<int> v2(3, data, 3); + typename TypeParam::template Vec<int> v1(3, data, 3); + typename TypeParam::template Vec<int> v2(3, data, 3); EXPECT_TRUE(v1.is_set_equal(v2)); EXPECT_TRUE(v2.is_set_equal(v1)); } -TEST(kmp_vector_test, IsSetEqualDifferentOrder) { +TYPED_TEST(kmp_vector_test, IsSetEqualDifferentOrder) { int data1[] = {1, 2, 3}; int data2[] = {3, 1, 2}; - kmp_vector<int> v1(3, data1, 3); - kmp_vector<int> v2(3, data2, 3); + typename TypeParam::template Vec<int> v1(3, data1, 3); + typename TypeParam::template Vec<int> v2(3, data2, 3); EXPECT_TRUE(v1.is_set_equal(v2)); EXPECT_TRUE(v2.is_set_equal(v1)); } -TEST(kmp_vector_test, IsSetEqualDifferentSize) { +TYPED_TEST(kmp_vector_test, IsSetEqualDifferentSize) { int data1[] = {1, 2, 3}; int data2[] = {1, 2}; - kmp_vector<int> v1(3, data1, 3); - kmp_vector<int> v2(2, data2, 2); + typename TypeParam::template Vec<int> v1(3, data1, 3); + typename TypeParam::template Vec<int> v2(2, data2, 2); EXPECT_FALSE(v1.is_set_equal(v2)); EXPECT_FALSE(v2.is_set_equal(v1)); } -TEST(kmp_vector_test, IsSetEqualDifferentElements) { +TYPED_TEST(kmp_vector_test, IsSetEqualDifferentElements) { int data1[] = {1, 2, 3}; int data2[] = {1, 2, 4}; - kmp_vector<int> v1(3, data1, 3); - kmp_vector<int> v2(3, data2, 3); + typename TypeParam::template Vec<int> v1(3, data1, 3); + typename TypeParam::template Vec<int> v2(3, data2, 3); EXPECT_FALSE(v1.is_set_equal(v2)); } -TEST(kmp_vector_test, IsSetEqualEmpty) { - kmp_vector<int> v1; - kmp_vector<int> v2; +TYPED_TEST(kmp_vector_test, IsSetEqualEmpty) { + typename TypeParam::template Vec<int> v1; + typename TypeParam::template Vec<int> v2; EXPECT_TRUE(v1.is_set_equal(v2)); } -TEST(kmp_vector_test, IsSetEqualWithDuplicates) { +TYPED_TEST(kmp_vector_test, IsSetEqualWithDuplicates) { int data1[] = {1, 1}; int data2[] = {1, 2}; - kmp_vector<int> v1(2, data1, 2); - kmp_vector<int> v2(2, data2, 2); + typename TypeParam::template Vec<int> v1(2, data1, 2); + typename TypeParam::template Vec<int> v2(2, data2, 2); EXPECT_FALSE(v1.is_set_equal(v2)); EXPECT_FALSE(v2.is_set_equal(v1)); } -TEST(kmp_vector_test, IsSetEqualWithDuplicatesSame) { +TYPED_TEST(kmp_vector_test, IsSetEqualWithDuplicatesSame) { int data1[] = {1, 1}; int data2[] = {1}; - kmp_vector<int> v1(2, data1, 2); - kmp_vector<int> v2(1, data2, 1); + typename TypeParam::template Vec<int> v1(2, data1, 2); + typename TypeParam::template Vec<int> v2(1, data2, 1); EXPECT_TRUE(v1.is_set_equal(v2)); EXPECT_TRUE(v2.is_set_equal(v1)); @@ -340,9 +352,9 @@ TEST(kmp_vector_test, IsSetEqualWithDuplicatesSame) { // contains with Comparator //===----------------------------------------------------------------------===// -TEST(kmp_vector_test, ContainsWithComparator) { +TYPED_TEST(kmp_vector_test, ContainsWithComparator) { int data[] = {10, 20, 30}; - kmp_vector<int> v(3, data, 3); + typename TypeParam::template Vec<int> v(3, data, 3); // Compare by tens digit auto same_tens = [](const int &a, const int &b) { @@ -354,10 +366,10 @@ TEST(kmp_vector_test, ContainsWithComparator) { EXPECT_FALSE(v.contains(45, same_tens)); // 45/10 == 4, no match } -TEST(kmp_vector_test, ContainsPointerWithComparator) { +TYPED_TEST(kmp_vector_test, ContainsPointerWithComparator) { int a = 100, b = 200, c = 300; int *data[] = {&a, &b, &c}; - kmp_vector<int *> v(3, data, 3); + typename TypeParam::template Vec<int *> v(3, data, 3); // Comparator that compares pointed-to values auto deref_comp = [](int *const &pa, int *const &pb) { return *pa == *pb; }; @@ -376,11 +388,11 @@ TEST(kmp_vector_test, ContainsPointerWithComparator) { // is_set_equal with Comparator //===----------------------------------------------------------------------===// -TEST(kmp_vector_test, IsSetEqualWithComparator) { +TYPED_TEST(kmp_vector_test, IsSetEqualWithComparator) { int data1[] = {10, 20, 30}; int data2[] = {35, 15, 25}; // Same tens digits as data1, different order - kmp_vector<int> v1(3, data1, 3); - kmp_vector<int> v2(3, data2, 3); + typename TypeParam::template Vec<int> v1(3, data1, 3); + typename TypeParam::template Vec<int> v2(3, data2, 3); auto same_tens = [](const int &a, const int &b) { return (a / 10) == (b / 10); @@ -393,13 +405,13 @@ TEST(kmp_vector_test, IsSetEqualWithComparator) { EXPECT_TRUE(v1.is_set_equal(v2, same_tens)); } -TEST(kmp_vector_test, IsSetEqualPointerWithComparator) { +TYPED_TEST(kmp_vector_test, IsSetEqualPointerWithComparator) { int a1 = 100, b1 = 200, c1 = 300; int a2 = 100, b2 = 200, c2 = 300; int *data1[] = {&a1, &b1, &c1}; int *data2[] = {&c2, &a2, &b2}; // Same values, different order and addresses - kmp_vector<int *> v1(3, data1, 3); - kmp_vector<int *> v2(3, data2, 3); + typename TypeParam::template Vec<int *> v1(3, data1, 3); + typename TypeParam::template Vec<int *> v2(3, data2, 3); auto deref_comp = [](int *const &pa, int *const &pb) { return *pa == *pb; }; @@ -414,27 +426,27 @@ TEST(kmp_vector_test, IsSetEqualPointerWithComparator) { // Indexing //===----------------------------------------------------------------------===// -TEST(kmp_vector_test, IndexOperator) { +TYPED_TEST(kmp_vector_test, IndexOperator) { int data[] = {10, 20, 30}; - kmp_vector<int> v(3, data, 3); + typename TypeParam::template Vec<int> v(3, data, 3); EXPECT_EQ(v[0], 10); EXPECT_EQ(v[1], 20); EXPECT_EQ(v[2], 30); } -TEST(kmp_vector_test, IndexOperatorModify) { +TYPED_TEST(kmp_vector_test, IndexOperatorModify) { int data[] = {10, 20, 30}; - kmp_vector<int> v(3, data, 3); + typename TypeParam::template Vec<int> v(3, data, 3); v[1] = 200; EXPECT_EQ(v[1], 200); } -TEST(kmp_vector_test, ConstIndexOperator) { +TYPED_TEST(kmp_vector_test, ConstIndexOperator) { int data[] = {10, 20, 30}; - const kmp_vector<int> v(3, data, 3); + const typename TypeParam::template Vec<int> v(3, data, 3); EXPECT_EQ(v[0], 10); EXPECT_EQ(v[1], 20); @@ -445,9 +457,9 @@ TEST(kmp_vector_test, ConstIndexOperator) { // Iterators //===----------------------------------------------------------------------===// -TEST(kmp_vector_test, BeginEnd) { +TYPED_TEST(kmp_vector_test, BeginEnd) { int data[] = {1, 2, 3}; - kmp_vector<int> v(3, data, 3); + typename TypeParam::template Vec<int> v(3, data, 3); int *begin = v.begin(); int *end = v.end(); @@ -457,9 +469,9 @@ TEST(kmp_vector_test, BeginEnd) { EXPECT_EQ(*(end - 1), 3); } -TEST(kmp_vector_test, ConstBeginEnd) { +TYPED_TEST(kmp_vector_test, ConstBeginEnd) { int data[] = {1, 2, 3}; - const kmp_vector<int> v(3, data, 3); + const typename TypeParam::template Vec<int> v(3, data, 3); const int *begin = v.begin(); const int *end = v.end(); @@ -468,33 +480,31 @@ TEST(kmp_vector_test, ConstBeginEnd) { EXPECT_EQ(*begin, 1); } -TEST(kmp_vector_test, RangeBasedFor) { +TYPED_TEST(kmp_vector_test, RangeBasedFor) { int data[] = {1, 2, 3, 4, 5}; - kmp_vector<int> v(5, data, 5); + typename TypeParam::template Vec<int> v(5, data, 5); int sum = 0; - for (int x : v) { + for (int x : v) sum += x; - } EXPECT_EQ(sum, 15); } -TEST(kmp_vector_test, RangeBasedForModify) { +TYPED_TEST(kmp_vector_test, RangeBasedForModify) { int data[] = {1, 2, 3}; - kmp_vector<int> v(3, data, 3); + typename TypeParam::template Vec<int> v(3, data, 3); - for (int &x : v) { + for (int &x : v) x *= 2; - } EXPECT_EQ(v[0], 2); EXPECT_EQ(v[1], 4); EXPECT_EQ(v[2], 6); } -TEST(kmp_vector_test, RangeBasedForEmpty) { - kmp_vector<int> v; +TYPED_TEST(kmp_vector_test, RangeBasedForEmpty) { + typename TypeParam::template Vec<int> v; int count = 0; for (int x : v) { @@ -509,16 +519,16 @@ TEST(kmp_vector_test, RangeBasedForEmpty) { // Edge Cases //===----------------------------------------------------------------------===// -TEST(kmp_vector_test, EmptyVector) { - kmp_vector<int> v; +TYPED_TEST(kmp_vector_test, EmptyVector) { + typename TypeParam::template Vec<int> v; EXPECT_EQ(v.size(), 0u); EXPECT_EQ(v.begin(), v.end()); EXPECT_FALSE(v.contains(0)); } -TEST(kmp_vector_test, SingleElement) { - kmp_vector<int> v; +TYPED_TEST(kmp_vector_test, SingleElement) { + typename TypeParam::template Vec<int> v; v.push_back(42); EXPECT_EQ(v.size(), 1u); @@ -531,10 +541,10 @@ TEST(kmp_vector_test, SingleElement) { // Different Types //===----------------------------------------------------------------------===// -TEST(kmp_vector_test, PointerType) { +TYPED_TEST(kmp_vector_test, PointerType) { int a = 1, b = 2, c = 3; int *data[] = {&a, &b, &c}; - kmp_vector<int *> v(3, data, 3); + typename TypeParam::template Vec<int *> v(3, data, 3); EXPECT_EQ(v.size(), 3u); EXPECT_EQ(*v[0], 1); @@ -542,9 +552,9 @@ TEST(kmp_vector_test, PointerType) { EXPECT_EQ(*v[2], 3); } -TEST(kmp_vector_test, SizeTType) { +TYPED_TEST(kmp_vector_test, SizeTType) { size_t data[] = {100, 200, 300}; - kmp_vector<size_t> v(3, data, 3); + typename TypeParam::template Vec<size_t> v(3, data, 3); EXPECT_EQ(v[0], 100u); EXPECT_EQ(v[1], 200u); @@ -555,8 +565,8 @@ TEST(kmp_vector_test, SizeTType) { // Reserve //===----------------------------------------------------------------------===// -TEST(kmp_vector_test, Reserve) { - kmp_vector<int> v; +TYPED_TEST(kmp_vector_test, Reserve) { + typename TypeParam::template Vec<int> v; v.reserve(100); EXPECT_EQ(v.size(), 0u); @@ -566,15 +576,13 @@ TEST(kmp_vector_test, Reserve) { const int *data_ptr = v.begin(); // Should be able to push without reallocation - for (int i = 1; i < 100; ++i) { + for (int i = 1; i < 100; ++i) v.push_back(i); - } EXPECT_EQ(v.size(), 100u); EXPECT_EQ(v.begin(), data_ptr) << "Reallocation occurred despite reserve()"; - for (int i = 0; i < 100; ++i) { + for (int i = 0; i < 100; ++i) EXPECT_EQ(v[i], i); - } } } // namespace _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
