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..a06c97c2f4cfdff339751bcaf85c462b5c401dbc 100644 |
--- a/courgette/third_party/bsdiff/paged_array.h |
+++ b/courgette/third_party/bsdiff/paged_array.h |
@@ -13,25 +13,237 @@ |
#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 iter
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 w
huangs
2016/05/25 19:36:42
For this revision, went with the standard way of d
|
+ 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 dif
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 Con
huangs
2016/05/25 19:36:42
May try this next. So conversion operator will se
|
+ |
+ 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
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
huangs
2016/05/25 19:36:42
Good point; removed!
Also removing const T& opera
|
+ 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 c
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); |
@@ -40,11 +252,20 @@ class PagedArray { |
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 supp
huangs
2016/05/25 19:36:42
PagedArray is meant to solve memory fragmentation
|
+ 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; |
@@ -64,22 +285,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_ |