[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..06043beba5c44aaa7628f6e07f6082fc27cb73d5 100644
--- a/courgette/third_party/bsdiff/paged_array_unittest.cc
+++ b/courgette/third_party/bsdiff/paged_array_unittest.cc
@@ -4,14 +4,117 @@
 
 #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(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 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_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(it2 < it1);
+        if (j > 0) {
+          EXPECT_TRUE(it1 < it2);
+          EXPECT_FALSE(it2 <= it1);
+          EXPECT_TRUE(it1 != it2);
+        }
+        EXPECT_EQ(kIteratorTestData[i + j], it1[j]);  // Pseudo-pointer.
+        EXPECT_EQ(kIteratorTestData[i + j], *it2);
+        EXPECT_EQ(j, it2 - it1);
+        EXPECT_EQ(it1, it2 - j);
+      }
+      EXPECT_TRUE(it1 < end);
+      EXPECT_TRUE(it1 <= end);
+      EXPECT_TRUE(it1 != end);
+    }
+
+    // Degenerate assignment from pointer: Result is always null, since pointer
+    // assignments are added for compatibility with initialization to null.
+    int dummy = 137;
+    Iterator it_dummy = begin;
+    it_dummy = &dummy;  // Reassign to pointer.
+    EXPECT_TRUE(it_dummy == nullptr);  // Doesn't matter; store null anyway.
+
+    // Test STL read-only usage.
+    std::vector<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 +123,75 @@ 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(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());
+
+  // Casting from non-const to const.
+  TestPagedArray::iterator non_const_it = a.begin();
+  TestPagedArray::const_iterator const_it = non_const_it;
+
+  // Pointer distance from non-const to const works.
+  EXPECT_EQ(kIteratorTestDataSize, a.end() - a_const.begin());
+  // Don't have (and don't need) the converse.
+}
+
+// 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]);
   }
 }