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 // contigous arrays. | 9 // contigous arrays. |
10 | 10 |
11 #ifndef COURGETTE_BSDIFF_PAGED_ARRAY_H_ | 11 #ifndef COURGETTE_BSDIFF_PAGED_ARRAY_H_ |
12 #define COURGETTE_BSDIFF_PAGED_ARRAY_H_ | 12 #define COURGETTE_BSDIFF_PAGED_ARRAY_H_ |
13 | 13 |
14 #include <stddef.h> | 14 #include <stddef.h> |
| 15 #include <iterator> |
15 | 16 |
16 #include "base/macros.h" | 17 #include "base/macros.h" |
17 #include "base/process/memory.h" | 18 #include "base/process/memory.h" |
18 | 19 |
19 namespace courgette { | 20 namespace courgette { |
20 | 21 |
| 22 template<typename T> |
| 23 class PagedArray; |
| 24 |
| 25 // RandomAccessIterator for PagedArray<T> to enable std::sort(). |
| 26 template<typename T> |
| 27 class PagedArray_iterator { |
| 28 public: |
| 29 PagedArray_iterator() : array_(nullptr), index_(0U) { } |
| 30 |
| 31 PagedArray_iterator(PagedArray<T>* array, size_t index) |
| 32 : array_(array), index_(index) { } |
| 33 |
| 34 ~PagedArray_iterator() { } |
| 35 |
| 36 const T& operator*() const { return (*array_)[index_]; } |
| 37 |
| 38 T& operator*() { return (*array_)[index_]; } |
| 39 |
| 40 PagedArray_iterator<T>& operator++() { |
| 41 ++index_; |
| 42 return *this; |
| 43 } |
| 44 |
| 45 PagedArray_iterator<T> operator++(int) { |
| 46 return PagedArray_iterator<T>(array_, index_++); |
| 47 } |
| 48 |
| 49 PagedArray_iterator<T> operator+=(size_t inc) { |
| 50 return PagedArray_iterator<T>(array_, index_ += inc); |
| 51 } |
| 52 |
| 53 PagedArray_iterator<T>& operator--() { |
| 54 --index_; |
| 55 return *this; |
| 56 } |
| 57 |
| 58 PagedArray_iterator<T> operator+(size_t offset) { |
| 59 return PagedArray_iterator<T>(array_, index_ + offset); |
| 60 } |
| 61 |
| 62 PagedArray_iterator<T> operator-(size_t offset) { |
| 63 return PagedArray_iterator<T>(array_, index_ - offset); |
| 64 } |
| 65 |
| 66 bool operator==(const PagedArray_iterator<T>& it) const { |
| 67 return index_ == it.index_ && array_ == it.array_; |
| 68 } |
| 69 |
| 70 bool operator!=(const PagedArray_iterator<T>& it) const { |
| 71 return index_ != it.index_ || array_ != it.array_; |
| 72 } |
| 73 |
| 74 bool operator<(const PagedArray_iterator<T>& it) const { |
| 75 // Not bothering to check array_, for performance. |
| 76 return index_ < it.index_; |
| 77 } |
| 78 |
| 79 ptrdiff_t operator-(const PagedArray_iterator<T>& it) const { |
| 80 return index_ - it.index_; |
| 81 } |
| 82 |
| 83 private: |
| 84 PagedArray<T>* array_; |
| 85 size_t index_; |
| 86 }; |
| 87 |
| 88 template<typename T> |
| 89 struct std::iterator_traits<class PagedArray_iterator<T> > { |
| 90 typedef ptrdiff_t difference_type; |
| 91 typedef T value_type; |
| 92 typedef T& reference; |
| 93 typedef T* pointer; |
| 94 typedef std::random_access_iterator_tag iterator_category; |
| 95 }; |
| 96 |
21 // PagedArray implements an array stored using many fixed-size pages. | 97 // PagedArray implements an array stored using many fixed-size pages. |
22 template<typename T> | 98 template<typename T> |
23 class PagedArray { | 99 class PagedArray { |
24 enum { | 100 enum { |
25 // Page size in elements. Page size of 2^18 * sizeof(T) is 1MB for T = int. | 101 // Page size in elements. Page size of 2^18 * sizeof(T) is 1MB for T = int. |
26 kLogPageSize = 18, | 102 kLogPageSize = 18, |
27 kPageSize = 1 << kLogPageSize | 103 kPageSize = 1 << kLogPageSize |
28 }; | 104 }; |
29 | 105 |
30 public: | 106 public: |
31 PagedArray() : pages_(NULL), page_count_(0) {} | 107 typedef PagedArray_iterator<T> iterator; |
| 108 |
| 109 PagedArray() { } |
32 | 110 |
33 ~PagedArray() { clear(); } | 111 ~PagedArray() { clear(); } |
34 | 112 |
| 113 iterator begin() { return iterator(this, 0); } |
| 114 |
| 115 iterator end() { return iterator(this, size_); } |
| 116 |
35 T& operator[](size_t i) { | 117 T& operator[](size_t i) { |
36 size_t page = i >> kLogPageSize; | 118 size_t page = i >> kLogPageSize; |
37 size_t offset = i & (kPageSize - 1); | 119 size_t offset = i & (kPageSize - 1); |
38 // It is tempting to add a DCHECK(page < page_count_), but that makes | 120 // It is tempting to add a DCHECK(page < page_count_), but that makes |
39 // bsdiff_create run 2x slower (even when compiled optimized.) | 121 // bsdiff_create run 2x slower (even when compiled optimized.) |
40 return pages_[page][offset]; | 122 return pages_[page][offset]; |
41 } | 123 } |
42 | 124 |
43 // Allocates storage for |size| elements. Returns true on success and false if | 125 // Allocates storage for |size| elements. Returns true on success and false if |
44 // allocation fails. | 126 // allocation fails. |
45 bool Allocate(size_t size) { | 127 bool Allocate(size_t size) { |
46 clear(); | 128 clear(); |
47 size_t pages_needed = (size + kPageSize - 1) >> kLogPageSize; | 129 size_ = size; |
| 130 size_t pages_needed = (size_ + kPageSize - 1) >> kLogPageSize; |
48 if (!base::UncheckedMalloc(sizeof(T*) * pages_needed, | 131 if (!base::UncheckedMalloc(sizeof(T*) * pages_needed, |
49 reinterpret_cast<void**>(&pages_))) { | 132 reinterpret_cast<void**>(&pages_))) { |
50 return false; | 133 return false; |
51 } | 134 } |
52 | 135 |
53 for (page_count_ = 0; page_count_ < pages_needed; ++page_count_) { | 136 for (page_count_ = 0; page_count_ < pages_needed; ++page_count_) { |
54 T* block = nullptr; | 137 T* block = nullptr; |
55 if (!base::UncheckedMalloc(sizeof(T) * kPageSize, | 138 if (!base::UncheckedMalloc(sizeof(T) * kPageSize, |
56 reinterpret_cast<void**>(&block))) { | 139 reinterpret_cast<void**>(&block))) { |
57 clear(); | 140 clear(); |
58 return false; | 141 return false; |
59 } | 142 } |
60 pages_[page_count_] = block; | 143 pages_[page_count_] = block; |
61 } | 144 } |
62 return true; | 145 return true; |
63 } | 146 } |
64 | 147 |
65 // Releases all storage. May be called more than once. | 148 // Releases all storage. May be called more than once. |
66 void clear() { | 149 void clear() { |
67 if (pages_ != NULL) { | 150 if (pages_ != nullptr) { |
68 while (page_count_ != 0) { | 151 while (page_count_ != 0) { |
69 --page_count_; | 152 --page_count_; |
70 free(pages_[page_count_]); | 153 free(pages_[page_count_]); |
71 } | 154 } |
72 free(pages_); | 155 free(pages_); |
73 pages_ = NULL; | 156 pages_ = nullptr; |
74 } | 157 } |
| 158 size_ = 0; |
75 } | 159 } |
76 | 160 |
77 private: | 161 private: |
78 T** pages_; | 162 T** pages_ = nullptr; |
79 size_t page_count_; | 163 size_t size_ = 0U; |
| 164 size_t page_count_ = 0U; |
80 | 165 |
81 DISALLOW_COPY_AND_ASSIGN(PagedArray); | 166 DISALLOW_COPY_AND_ASSIGN(PagedArray); |
82 }; | 167 }; |
83 } // namespace | 168 |
| 169 } // namespace courgette |
| 170 |
84 #endif // COURGETTE_BSDIFF_PAGED_ARRAY_H_ | 171 #endif // COURGETTE_BSDIFF_PAGED_ARRAY_H_ |
OLD | NEW |