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_FALSE(begin > it1); |
| 81 EXPECT_TRUE(it1 >= begin); |
| 82 EXPECT_FALSE(it1 < begin); |
| 83 EXPECT_EQ(begin, it1 - i); |
| 84 EXPECT_EQ(end, it1 + (kIteratorTestDataSize - i)); |
| 85 EXPECT_EQ(kIteratorTestData[i], *it1); |
| 86 EXPECT_EQ(kIteratorTestData[i], begin[i]); |
| 87 for (size_t j = 0; i + j < kIteratorTestDataSize; ++j) { |
| 88 Iterator it2 = it1 + j; |
| 89 EXPECT_TRUE(it1 <= it2); |
| 90 EXPECT_FALSE(it1 > it2); |
| 91 EXPECT_TRUE(it2 >= it1); |
| 92 EXPECT_FALSE(it2 < it1); |
| 93 if (j > 0) { |
| 94 EXPECT_TRUE(it1 < it2); |
| 95 EXPECT_FALSE(it1 >= it2); |
| 96 EXPECT_TRUE(it2 > it1); |
| 97 EXPECT_FALSE(it2 <= it1); |
| 98 EXPECT_FALSE(it1 == it2); |
| 99 EXPECT_TRUE(it1 != it2); |
| 100 } |
| 101 EXPECT_EQ(kIteratorTestData[i + j], it1[j]); // Pseudo-pointer. |
| 102 EXPECT_EQ(kIteratorTestData[i + j], *it2); |
| 103 EXPECT_EQ(static_cast<ptrdiff_t>(j), it2 - it1); |
| 104 EXPECT_EQ(it1, it2 - j); |
| 105 } |
| 106 EXPECT_TRUE(it1 < end); |
| 107 EXPECT_FALSE(it1 >= end); |
| 108 EXPECT_TRUE(it1 <= end); |
| 109 EXPECT_FALSE(it1 > end); |
| 110 EXPECT_TRUE(end > it1); |
| 111 EXPECT_FALSE(end <= it1); |
| 112 EXPECT_TRUE(end >= it1); |
| 113 EXPECT_FALSE(end < it1); |
| 114 EXPECT_TRUE(it1 != end); |
| 115 EXPECT_FALSE(it1 == end); |
| 116 } |
| 117 |
| 118 // Test initialize with null. |
| 119 Iterator it_dummy; |
| 120 it_dummy = nullptr; |
| 121 EXPECT_TRUE(it_dummy == nullptr); |
| 122 |
| 123 // Test copy constructor. |
| 124 Iterator begin_copy(begin); |
| 125 EXPECT_TRUE(begin_copy == begin); |
| 126 |
| 127 // Test STL read-only usage. |
| 128 std::vector<typename std::iterator_traits<Iterator>::value_type> v(begin, |
| 129 end); |
| 130 EXPECT_TRUE(std::equal(begin, end, v.begin())); |
| 131 EXPECT_TRUE(std::equal(v.begin(), v.end(), begin)); |
| 132 } |
15 }; | 133 }; |
16 | 134 |
17 // AddressSanitizer on Windows adds additional memory overhead, which | 135 // AddressSanitizer on Windows adds additional memory overhead, which |
18 // causes these tests to go OOM and fail. | 136 // causes these tests to go OOM and fail. |
19 #if !defined(ADDRESS_SANITIZER) || !defined(OS_WIN) | 137 #if !defined(ADDRESS_SANITIZER) || !defined(OS_WIN) |
20 TEST_F(PagedArrayTest, TestManyAllocationsDestructorFree) { | 138 TEST_F(PagedArrayTest, TestManyAllocationsDestructorFree) { |
21 for (int i = 0; i < kIterations; ++i) { | 139 for (int i = 0; i < kIterations; ++i) { |
22 courgette::PagedArray<int> a; | 140 courgette::PagedArray<int> a; |
23 EXPECT_TRUE(a.Allocate(kSize)); | 141 EXPECT_TRUE(a.Allocate(kSizeBig)); |
24 } | 142 } |
25 } | 143 } |
26 | 144 |
27 TEST_F(PagedArrayTest, TestManyAllocationsManualFree) { | 145 TEST_F(PagedArrayTest, TestManyAllocationsManualFree) { |
28 courgette::PagedArray<int> a; | 146 courgette::PagedArray<int> a; |
29 for (int i = 0; i < kIterations; ++i) { | 147 for (int i = 0; i < kIterations; ++i) { |
30 EXPECT_TRUE(a.Allocate(kSize)); | 148 EXPECT_TRUE(a.Allocate(kSizeBig)); |
31 a.clear(); | 149 a.clear(); |
32 } | 150 } |
33 } | 151 } |
34 #endif | 152 #endif |
35 | 153 |
36 TEST_F(PagedArrayTest, TestAccess) { | 154 TEST_F(PagedArrayTest, TestAccess) { |
37 const int kAccessSize = 3 * 1024 * 1024; | 155 for (size_t size : kSizeList) { |
38 courgette::PagedArray<int> a; | 156 courgette::PagedArray<int32_t, kLogBlockSizeSmall> a; |
39 a.Allocate(kAccessSize); | 157 EXPECT_TRUE(a.Allocate(size)); |
40 for (int i = 0; i < kAccessSize; ++i) { | 158 for (size_t i = 0; i < size; ++i) |
41 a[i] = i; | 159 a[i] = i; |
42 } | 160 for (size_t i = 0; i < size; ++i) |
43 for (int i = 0; i < kAccessSize; ++i) { | 161 EXPECT_EQ(static_cast<int32_t>(i), a[i]); |
44 EXPECT_EQ(i, a[i]); | |
45 } | 162 } |
46 } | 163 } |
| 164 |
| 165 TEST_F(PagedArrayTest, TestIterator) { |
| 166 using TestPagedArray = courgette::PagedArray<int32_t, 1>; // Page size = 2. |
| 167 |
| 168 TestPagedArray::const_iterator uninit_const_it; |
| 169 EXPECT_TRUE(uninit_const_it == nullptr); |
| 170 |
| 171 TestPagedArray::iterator uninit_it; |
| 172 EXPECT_TRUE(uninit_it == nullptr); |
| 173 |
| 174 TestPagedArray a; |
| 175 EXPECT_TRUE(a.Allocate(kIteratorTestDataSize)); |
| 176 std::copy(kIteratorTestData, kIteratorTestData + kIteratorTestDataSize, |
| 177 a.begin()); |
| 178 const TestPagedArray& a_const = a; |
| 179 |
| 180 // Test TestPagedArray::const_iterator. |
| 181 TestIteratorBasic(a_const.begin(), a_const.end()); |
| 182 |
| 183 // Test TestPagedArray::iterator. |
| 184 TestIteratorBasic(a.begin(), a.end()); |
| 185 |
| 186 // Test equality of const and non-const. |
| 187 EXPECT_TRUE(a.begin() == a_const.begin()); |
| 188 EXPECT_TRUE(a_const.begin() == a.begin()); |
| 189 |
| 190 // Test casting from non-const to const. |
| 191 TestPagedArray::iterator non_const_it = a.begin(); |
| 192 EXPECT_TRUE(non_const_it == a.begin()); |
| 193 TestPagedArray::const_iterator const_it = non_const_it; |
| 194 EXPECT_TRUE(const_it == non_const_it); |
| 195 // The following should and will emit compile error: |
| 196 // non_const_it = a_const.begin(); |
| 197 |
| 198 // Test copy constructor from non-const to const. |
| 199 TestPagedArray::iterator const_it2(a.begin()); |
| 200 EXPECT_TRUE(const_it2 == a.begin()); |
| 201 |
| 202 // Test pointer distance from non-const to const. |
| 203 EXPECT_EQ(static_cast<ptrdiff_t>(kIteratorTestDataSize), |
| 204 a.end() - a_const.begin()); |
| 205 EXPECT_EQ(static_cast<ptrdiff_t>(kIteratorTestDataSize), |
| 206 a_const.end() - a.begin()); |
| 207 |
| 208 // Test operator->(). |
| 209 struct TestStruct { |
| 210 int32_t value = 0; |
| 211 }; |
| 212 using TestStructPagedArray = courgette::PagedArray<TestStruct, 1>; |
| 213 TestStructPagedArray b; |
| 214 b.Allocate(3); |
| 215 b[0].value = 100; |
| 216 b[1].value = 200; |
| 217 b[2].value = 300; |
| 218 const TestStructPagedArray& b_const = b; |
| 219 |
| 220 EXPECT_EQ(100, b.begin()->value); |
| 221 EXPECT_EQ(100, b_const.begin()->value); |
| 222 EXPECT_EQ(200, (b.begin() + 1)->value); |
| 223 EXPECT_EQ(200, (b_const.begin() + 1)->value); |
| 224 (b.begin() + 2)->value *= -1; |
| 225 EXPECT_EQ(-300, (b.begin() + 2)->value); |
| 226 EXPECT_EQ(-300, (b_const.begin() + 2)->value); |
| 227 } |
| 228 |
| 229 // Test generic read-write of itrators by sorting pseudo-random numbers. |
| 230 TEST_F(PagedArrayTest, TestSort) { |
| 231 courgette::PagedArray<int> a; |
| 232 std::minstd_rand pseudo_rand_gen; // Deterministic, using defaults. |
| 233 for (size_t size : kSizeList) { |
| 234 std::vector<int32_t> v(size); |
| 235 courgette::PagedArray<int32_t, kLogBlockSizeSmall> a; |
| 236 EXPECT_TRUE(a.Allocate(size)); |
| 237 for (size_t i = 0; i < size; ++i) { |
| 238 v[i] = pseudo_rand_gen(); |
| 239 a[i] = v[i]; |
| 240 } |
| 241 std::sort(v.begin(), v.end()); |
| 242 std::sort(a.begin(), a.end()); |
| 243 for (size_t i = 0; i < size; ++i) |
| 244 EXPECT_EQ(v[i], a[i]); |
| 245 } |
| 246 } |
OLD | NEW |