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..251ea973c6da22ac9ebf225b004d8d8571f96318 100644 |
--- a/courgette/third_party/bsdiff/paged_array.h |
+++ b/courgette/third_party/bsdiff/paged_array.h |
@@ -11,32 +11,189 @@ |
#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; |
+ |
+// A random access iterator with pointer-like semantics, for PagedArray. |
+template <typename ContainerType, typename T> |
+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 { |
+#ifndef NDEBUG |
+ // For performance, skip the |array_| check in Release builds. |
+ if (array_ != it.array_) |
+ return false; |
+#endif |
+ return index_ < it.index_; |
+ } |
+ template <typename ContainerType2, typename T2> |
+ bool operator<=(const PagedArray_iterator<ContainerType2, T2>& it) const { |
+#ifndef NDEBUG |
+ // For performance, skip the |array_| check in Release builds. |
+ if (array_ != it.array_) |
+ return false; |
+#endif |
+ return index_ <= it.index_; |
+ } |
+ template <typename ContainerType2, typename T2> |
+ bool operator>(const PagedArray_iterator<ContainerType2, T2>& it) const { |
+#ifndef NDEBUG |
+ // For performance, skip the |array_| check in Release builds. |
+ if (array_ != it.array_) |
+ return false; |
+#endif |
+ return index_ > it.index_; |
+ } |
+ template <typename ContainerType2, typename T2> |
+ bool operator>=(const PagedArray_iterator<ContainerType2, T2>& it) const { |
+#ifndef NDEBUG |
+ // For performance, skip the |array_| check in Release builds. |
+ if (array_ != it.array_) |
+ return false; |
+#endif |
+ 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(); } |
+ 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.) |
+#ifndef NDEBUG |
+ // Without the #ifndef, DCHECK() will significaltly slow down bsdiff_create |
+ // even in optimized Release build (about 1.4x). |
+ DCHECK(page < page_count_); |
+#endif |
+ return pages_[page][offset]; |
+ } |
+ |
+ const T& operator[](size_t i) const { |
+ // Duplicating code here for performance. If we use common code for this |
+ // then bsdiff_create slows down by ~5% in optimized Release build. |
+ size_t page = i >> kLogPageSize; |
+ size_t offset = i & (kPageSize - 1); |
+#ifndef NDEBUG |
+ // Without the #ifndef, DCHECK() will significaltly slow down bsdiff_create |
+ // even in optimized Release build (about 1.4x). |
+ DCHECK(page < page_count_); |
+#endif |
return pages_[page][offset]; |
} |
@@ -44,7 +201,8 @@ class PagedArray { |
// 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 +222,24 @@ 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_; |
+ 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_ |