OLD | NEW |
1 // Copyright (c) 2010 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2010 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 // PagedArray implements an array stored using many fixed-size pages. | 5 // PagedArray implements an array stored using many fixed-size pages. |
6 // | 6 // |
7 // PagedArray is a work-around to allow large arrays to be allocated when there | 7 // PagedArray is a work-around to allow large arrays to be allocated when there |
8 // is too much address space fragmentation for allocating the large arrays as | 8 // is too much address space fragmentation for allocating the large arrays as |
9 // contiguous arrays. | 9 // contiguous arrays. |
10 | 10 |
11 #ifndef COURGETTE_THIRD_PARTY_BSDIFF_PAGED_ARRAY_H_ | 11 #ifndef COURGETTE_THIRD_PARTY_BSDIFF_PAGED_ARRAY_H_ |
12 #define COURGETTE_THIRD_PARTY_BSDIFF_PAGED_ARRAY_H_ | 12 #define COURGETTE_THIRD_PARTY_BSDIFF_PAGED_ARRAY_H_ |
13 | 13 |
14 #include <stddef.h> | 14 #include <cstddef> |
| 15 #include <iterator> |
| 16 #include <type_traits> |
15 | 17 |
| 18 #include "base/logging.h" |
16 #include "base/macros.h" | 19 #include "base/macros.h" |
17 #include "base/process/memory.h" | 20 #include "base/process/memory.h" |
18 | 21 |
19 namespace courgette { | 22 namespace courgette { |
20 | 23 |
| 24 // Page size of 2^18 * sizeof(T) is 1MB for T = int32_t. |
| 25 constexpr int kPagedArrayDefaultPageLogSize = 18; |
| 26 |
| 27 template <typename T, int LOG_PAGE_SIZE = kPagedArrayDefaultPageLogSize> |
| 28 class PagedArray; |
| 29 |
| 30 // A random access iterator with pointer-like semantics, for PagedArray. |
| 31 template <typename ContainerType, typename T> |
| 32 class PagedArray_iterator { |
| 33 public: |
| 34 using ThisType = PagedArray_iterator<ContainerType, T>; |
| 35 using difference_type = ptrdiff_t; |
| 36 using value_type = typename std::remove_const<T>::type; |
| 37 using reference = T&; |
| 38 using pointer = T*; |
| 39 using iterator_category = std::random_access_iterator_tag; |
| 40 |
| 41 PagedArray_iterator() : array_(nullptr), index_(0U) {} |
| 42 PagedArray_iterator(ContainerType* array, size_t index) |
| 43 : array_(array), index_(index) {} |
| 44 |
| 45 template <typename ContainerType2, typename T2> |
| 46 PagedArray_iterator(const PagedArray_iterator<ContainerType2, T2>& it) |
| 47 : array_(it.array_), index_(it.index_) {} |
| 48 |
| 49 PagedArray_iterator(std::nullptr_t) : array_(nullptr), index_(0) {} |
| 50 |
| 51 ~PagedArray_iterator() = default; |
| 52 |
| 53 reference operator*() const { return (*array_)[index_]; } |
| 54 reference operator[](size_t idx) const { return (*array_)[index_ + idx]; } |
| 55 pointer operator->() const { return &(*array_)[index_]; } |
| 56 |
| 57 ThisType& operator=(std::nullptr_t) { |
| 58 array_ = nullptr; |
| 59 index_ = 0; |
| 60 return *this; |
| 61 } |
| 62 |
| 63 ThisType& operator++() { |
| 64 ++index_; |
| 65 return *this; |
| 66 } |
| 67 ThisType& operator--() { |
| 68 --index_; |
| 69 return *this; |
| 70 } |
| 71 |
| 72 ThisType operator++(int) { return ThisType(array_, index_++); } |
| 73 ThisType operator--(int) { return ThisType(array_, index_--); } |
| 74 |
| 75 ThisType& operator+=(difference_type delta) { |
| 76 index_ += delta; |
| 77 return *this; |
| 78 } |
| 79 ThisType& operator-=(difference_type delta) { |
| 80 index_ -= delta; |
| 81 return *this; |
| 82 } |
| 83 |
| 84 ThisType operator+(difference_type offset) const { |
| 85 return ThisType(array_, index_ + offset); |
| 86 } |
| 87 ThisType operator-(difference_type offset) const { |
| 88 return ThisType(array_, index_ - offset); |
| 89 } |
| 90 |
| 91 template <typename ContainerType2, typename T2> |
| 92 bool operator==(const PagedArray_iterator<ContainerType2, T2>& it) const { |
| 93 return index_ == it.index_ && array_ == it.array_; |
| 94 } |
| 95 bool operator==(std::nullptr_t) const { |
| 96 return index_ == 0 && array_ == nullptr; |
| 97 } |
| 98 template <typename ContainerType2, typename T2> |
| 99 bool operator!=(const PagedArray_iterator<ContainerType2, T2>& it) const { |
| 100 return !(*this == it); |
| 101 } |
| 102 |
| 103 template <typename ContainerType2, typename T2> |
| 104 bool operator<(const PagedArray_iterator<ContainerType2, T2>& it) const { |
| 105 #ifndef NDEBUG |
| 106 // For performance, skip the |array_| check in Release builds. |
| 107 if (array_ != it.array_) |
| 108 return false; |
| 109 #endif |
| 110 return index_ < it.index_; |
| 111 } |
| 112 template <typename ContainerType2, typename T2> |
| 113 bool operator<=(const PagedArray_iterator<ContainerType2, T2>& it) const { |
| 114 #ifndef NDEBUG |
| 115 // For performance, skip the |array_| check in Release builds. |
| 116 if (array_ != it.array_) |
| 117 return false; |
| 118 #endif |
| 119 return index_ <= it.index_; |
| 120 } |
| 121 template <typename ContainerType2, typename T2> |
| 122 bool operator>(const PagedArray_iterator<ContainerType2, T2>& it) const { |
| 123 #ifndef NDEBUG |
| 124 // For performance, skip the |array_| check in Release builds. |
| 125 if (array_ != it.array_) |
| 126 return false; |
| 127 #endif |
| 128 return index_ > it.index_; |
| 129 } |
| 130 template <typename ContainerType2, typename T2> |
| 131 bool operator>=(const PagedArray_iterator<ContainerType2, T2>& it) const { |
| 132 #ifndef NDEBUG |
| 133 // For performance, skip the |array_| check in Release builds. |
| 134 if (array_ != it.array_) |
| 135 return false; |
| 136 #endif |
| 137 return index_ >= it.index_; |
| 138 } |
| 139 |
| 140 template <typename ContainerType2, typename T2> |
| 141 difference_type operator-( |
| 142 const PagedArray_iterator<ContainerType2, T2>& it) const { |
| 143 return index_ - it.index_; |
| 144 } |
| 145 |
| 146 private: |
| 147 template <typename, typename> |
| 148 friend class PagedArray_iterator; |
| 149 |
| 150 ContainerType* array_; |
| 151 size_t index_; |
| 152 }; |
| 153 |
21 // PagedArray implements an array stored using many fixed-size pages. | 154 // PagedArray implements an array stored using many fixed-size pages. |
22 template <typename T> | 155 template <typename T, int LOG_PAGE_SIZE> |
23 class PagedArray { | 156 class PagedArray { |
24 enum { | 157 enum { |
25 // Page size in elements. Page size of 2^18 * sizeof(T) is 1MB for T = int. | 158 // Page size in elements. |
26 kLogPageSize = 18, | 159 kLogPageSize = LOG_PAGE_SIZE, |
27 kPageSize = 1 << kLogPageSize | 160 kPageSize = 1 << LOG_PAGE_SIZE |
28 }; | 161 }; |
29 | 162 |
30 public: | 163 public: |
31 PagedArray() : pages_(NULL), page_count_(0) {} | 164 using ThisType = PagedArray<T, LOG_PAGE_SIZE>; |
| 165 using const_iterator = PagedArray_iterator<const ThisType, const T>; |
| 166 using iterator = PagedArray_iterator<ThisType, T>; |
32 | 167 |
| 168 PagedArray() = default; |
33 ~PagedArray() { clear(); } | 169 ~PagedArray() { clear(); } |
34 | 170 |
| 171 iterator begin() { return iterator(this, 0); } |
| 172 iterator end() { return iterator(this, size_); } |
| 173 const_iterator begin() const { return const_iterator(this, 0); } |
| 174 const_iterator end() const { return const_iterator(this, size_); } |
| 175 |
35 T& operator[](size_t i) { | 176 T& operator[](size_t i) { |
36 size_t page = i >> kLogPageSize; | 177 size_t page = i >> kLogPageSize; |
37 size_t offset = i & (kPageSize - 1); | 178 size_t offset = i & (kPageSize - 1); |
38 // It is tempting to add a DCHECK(page < page_count_), but that makes | 179 #ifndef NDEBUG |
39 // bsdiff_create run 2x slower (even when compiled optimized.) | 180 // Without the #ifndef, DCHECK() will significaltly slow down bsdiff_create |
| 181 // even in optimized Release build (about 1.4x). |
| 182 DCHECK(page < page_count_); |
| 183 #endif |
40 return pages_[page][offset]; | 184 return pages_[page][offset]; |
41 } | 185 } |
42 | 186 |
| 187 const T& operator[](size_t i) const { |
| 188 // Duplicating code here for performance. If we use common code for this |
| 189 // then bsdiff_create slows down by ~5% in optimized Release build. |
| 190 size_t page = i >> kLogPageSize; |
| 191 size_t offset = i & (kPageSize - 1); |
| 192 #ifndef NDEBUG |
| 193 // Without the #ifndef, DCHECK() will significaltly slow down bsdiff_create |
| 194 // even in optimized Release build (about 1.4x). |
| 195 DCHECK(page < page_count_); |
| 196 #endif |
| 197 return pages_[page][offset]; |
| 198 } |
| 199 |
43 // Allocates storage for |size| elements. Returns true on success and false if | 200 // Allocates storage for |size| elements. Returns true on success and false if |
44 // allocation fails. | 201 // allocation fails. |
45 bool Allocate(size_t size) { | 202 bool Allocate(size_t size) { |
46 clear(); | 203 clear(); |
47 size_t pages_needed = (size + kPageSize - 1) >> kLogPageSize; | 204 size_ = size; |
| 205 size_t pages_needed = (size_ + kPageSize - 1) >> kLogPageSize; |
48 if (!base::UncheckedMalloc(sizeof(T*) * pages_needed, | 206 if (!base::UncheckedMalloc(sizeof(T*) * pages_needed, |
49 reinterpret_cast<void**>(&pages_))) { | 207 reinterpret_cast<void**>(&pages_))) { |
50 return false; | 208 return false; |
51 } | 209 } |
52 | 210 |
53 for (page_count_ = 0; page_count_ < pages_needed; ++page_count_) { | 211 for (page_count_ = 0; page_count_ < pages_needed; ++page_count_) { |
54 T* block = nullptr; | 212 T* block = nullptr; |
55 if (!base::UncheckedMalloc(sizeof(T) * kPageSize, | 213 if (!base::UncheckedMalloc(sizeof(T) * kPageSize, |
56 reinterpret_cast<void**>(&block))) { | 214 reinterpret_cast<void**>(&block))) { |
57 clear(); | 215 clear(); |
58 return false; | 216 return false; |
59 } | 217 } |
60 pages_[page_count_] = block; | 218 pages_[page_count_] = block; |
61 } | 219 } |
62 return true; | 220 return true; |
63 } | 221 } |
64 | 222 |
65 // Releases all storage. May be called more than once. | 223 // Releases all storage. May be called more than once. |
66 void clear() { | 224 void clear() { |
67 if (pages_ != NULL) { | 225 if (pages_ != nullptr) { |
68 while (page_count_ != 0) { | 226 while (page_count_ != 0) { |
69 --page_count_; | 227 --page_count_; |
70 free(pages_[page_count_]); | 228 free(pages_[page_count_]); |
71 } | 229 } |
72 free(pages_); | 230 free(pages_); |
73 pages_ = NULL; | 231 pages_ = nullptr; |
74 } | 232 } |
75 } | 233 } |
76 | 234 |
77 private: | 235 private: |
78 T** pages_; | 236 T** pages_ = nullptr; |
79 size_t page_count_; | 237 size_t size_ = 0U; |
| 238 size_t page_count_ = 0U; |
80 | 239 |
81 DISALLOW_COPY_AND_ASSIGN(PagedArray); | 240 DISALLOW_COPY_AND_ASSIGN(PagedArray); |
82 }; | 241 }; |
83 | 242 |
84 } // namespace courgette | 243 } // namespace courgette |
| 244 |
85 #endif // COURGETTE_THIRD_PARTY_BSDIFF_PAGED_ARRAY_H_ | 245 #endif // COURGETTE_THIRD_PARTY_BSDIFF_PAGED_ARRAY_H_ |
OLD | NEW |