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.
5 #include "cc/quads/list_container.h"
10 #include "cc/base/scoped_ptr_vector.h"
11 #include "cc/quads/draw_quad.h"
12 #include "cc/quads/shared_quad_state.h"
15 const size_t kDefaultNumElementTypesToReserve
= 32;
20 // ListContainerCharAllocator
21 ////////////////////////////////////////////////////
22 // This class deals only with char* and void*. It does allocation and passing
23 // out raw pointers, as well as memory deallocation when being destroyed.
24 template <typename BaseElementType
>
25 class ListContainer
<BaseElementType
>::ListContainerCharAllocator
{
27 // ListContainerCharAllocator::InnerList
28 /////////////////////////////////////////////
29 // This class holds the raw memory chunk, as well as information about its
30 // size and availability.
32 scoped_ptr
<char[]> data
;
33 // The number of elements in total the memory can hold. The difference
34 // between capacity and size is the how many more elements this list can
37 // The number of elements have been put into this list.
39 // The size of each element is in bytes. This is used to move from between
40 // elements' memory locations.
43 InnerList() : capacity(0), size(0), step(0) {}
45 void Erase(char* position
) {
46 // Confident that destructor is called by caller of this function. Since
47 // ListContainerCharAllocator does not handle construction after
48 // allocation, it doesn't handle desctrution before deallocation.
49 DCHECK_LE(position
, LastElement());
50 DCHECK_GE(position
, Begin());
51 char* start
= position
+ step
;
52 std::copy(start
, End(), position
);
55 // Decrease capacity to avoid creating not full not last InnerList.
59 bool IsFull() { return capacity
== size
; }
60 size_t NumElementsAvailable() const { return capacity
- size
; }
63 DCHECK_LT(size
, capacity
);
68 char* Begin() const { return data
.get(); }
69 char* End() const { return data
.get() + size
* step
; }
70 char* LastElement() const { return data
.get() + (size
- 1) * step
; }
71 char* ElementAt(size_t index
) const { return data
.get() + index
* step
; }
74 DISALLOW_COPY_AND_ASSIGN(InnerList
);
77 explicit ListContainerCharAllocator(size_t element_size
)
78 : element_size_(element_size
),
82 AllocateNewList(kDefaultNumElementTypesToReserve
);
85 ListContainerCharAllocator(size_t element_size
, size_t element_count
)
86 : element_size_(element_size
),
90 AllocateNewList(element_count
> 0 ? element_count
91 : kDefaultNumElementTypesToReserve
);
94 ~ListContainerCharAllocator() {}
97 if (last_list_
->IsFull())
98 AllocateNewList(last_list_
->capacity
* 2);
101 return last_list_
->AddElement();
104 size_t element_size() const { return element_size_
; }
105 size_t list_count() const { return list_count_
; }
106 size_t size() const { return size_
; }
107 bool IsEmpty() const { return size() == 0; }
109 size_t Capacity() const {
110 size_t capacity_sum
= 0;
111 for (typename ScopedPtrVector
<InnerList
>::const_iterator iter
=
113 iter
!= storage_
.end();
115 capacity_sum
+= (*iter
)->capacity
;
121 size_t initial_allocation_size
= storage_
.front()->capacity
;
126 AllocateNewList(initial_allocation_size
);
129 void Erase(PositionInListContainerCharAllocator position
) {
130 DCHECK_EQ(this, position
.ptr_to_container
);
131 storage_
[position
.vector_index
]->Erase(position
.item_iterator
);
132 // TODO(weiliangc): Free the InnerList if it is empty.
136 InnerList
* InnerListById(size_t id
) const {
137 DCHECK_LT(id
, list_count_
);
141 void AllocateNewList(size_t list_size
) {
143 scoped_ptr
<InnerList
> new_list(new InnerList
);
144 storage_
.push_back(new_list
.Pass());
145 last_list_
= storage_
.back();
146 InnerList
* list
= last_list_
;
147 list
->capacity
= list_size
;
149 list
->step
= element_size_
;
150 list
->data
.reset(new char[list
->capacity
* list
->step
]);
153 size_t NumAvailableElementsInLastList() const {
154 return last_list_
->NumElementsAvailable();
158 ScopedPtrVector
<InnerList
> storage_
;
159 const size_t element_size_
;
162 InnerList
* last_list_
;
164 DISALLOW_COPY_AND_ASSIGN(ListContainerCharAllocator
);
167 // PositionInListContainerCharAllocator
168 //////////////////////////////////////////////////////
169 template <typename BaseElementType
>
170 ListContainer
<BaseElementType
>::PositionInListContainerCharAllocator::
171 PositionInListContainerCharAllocator(const typename ListContainer
<
172 BaseElementType
>::PositionInListContainerCharAllocator
& other
)
173 : ptr_to_container(other
.ptr_to_container
),
174 vector_index(other
.vector_index
),
175 item_iterator(other
.item_iterator
) {
178 template <typename BaseElementType
>
179 ListContainer
<BaseElementType
>::PositionInListContainerCharAllocator::
180 PositionInListContainerCharAllocator(
181 typename ListContainer
<BaseElementType
>::ListContainerCharAllocator
*
185 : ptr_to_container(container
),
186 vector_index(vector_ind
),
187 item_iterator(item_iter
) {
190 template <typename BaseElementType
>
191 bool ListContainer
<BaseElementType
>::PositionInListContainerCharAllocator::
192 operator==(const typename ListContainer
<
193 BaseElementType
>::PositionInListContainerCharAllocator
& other
) const {
194 DCHECK_EQ(ptr_to_container
, other
.ptr_to_container
);
195 return vector_index
== other
.vector_index
&&
196 item_iterator
== other
.item_iterator
;
199 template <typename BaseElementType
>
200 bool ListContainer
<BaseElementType
>::PositionInListContainerCharAllocator::
201 operator!=(const typename ListContainer
<
202 BaseElementType
>::PositionInListContainerCharAllocator
& other
) const {
203 return !(*this == other
);
206 template <typename BaseElementType
>
207 typename ListContainer
<BaseElementType
>::PositionInListContainerCharAllocator
209 BaseElementType
>::PositionInListContainerCharAllocator::Increment() {
210 typename
ListContainerCharAllocator::InnerList
* list
=
211 ptr_to_container
->InnerListById(vector_index
);
212 if (item_iterator
== list
->LastElement()) {
213 if (vector_index
< ptr_to_container
->list_count() - 1) {
215 item_iterator
= ptr_to_container
->InnerListById(vector_index
)->Begin();
217 item_iterator
= NULL
;
220 item_iterator
+= list
->step
;
225 template <typename BaseElementType
>
226 typename ListContainer
<BaseElementType
>::PositionInListContainerCharAllocator
228 BaseElementType
>::PositionInListContainerCharAllocator::ReverseIncrement() {
229 typename
ListContainerCharAllocator::InnerList
* list
=
230 ptr_to_container
->InnerListById(vector_index
);
231 if (item_iterator
== list
->Begin()) {
232 if (vector_index
> 0) {
235 ptr_to_container
->InnerListById(vector_index
)->LastElement();
237 item_iterator
= NULL
;
240 item_iterator
-= list
->step
;
246 ////////////////////////////////////////////
247 template <typename BaseElementType
>
248 ListContainer
<BaseElementType
>::ListContainer(size_t max_size_for_derived_class
)
249 : data_(new ListContainerCharAllocator(max_size_for_derived_class
)) {
252 template <typename BaseElementType
>
253 ListContainer
<BaseElementType
>::ListContainer(
254 size_t max_size_for_derived_class
,
255 size_t num_of_elements_to_reserve_for
)
256 : data_(new ListContainerCharAllocator(max_size_for_derived_class
,
257 num_of_elements_to_reserve_for
)) {
260 template <typename BaseElementType
>
261 ListContainer
<BaseElementType
>::ListContainer()
262 : data_(new ListContainerCharAllocator(sizeof(BaseElementType
))) {
265 template <typename BaseElementType
>
266 ListContainer
<BaseElementType
>::~ListContainer() {
267 for (Iterator i
= begin(); i
!= end(); ++i
) {
268 i
->~BaseElementType();
272 template <typename BaseElementType
>
273 void ListContainer
<BaseElementType
>::EraseAndInvalidateAllPointers(
274 typename ListContainer
<BaseElementType
>::Iterator position
) {
275 BaseElementType
* item
= *position
;
276 item
->~BaseElementType();
277 data_
->Erase(position
);
280 template <typename BaseElementType
>
281 typename ListContainer
<BaseElementType
>::ConstReverseIterator
282 ListContainer
<BaseElementType
>::crbegin() const {
283 if (data_
->IsEmpty())
284 return ConstReverseIterator(data_
.get(), 0, NULL
, 0);
286 size_t last_id
= data_
->list_count() - 1;
287 return ConstReverseIterator(
288 data_
.get(), last_id
, data_
->InnerListById(last_id
)->LastElement(), 0);
291 template <typename BaseElementType
>
292 typename ListContainer
<BaseElementType
>::ConstReverseIterator
293 ListContainer
<BaseElementType
>::crend() const {
294 return ConstReverseIterator(data_
.get(), 0, NULL
, size());
297 template <typename BaseElementType
>
298 typename ListContainer
<BaseElementType
>::ConstReverseIterator
299 ListContainer
<BaseElementType
>::rbegin() const {
303 template <typename BaseElementType
>
304 typename ListContainer
<BaseElementType
>::ConstReverseIterator
305 ListContainer
<BaseElementType
>::rend() const {
309 template <typename BaseElementType
>
310 typename ListContainer
<BaseElementType
>::ReverseIterator
311 ListContainer
<BaseElementType
>::rbegin() {
312 if (data_
->IsEmpty())
313 return ReverseIterator(data_
.get(), 0, NULL
, 0);
315 size_t last_id
= data_
->list_count() - 1;
316 return ReverseIterator(
317 data_
.get(), last_id
, data_
->InnerListById(last_id
)->LastElement(), 0);
320 template <typename BaseElementType
>
321 typename ListContainer
<BaseElementType
>::ReverseIterator
322 ListContainer
<BaseElementType
>::rend() {
323 return ReverseIterator(data_
.get(), 0, NULL
, size());
326 template <typename BaseElementType
>
327 typename ListContainer
<BaseElementType
>::ConstIterator
328 ListContainer
<BaseElementType
>::cbegin() const {
329 if (data_
->IsEmpty())
330 return ConstIterator(data_
.get(), 0, NULL
, 0);
332 return ConstIterator(data_
.get(), 0, data_
->InnerListById(0)->Begin(), 0);
335 template <typename BaseElementType
>
336 typename ListContainer
<BaseElementType
>::ConstIterator
337 ListContainer
<BaseElementType
>::cend() const {
338 if (data_
->IsEmpty())
339 return ConstIterator(data_
.get(), 0, NULL
, size());
341 size_t last_id
= data_
->list_count() - 1;
342 return ConstIterator(data_
.get(), last_id
, NULL
, size());
345 template <typename BaseElementType
>
346 typename ListContainer
<BaseElementType
>::ConstIterator
347 ListContainer
<BaseElementType
>::begin() const {
351 template <typename BaseElementType
>
352 typename ListContainer
<BaseElementType
>::ConstIterator
353 ListContainer
<BaseElementType
>::end() const {
357 template <typename BaseElementType
>
358 typename ListContainer
<BaseElementType
>::Iterator
359 ListContainer
<BaseElementType
>::begin() {
360 if (data_
->IsEmpty())
361 return Iterator(data_
.get(), 0, NULL
, 0);
363 return Iterator(data_
.get(), 0, data_
->InnerListById(0)->Begin(), 0);
366 template <typename BaseElementType
>
367 typename ListContainer
<BaseElementType
>::Iterator
368 ListContainer
<BaseElementType
>::end() {
369 if (data_
->IsEmpty())
370 return Iterator(data_
.get(), 0, NULL
, size());
372 size_t last_id
= data_
->list_count() - 1;
373 return Iterator(data_
.get(), last_id
, NULL
, size());
376 template <typename BaseElementType
>
377 BaseElementType
* ListContainer
<BaseElementType
>::front() {
378 Iterator iter
= begin();
382 template <typename BaseElementType
>
383 BaseElementType
* ListContainer
<BaseElementType
>::back() {
384 ReverseIterator iter
= rbegin();
388 template <typename BaseElementType
>
389 const BaseElementType
* ListContainer
<BaseElementType
>::front() const {
390 ConstIterator iter
= begin();
394 template <typename BaseElementType
>
395 const BaseElementType
* ListContainer
<BaseElementType
>::back() const {
396 ConstReverseIterator iter
= rbegin();
400 template <typename BaseElementType
>
401 const BaseElementType
* ListContainer
<BaseElementType
>::ElementAt(
402 size_t index
) const {
403 DCHECK_LT(index
, size());
404 size_t original_index
= index
;
406 for (list_index
= 0; list_index
< data_
->list_count(); ++list_index
) {
407 size_t current_size
= data_
->InnerListById(list_index
)->size
;
408 if (index
< current_size
)
410 index
-= current_size
;
412 return *ConstIterator(data_
.get(),
414 data_
->InnerListById(list_index
)->ElementAt(index
),
418 template <typename BaseElementType
>
419 BaseElementType
* ListContainer
<BaseElementType
>::ElementAt(size_t index
) {
420 DCHECK_LT(index
, size());
421 size_t original_index
= index
;
423 for (list_index
= 0; list_index
< data_
->list_count(); ++list_index
) {
424 size_t current_size
= data_
->InnerListById(list_index
)->size
;
425 if (index
< current_size
)
427 index
-= current_size
;
429 return *Iterator(data_
.get(),
431 data_
->InnerListById(list_index
)->ElementAt(index
),
435 template <typename BaseElementType
>
436 BaseElementType
* ListContainer
<BaseElementType
>::Allocate(
437 size_t size_of_actual_element_in_bytes
) {
438 DCHECK_LE(size_of_actual_element_in_bytes
, data_
->element_size());
439 void* result
= data_
->Allocate();
440 return static_cast<BaseElementType
*>(result
);
443 template <typename BaseElementType
>
444 size_t ListContainer
<BaseElementType
>::size() const {
445 return data_
->size();
448 template <typename BaseElementType
>
449 bool ListContainer
<BaseElementType
>::empty() const {
450 return data_
->IsEmpty();
453 template <typename BaseElementType
>
454 void ListContainer
<BaseElementType
>::clear() {
455 for (Iterator i
= begin(); i
!= end(); ++i
) {
456 i
->~BaseElementType();
461 template <typename BaseElementType
>
462 size_t ListContainer
<
463 BaseElementType
>::AvailableSizeWithoutAnotherAllocationForTesting() const {
464 return data_
->NumAvailableElementsInLastList();
467 // ListContainer::Iterator
468 /////////////////////////////////////////////////
469 template <typename BaseElementType
>
470 ListContainer
<BaseElementType
>::Iterator::Iterator(
471 ListContainerCharAllocator
* container
,
475 : PositionInListContainerCharAllocator(container
, vector_ind
, item_iter
),
479 template <typename BaseElementType
>
480 ListContainer
<BaseElementType
>::Iterator::~Iterator() {
483 template <typename BaseElementType
>
484 BaseElementType
* ListContainer
<BaseElementType
>::Iterator::operator->() const {
485 return reinterpret_cast<BaseElementType
*>(this->item_iterator
);
488 template <typename BaseElementType
>
489 BaseElementType
* ListContainer
<BaseElementType
>::Iterator::operator*() const {
490 return reinterpret_cast<BaseElementType
*>(this->item_iterator
);
493 template <typename BaseElementType
>
494 typename ListContainer
<BaseElementType
>::Iterator
495 ListContainer
<BaseElementType
>::Iterator::
496 operator++(int unused_post_increment
) {
497 Iterator tmp
= *this;
502 template <typename BaseElementType
>
503 typename ListContainer
<BaseElementType
>::Iterator
&
504 ListContainer
<BaseElementType
>::Iterator::
511 template <typename BaseElementType
>
512 size_t ListContainer
<BaseElementType
>::Iterator::index() const {
516 // ListContainer::ConstIterator
517 /////////////////////////////////////////////////
518 template <typename BaseElementType
>
519 ListContainer
<BaseElementType
>::ConstIterator::ConstIterator(
520 const typename ListContainer
<BaseElementType
>::Iterator
& other
)
521 : PositionInListContainerCharAllocator(other
), index_(other
.index()) {
524 template <typename BaseElementType
>
525 ListContainer
<BaseElementType
>::ConstIterator::ConstIterator(
526 ListContainerCharAllocator
* container
,
530 : PositionInListContainerCharAllocator(container
, vector_ind
, item_iter
),
534 template <typename BaseElementType
>
535 ListContainer
<BaseElementType
>::ConstIterator::~ConstIterator() {
538 template <typename BaseElementType
>
539 const BaseElementType
* ListContainer
<BaseElementType
>::ConstIterator::
541 return reinterpret_cast<const BaseElementType
*>(this->item_iterator
);
544 template <typename BaseElementType
>
545 const BaseElementType
* ListContainer
<BaseElementType
>::ConstIterator::
547 return reinterpret_cast<const BaseElementType
*>(this->item_iterator
);
550 template <typename BaseElementType
>
551 typename ListContainer
<BaseElementType
>::ConstIterator
552 ListContainer
<BaseElementType
>::ConstIterator::
553 operator++(int unused_post_increment
) {
554 ConstIterator tmp
= *this;
559 template <typename BaseElementType
>
560 typename ListContainer
<BaseElementType
>::ConstIterator
&
561 ListContainer
<BaseElementType
>::ConstIterator::
568 template <typename BaseElementType
>
569 size_t ListContainer
<BaseElementType
>::ConstIterator::index() const {
573 // ListContainer::ReverseIterator
574 /////////////////////////////////////////////////
575 template <typename BaseElementType
>
576 ListContainer
<BaseElementType
>::ReverseIterator::ReverseIterator(
577 ListContainerCharAllocator
* container
,
581 : PositionInListContainerCharAllocator(container
, vector_ind
, item_iter
),
585 template <typename BaseElementType
>
586 ListContainer
<BaseElementType
>::ReverseIterator::~ReverseIterator() {
589 template <typename BaseElementType
>
590 BaseElementType
* ListContainer
<BaseElementType
>::ReverseIterator::operator->()
592 return reinterpret_cast<BaseElementType
*>(this->item_iterator
);
595 template <typename BaseElementType
>
596 BaseElementType
* ListContainer
<BaseElementType
>::ReverseIterator::operator*()
598 return reinterpret_cast<BaseElementType
*>(this->item_iterator
);
601 template <typename BaseElementType
>
602 typename ListContainer
<BaseElementType
>::ReverseIterator
603 ListContainer
<BaseElementType
>::ReverseIterator::
604 operator++(int unused_post_increment
) {
605 ReverseIterator tmp
= *this;
610 template <typename BaseElementType
>
611 typename ListContainer
<BaseElementType
>::ReverseIterator
&
612 ListContainer
<BaseElementType
>::ReverseIterator::
614 this->ReverseIncrement();
619 template <typename BaseElementType
>
620 size_t ListContainer
<BaseElementType
>::ReverseIterator::index() const {
624 // ListContainer::ConstReverseIterator
625 /////////////////////////////////////////////////
626 template <typename BaseElementType
>
627 ListContainer
<BaseElementType
>::ConstReverseIterator::ConstReverseIterator(
628 const typename ListContainer
<BaseElementType
>::ReverseIterator
& other
)
629 : PositionInListContainerCharAllocator(other
), index_(other
.index()) {
632 template <typename BaseElementType
>
633 ListContainer
<BaseElementType
>::ConstReverseIterator::ConstReverseIterator(
634 ListContainerCharAllocator
* container
,
638 : PositionInListContainerCharAllocator(container
, vector_ind
, item_iter
),
642 template <typename BaseElementType
>
643 ListContainer
<BaseElementType
>::ConstReverseIterator::~ConstReverseIterator() {
646 template <typename BaseElementType
>
647 const BaseElementType
* ListContainer
<BaseElementType
>::ConstReverseIterator::
649 return reinterpret_cast<const BaseElementType
*>(this->item_iterator
);
652 template <typename BaseElementType
>
653 const BaseElementType
* ListContainer
<BaseElementType
>::ConstReverseIterator::
655 return reinterpret_cast<const BaseElementType
*>(this->item_iterator
);
658 template <typename BaseElementType
>
659 typename ListContainer
<BaseElementType
>::ConstReverseIterator
660 ListContainer
<BaseElementType
>::ConstReverseIterator::
661 operator++(int unused_post_increment
) {
662 ConstReverseIterator tmp
= *this;
667 template <typename BaseElementType
>
668 typename ListContainer
<BaseElementType
>::ConstReverseIterator
&
669 ListContainer
<BaseElementType
>::ConstReverseIterator::
671 this->ReverseIncrement();
676 template <typename BaseElementType
>
677 size_t ListContainer
<BaseElementType
>::ConstReverseIterator::index() const {
681 template class ListContainer
<SharedQuadState
>;
682 template class ListContainer
<DrawQuad
>;