OLD | NEW |
1 // Copyright 2014 The Chromium Authors. All rights reserved. | 1 // Copyright 2014 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 #include "cc/base/list_container_helper.h" | 5 #include "cc/base/list_container_helper.h" |
6 | 6 |
7 #include <algorithm> | 7 #include <algorithm> |
8 #include <vector> | 8 #include <vector> |
9 | 9 |
10 #include "cc/base/scoped_ptr_vector.h" | |
11 | |
12 namespace { | 10 namespace { |
13 const size_t kDefaultNumElementTypesToReserve = 32; | 11 const size_t kDefaultNumElementTypesToReserve = 32; |
14 } // namespace | 12 } // namespace |
15 | 13 |
16 namespace cc { | 14 namespace cc { |
17 | 15 |
18 // CharAllocator | 16 // CharAllocator |
19 //////////////////////////////////////////////////// | 17 //////////////////////////////////////////////////// |
20 // This class deals only with char* and void*. It does allocation and passing | 18 // This class deals only with char* and void*. It does allocation and passing |
21 // out raw pointers, as well as memory deallocation when being destroyed. | 19 // out raw pointers, as well as memory deallocation when being destroyed. |
(...skipping 74 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
96 char* ElementAt(size_t index) const { return data.get() + index * step; } | 94 char* ElementAt(size_t index) const { return data.get() + index * step; } |
97 | 95 |
98 private: | 96 private: |
99 DISALLOW_COPY_AND_ASSIGN(InnerList); | 97 DISALLOW_COPY_AND_ASSIGN(InnerList); |
100 }; | 98 }; |
101 | 99 |
102 explicit CharAllocator(size_t element_size) | 100 explicit CharAllocator(size_t element_size) |
103 : element_size_(element_size), | 101 : element_size_(element_size), |
104 size_(0), | 102 size_(0), |
105 last_list_index_(0), | 103 last_list_index_(0), |
106 last_list_(NULL) { | 104 last_list_(nullptr) { |
107 AllocateNewList(kDefaultNumElementTypesToReserve); | 105 AllocateNewList(kDefaultNumElementTypesToReserve); |
108 last_list_ = storage_[last_list_index_]; | 106 last_list_ = storage_[last_list_index_].get(); |
109 } | 107 } |
110 | 108 |
111 CharAllocator(size_t element_size, size_t element_count) | 109 CharAllocator(size_t element_size, size_t element_count) |
112 : element_size_(element_size), | 110 : element_size_(element_size), |
113 size_(0), | 111 size_(0), |
114 last_list_index_(0), | 112 last_list_index_(0), |
115 last_list_(NULL) { | 113 last_list_(nullptr) { |
116 AllocateNewList(element_count > 0 ? element_count | 114 AllocateNewList(element_count > 0 ? element_count |
117 : kDefaultNumElementTypesToReserve); | 115 : kDefaultNumElementTypesToReserve); |
118 last_list_ = storage_[last_list_index_]; | 116 last_list_ = storage_[last_list_index_].get(); |
119 } | 117 } |
120 | 118 |
121 ~CharAllocator() {} | 119 ~CharAllocator() {} |
122 | 120 |
123 void* Allocate() { | 121 void* Allocate() { |
124 if (last_list_->IsFull()) { | 122 if (last_list_->IsFull()) { |
125 // Only allocate a new list if there isn't a spare one still there from | 123 // Only allocate a new list if there isn't a spare one still there from |
126 // previous usage. | 124 // previous usage. |
127 if (last_list_index_ + 1 >= storage_.size()) | 125 if (last_list_index_ + 1 >= storage_.size()) |
128 AllocateNewList(last_list_->capacity * 2); | 126 AllocateNewList(last_list_->capacity * 2); |
129 | 127 |
130 ++last_list_index_; | 128 ++last_list_index_; |
131 last_list_ = storage_[last_list_index_]; | 129 last_list_ = storage_[last_list_index_].get(); |
132 } | 130 } |
133 | 131 |
134 ++size_; | 132 ++size_; |
135 return last_list_->AddElement(); | 133 return last_list_->AddElement(); |
136 } | 134 } |
137 | 135 |
138 size_t element_size() const { return element_size_; } | 136 size_t element_size() const { return element_size_; } |
139 size_t list_count() const { return storage_.size(); } | 137 size_t list_count() const { return storage_.size(); } |
140 size_t size() const { return size_; } | 138 size_t size() const { return size_; } |
141 bool IsEmpty() const { return size() == 0; } | 139 bool IsEmpty() const { return size() == 0; } |
142 | 140 |
143 size_t Capacity() const { | 141 size_t Capacity() const { |
144 size_t capacity_sum = 0; | 142 size_t capacity_sum = 0; |
145 for (const auto& inner_list : storage_) | 143 for (const auto& inner_list : storage_) |
146 capacity_sum += inner_list->capacity; | 144 capacity_sum += inner_list->capacity; |
147 return capacity_sum; | 145 return capacity_sum; |
148 } | 146 } |
149 | 147 |
150 void Clear() { | 148 void Clear() { |
151 // Remove all except for the first InnerList. | 149 // Remove all except for the first InnerList. |
152 DCHECK(!storage_.empty()); | 150 DCHECK(!storage_.empty()); |
153 storage_.erase(storage_.begin() + 1, storage_.end()); | 151 storage_.erase(storage_.begin() + 1, storage_.end()); |
154 last_list_index_ = 0; | 152 last_list_index_ = 0; |
155 last_list_ = storage_[0]; | 153 last_list_ = storage_[0].get(); |
156 last_list_->size = 0; | 154 last_list_->size = 0; |
157 size_ = 0; | 155 size_ = 0; |
158 } | 156 } |
159 | 157 |
160 void RemoveLast() { | 158 void RemoveLast() { |
161 DCHECK(!IsEmpty()); | 159 DCHECK(!IsEmpty()); |
162 last_list_->RemoveLast(); | 160 last_list_->RemoveLast(); |
163 if (last_list_->IsEmpty() && last_list_index_ > 0) { | 161 if (last_list_->IsEmpty() && last_list_index_ > 0) { |
164 --last_list_index_; | 162 --last_list_index_; |
165 last_list_ = storage_[last_list_index_]; | 163 last_list_ = storage_[last_list_index_].get(); |
166 | 164 |
167 // If there are now two empty inner lists, free one of them. | 165 // If there are now two empty inner lists, free one of them. |
168 if (last_list_index_ + 2 < storage_.size()) | 166 if (last_list_index_ + 2 < storage_.size()) |
169 storage_.pop_back(); | 167 storage_.pop_back(); |
170 } | 168 } |
171 --size_; | 169 --size_; |
172 } | 170 } |
173 | 171 |
174 void Erase(PositionInCharAllocator* position) { | 172 void Erase(PositionInCharAllocator* position) { |
175 DCHECK_EQ(this, position->ptr_to_container); | 173 DCHECK_EQ(this, position->ptr_to_container); |
176 | 174 |
177 // Update |position| to point to the element after the erased element. | 175 // Update |position| to point to the element after the erased element. |
178 InnerList* list = storage_[position->vector_index]; | 176 InnerList* list = storage_[position->vector_index].get(); |
179 char* item_iterator = position->item_iterator; | 177 char* item_iterator = position->item_iterator; |
180 if (item_iterator == list->LastElement()) | 178 if (item_iterator == list->LastElement()) |
181 position->Increment(); | 179 position->Increment(); |
182 | 180 |
183 list->Erase(item_iterator); | 181 list->Erase(item_iterator); |
184 // TODO(weiliangc): Free the InnerList if it is empty. | 182 // TODO(weiliangc): Free the InnerList if it is empty. |
185 --size_; | 183 --size_; |
186 } | 184 } |
187 | 185 |
188 void InsertBefore(ListContainerHelper::Iterator* position, size_t count) { | 186 void InsertBefore(ListContainerHelper::Iterator* position, size_t count) { |
(...skipping 12 matching lines...) Expand all Loading... |
201 Allocate(); | 199 Allocate(); |
202 } else { | 200 } else { |
203 storage_[position->vector_index]->InsertBefore(&position->item_iterator, | 201 storage_[position->vector_index]->InsertBefore(&position->item_iterator, |
204 count); | 202 count); |
205 size_ += count; | 203 size_ += count; |
206 } | 204 } |
207 } | 205 } |
208 | 206 |
209 InnerList* InnerListById(size_t id) const { | 207 InnerList* InnerListById(size_t id) const { |
210 DCHECK_LT(id, storage_.size()); | 208 DCHECK_LT(id, storage_.size()); |
211 return storage_[id]; | 209 return storage_[id].get(); |
212 } | 210 } |
213 | 211 |
214 size_t FirstInnerListId() const { | 212 size_t FirstInnerListId() const { |
215 // |size_| > 0 means that at least one vector in |storage_| will be | 213 // |size_| > 0 means that at least one vector in |storage_| will be |
216 // non-empty. | 214 // non-empty. |
217 DCHECK_GT(size_, 0u); | 215 DCHECK_GT(size_, 0u); |
218 size_t id = 0; | 216 size_t id = 0; |
219 while (storage_[id]->size == 0) | 217 while (storage_[id]->size == 0) |
220 ++id; | 218 ++id; |
221 return id; | 219 return id; |
(...skipping 16 matching lines...) Expand all Loading... |
238 private: | 236 private: |
239 void AllocateNewList(size_t list_size) { | 237 void AllocateNewList(size_t list_size) { |
240 scoped_ptr<InnerList> new_list(new InnerList); | 238 scoped_ptr<InnerList> new_list(new InnerList); |
241 new_list->capacity = list_size; | 239 new_list->capacity = list_size; |
242 new_list->size = 0; | 240 new_list->size = 0; |
243 new_list->step = element_size_; | 241 new_list->step = element_size_; |
244 new_list->data.reset(new char[list_size * element_size_]); | 242 new_list->data.reset(new char[list_size * element_size_]); |
245 storage_.push_back(new_list.Pass()); | 243 storage_.push_back(new_list.Pass()); |
246 } | 244 } |
247 | 245 |
248 ScopedPtrVector<InnerList> storage_; | 246 std::vector<scoped_ptr<InnerList>> storage_; |
249 const size_t element_size_; | 247 const size_t element_size_; |
250 | 248 |
251 // The number of elements in the list. | 249 // The number of elements in the list. |
252 size_t size_; | 250 size_t size_; |
253 | 251 |
254 // The index of the last list to have had elements added to it, or the only | 252 // The index of the last list to have had elements added to it, or the only |
255 // list if the container has not had elements added since being cleared. | 253 // list if the container has not had elements added since being cleared. |
256 size_t last_list_index_; | 254 size_t last_list_index_; |
257 | 255 |
258 // This is equivalent to |storage_[last_list_index_]|. | 256 // This is equivalent to |storage_[last_list_index_]|. |
(...skipping 287 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
546 : PositionInCharAllocator(container, vector_ind, item_iter), | 544 : PositionInCharAllocator(container, vector_ind, item_iter), |
547 index_(index) {} | 545 index_(index) {} |
548 | 546 |
549 ListContainerHelper::ConstReverseIterator::~ConstReverseIterator() {} | 547 ListContainerHelper::ConstReverseIterator::~ConstReverseIterator() {} |
550 | 548 |
551 size_t ListContainerHelper::ConstReverseIterator::index() const { | 549 size_t ListContainerHelper::ConstReverseIterator::index() const { |
552 return index_; | 550 return index_; |
553 } | 551 } |
554 | 552 |
555 } // namespace cc | 553 } // namespace cc |
OLD | NEW |