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
3 // found in the LICENSE file.
4
5 #include "cc/base/list_container_helper.h"
6
7 #include <stddef.h>
8
9 #include <algorithm>
10 #include <cstring>
11 #include <vector>
12
13 #include "base/check_op.h"
14 #include "base/memory/aligned_memory.h"
15
16 namespace {
17 const size_t kDefaultNumElementTypesToReserve = 32;
18 } // namespace
19
20 namespace cc {
21
22 // CharAllocator
23 ////////////////////////////////////////////////////
24 // This class deals only with char* and void*. It does allocation and passing
25 // out raw pointers, as well as memory deallocation when being destroyed.
26 class ListContainerHelper::CharAllocator {
27 public:
28 // CharAllocator::InnerList
29 /////////////////////////////////////////////
30 // This class holds the raw memory chunk, as well as information about its
31 // size and availability.
32 struct InnerList {
33 InnerList(const InnerList&) = delete;
34 InnerList& operator=(const InnerList&) = delete;
35
36 std::unique_ptr<char[], base::AlignedFreeDeleter> data;
37 // The number of elements in total the memory can hold. The difference
38 // between capacity and size is the how many more elements this list can
39 // hold.
40 size_t capacity;
41 // The number of elements have been put into this list.
42 size_t size;
43 // The size of each element is in bytes. This is used to move from between
44 // elements' memory locations.
45 size_t step;
46
InnerListcc::ListContainerHelper::CharAllocator::InnerList47 InnerList() : capacity(0), size(0), step(0) {}
48
Erasecc::ListContainerHelper::CharAllocator::InnerList49 void Erase(char* position) {
50 // Confident that destructor is called by caller of this function. Since
51 // CharAllocator does not handle construction after
52 // allocation, it doesn't handle desctrution before deallocation.
53 DCHECK_LE(position, LastElement());
54 DCHECK_GE(position, Begin());
55 char* start = position + step;
56 std::copy(start, End(), position);
57
58 --size;
59 // Decrease capacity to avoid creating not full not last InnerList.
60 --capacity;
61 }
62
InsertBeforecc::ListContainerHelper::CharAllocator::InnerList63 void InsertBefore(size_t alignment, char** position, size_t count) {
64 DCHECK_LE(*position, LastElement() + step);
65 DCHECK_GE(*position, Begin());
66
67 // Adjust the size and capacity
68 size_t old_size = size;
69 size += count;
70 capacity = size;
71
72 // Allocate the new data and update the iterator's pointer.
73 std::unique_ptr<char[], base::AlignedFreeDeleter> new_data(
74 static_cast<char*>(base::AlignedAlloc(size * step, alignment)));
75 size_t position_offset = *position - Begin();
76 *position = new_data.get() + position_offset;
77
78 // Copy the data before the inserted segment
79 memcpy(new_data.get(), data.get(), position_offset);
80 // Copy the data after the inserted segment.
81 memcpy(new_data.get() + position_offset + count * step,
82 data.get() + position_offset, old_size * step - position_offset);
83 data = std::move(new_data);
84 }
85
IsEmptycc::ListContainerHelper::CharAllocator::InnerList86 bool IsEmpty() const { return !size; }
IsFullcc::ListContainerHelper::CharAllocator::InnerList87 bool IsFull() { return capacity == size; }
NumElementsAvailablecc::ListContainerHelper::CharAllocator::InnerList88 size_t NumElementsAvailable() const { return capacity - size; }
89
AddElementcc::ListContainerHelper::CharAllocator::InnerList90 void* AddElement() {
91 DCHECK_LT(size, capacity);
92 ++size;
93 return LastElement();
94 }
95
RemoveLastcc::ListContainerHelper::CharAllocator::InnerList96 void RemoveLast() {
97 DCHECK(!IsEmpty());
98 --size;
99 }
100
Begincc::ListContainerHelper::CharAllocator::InnerList101 char* Begin() const { return data.get(); }
Endcc::ListContainerHelper::CharAllocator::InnerList102 char* End() const { return data.get() + size * step; }
LastElementcc::ListContainerHelper::CharAllocator::InnerList103 char* LastElement() const { return data.get() + (size - 1) * step; }
ElementAtcc::ListContainerHelper::CharAllocator::InnerList104 char* ElementAt(size_t index) const { return data.get() + index * step; }
105 };
106
CharAllocator(size_t alignment,size_t element_size,size_t element_count)107 CharAllocator(size_t alignment, size_t element_size, size_t element_count)
108 // base::AlignedAlloc does not accept alignment less than sizeof(void*).
109 : alignment_(std::max(sizeof(void*), alignment)),
110 element_size_(element_size),
111 size_(0),
112 last_list_index_(0),
113 last_list_(nullptr) {
114 // If this fails, then alignment of elements after the first could be wrong,
115 // and we need to pad sizes to fix that.
116 DCHECK_EQ(element_size % alignment, 0u);
117 AllocateNewList(element_count > 0 ? element_count
118 : kDefaultNumElementTypesToReserve);
119 last_list_ = storage_[last_list_index_].get();
120 }
121
122 CharAllocator(const CharAllocator&) = delete;
123 ~CharAllocator() = default;
124
125 CharAllocator& operator=(const CharAllocator&) = delete;
126
Allocate()127 void* Allocate() {
128 if (last_list_->IsFull()) {
129 // Only allocate a new list if there isn't a spare one still there from
130 // previous usage.
131 if (last_list_index_ + 1 >= storage_.size())
132 AllocateNewList(last_list_->capacity * 2);
133
134 ++last_list_index_;
135 last_list_ = storage_[last_list_index_].get();
136 }
137
138 ++size_;
139 return last_list_->AddElement();
140 }
141
alignment() const142 size_t alignment() const { return alignment_; }
element_size() const143 size_t element_size() const { return element_size_; }
list_count() const144 size_t list_count() const { return storage_.size(); }
size() const145 size_t size() const { return size_; }
IsEmpty() const146 bool IsEmpty() const { return size() == 0; }
147
Capacity() const148 size_t Capacity() const {
149 size_t capacity_sum = 0;
150 for (const auto& inner_list : storage_)
151 capacity_sum += inner_list->capacity;
152 return capacity_sum;
153 }
154
Clear()155 void Clear() {
156 // Remove all except for the first InnerList.
157 DCHECK(!storage_.empty());
158 storage_.erase(storage_.begin() + 1, storage_.end());
159 last_list_index_ = 0;
160 last_list_ = storage_[0].get();
161 last_list_->size = 0;
162 size_ = 0;
163 }
164
RemoveLast()165 void RemoveLast() {
166 DCHECK(!IsEmpty());
167 last_list_->RemoveLast();
168 if (last_list_->IsEmpty() && last_list_index_ > 0) {
169 --last_list_index_;
170 last_list_ = storage_[last_list_index_].get();
171
172 // If there are now two empty inner lists, free one of them.
173 if (last_list_index_ + 2 < storage_.size())
174 storage_.pop_back();
175 }
176 --size_;
177 }
178
Erase(PositionInCharAllocator * position)179 void Erase(PositionInCharAllocator* position) {
180 DCHECK_EQ(this, position->ptr_to_container);
181
182 // Update |position| to point to the element after the erased element.
183 InnerList* list = storage_[position->vector_index].get();
184 char* item_iterator = position->item_iterator;
185 if (item_iterator == list->LastElement())
186 position->Increment();
187
188 list->Erase(item_iterator);
189 // TODO(weiliangc): Free the InnerList if it is empty.
190 --size_;
191 }
192
InsertBefore(ListContainerHelper::Iterator * position,size_t count)193 void InsertBefore(ListContainerHelper::Iterator* position, size_t count) {
194 if (!count)
195 return;
196
197 // If |position| is End(), then append |count| elements at the end. This
198 // will happen to not invalidate any iterators or memory.
199 if (!position->item_iterator) {
200 // Set |position| to be the first inserted element.
201 Allocate();
202 position->vector_index = storage_.size() - 1;
203 position->item_iterator = storage_[position->vector_index]->LastElement();
204 // Allocate the rest.
205 for (size_t i = 1; i < count; ++i)
206 Allocate();
207 } else {
208 storage_[position->vector_index]->InsertBefore(
209 alignment_, &position->item_iterator, count);
210 size_ += count;
211 }
212 }
213
InnerListById(size_t id) const214 InnerList* InnerListById(size_t id) const {
215 DCHECK_LT(id, storage_.size());
216 return storage_[id].get();
217 }
218
FirstInnerListId() const219 size_t FirstInnerListId() const {
220 // |size_| > 0 means that at least one vector in |storage_| will be
221 // non-empty.
222 DCHECK_GT(size_, 0u);
223 size_t id = 0;
224 while (storage_[id]->size == 0)
225 ++id;
226 return id;
227 }
228
LastInnerListId() const229 size_t LastInnerListId() const {
230 // |size_| > 0 means that at least one vector in |storage_| will be
231 // non-empty.
232 DCHECK_GT(size_, 0u);
233 size_t id = storage_.size() - 1;
234 while (storage_[id]->size == 0)
235 --id;
236 return id;
237 }
238
NumAvailableElementsInLastList() const239 size_t NumAvailableElementsInLastList() const {
240 return last_list_->NumElementsAvailable();
241 }
242
243 private:
AllocateNewList(size_t list_size)244 void AllocateNewList(size_t list_size) {
245 std::unique_ptr<InnerList> new_list(new InnerList);
246 new_list->capacity = list_size;
247 new_list->size = 0;
248 new_list->step = element_size_;
249 new_list->data.reset(static_cast<char*>(
250 base::AlignedAlloc(list_size * element_size_, alignment_)));
251 storage_.push_back(std::move(new_list));
252 }
253
254 std::vector<std::unique_ptr<InnerList>> storage_;
255 const size_t alignment_;
256 const size_t element_size_;
257
258 // The number of elements in the list.
259 size_t size_;
260
261 // The index of the last list to have had elements added to it, or the only
262 // list if the container has not had elements added since being cleared.
263 size_t last_list_index_;
264
265 // This is equivalent to |storage_[last_list_index_]|.
266 InnerList* last_list_;
267 };
268
269 // PositionInCharAllocator
270 //////////////////////////////////////////////////////
271 ListContainerHelper::PositionInCharAllocator::PositionInCharAllocator(
272 const ListContainerHelper::PositionInCharAllocator& other) = default;
273
PositionInCharAllocator(ListContainerHelper::CharAllocator * container,size_t vector_ind,char * item_iter)274 ListContainerHelper::PositionInCharAllocator::PositionInCharAllocator(
275 ListContainerHelper::CharAllocator* container,
276 size_t vector_ind,
277 char* item_iter)
278 : ptr_to_container(container),
279 vector_index(vector_ind),
280 item_iterator(item_iter) {}
281
operator ==(const ListContainerHelper::PositionInCharAllocator & other) const282 bool ListContainerHelper::PositionInCharAllocator::operator==(
283 const ListContainerHelper::PositionInCharAllocator& other) const {
284 DCHECK_EQ(ptr_to_container, other.ptr_to_container);
285 return vector_index == other.vector_index &&
286 item_iterator == other.item_iterator;
287 }
288
operator !=(const ListContainerHelper::PositionInCharAllocator & other) const289 bool ListContainerHelper::PositionInCharAllocator::operator!=(
290 const ListContainerHelper::PositionInCharAllocator& other) const {
291 return !(*this == other);
292 }
293
294 ListContainerHelper::PositionInCharAllocator
Increment()295 ListContainerHelper::PositionInCharAllocator::Increment() {
296 CharAllocator::InnerList* list =
297 ptr_to_container->InnerListById(vector_index);
298 if (item_iterator == list->LastElement()) {
299 ++vector_index;
300 while (vector_index < ptr_to_container->list_count()) {
301 if (ptr_to_container->InnerListById(vector_index)->size != 0)
302 break;
303 ++vector_index;
304 }
305 if (vector_index < ptr_to_container->list_count())
306 item_iterator = ptr_to_container->InnerListById(vector_index)->Begin();
307 else
308 item_iterator = nullptr;
309 } else {
310 item_iterator += list->step;
311 }
312 return *this;
313 }
314
315 ListContainerHelper::PositionInCharAllocator
ReverseIncrement()316 ListContainerHelper::PositionInCharAllocator::ReverseIncrement() {
317 CharAllocator::InnerList* list =
318 ptr_to_container->InnerListById(vector_index);
319 if (item_iterator == list->Begin()) {
320 --vector_index;
321 // Since |vector_index| is unsigned, we compare < list_count() instead of
322 // comparing >= 0, as the variable will wrap around when it goes out of
323 // range (below 0).
324 while (vector_index < ptr_to_container->list_count()) {
325 if (ptr_to_container->InnerListById(vector_index)->size != 0)
326 break;
327 --vector_index;
328 }
329 if (vector_index < ptr_to_container->list_count()) {
330 item_iterator =
331 ptr_to_container->InnerListById(vector_index)->LastElement();
332 } else {
333 item_iterator = nullptr;
334 }
335 } else {
336 item_iterator -= list->step;
337 }
338 return *this;
339 }
340
341 // ListContainerHelper
342 ////////////////////////////////////////////
ListContainerHelper(size_t alignment,size_t max_size_for_derived_class,size_t num_of_elements_to_reserve_for)343 ListContainerHelper::ListContainerHelper(size_t alignment,
344 size_t max_size_for_derived_class,
345 size_t num_of_elements_to_reserve_for)
346 : data_(new CharAllocator(alignment,
347 max_size_for_derived_class,
348 num_of_elements_to_reserve_for)) {}
349
350 ListContainerHelper::~ListContainerHelper() = default;
351
RemoveLast()352 void ListContainerHelper::RemoveLast() {
353 data_->RemoveLast();
354 }
355
EraseAndInvalidateAllPointers(ListContainerHelper::Iterator * position)356 void ListContainerHelper::EraseAndInvalidateAllPointers(
357 ListContainerHelper::Iterator* position) {
358 data_->Erase(position);
359 }
360
InsertBeforeAndInvalidateAllPointers(ListContainerHelper::Iterator * position,size_t count)361 void ListContainerHelper::InsertBeforeAndInvalidateAllPointers(
362 ListContainerHelper::Iterator* position,
363 size_t count) {
364 data_->InsertBefore(position, count);
365 }
366
crbegin() const367 ListContainerHelper::ConstReverseIterator ListContainerHelper::crbegin() const {
368 if (data_->IsEmpty())
369 return crend();
370
371 size_t id = data_->LastInnerListId();
372 return ConstReverseIterator(data_.get(), id,
373 data_->InnerListById(id)->LastElement(), 0);
374 }
375
crend() const376 ListContainerHelper::ConstReverseIterator ListContainerHelper::crend() const {
377 return ConstReverseIterator(data_.get(), static_cast<size_t>(-1), nullptr,
378 size());
379 }
380
rbegin()381 ListContainerHelper::ReverseIterator ListContainerHelper::rbegin() {
382 if (data_->IsEmpty())
383 return rend();
384
385 size_t id = data_->LastInnerListId();
386 return ReverseIterator(data_.get(), id,
387 data_->InnerListById(id)->LastElement(), 0);
388 }
389
rend()390 ListContainerHelper::ReverseIterator ListContainerHelper::rend() {
391 return ReverseIterator(data_.get(), static_cast<size_t>(-1), nullptr, size());
392 }
393
cbegin() const394 ListContainerHelper::ConstIterator ListContainerHelper::cbegin() const {
395 if (data_->IsEmpty())
396 return cend();
397
398 size_t id = data_->FirstInnerListId();
399 return ConstIterator(data_.get(), id, data_->InnerListById(id)->Begin(), 0);
400 }
401
cend() const402 ListContainerHelper::ConstIterator ListContainerHelper::cend() const {
403 if (data_->IsEmpty())
404 return ConstIterator(data_.get(), 0, nullptr, size());
405
406 size_t id = data_->list_count();
407 return ConstIterator(data_.get(), id, nullptr, size());
408 }
409
begin()410 ListContainerHelper::Iterator ListContainerHelper::begin() {
411 if (data_->IsEmpty())
412 return end();
413
414 size_t id = data_->FirstInnerListId();
415 return Iterator(data_.get(), id, data_->InnerListById(id)->Begin(), 0);
416 }
417
end()418 ListContainerHelper::Iterator ListContainerHelper::end() {
419 if (data_->IsEmpty())
420 return Iterator(data_.get(), 0, nullptr, size());
421
422 size_t id = data_->list_count();
423 return Iterator(data_.get(), id, nullptr, size());
424 }
425
IteratorAt(size_t index) const426 ListContainerHelper::ConstIterator ListContainerHelper::IteratorAt(
427 size_t index) const {
428 DCHECK_LT(index, size());
429 size_t original_index = index;
430 size_t list_index;
431 for (list_index = 0; list_index < data_->list_count(); ++list_index) {
432 size_t current_size = data_->InnerListById(list_index)->size;
433 if (index < current_size)
434 break;
435 index -= current_size;
436 }
437 return ConstIterator(data_.get(), list_index,
438 data_->InnerListById(list_index)->ElementAt(index),
439 original_index);
440 }
441
IteratorAt(size_t index)442 ListContainerHelper::Iterator ListContainerHelper::IteratorAt(size_t index) {
443 DCHECK_LT(index, size());
444 size_t original_index = index;
445 size_t list_index;
446 for (list_index = 0; list_index < data_->list_count(); ++list_index) {
447 size_t current_size = data_->InnerListById(list_index)->size;
448 if (index < current_size)
449 break;
450 index -= current_size;
451 }
452 return Iterator(data_.get(), list_index,
453 data_->InnerListById(list_index)->ElementAt(index),
454 original_index);
455 }
456
Allocate(size_t alignment,size_t size_of_actual_element_in_bytes)457 void* ListContainerHelper::Allocate(size_t alignment,
458 size_t size_of_actual_element_in_bytes) {
459 DCHECK_LE(alignment, data_->alignment());
460 DCHECK_LE(size_of_actual_element_in_bytes, data_->element_size());
461 return data_->Allocate();
462 }
463
size() const464 size_t ListContainerHelper::size() const {
465 return data_->size();
466 }
467
empty() const468 bool ListContainerHelper::empty() const {
469 return data_->IsEmpty();
470 }
471
MaxSizeForDerivedClass() const472 size_t ListContainerHelper::MaxSizeForDerivedClass() const {
473 return data_->element_size();
474 }
475
GetCapacityInBytes() const476 size_t ListContainerHelper::GetCapacityInBytes() const {
477 return data_->Capacity() * data_->element_size();
478 }
479
clear()480 void ListContainerHelper::clear() {
481 data_->Clear();
482 }
483
AvailableSizeWithoutAnotherAllocationForTesting() const484 size_t ListContainerHelper::AvailableSizeWithoutAnotherAllocationForTesting()
485 const {
486 return data_->NumAvailableElementsInLastList();
487 }
488
489 // ListContainerHelper::Iterator
490 /////////////////////////////////////////////////
Iterator(CharAllocator * container,size_t vector_ind,char * item_iter,size_t index)491 ListContainerHelper::Iterator::Iterator(CharAllocator* container,
492 size_t vector_ind,
493 char* item_iter,
494 size_t index)
495 : PositionInCharAllocator(container, vector_ind, item_iter),
496 index_(index) {}
497
498 ListContainerHelper::Iterator::~Iterator() = default;
499
index() const500 size_t ListContainerHelper::Iterator::index() const {
501 return index_;
502 }
503
504 // ListContainerHelper::ConstIterator
505 /////////////////////////////////////////////////
ConstIterator(const ListContainerHelper::Iterator & other)506 ListContainerHelper::ConstIterator::ConstIterator(
507 const ListContainerHelper::Iterator& other)
508 : PositionInCharAllocator(other), index_(other.index()) {}
509
ConstIterator(CharAllocator * container,size_t vector_ind,char * item_iter,size_t index)510 ListContainerHelper::ConstIterator::ConstIterator(CharAllocator* container,
511 size_t vector_ind,
512 char* item_iter,
513 size_t index)
514 : PositionInCharAllocator(container, vector_ind, item_iter),
515 index_(index) {}
516
517 ListContainerHelper::ConstIterator::~ConstIterator() = default;
518
index() const519 size_t ListContainerHelper::ConstIterator::index() const {
520 return index_;
521 }
522
523 // ListContainerHelper::ReverseIterator
524 /////////////////////////////////////////////////
ReverseIterator(CharAllocator * container,size_t vector_ind,char * item_iter,size_t index)525 ListContainerHelper::ReverseIterator::ReverseIterator(CharAllocator* container,
526 size_t vector_ind,
527 char* item_iter,
528 size_t index)
529 : PositionInCharAllocator(container, vector_ind, item_iter),
530 index_(index) {}
531
532 ListContainerHelper::ReverseIterator::~ReverseIterator() = default;
533
index() const534 size_t ListContainerHelper::ReverseIterator::index() const {
535 return index_;
536 }
537
538 // ListContainerHelper::ConstReverseIterator
539 /////////////////////////////////////////////////
ConstReverseIterator(const ListContainerHelper::ReverseIterator & other)540 ListContainerHelper::ConstReverseIterator::ConstReverseIterator(
541 const ListContainerHelper::ReverseIterator& other)
542 : PositionInCharAllocator(other), index_(other.index()) {}
543
ConstReverseIterator(CharAllocator * container,size_t vector_ind,char * item_iter,size_t index)544 ListContainerHelper::ConstReverseIterator::ConstReverseIterator(
545 CharAllocator* container,
546 size_t vector_ind,
547 char* item_iter,
548 size_t index)
549 : PositionInCharAllocator(container, vector_ind, item_iter),
550 index_(index) {}
551
552 ListContainerHelper::ConstReverseIterator::~ConstReverseIterator() = default;
553
index() const554 size_t ListContainerHelper::ConstReverseIterator::index() const {
555 return index_;
556 }
557
558 } // namespace cc
559