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