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

courgette/third_party/bsdiff/paged_array.h

 // Copyright (c) 2010 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 // PagedArray implements an array stored using many fixed-size pages.
 //
 // PagedArray is a work-around to allow large arrays to be allocated when there
 // is too much address space fragmentation for allocating the large arrays as
 // contiguous arrays.
 
 #ifndef COURGETTE_THIRD_PARTY_BSDIFF_PAGED_ARRAY_H_
 #define COURGETTE_THIRD_PARTY_BSDIFF_PAGED_ARRAY_H_
 
 #include <stddef.h>
 
+#include <iterator>
+
+#include "base/logging.h"
 #include "base/macros.h"
 #include "base/process/memory.h"
 
 namespace courgette {
 
+// Page size of 2^18 * sizeof(T) is 1MB for T = int32_t.
+constexpr int kPagedArrayDefaultPageLogSize = 18;
+
+template <typename T, int LOG_PAGE_SIZE = kPagedArrayDefaultPageLogSize>
+class PagedArray;
+
+template <typename T, int LOG_PAGE_SIZE = kPagedArrayDefaultPageLogSize>
+class PagedArray_const_iterator;
+
+template <typename T, int LOG_PAGE_SIZE = kPagedArrayDefaultPageLogSize>
+class PagedArray_iterator;
+
+}  // courgette
+
+namespace std {
+
+template <typename T, int LOG_PAGE_SIZE>
+struct iterator_traits<class courgette::PagedArray_iterator<T, LOG_PAGE_SIZE>> {

[etiennep, 2016/05/25 14:19:02]

We can declare these typedefs directly in the iterator class, and
iterator_traits does not need to be specialized. Optionally, we can get them by
making the iterator class derived from std::iterator<random_access_iterator_tag,
T>. 

[huangs, 2016/05/25 19:36:42]

Went with directly declaring, using "using".

+  typedef ptrdiff_t difference_type;
+  typedef T value_type;
+  typedef T& reference;
+  typedef T* pointer;
+  typedef random_access_iterator_tag iterator_category;
+};
+
+template <typename T, int LOG_PAGE_SIZE>
+struct iterator_traits<
+    class courgette::PagedArray_const_iterator<T, LOG_PAGE_SIZE>> {
+  typedef ptrdiff_t difference_type;
+  typedef T value_type;
+  typedef const T& reference;
+  typedef const T* pointer;
+  typedef random_access_iterator_tag iterator_category;
+};
+
+}  // namespace std
+
+namespace courgette {
+
+template <typename T, int LOG_PAGE_SIZE>
+class PagedArray_const_iterator {

[etiennep, 2016/05/25 14:19:01]

This does a lot of duplicate code. I don't think we need to define two
iterators. ContainerType could be injected through a template parameter. We can
then define iterators in PagedArray class as
const_iterator = PagedArray_iterator<const PagedArray, const T, LOG_PAGE_SIZE>;
iterator = PagedArray_iterator<PagedArray, T, LOG_PAGE_SIZE>;

[huangs, 2016/05/25 19:36:42]

For this revision, went with the standard way of defining const iterator with
mutable element, then have non-const iterator inherited class.  Still have to
implement many operators though.

Maybe the way you described is more modern, and should try that next? Does it
allow one-way cast from non-const to const?

+ public:
+  using ContainerType = PagedArray<T, LOG_PAGE_SIZE>;
+  using ConstItType = PagedArray_const_iterator<T, LOG_PAGE_SIZE>;
+
+  PagedArray_const_iterator() : array_(nullptr), index_(0U) { }
+
+  PagedArray_const_iterator(const ContainerType* array, size_t index)
+      : array_(array), index_(index) { }
+
+  PagedArray_const_iterator(const PagedArray_const_iterator&) = default;
+
+  PagedArray_const_iterator(void*)
+      : array_(nullptr), index_(0) { }
+
+  ~PagedArray_const_iterator() { }
+
+  const T& operator*() const { return (*array_)[index_]; }
+
+  const T& operator[](size_t idx) const { return (*array_)[index_ + idx]; }
+
+  ConstItType& operator++() {
+    ++index_;
+    return *this;
+  }
+
+  ConstItType& operator--() {
+    --index_;
+    return *this;
+  }
+
+  ConstItType operator++(int) { return ConstItType(array_, index_++); }
+  ConstItType operator--(int) { return ConstItType(array_, index_--); }
+
+  ConstItType operator+=(size_t delta) {

[etiennep, 2016/05/25 14:19:01]

NIT: the iterator concept requires delta to be difference_type (std::ptrdiff_t)

[huangs, 2016/05/25 19:36:42]

Done.

+    return ConstItType(array_, index_ += delta);
+  }
+  ConstItType operator-=(size_t delta) {
+    return ConstItType(array_, index_ -= delta);
+  }
+
+  ConstItType operator+(size_t offset) {
+    return ConstItType(array_, index_ + offset);
+  }
+  ConstItType operator-(size_t offset) {
+    return ConstItType(array_, index_ - offset);
+  }
+
+  bool operator==(const ConstItType& it) const {
+    return index_ == it.index_ && array_ == it.array_;
+  }
+  bool operator!=(const ConstItType& it) const {

[etiennep, 2016/05/25 14:19:02]

The implementation could be {return !(*this == it);} 

[huangs, 2016/05/25 19:36:42]

Done.

+    return index_ != it.index_ || array_ != it.array_;
+  }
+
+  bool operator<(const ConstItType& it) const {
+    // Not bothering to check array_, for performance.
+    return index_ < it.index_;
+  }
+  bool operator<=(const ConstItType& it) const {
+    // Not bothering to check array_, for performance.
+    return index_ <= it.index_;
+  }
+
+  ptrdiff_t operator-(const ConstItType& it) const {
+    return index_ - it.index_;
+  }
+
+ private:
+  friend PagedArray_iterator<T, LOG_PAGE_SIZE>;
+
+  const ContainerType* array_;
+  size_t index_;
+};
+
+// RandomAccessIterator for PagedArray<T> to enable std::sort().
+template <typename T, int LOG_PAGE_SIZE>
+class PagedArray_iterator {
+ public:
+  using ContainerType = PagedArray<T, LOG_PAGE_SIZE>;
+  using ItType = PagedArray_iterator<T, LOG_PAGE_SIZE>;
+  using ConstItType = PagedArray_const_iterator<T, LOG_PAGE_SIZE>;

[etiennep, 2016/05/25 14:19:01]

If you were to merge both iterator, we can get ConstItType with
PagedArray_const_iterator<
  typename add_const<ContainerType>::type,
  typename add_const<T>::type, 
  LOG_PAGE_SIZE>

Even if ConstItType is the same type as the iterator itself, conversion operator
overload works in any case.

[huangs, 2016/05/25 19:36:42]

May try this next.  So conversion operator will seamlessly handle non-const to
const cast, and raise error if we try the reverse?

+
+  PagedArray_iterator() : array_(nullptr), index_(0U) { }
+
+  PagedArray_iterator(ContainerType* array, size_t index)
+      : array_(array), index_(index) { }
+
+  PagedArray_iterator(const PagedArray_iterator&) = default;
+
+  ~PagedArray_iterator() { }

[etiennep, 2016/05/25 14:19:02]

Would be more consistent = default

[huangs, 2016/05/25 19:36:42]

Done.

+
+  operator ConstItType() { return ConstItType(array_, index_); }
+
+  const T& operator*() const { return (*array_)[index_]; }
+  T& operator*() { return (*array_)[index_]; }
+

[etiennep, 2016/05/25 14:19:01]

We could put operator-> as it is a requirement for iterators (it would probably
never be used though)

[huangs, 2016/05/25 19:36:42]

Added, with tests.

+  const T& operator[](size_t idx) const { return (*array_)[index_ + idx]; }

[etiennep, 2016/05/25 14:19:01]

Not very useful. A const-qualified iterator (could not increment) does not mean
data is const.

[huangs, 2016/05/25 19:36:42]

Good point; removed!

Also removing const T& operator*().

And adding "const" to functions that don't affect the iterator itself (but
perhaps the data it points to).

+  T& operator[](size_t idx) { return (*array_)[index_ + idx]; }
+
+  ItType& operator++() {
+    ++index_;
+    return *this;
+  }
+
+  ItType& operator--() {
+    --index_;
+    return *this;
+  }
+
+  ItType operator++(int) { return ItType(array_, index_++); }
+  ItType operator--(int) { return ItType(array_, index_--); }
+
+  ItType operator+=(size_t delta) { return ItType(array_, index_ += delta); }
+  ItType operator-=(size_t delta) { return ItType(array_, index_ -= delta); }
+
+  ItType operator+(size_t offset) { return ItType(array_, index_ + offset); }
+  ItType operator-(size_t offset) { return ItType(array_, index_ - offset); }
+
+  // Only useful for assigning nullptr.
+  ItType& operator=(void*) {

[etiennep, 2016/05/25 14:19:01]

The arguments should be std::nullptr_t instead.

[huangs, 2016/05/25 19:36:42]

Done.

+    array_ = nullptr;
+    index_ = 0;
+    return *this;
+  }
+
+  bool operator==(const ItType& it) const {
+    return index_ == it.index_ && array_ == it.array_;
+  }
+
+  // Only intended for comparing against nullptr.
+  bool operator==(const void* p) const {

[etiennep, 2016/05/25 14:19:02]

std::nullptr_t again. There would be non need to check.

[huangs, 2016/05/25 19:36:42]

Done.

+    DCHECK_EQ(nullptr, p);
+    return index_ == 0 && array_ == p;
+  }
+
+  bool operator!=(const ItType& it) const {
+    return index_ != it.index_ || array_ != it.array_;
+  }
+
+  bool operator<(const ItType& it) const {
+    // Not bothering to check array_, for performance.
+    return index_ < it.index_;
+  }
+  bool operator<=(const ItType& it) const {
+    // Not bothering to check array_, for performance.
+    return index_ <= it.index_;
+  }
+
+  ptrdiff_t operator-(const ItType& it) const {
+    return index_ - it.index_;
+  }
+
+  ptrdiff_t operator-(const ConstItType& it) const {
+    return index_ - it.index_;
+  }
+
+ private:
+  ContainerType* array_;
+  size_t index_;
+};
+
 // PagedArray implements an array stored using many fixed-size pages.
-template <typename T>
+template <typename T, int LOG_PAGE_SIZE>
 class PagedArray {
   enum {
-    // Page size in elements.  Page size of 2^18 * sizeof(T) is 1MB for T = int.
-    kLogPageSize = 18,
-    kPageSize = 1 << kLogPageSize
+    // Page size in elements.
+    kLogPageSize = LOG_PAGE_SIZE,
+    kPageSize = 1 << LOG_PAGE_SIZE
   };
 
  public:
-  PagedArray() : pages_(NULL), page_count_(0) {}
-
+  typedef PagedArray_const_iterator<T, LOG_PAGE_SIZE> const_iterator;
+  typedef PagedArray_iterator<T, LOG_PAGE_SIZE> iterator;
+
+  PagedArray() { }
   ~PagedArray() { clear(); }
 
+  iterator begin() { return iterator(this, 0); }
+  iterator end() { return iterator(this, size_); }
+  const_iterator begin() const { return const_iterator(this, 0); }
+  const_iterator end() const { return const_iterator(this, size_); }
+
   T& operator[](size_t i) {
     size_t page = i >> kLogPageSize;
     size_t offset = i & (kPageSize - 1);
     // It is tempting to add a DCHECK(page < page_count_), but that makes
     // bsdiff_create run 2x slower (even when compiled optimized.)
     return pages_[page][offset];
   }
 
+  const T& operator[](size_t i) const {

[etiennep, 2016/05/25 14:19:01]

This is me asking : If PagedArray is meant to support array bigger than 4GB on
32bit systems, wouldn't size_t (probably equivalent to uint32_t) overflow anyway
(I'm guessing i'm wrong because it is being used in bsdiff, but why)?

[huangs, 2016/05/25 19:36:42]

PagedArray is meant to solve memory fragmentation problem; otherwise we'll need
1 GB of consecutive memory address, and that's likely to be unavailable.

+    size_t page = i >> kLogPageSize;
+    size_t offset = i & (kPageSize - 1);
+    // It is tempting to add a DCHECK(page < page_count_), but that makes
+    // bsdiff_create run 2x slower (even when compiled optimized.)
+    return pages_[page][offset];
+  }
+
   // Allocates storage for |size| elements. Returns true on success and false if
   // allocation fails.
   bool Allocate(size_t size) {
     clear();
-    size_t pages_needed = (size + kPageSize - 1) >> kLogPageSize;
+    size_ = size;
+    size_t pages_needed = (size_ + kPageSize - 1) >> kLogPageSize;
     if (!base::UncheckedMalloc(sizeof(T*) * pages_needed,
                                reinterpret_cast<void**>(&pages_))) {
       return false;
     }
 
     for (page_count_ = 0; page_count_ < pages_needed; ++page_count_) {
       T* block = nullptr;
       if (!base::UncheckedMalloc(sizeof(T) * kPageSize,
                                  reinterpret_cast<void**>(&block))) {
         clear();
         return false;
       }
       pages_[page_count_] = block;
     }
     return true;
   }
 
   // Releases all storage.  May be called more than once.
   void clear() {
-    if (pages_ != NULL) {
+    if (pages_ != nullptr) {
       while (page_count_ != 0) {
         --page_count_;
         free(pages_[page_count_]);
       }
       free(pages_);
-      pages_ = NULL;
+      pages_ = nullptr;
     }
   }
 
  private:
-  T** pages_;
-  size_t page_count_;
+  T** pages_ = nullptr;
+  size_t size_ = 0U;
+  size_t page_count_ = 0U;
 
   DISALLOW_COPY_AND_ASSIGN(PagedArray);
 };
 
 }  // namespace courgette
+
 #endif  // COURGETTE_THIRD_PARTY_BSDIFF_PAGED_ARRAY_H_