[Courgette] PagedArray: Add Iterators and Parametrize Page Size as int Template.

courgette/third_party/bsdiff/paged_array_unittest.cc

Index: courgette/third_party/bsdiff/paged_array_unittest.cc
diff --git a/courgette/third_party/bsdiff/paged_array_unittest.cc b/courgette/third_party/bsdiff/paged_array_unittest.cc
index 7ae4f1c7888088c93ef4682cc3c911a785e7872c..17edde59dca92c6caca9353680a2a99b4cc9f3ff 100644
--- a/courgette/third_party/bsdiff/paged_array_unittest.cc
+++ b/courgette/third_party/bsdiff/paged_array_unittest.cc
@@ -4,14 +4,132 @@
 
 #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 {
+
+// 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
+
+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:
-  // Total allocation of 4GB will fail in 32 bit programs if allocations are
-  // leaked.
-  static const int kIterations = 20;
-  static const int kSize = 200 * 1024 * 1024 / sizeof(int);  // 200MB
+  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
@@ -20,27 +138,109 @@ class PagedArrayTest : public testing::Test {
 TEST_F(PagedArrayTest, TestManyAllocationsDestructorFree) {
   for (int i = 0; i < kIterations; ++i) {
     courgette::PagedArray<int> a;
-    EXPECT_TRUE(a.Allocate(kSize));
+    EXPECT_TRUE(a.Allocate(kSizeBig));
   }
 }
 
 TEST_F(PagedArrayTest, TestManyAllocationsManualFree) {
   courgette::PagedArray<int> a;
   for (int i = 0; i < kIterations; ++i) {
-    EXPECT_TRUE(a.Allocate(kSize));
+    EXPECT_TRUE(a.Allocate(kSizeBig));
     a.clear();
   }
 }
 #endif
 
 TEST_F(PagedArrayTest, TestAccess) {
-  const int kAccessSize = 3 * 1024 * 1024;
-  courgette::PagedArray<int> a;
-  a.Allocate(kAccessSize);
-  for (int i = 0; i < kAccessSize; ++i) {
-    a[i] = i;
+  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]);
   }
-  for (int i = 0; i < kAccessSize; ++i) {
-    EXPECT_EQ(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]);
   }
 }