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[] = { |
| 26 1, |
| 27 16, |
| 28 123, |
| 29 kBlockSizeSmall, |
| 30 kBlockSizeSmall + 1, |
| 31 123 * kBlockSizeSmall + 567 |
| 32 }; |
| 33 |
| 34 const size_t kIteratorTestDataSize = 7; |
| 35 const int32_t kIteratorTestData[kIteratorTestDataSize] = { |
| 36 2, 3, 5, 7, 11, 13, 17}; |
| 37 |
| 38 } // namespace |
| 39 |
9 class PagedArrayTest : public testing::Test { | 40 class PagedArrayTest : public testing::Test { |
10 public: | 41 public: |
11 // Total allocation of 4GB will fail in 32 bit programs if allocations are | 42 |
12 // leaked. | 43 template <typename Iterator> |
13 static const int kIterations = 20; | 44 void TestIteratorBasic(Iterator begin, Iterator end) { |
14 static const int kSize = 200 * 1024 * 1024 / sizeof(int); // 200MB | 45 EXPECT_FALSE(begin == nullptr); |
| 46 EXPECT_FALSE(end == nullptr); |
| 47 |
| 48 // Test TestPagedArray::iterator data read. |
| 49 Iterator it = begin; |
| 50 EXPECT_EQ(2, *it); |
| 51 EXPECT_EQ(3, *(it + 1)); |
| 52 EXPECT_EQ(5, it[2]); // Pseudo-pointer. |
| 53 EXPECT_EQ(7, (it + 1)[2]); |
| 54 EXPECT_EQ(3, *(++it)); |
| 55 EXPECT_EQ(3, *it); |
| 56 EXPECT_EQ(3, *(it++)); |
| 57 EXPECT_EQ(5, *it); |
| 58 EXPECT_EQ(11, *(it += 2)); |
| 59 EXPECT_EQ(11, *it); |
| 60 EXPECT_FALSE(it == begin); |
| 61 EXPECT_TRUE(it != begin); |
| 62 EXPECT_TRUE(it == (begin + 4)); |
| 63 EXPECT_FALSE(it != (begin + 4)); |
| 64 EXPECT_EQ(kIteratorTestDataSize, end - begin); |
| 65 it = begin + 5; |
| 66 EXPECT_EQ(begin, it - 5); |
| 67 EXPECT_EQ(13, *it); |
| 68 EXPECT_EQ(11, *(--it)); |
| 69 EXPECT_EQ(11, *it); |
| 70 EXPECT_EQ(11, *(it--)); |
| 71 EXPECT_EQ(7, *it); |
| 72 EXPECT_EQ(3, *(it -= 2)); |
| 73 EXPECT_EQ(3, *it); |
| 74 |
| 75 // Test every pair of iterator. |
| 76 EXPECT_TRUE(begin <= end); |
| 77 EXPECT_TRUE(begin < end); |
| 78 for (size_t i = 0; i < kIteratorTestDataSize; ++i) { |
| 79 Iterator it1 = begin + i; |
| 80 EXPECT_TRUE(it1 == it1); |
| 81 EXPECT_FALSE(it1 != it1); |
| 82 EXPECT_TRUE(begin <= it1); |
| 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(it2 < it1); |
| 91 if (j > 0) { |
| 92 EXPECT_TRUE(it1 < it2); |
| 93 EXPECT_FALSE(it2 <= it1); |
| 94 EXPECT_TRUE(it1 != it2); |
| 95 } |
| 96 EXPECT_EQ(kIteratorTestData[i + j], it1[j]); // Pseudo-pointer. |
| 97 EXPECT_EQ(kIteratorTestData[i + j], *it2); |
| 98 EXPECT_EQ(j, it2 - it1); |
| 99 EXPECT_EQ(it1, it2 - j); |
| 100 } |
| 101 EXPECT_TRUE(it1 < end); |
| 102 EXPECT_TRUE(it1 <= end); |
| 103 EXPECT_TRUE(it1 != end); |
| 104 } |
| 105 |
| 106 // Degenerate assignment from pointer: Result is always null, since pointer |
| 107 // assignments are added for compatibility with initialization to null. |
| 108 int dummy = 137; |
| 109 Iterator it_dummy = begin; |
| 110 it_dummy = &dummy; // Reassign to pointer. |
| 111 EXPECT_TRUE(it_dummy == nullptr); // Doesn't matter; store null anyway. |
| 112 |
| 113 // Test STL read-only usage. |
| 114 std::vector<std::iterator_traits<Iterator>::value_type> v(begin, 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(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 // Casting from non-const to const. |
| 172 TestPagedArray::iterator non_const_it = a.begin(); |
| 173 TestPagedArray::const_iterator const_it = non_const_it; |
| 174 |
| 175 // Pointer distance from non-const to const works. |
| 176 EXPECT_EQ(kIteratorTestDataSize, a.end() - a_const.begin()); |
| 177 // Don't have (and don't need) the converse. |
| 178 } |
| 179 |
| 180 // Test generic read-write of itrators by sorting pseudo-random numbers. |
| 181 TEST_F(PagedArrayTest, TestSort) { |
| 182 courgette::PagedArray<int> a; |
| 183 std::minstd_rand pseudo_rand_gen; // Deterministic, using defaults. |
| 184 for (size_t size : kSizeList) { |
| 185 std::vector<int32_t> v(size); |
| 186 courgette::PagedArray<int32_t, kLogBlockSizeSmall> a; |
| 187 EXPECT_TRUE(a.Allocate(size)); |
| 188 for (size_t i = 0; i < size; ++i) { |
| 189 v[i] = pseudo_rand_gen(); |
| 190 a[i] = v[i]; |
| 191 } |
| 192 std::sort(v.begin(), v.end()); |
| 193 std::sort(a.begin(), a.end()); |
| 194 for (size_t i = 0; i < size; ++i) |
| 195 EXPECT_EQ(v[i], a[i]); |
| 196 } |
| 197 } |
OLD | NEW |