OLD | NEW |
1 // Copyright (c) 2010 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2010 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "courgette/third_party/bsdiff/paged_array.h" | 5 #include "courgette/third_party/bsdiff/paged_array.h" |
6 | 6 |
| 7 #include <stdint.h> |
| 8 |
| 9 #include <algorithm> |
| 10 #include <iterator> |
| 11 #include <random> |
| 12 #include <vector> |
| 13 |
7 #include "testing/gtest/include/gtest/gtest.h" | 14 #include "testing/gtest/include/gtest/gtest.h" |
8 | 15 |
| 16 namespace { |
| 17 |
| 18 // Total allocation of 4GB will fail in 32 bit programs if allocations are |
| 19 // leaked. |
| 20 const int kIterations = 20; |
| 21 const int kSizeBig = 200 * 1024 * 1024 / sizeof(int); // 200MB |
| 22 |
| 23 const size_t kLogBlockSizeSmall = 10; |
| 24 const size_t kBlockSizeSmall = 1 << kLogBlockSizeSmall; |
| 25 const size_t kSizeList[] = {1, |
| 26 16, |
| 27 123, |
| 28 kBlockSizeSmall, |
| 29 kBlockSizeSmall + 1, |
| 30 123 * kBlockSizeSmall + 567}; |
| 31 |
| 32 const size_t kIteratorTestDataSize = 7; |
| 33 const int32_t kIteratorTestData[kIteratorTestDataSize] = {2, 3, 5, 7, |
| 34 11, 13, 17}; |
| 35 |
| 36 } // namespace |
| 37 |
9 class PagedArrayTest : public testing::Test { | 38 class PagedArrayTest : public testing::Test { |
10 public: | 39 public: |
11 // Total allocation of 4GB will fail in 32 bit programs if allocations are | 40 template <typename Iterator> |
12 // leaked. | 41 void TestIteratorBasic(Iterator begin, Iterator end) { |
13 static const int kIterations = 20; | 42 EXPECT_FALSE(begin == nullptr); |
14 static const int kSize = 200 * 1024 * 1024 / sizeof(int); // 200MB | 43 EXPECT_FALSE(end == nullptr); |
| 44 |
| 45 // Test TestPagedArray::iterator data read. |
| 46 Iterator it = begin; |
| 47 EXPECT_EQ(2, *it); |
| 48 EXPECT_EQ(3, *(it + 1)); |
| 49 EXPECT_EQ(5, it[2]); // Pseudo-pointer. |
| 50 EXPECT_EQ(7, (it + 1)[2]); |
| 51 EXPECT_EQ(3, *(++it)); |
| 52 EXPECT_EQ(3, *it); |
| 53 EXPECT_EQ(3, *(it++)); |
| 54 EXPECT_EQ(5, *it); |
| 55 EXPECT_EQ(11, *(it += 2)); |
| 56 EXPECT_EQ(11, *it); |
| 57 EXPECT_FALSE(it == begin); |
| 58 EXPECT_TRUE(it != begin); |
| 59 EXPECT_TRUE(it == (begin + 4)); |
| 60 EXPECT_FALSE(it != (begin + 4)); |
| 61 EXPECT_EQ(static_cast<ptrdiff_t>(kIteratorTestDataSize), end - begin); |
| 62 it = begin + 5; |
| 63 EXPECT_EQ(begin, it - 5); |
| 64 EXPECT_EQ(13, *it); |
| 65 EXPECT_EQ(11, *(--it)); |
| 66 EXPECT_EQ(11, *it); |
| 67 EXPECT_EQ(11, *(it--)); |
| 68 EXPECT_EQ(7, *it); |
| 69 EXPECT_EQ(3, *(it -= 2)); |
| 70 EXPECT_EQ(3, *it); |
| 71 |
| 72 // Test binary operators for every pair of iterator. |
| 73 EXPECT_TRUE(begin <= end); |
| 74 EXPECT_TRUE(begin < end); |
| 75 for (size_t i = 0; i < kIteratorTestDataSize; ++i) { |
| 76 Iterator it1 = begin + i; |
| 77 EXPECT_TRUE(it1 == it1); |
| 78 EXPECT_FALSE(it1 != it1); |
| 79 EXPECT_TRUE(begin <= it1); |
| 80 EXPECT_EQ(begin, it1 - i); |
| 81 EXPECT_EQ(end, it1 + (kIteratorTestDataSize - i)); |
| 82 EXPECT_EQ(kIteratorTestData[i], *it1); |
| 83 EXPECT_EQ(kIteratorTestData[i], begin[i]); |
| 84 for (size_t j = 0; i + j < kIteratorTestDataSize; ++j) { |
| 85 Iterator it2 = it1 + j; |
| 86 EXPECT_TRUE(it1 <= it2); |
| 87 EXPECT_FALSE(it2 < it1); |
| 88 if (j > 0) { |
| 89 EXPECT_TRUE(it1 < it2); |
| 90 EXPECT_FALSE(it2 <= it1); |
| 91 EXPECT_TRUE(it1 != it2); |
| 92 } |
| 93 EXPECT_EQ(kIteratorTestData[i + j], it1[j]); // Pseudo-pointer. |
| 94 EXPECT_EQ(kIteratorTestData[i + j], *it2); |
| 95 EXPECT_EQ(static_cast<ptrdiff_t>(j), it2 - it1); |
| 96 EXPECT_EQ(it1, it2 - j); |
| 97 } |
| 98 EXPECT_TRUE(it1 < end); |
| 99 EXPECT_TRUE(it1 <= end); |
| 100 EXPECT_TRUE(it1 != end); |
| 101 } |
| 102 |
| 103 // Test initialize with null. |
| 104 Iterator it_dummy; |
| 105 it_dummy = nullptr; |
| 106 EXPECT_TRUE(it_dummy == nullptr); |
| 107 |
| 108 // Test copy constructor. |
| 109 Iterator begin_copy(begin); |
| 110 EXPECT_TRUE(begin_copy == begin); |
| 111 |
| 112 // Test STL read-only usage. |
| 113 std::vector<typename std::iterator_traits<Iterator>::value_type> v(begin, |
| 114 end); |
| 115 EXPECT_TRUE(std::equal(begin, end, v.begin())); |
| 116 EXPECT_TRUE(std::equal(v.begin(), v.end(), begin)); |
| 117 } |
15 }; | 118 }; |
16 | 119 |
17 // AddressSanitizer on Windows adds additional memory overhead, which | 120 // AddressSanitizer on Windows adds additional memory overhead, which |
18 // causes these tests to go OOM and fail. | 121 // causes these tests to go OOM and fail. |
19 #if !defined(ADDRESS_SANITIZER) || !defined(OS_WIN) | 122 #if !defined(ADDRESS_SANITIZER) || !defined(OS_WIN) |
20 TEST_F(PagedArrayTest, TestManyAllocationsDestructorFree) { | 123 TEST_F(PagedArrayTest, TestManyAllocationsDestructorFree) { |
21 for (int i = 0; i < kIterations; ++i) { | 124 for (int i = 0; i < kIterations; ++i) { |
22 courgette::PagedArray<int> a; | 125 courgette::PagedArray<int> a; |
23 EXPECT_TRUE(a.Allocate(kSize)); | 126 EXPECT_TRUE(a.Allocate(kSizeBig)); |
24 } | 127 } |
25 } | 128 } |
26 | 129 |
27 TEST_F(PagedArrayTest, TestManyAllocationsManualFree) { | 130 TEST_F(PagedArrayTest, TestManyAllocationsManualFree) { |
28 courgette::PagedArray<int> a; | 131 courgette::PagedArray<int> a; |
29 for (int i = 0; i < kIterations; ++i) { | 132 for (int i = 0; i < kIterations; ++i) { |
30 EXPECT_TRUE(a.Allocate(kSize)); | 133 EXPECT_TRUE(a.Allocate(kSizeBig)); |
31 a.clear(); | 134 a.clear(); |
32 } | 135 } |
33 } | 136 } |
34 #endif | 137 #endif |
35 | 138 |
36 TEST_F(PagedArrayTest, TestAccess) { | 139 TEST_F(PagedArrayTest, TestAccess) { |
37 const int kAccessSize = 3 * 1024 * 1024; | 140 for (size_t size : kSizeList) { |
38 courgette::PagedArray<int> a; | 141 courgette::PagedArray<int32_t, kLogBlockSizeSmall> a; |
39 a.Allocate(kAccessSize); | 142 EXPECT_TRUE(a.Allocate(size)); |
40 for (int i = 0; i < kAccessSize; ++i) { | 143 for (size_t i = 0; i < size; ++i) |
41 a[i] = i; | 144 a[i] = i; |
42 } | 145 for (size_t i = 0; i < size; ++i) |
43 for (int i = 0; i < kAccessSize; ++i) { | 146 EXPECT_EQ(static_cast<int32_t>(i), a[i]); |
44 EXPECT_EQ(i, a[i]); | |
45 } | 147 } |
46 } | 148 } |
| 149 |
| 150 TEST_F(PagedArrayTest, TestIterator) { |
| 151 using TestPagedArray = courgette::PagedArray<int32_t, 1>; // Page size = 2. |
| 152 |
| 153 TestPagedArray::const_iterator uninit_const_it; |
| 154 EXPECT_TRUE(uninit_const_it == nullptr); |
| 155 |
| 156 TestPagedArray::iterator uninit_it; |
| 157 EXPECT_TRUE(uninit_it == nullptr); |
| 158 |
| 159 TestPagedArray a; |
| 160 EXPECT_TRUE(a.Allocate(kIteratorTestDataSize)); |
| 161 std::copy(kIteratorTestData, kIteratorTestData + kIteratorTestDataSize, |
| 162 a.begin()); |
| 163 const TestPagedArray& a_const = a; |
| 164 |
| 165 // Test TestPagedArray::const_iterator. |
| 166 TestIteratorBasic(a_const.begin(), a_const.end()); |
| 167 |
| 168 // Test TestPagedArray::iterator. |
| 169 TestIteratorBasic(a.begin(), a.end()); |
| 170 |
| 171 // Test equality of const and non-const. |
| 172 EXPECT_TRUE(a.begin() == a_const.begin()); |
| 173 EXPECT_TRUE(a_const.begin() == a.begin()); |
| 174 |
| 175 // Test casting from non-const to const. |
| 176 TestPagedArray::iterator non_const_it = a.begin(); |
| 177 EXPECT_TRUE(non_const_it == a.begin()); |
| 178 TestPagedArray::const_iterator const_it = non_const_it; |
| 179 EXPECT_TRUE(const_it == non_const_it); |
| 180 // The following should and will emit compile error: |
| 181 // non_const_it = a_const.begin(); |
| 182 |
| 183 // Test copy constructor from non-const to const. |
| 184 TestPagedArray::iterator const_it2(a.begin()); |
| 185 EXPECT_TRUE(const_it2 == a.begin()); |
| 186 |
| 187 // Test pointer distance from non-const to const. |
| 188 EXPECT_EQ(static_cast<ptrdiff_t>(kIteratorTestDataSize), |
| 189 a.end() - a_const.begin()); |
| 190 EXPECT_EQ(static_cast<ptrdiff_t>(kIteratorTestDataSize), |
| 191 a_const.end() - a.begin()); |
| 192 |
| 193 // Test operator->(). |
| 194 struct TestStruct { |
| 195 int32_t value = 0; |
| 196 }; |
| 197 using TestStructPagedArray = courgette::PagedArray<TestStruct, 1>; |
| 198 TestStructPagedArray b; |
| 199 b.Allocate(3); |
| 200 b[0].value = 100; |
| 201 b[1].value = 200; |
| 202 b[2].value = 300; |
| 203 const TestStructPagedArray& b_const = b; |
| 204 |
| 205 EXPECT_EQ(100, b.begin()->value); |
| 206 EXPECT_EQ(100, b_const.begin()->value); |
| 207 EXPECT_EQ(200, (b.begin() + 1)->value); |
| 208 EXPECT_EQ(200, (b_const.begin() + 1)->value); |
| 209 (b.begin() + 2)->value *= -1; |
| 210 EXPECT_EQ(-300, (b.begin() + 2)->value); |
| 211 EXPECT_EQ(-300, (b_const.begin() + 2)->value); |
| 212 } |
| 213 |
| 214 // Test generic read-write of itrators by sorting pseudo-random numbers. |
| 215 TEST_F(PagedArrayTest, TestSort) { |
| 216 courgette::PagedArray<int> a; |
| 217 std::minstd_rand pseudo_rand_gen; // Deterministic, using defaults. |
| 218 for (size_t size : kSizeList) { |
| 219 std::vector<int32_t> v(size); |
| 220 courgette::PagedArray<int32_t, kLogBlockSizeSmall> a; |
| 221 EXPECT_TRUE(a.Allocate(size)); |
| 222 for (size_t i = 0; i < size; ++i) { |
| 223 v[i] = pseudo_rand_gen(); |
| 224 a[i] = v[i]; |
| 225 } |
| 226 std::sort(v.begin(), v.end()); |
| 227 std::sort(a.begin(), a.end()); |
| 228 for (size_t i = 0; i < size; ++i) |
| 229 EXPECT_EQ(v[i], a[i]); |
| 230 } |
| 231 } |
OLD | NEW |