| // Copyright (c) 2010 The Chromium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "courgette/third_party/bsdiff/paged_array.h" |
| |
| #include <stdint.h> |
| |
| #include <algorithm> |
| #include <iterator> |
| #include <random> |
| #include <vector> |
| |
| #include "testing/gtest/include/gtest/gtest.h" |
| |
| namespace { |
| |
| #if !defined(ADDRESS_SANITIZER) || !defined(OS_WIN) |
| // Total allocation of 4GB will fail in 32 bit programs if allocations are |
| // leaked. |
| const int kIterations = 20; |
| const int kSizeBig = 200 * 1024 * 1024 / sizeof(int); // 200MB |
| #endif |
| |
| const size_t kLogBlockSizeSmall = 10; |
| const size_t kBlockSizeSmall = 1 << kLogBlockSizeSmall; |
| const size_t kSizeList[] = {1, |
| 16, |
| 123, |
| kBlockSizeSmall, |
| kBlockSizeSmall + 1, |
| 123 * kBlockSizeSmall + 567}; |
| |
| const size_t kIteratorTestDataSize = 7; |
| const int32_t kIteratorTestData[kIteratorTestDataSize] = {2, 3, 5, 7, |
| 11, 13, 17}; |
| |
| } // namespace |
| |
| class PagedArrayTest : public testing::Test { |
| public: |
| template <typename Iterator> |
| void TestIteratorBasic(Iterator begin, Iterator end) { |
| EXPECT_FALSE(begin == nullptr); |
| EXPECT_FALSE(end == nullptr); |
| |
| // Test TestPagedArray::iterator data read. |
| Iterator it = begin; |
| EXPECT_EQ(2, *it); |
| EXPECT_EQ(3, *(it + 1)); |
| EXPECT_EQ(5, it[2]); // Pseudo-pointer. |
| EXPECT_EQ(7, (it + 1)[2]); |
| EXPECT_EQ(3, *(++it)); |
| EXPECT_EQ(3, *it); |
| EXPECT_EQ(3, *(it++)); |
| EXPECT_EQ(5, *it); |
| EXPECT_EQ(11, *(it += 2)); |
| EXPECT_EQ(11, *it); |
| EXPECT_FALSE(it == begin); |
| EXPECT_TRUE(it != begin); |
| EXPECT_TRUE(it == (begin + 4)); |
| EXPECT_FALSE(it != (begin + 4)); |
| EXPECT_EQ(static_cast<ptrdiff_t>(kIteratorTestDataSize), end - begin); |
| it = begin + 5; |
| EXPECT_EQ(begin, it - 5); |
| EXPECT_EQ(13, *it); |
| EXPECT_EQ(11, *(--it)); |
| EXPECT_EQ(11, *it); |
| EXPECT_EQ(11, *(it--)); |
| EXPECT_EQ(7, *it); |
| EXPECT_EQ(3, *(it -= 2)); |
| EXPECT_EQ(3, *it); |
| |
| // Test binary operators for every pair of iterator. |
| EXPECT_TRUE(begin <= end); |
| EXPECT_TRUE(begin < end); |
| for (size_t i = 0; i < kIteratorTestDataSize; ++i) { |
| Iterator it1 = begin + i; |
| EXPECT_TRUE(it1 == it1); |
| EXPECT_FALSE(it1 != it1); |
| EXPECT_TRUE(begin <= it1); |
| EXPECT_FALSE(begin > it1); |
| EXPECT_TRUE(it1 >= begin); |
| EXPECT_FALSE(it1 < begin); |
| EXPECT_EQ(begin, it1 - i); |
| EXPECT_EQ(end, it1 + (kIteratorTestDataSize - i)); |
| EXPECT_EQ(kIteratorTestData[i], *it1); |
| EXPECT_EQ(kIteratorTestData[i], begin[i]); |
| for (size_t j = 0; i + j < kIteratorTestDataSize; ++j) { |
| Iterator it2 = it1 + j; |
| EXPECT_TRUE(it1 <= it2); |
| EXPECT_FALSE(it1 > it2); |
| EXPECT_TRUE(it2 >= it1); |
| EXPECT_FALSE(it2 < it1); |
| if (j > 0) { |
| EXPECT_TRUE(it1 < it2); |
| EXPECT_FALSE(it1 >= it2); |
| EXPECT_TRUE(it2 > it1); |
| EXPECT_FALSE(it2 <= it1); |
| EXPECT_FALSE(it1 == it2); |
| EXPECT_TRUE(it1 != it2); |
| } |
| EXPECT_EQ(kIteratorTestData[i + j], it1[j]); // Pseudo-pointer. |
| EXPECT_EQ(kIteratorTestData[i + j], *it2); |
| EXPECT_EQ(static_cast<ptrdiff_t>(j), it2 - it1); |
| EXPECT_EQ(it1, it2 - j); |
| } |
| EXPECT_TRUE(it1 < end); |
| EXPECT_FALSE(it1 >= end); |
| EXPECT_TRUE(it1 <= end); |
| EXPECT_FALSE(it1 > end); |
| EXPECT_TRUE(end > it1); |
| EXPECT_FALSE(end <= it1); |
| EXPECT_TRUE(end >= it1); |
| EXPECT_FALSE(end < it1); |
| EXPECT_TRUE(it1 != end); |
| EXPECT_FALSE(it1 == end); |
| } |
| |
| // Test initialize with null. |
| Iterator it_dummy; |
| it_dummy = nullptr; |
| EXPECT_TRUE(it_dummy == nullptr); |
| |
| // Test copy constructor. |
| Iterator begin_copy(begin); |
| EXPECT_TRUE(begin_copy == begin); |
| |
| // Test STL read-only usage. |
| std::vector<typename std::iterator_traits<Iterator>::value_type> v(begin, |
| end); |
| EXPECT_TRUE(std::equal(begin, end, v.begin())); |
| EXPECT_TRUE(std::equal(v.begin(), v.end(), begin)); |
| } |
| }; |
| |
| // AddressSanitizer on Windows adds additional memory overhead, which |
| // causes these tests to go OOM and fail. |
| #if !defined(ADDRESS_SANITIZER) || !defined(OS_WIN) |
| TEST_F(PagedArrayTest, TestManyAllocationsDestructorFree) { |
| for (int i = 0; i < kIterations; ++i) { |
| courgette::PagedArray<int> a; |
| EXPECT_TRUE(a.Allocate(kSizeBig)); |
| } |
| } |
| |
| TEST_F(PagedArrayTest, TestManyAllocationsManualFree) { |
| courgette::PagedArray<int> a; |
| for (int i = 0; i < kIterations; ++i) { |
| EXPECT_TRUE(a.Allocate(kSizeBig)); |
| a.clear(); |
| } |
| } |
| #endif |
| |
| TEST_F(PagedArrayTest, TestAccess) { |
| for (size_t size : kSizeList) { |
| courgette::PagedArray<int32_t, kLogBlockSizeSmall> a; |
| EXPECT_TRUE(a.Allocate(size)); |
| for (size_t i = 0; i < size; ++i) |
| a[i] = i; |
| for (size_t i = 0; i < size; ++i) |
| EXPECT_EQ(static_cast<int32_t>(i), a[i]); |
| } |
| } |
| |
| TEST_F(PagedArrayTest, TestIterator) { |
| using TestPagedArray = courgette::PagedArray<int32_t, 1>; // Page size = 2. |
| |
| TestPagedArray::const_iterator uninit_const_it; |
| EXPECT_TRUE(uninit_const_it == nullptr); |
| |
| TestPagedArray::iterator uninit_it; |
| EXPECT_TRUE(uninit_it == nullptr); |
| |
| TestPagedArray a; |
| EXPECT_TRUE(a.Allocate(kIteratorTestDataSize)); |
| std::copy(kIteratorTestData, kIteratorTestData + kIteratorTestDataSize, |
| a.begin()); |
| const TestPagedArray& a_const = a; |
| |
| // Test TestPagedArray::const_iterator. |
| TestIteratorBasic(a_const.begin(), a_const.end()); |
| |
| // Test TestPagedArray::iterator. |
| TestIteratorBasic(a.begin(), a.end()); |
| |
| // Test equality of const and non-const. |
| EXPECT_TRUE(a.begin() == a_const.begin()); |
| EXPECT_TRUE(a_const.begin() == a.begin()); |
| |
| // Test casting from non-const to const. |
| TestPagedArray::iterator non_const_it = a.begin(); |
| EXPECT_TRUE(non_const_it == a.begin()); |
| TestPagedArray::const_iterator const_it = non_const_it; |
| EXPECT_TRUE(const_it == non_const_it); |
| // The following should and will emit compile error: |
| // non_const_it = a_const.begin(); |
| |
| // Test copy constructor from non-const to const. |
| TestPagedArray::iterator const_it2(a.begin()); |
| EXPECT_TRUE(const_it2 == a.begin()); |
| |
| // Test pointer distance from non-const to const. |
| EXPECT_EQ(static_cast<ptrdiff_t>(kIteratorTestDataSize), |
| a.end() - a_const.begin()); |
| EXPECT_EQ(static_cast<ptrdiff_t>(kIteratorTestDataSize), |
| a_const.end() - a.begin()); |
| |
| // Test operator->(). |
| struct TestStruct { |
| int32_t value = 0; |
| }; |
| using TestStructPagedArray = courgette::PagedArray<TestStruct, 1>; |
| TestStructPagedArray b; |
| b.Allocate(3); |
| b[0].value = 100; |
| b[1].value = 200; |
| b[2].value = 300; |
| const TestStructPagedArray& b_const = b; |
| |
| EXPECT_EQ(100, b.begin()->value); |
| EXPECT_EQ(100, b_const.begin()->value); |
| EXPECT_EQ(200, (b.begin() + 1)->value); |
| EXPECT_EQ(200, (b_const.begin() + 1)->value); |
| (b.begin() + 2)->value *= -1; |
| EXPECT_EQ(-300, (b.begin() + 2)->value); |
| EXPECT_EQ(-300, (b_const.begin() + 2)->value); |
| } |
| |
| // Test generic read-write of itrators by sorting pseudo-random numbers. |
| TEST_F(PagedArrayTest, TestSort) { |
| courgette::PagedArray<int> a; |
| std::minstd_rand pseudo_rand_gen; // Deterministic, using defaults. |
| for (size_t size : kSizeList) { |
| std::vector<int32_t> v(size); |
| courgette::PagedArray<int32_t, kLogBlockSizeSmall> a; |
| EXPECT_TRUE(a.Allocate(size)); |
| for (size_t i = 0; i < size; ++i) { |
| v[i] = pseudo_rand_gen(); |
| a[i] = v[i]; |
| } |
| std::sort(v.begin(), v.end()); |
| std::sort(a.begin(), a.end()); |
| for (size_t i = 0; i < size; ++i) |
| EXPECT_EQ(v[i], a[i]); |
| } |
| } |