Index: courgette/third_party/bsdiff/paged_array.h |
diff --git a/courgette/third_party/bsdiff/paged_array.h b/courgette/third_party/bsdiff/paged_array.h |
index 27c3c0b37db7fbfce7038aed7728f7a333477526..fbe902c53296282484ab366bf680de75e0d85fc2 100644 |
--- a/courgette/third_party/bsdiff/paged_array.h |
+++ b/courgette/third_party/bsdiff/paged_array.h |
@@ -11,40 +11,150 @@ |
#ifndef COURGETTE_THIRD_PARTY_BSDIFF_PAGED_ARRAY_H_ |
#define COURGETTE_THIRD_PARTY_BSDIFF_PAGED_ARRAY_H_ |
-#include <stddef.h> |
+#include <cstddef> |
+#include <iterator> |
+#include <type_traits> |
+#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 ContainerType, typename T> |
chrisha
2016/05/31 20:15:17
A class comment would be nice: ie, this provides a
huangs
2016/06/01 22:07:29
Done.
|
+class PagedArray_iterator { |
+ public: |
+ using ThisType = PagedArray_iterator<ContainerType, T>; |
+ using difference_type = ptrdiff_t; |
+ using value_type = typename std::remove_const<T>::type; |
+ using reference = T&; |
+ using pointer = T*; |
+ using iterator_category = std::random_access_iterator_tag; |
+ |
+ PagedArray_iterator() : array_(nullptr), index_(0U) {} |
+ PagedArray_iterator(ContainerType* array, size_t index) |
+ : array_(array), index_(index) {} |
+ |
+ template <typename ContainerType2, typename T2> |
+ PagedArray_iterator(const PagedArray_iterator<ContainerType2, T2>& it) |
+ : array_(it.array_), index_(it.index_) {} |
+ |
+ PagedArray_iterator(std::nullptr_t) : array_(nullptr), index_(0) {} |
+ |
+ ~PagedArray_iterator() = default; |
+ |
+ reference operator*() const { return (*array_)[index_]; } |
+ reference operator[](size_t idx) const { return (*array_)[index_ + idx]; } |
+ pointer operator->() const { return &(*array_)[index_]; } |
+ |
+ ThisType& operator=(std::nullptr_t) { |
+ array_ = nullptr; |
+ index_ = 0; |
+ return *this; |
+ } |
+ |
+ ThisType& operator++() { |
+ ++index_; |
+ return *this; |
+ } |
+ ThisType& operator--() { |
+ --index_; |
+ return *this; |
+ } |
+ |
+ ThisType operator++(int) { return ThisType(array_, index_++); } |
+ ThisType operator--(int) { return ThisType(array_, index_--); } |
+ |
+ ThisType& operator+=(difference_type delta) { |
+ index_ += delta; |
+ return *this; |
+ } |
+ ThisType& operator-=(difference_type delta) { |
+ index_ -= delta; |
+ return *this; |
+ } |
+ |
+ ThisType operator+(difference_type offset) const { |
+ return ThisType(array_, index_ + offset); |
+ } |
+ ThisType operator-(difference_type offset) const { |
+ return ThisType(array_, index_ - offset); |
+ } |
+ |
+ template <typename ContainerType2, typename T2> |
+ bool operator==(const PagedArray_iterator<ContainerType2, T2>& it) const { |
+ return index_ == it.index_ && array_ == it.array_; |
+ } |
+ bool operator==(std::nullptr_t) const { |
+ return index_ == 0 && array_ == nullptr; |
+ } |
+ template <typename ContainerType2, typename T2> |
+ bool operator!=(const PagedArray_iterator<ContainerType2, T2>& it) const { |
+ return !(*this == it); |
+ } |
+ |
+ template <typename ContainerType2, typename T2> |
+ bool operator<(const PagedArray_iterator<ContainerType2, T2>& it) const { |
+ // Not bothering to check array_, for performance. |
chrisha
2016/05/31 20:15:16
Could put such a check behind #ifdef DEBUG or #ifn
huangs
2016/06/01 22:07:30
Done.
|
+ return index_ < it.index_; |
+ } |
+ template <typename ContainerType2, typename T2> |
+ bool operator<=(const PagedArray_iterator<ContainerType2, T2>& it) const { |
+ // Not bothering to check array_, for performance. |
chrisha
2016/05/31 20:15:16
Ditto
huangs
2016/06/01 22:07:29
Done.
|
+ return index_ <= it.index_; |
+ } |
+ |
+ template <typename ContainerType2, typename T2> |
+ difference_type operator-( |
+ const PagedArray_iterator<ContainerType2, T2>& it) const { |
+ return index_ - it.index_; |
+ } |
+ |
+ private: |
+ template <typename, typename> |
+ friend class PagedArray_iterator; |
+ |
+ 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) {} |
+ using ThisType = PagedArray<T, LOG_PAGE_SIZE>; |
+ using const_iterator = PagedArray_iterator<const ThisType, const T>; |
+ using iterator = PagedArray_iterator<ThisType, T>; |
+ PagedArray() = default; |
~PagedArray() { clear(); } |
- 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]; |
- } |
+ 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) { return at(i); } |
+ const T& operator[](size_t i) const { return at(i); } |
// 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; |
@@ -64,22 +174,32 @@ class PagedArray { |
// 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_; |
+ inline T& at(size_t i) const { |
+ 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.) |
chrisha
2016/05/31 20:15:16
Ditto
huangs
2016/06/01 22:07:29
Done. Remeasured impact of DCHECK on Release: Abou
|
+ return pages_[page][offset]; |
+ } |
+ |
+ 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_ |