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 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.
| |
31 class PagedArray_iterator { | |
32 public: | |
33 using ThisType = PagedArray_iterator<ContainerType, T>; | |
34 using difference_type = ptrdiff_t; | |
35 using value_type = typename std::remove_const<T>::type; | |
36 using reference = T&; | |
37 using pointer = T*; | |
38 using iterator_category = std::random_access_iterator_tag; | |
39 | |
40 PagedArray_iterator() : array_(nullptr), index_(0U) {} | |
41 PagedArray_iterator(ContainerType* array, size_t index) | |
42 : array_(array), index_(index) {} | |
43 | |
44 template <typename ContainerType2, typename T2> | |
45 PagedArray_iterator(const PagedArray_iterator<ContainerType2, T2>& it) | |
46 : array_(it.array_), index_(it.index_) {} | |
47 | |
48 PagedArray_iterator(std::nullptr_t) : array_(nullptr), index_(0) {} | |
49 | |
50 ~PagedArray_iterator() = default; | |
51 | |
52 reference operator*() const { return (*array_)[index_]; } | |
53 reference operator[](size_t idx) const { return (*array_)[index_ + idx]; } | |
54 pointer operator->() const { return &(*array_)[index_]; } | |
55 | |
56 ThisType& operator=(std::nullptr_t) { | |
57 array_ = nullptr; | |
58 index_ = 0; | |
59 return *this; | |
60 } | |
61 | |
62 ThisType& operator++() { | |
63 ++index_; | |
64 return *this; | |
65 } | |
66 ThisType& operator--() { | |
67 --index_; | |
68 return *this; | |
69 } | |
70 | |
71 ThisType operator++(int) { return ThisType(array_, index_++); } | |
72 ThisType operator--(int) { return ThisType(array_, index_--); } | |
73 | |
74 ThisType& operator+=(difference_type delta) { | |
75 index_ += delta; | |
76 return *this; | |
77 } | |
78 ThisType& operator-=(difference_type delta) { | |
79 index_ -= delta; | |
80 return *this; | |
81 } | |
82 | |
83 ThisType operator+(difference_type offset) const { | |
84 return ThisType(array_, index_ + offset); | |
85 } | |
86 ThisType operator-(difference_type offset) const { | |
87 return ThisType(array_, index_ - offset); | |
88 } | |
89 | |
90 template <typename ContainerType2, typename T2> | |
91 bool operator==(const PagedArray_iterator<ContainerType2, T2>& it) const { | |
92 return index_ == it.index_ && array_ == it.array_; | |
93 } | |
94 bool operator==(std::nullptr_t) const { | |
95 return index_ == 0 && array_ == nullptr; | |
96 } | |
97 template <typename ContainerType2, typename T2> | |
98 bool operator!=(const PagedArray_iterator<ContainerType2, T2>& it) const { | |
99 return !(*this == it); | |
100 } | |
101 | |
102 template <typename ContainerType2, typename T2> | |
103 bool operator<(const PagedArray_iterator<ContainerType2, T2>& it) const { | |
104 // 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.
| |
105 return index_ < it.index_; | |
106 } | |
107 template <typename ContainerType2, typename T2> | |
108 bool operator<=(const PagedArray_iterator<ContainerType2, T2>& it) const { | |
109 // Not bothering to check array_, for performance. | |
chrisha
2016/05/31 20:15:16
Ditto
huangs
2016/06/01 22:07:29
Done.
| |
110 return index_ <= it.index_; | |
111 } | |
112 | |
113 template <typename ContainerType2, typename T2> | |
114 difference_type operator-( | |
115 const PagedArray_iterator<ContainerType2, T2>& it) const { | |
116 return index_ - it.index_; | |
117 } | |
118 | |
119 private: | |
120 template <typename, typename> | |
121 friend class PagedArray_iterator; | |
122 | |
123 ContainerType* array_; | |
124 size_t index_; | |
125 }; | |
126 | |
21 // PagedArray implements an array stored using many fixed-size pages. | 127 // PagedArray implements an array stored using many fixed-size pages. |
22 template <typename T> | 128 template <typename T, int LOG_PAGE_SIZE> |
23 class PagedArray { | 129 class PagedArray { |
24 enum { | 130 enum { |
25 // Page size in elements. Page size of 2^18 * sizeof(T) is 1MB for T = int. | 131 // Page size in elements. |
26 kLogPageSize = 18, | 132 kLogPageSize = LOG_PAGE_SIZE, |
27 kPageSize = 1 << kLogPageSize | 133 kPageSize = 1 << LOG_PAGE_SIZE |
28 }; | 134 }; |
29 | 135 |
30 public: | 136 public: |
31 PagedArray() : pages_(NULL), page_count_(0) {} | 137 using ThisType = PagedArray<T, LOG_PAGE_SIZE>; |
138 using const_iterator = PagedArray_iterator<const ThisType, const T>; | |
139 using iterator = PagedArray_iterator<ThisType, T>; | |
32 | 140 |
141 PagedArray() = default; | |
33 ~PagedArray() { clear(); } | 142 ~PagedArray() { clear(); } |
34 | 143 |
35 T& operator[](size_t i) { | 144 iterator begin() { return iterator(this, 0); } |
36 size_t page = i >> kLogPageSize; | 145 iterator end() { return iterator(this, size_); } |
37 size_t offset = i & (kPageSize - 1); | 146 const_iterator begin() const { return const_iterator(this, 0); } |
38 // It is tempting to add a DCHECK(page < page_count_), but that makes | 147 const_iterator end() const { return const_iterator(this, size_); } |
39 // bsdiff_create run 2x slower (even when compiled optimized.) | 148 |
40 return pages_[page][offset]; | 149 T& operator[](size_t i) { return at(i); } |
41 } | 150 const T& operator[](size_t i) const { return at(i); } |
42 | 151 |
43 // Allocates storage for |size| elements. Returns true on success and false if | 152 // Allocates storage for |size| elements. Returns true on success and false if |
44 // allocation fails. | 153 // allocation fails. |
45 bool Allocate(size_t size) { | 154 bool Allocate(size_t size) { |
46 clear(); | 155 clear(); |
47 size_t pages_needed = (size + kPageSize - 1) >> kLogPageSize; | 156 size_ = size; |
157 size_t pages_needed = (size_ + kPageSize - 1) >> kLogPageSize; | |
48 if (!base::UncheckedMalloc(sizeof(T*) * pages_needed, | 158 if (!base::UncheckedMalloc(sizeof(T*) * pages_needed, |
49 reinterpret_cast<void**>(&pages_))) { | 159 reinterpret_cast<void**>(&pages_))) { |
50 return false; | 160 return false; |
51 } | 161 } |
52 | 162 |
53 for (page_count_ = 0; page_count_ < pages_needed; ++page_count_) { | 163 for (page_count_ = 0; page_count_ < pages_needed; ++page_count_) { |
54 T* block = nullptr; | 164 T* block = nullptr; |
55 if (!base::UncheckedMalloc(sizeof(T) * kPageSize, | 165 if (!base::UncheckedMalloc(sizeof(T) * kPageSize, |
56 reinterpret_cast<void**>(&block))) { | 166 reinterpret_cast<void**>(&block))) { |
57 clear(); | 167 clear(); |
58 return false; | 168 return false; |
59 } | 169 } |
60 pages_[page_count_] = block; | 170 pages_[page_count_] = block; |
61 } | 171 } |
62 return true; | 172 return true; |
63 } | 173 } |
64 | 174 |
65 // Releases all storage. May be called more than once. | 175 // Releases all storage. May be called more than once. |
66 void clear() { | 176 void clear() { |
67 if (pages_ != NULL) { | 177 if (pages_ != nullptr) { |
68 while (page_count_ != 0) { | 178 while (page_count_ != 0) { |
69 --page_count_; | 179 --page_count_; |
70 free(pages_[page_count_]); | 180 free(pages_[page_count_]); |
71 } | 181 } |
72 free(pages_); | 182 free(pages_); |
73 pages_ = NULL; | 183 pages_ = nullptr; |
74 } | 184 } |
75 } | 185 } |
76 | 186 |
77 private: | 187 private: |
78 T** pages_; | 188 inline T& at(size_t i) const { |
79 size_t page_count_; | 189 size_t page = i >> kLogPageSize; |
190 size_t offset = i & (kPageSize - 1); | |
191 // It is tempting to add a DCHECK(page < page_count_), but that makes | |
192 // 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
| |
193 return pages_[page][offset]; | |
194 } | |
195 | |
196 T** pages_ = nullptr; | |
197 size_t size_ = 0U; | |
198 size_t page_count_ = 0U; | |
80 | 199 |
81 DISALLOW_COPY_AND_ASSIGN(PagedArray); | 200 DISALLOW_COPY_AND_ASSIGN(PagedArray); |
82 }; | 201 }; |
83 | 202 |
84 } // namespace courgette | 203 } // namespace courgette |
204 | |
85 #endif // COURGETTE_THIRD_PARTY_BSDIFF_PAGED_ARRAY_H_ | 205 #endif // COURGETTE_THIRD_PARTY_BSDIFF_PAGED_ARRAY_H_ |
OLD | NEW |