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/quads/list_container.h" 6 7 #include <algorithm> 8 #include <vector> 9 10 #include "cc/base/scoped_ptr_vector.h" 11 #include "cc/quads/draw_quad.h" 12 #include "cc/quads/shared_quad_state.h" 13 14 namespace { 15 const size_t kDefaultNumElementTypesToReserve = 32; 16 } // namespace 17 18 namespace cc { 19 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 { 26 public: 27 // ListContainerCharAllocator::InnerList 28 ///////////////////////////////////////////// 29 // This class holds the raw memory chunk, as well as information about its 30 // size and availability. 31 struct InnerList { 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 35 // hold. 36 size_t capacity; 37 // The number of elements have been put into this list. 38 size_t size; 39 // The size of each element is in bytes. This is used to move from between 40 // elements' memory locations. 41 size_t step; 42 43 InnerList() : capacity(0), size(0), step(0) {} 44 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); 53 54 --size; 55 // Decrease capacity to avoid creating not full not last InnerList. 56 --capacity; 57 } 58 59 bool IsFull() { return capacity == size; } 60 size_t NumElementsAvailable() const { return capacity - size; } 61 62 void* AddElement() { 63 DCHECK_LT(size, capacity); 64 ++size; 65 return LastElement(); 66 } 67 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; } 72 73 private: 74 DISALLOW_COPY_AND_ASSIGN(InnerList); 75 }; 76 77 explicit ListContainerCharAllocator(size_t element_size) 78 : element_size_(element_size), 79 size_(0), 80 list_count_(0), 81 last_list_(NULL) { 82 AllocateNewList(kDefaultNumElementTypesToReserve); 83 } 84 85 ListContainerCharAllocator(size_t element_size, size_t element_count) 86 : element_size_(element_size), 87 size_(0), 88 list_count_(0), 89 last_list_(NULL) { 90 DCHECK_NE(0u, element_count); 91 AllocateNewList(element_count); 92 } 93 94 ~ListContainerCharAllocator() {} 95 96 void* Allocate() { 97 if (last_list_->IsFull()) 98 AllocateNewList(last_list_->capacity * 2); 99 100 ++size_; 101 return last_list_->AddElement(); 102 } 103 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; } 108 109 size_t Capacity() const { 110 size_t capacity_sum = 0; 111 for (typename ScopedPtrVector<InnerList>::const_iterator iter = 112 storage_.begin(); 113 iter != storage_.end(); 114 ++iter) { 115 capacity_sum += (*iter)->capacity; 116 } 117 return capacity_sum; 118 } 119 120 void Clear() { 121 size_t initial_allocation_size = storage_.front()->capacity; 122 storage_.clear(); 123 list_count_ = 0; 124 last_list_ = NULL; 125 size_ = 0; 126 AllocateNewList(initial_allocation_size); 127 } 128 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. 133 --size_; 134 } 135 136 InnerList* InnerListById(size_t id) const { 137 DCHECK_LT(id, list_count_); 138 return storage_[id]; 139 } 140 141 void AllocateNewList(size_t list_size) { 142 ++list_count_; 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; 148 list->size = 0; 149 list->step = element_size_; 150 list->data.reset(new char[list->capacity * list->step]); 151 } 152 153 size_t NumAvailableElementsInLastList() const { 154 return last_list_->NumElementsAvailable(); 155 } 156 157 private: 158 ScopedPtrVector<InnerList> storage_; 159 const size_t element_size_; 160 size_t size_; 161 size_t list_count_; 162 InnerList* last_list_; 163 164 DISALLOW_COPY_AND_ASSIGN(ListContainerCharAllocator); 165 }; 166 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) { 176 } 177 178 template <typename BaseElementType> 179 ListContainer<BaseElementType>::PositionInListContainerCharAllocator:: 180 PositionInListContainerCharAllocator( 181 typename ListContainer<BaseElementType>::ListContainerCharAllocator* 182 container, 183 size_t vector_ind, 184 char* item_iter) 185 : ptr_to_container(container), 186 vector_index(vector_ind), 187 item_iterator(item_iter) { 188 } 189 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; 197 } 198 199 template <typename BaseElementType> 200 bool ListContainer<BaseElementType>::PositionInListContainerCharAllocator:: 201 operator!=(const typename ListContainer< 202 BaseElementType>::PositionInListContainerCharAllocator& other) const { 203 return !(*this == other); 204 } 205 206 template <typename BaseElementType> 207 typename ListContainer<BaseElementType>::PositionInListContainerCharAllocator 208 ListContainer< 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) { 214 ++vector_index; 215 item_iterator = ptr_to_container->InnerListById(vector_index)->Begin(); 216 } else { 217 item_iterator = NULL; 218 } 219 } else { 220 item_iterator += list->step; 221 } 222 return *this; 223 } 224 225 template <typename BaseElementType> 226 typename ListContainer<BaseElementType>::PositionInListContainerCharAllocator 227 ListContainer< 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) { 233 --vector_index; 234 item_iterator = 235 ptr_to_container->InnerListById(vector_index)->LastElement(); 236 } else { 237 item_iterator = NULL; 238 } 239 } else { 240 item_iterator -= list->step; 241 } 242 return *this; 243 } 244 245 // ListContainer 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)) { 250 } 251 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)) { 258 } 259 260 template <typename BaseElementType> 261 ListContainer<BaseElementType>::ListContainer() 262 : data_(new ListContainerCharAllocator(sizeof(BaseElementType))) { 263 } 264 265 template <typename BaseElementType> 266 ListContainer<BaseElementType>::~ListContainer() { 267 for (Iterator i = begin(); i != end(); ++i) { 268 i->~BaseElementType(); 269 } 270 } 271 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); 278 } 279 280 template <typename BaseElementType> 281 typename ListContainer<BaseElementType>::ConstReverseIterator 282 ListContainer<BaseElementType>::rbegin() const { 283 if (data_->IsEmpty()) 284 return ConstReverseIterator(data_.get(), 0, NULL); 285 286 size_t last_id = data_->list_count() - 1; 287 return ConstReverseIterator( 288 data_.get(), last_id, data_->InnerListById(last_id)->LastElement()); 289 } 290 291 template <typename BaseElementType> 292 typename ListContainer<BaseElementType>::ConstReverseIterator 293 ListContainer<BaseElementType>::rend() const { 294 return ConstReverseIterator(data_.get(), 0, NULL); 295 } 296 297 template <typename BaseElementType> 298 typename ListContainer<BaseElementType>::ReverseIterator 299 ListContainer<BaseElementType>::rbegin() { 300 if (data_->IsEmpty()) 301 return ReverseIterator(data_.get(), 0, NULL); 302 303 size_t last_id = data_->list_count() - 1; 304 return ReverseIterator( 305 data_.get(), last_id, data_->InnerListById(last_id)->LastElement()); 306 } 307 308 template <typename BaseElementType> 309 typename ListContainer<BaseElementType>::ReverseIterator 310 ListContainer<BaseElementType>::rend() { 311 return ReverseIterator(data_.get(), 0, NULL); 312 } 313 314 template <typename BaseElementType> 315 typename ListContainer<BaseElementType>::ConstIterator 316 ListContainer<BaseElementType>::begin() const { 317 if (data_->IsEmpty()) 318 return ConstIterator(data_.get(), 0, NULL); 319 320 return ConstIterator(data_.get(), 0, data_->InnerListById(0)->Begin()); 321 } 322 323 template <typename BaseElementType> 324 typename ListContainer<BaseElementType>::ConstIterator 325 ListContainer<BaseElementType>::end() const { 326 if (data_->IsEmpty()) 327 return ConstIterator(data_.get(), 0, NULL); 328 329 size_t last_id = data_->list_count() - 1; 330 return ConstIterator(data_.get(), last_id, NULL); 331 } 332 333 template <typename BaseElementType> 334 typename ListContainer<BaseElementType>::Iterator 335 ListContainer<BaseElementType>::begin() { 336 if (data_->IsEmpty()) 337 return Iterator(data_.get(), 0, NULL); 338 339 return Iterator(data_.get(), 0, data_->InnerListById(0)->Begin()); 340 } 341 342 template <typename BaseElementType> 343 typename ListContainer<BaseElementType>::Iterator 344 ListContainer<BaseElementType>::end() { 345 if (data_->IsEmpty()) 346 return Iterator(data_.get(), 0, NULL); 347 348 size_t last_id = data_->list_count() - 1; 349 return Iterator(data_.get(), last_id, NULL); 350 } 351 352 template <typename BaseElementType> 353 BaseElementType* ListContainer<BaseElementType>::front() { 354 Iterator iter = begin(); 355 return &*iter; 356 } 357 358 template <typename BaseElementType> 359 BaseElementType* ListContainer<BaseElementType>::back() { 360 ReverseIterator iter = rbegin(); 361 return &*iter; 362 } 363 364 template <typename BaseElementType> 365 const BaseElementType* ListContainer<BaseElementType>::front() const { 366 ConstIterator iter = begin(); 367 return &*iter; 368 } 369 370 template <typename BaseElementType> 371 const BaseElementType* ListContainer<BaseElementType>::back() const { 372 ConstReverseIterator iter = rbegin(); 373 return &*iter; 374 } 375 376 template <typename BaseElementType> 377 const BaseElementType* ListContainer<BaseElementType>::ElementAt( 378 size_t index) const { 379 DCHECK_LT(index, size()); 380 size_t list_index; 381 for (list_index = 0; list_index < data_->list_count(); ++list_index) { 382 size_t current_size = data_->InnerListById(list_index)->size; 383 if (index < current_size) 384 break; 385 index -= current_size; 386 } 387 return &*ConstIterator(data_.get(), 388 list_index, 389 data_->InnerListById(list_index)->ElementAt(index)); 390 } 391 392 template <typename BaseElementType> 393 BaseElementType* ListContainer<BaseElementType>::ElementAt(size_t index) { 394 DCHECK_LT(index, size()); 395 size_t list_index; 396 for (list_index = 0; list_index < data_->list_count(); ++list_index) { 397 size_t current_size = data_->InnerListById(list_index)->size; 398 if (index < current_size) 399 break; 400 index -= current_size; 401 } 402 return &*Iterator(data_.get(), 403 list_index, 404 data_->InnerListById(list_index)->ElementAt(index)); 405 } 406 407 template <typename BaseElementType> 408 BaseElementType* ListContainer<BaseElementType>::Allocate( 409 size_t size_of_actual_element_in_bytes) { 410 DCHECK_LE(size_of_actual_element_in_bytes, data_->element_size()); 411 void* result = data_->Allocate(); 412 return static_cast<BaseElementType*>(result); 413 } 414 415 template <typename BaseElementType> 416 size_t ListContainer<BaseElementType>::size() const { 417 return data_->size(); 418 } 419 420 template <typename BaseElementType> 421 bool ListContainer<BaseElementType>::empty() const { 422 return data_->IsEmpty(); 423 } 424 425 template <typename BaseElementType> 426 void ListContainer<BaseElementType>::clear() { 427 for (Iterator i = begin(); i != end(); ++i) { 428 i->~BaseElementType(); 429 } 430 data_->Clear(); 431 } 432 433 template <typename BaseElementType> 434 size_t ListContainer< 435 BaseElementType>::AvailableSizeWithoutAnotherAllocationForTesting() const { 436 return data_->NumAvailableElementsInLastList(); 437 } 438 439 // ListContainer::Iterator 440 ///////////////////////////////////////////////// 441 template <typename BaseElementType> 442 ListContainer<BaseElementType>::Iterator::Iterator( 443 ListContainerCharAllocator* container, 444 size_t vector_ind, 445 char* item_iter) 446 : PositionInListContainerCharAllocator(container, vector_ind, item_iter) { 447 } 448 449 template <typename BaseElementType> 450 ListContainer<BaseElementType>::Iterator::~Iterator() { 451 } 452 453 template <typename BaseElementType> 454 BaseElementType* ListContainer<BaseElementType>::Iterator::operator->() const { 455 return reinterpret_cast<BaseElementType*>(this->item_iterator); 456 } 457 458 template <typename BaseElementType> 459 BaseElementType& ListContainer<BaseElementType>::Iterator::operator*() const { 460 return *(reinterpret_cast<BaseElementType*>(this->item_iterator)); 461 } 462 463 template <typename BaseElementType> 464 typename ListContainer<BaseElementType>::Iterator 465 ListContainer<BaseElementType>::Iterator:: 466 operator++(int unused_post_increment) { 467 Iterator tmp = *this; 468 operator++(); 469 return tmp; 470 } 471 472 template <typename BaseElementType> 473 typename ListContainer<BaseElementType>::Iterator 474 ListContainer<BaseElementType>::Iterator:: 475 operator++() { 476 this->Increment(); 477 return *this; 478 } 479 480 // ListContainer::ConstIterator 481 ///////////////////////////////////////////////// 482 template <typename BaseElementType> 483 ListContainer<BaseElementType>::ConstIterator::ConstIterator( 484 const typename ListContainer<BaseElementType>::Iterator& other) 485 : PositionInListContainerCharAllocator(other) { 486 } 487 488 template <typename BaseElementType> 489 ListContainer<BaseElementType>::ConstIterator::ConstIterator( 490 ListContainerCharAllocator* container, 491 size_t vector_ind, 492 char* item_iter) 493 : PositionInListContainerCharAllocator(container, vector_ind, item_iter) { 494 } 495 496 template <typename BaseElementType> 497 ListContainer<BaseElementType>::ConstIterator::~ConstIterator() { 498 } 499 500 template <typename BaseElementType> 501 const BaseElementType* ListContainer<BaseElementType>::ConstIterator:: 502 operator->() const { 503 return reinterpret_cast<const BaseElementType*>(this->item_iterator); 504 } 505 506 template <typename BaseElementType> 507 const BaseElementType& ListContainer<BaseElementType>::ConstIterator:: 508 operator*() const { 509 return *(reinterpret_cast<const BaseElementType*>(this->item_iterator)); 510 } 511 512 template <typename BaseElementType> 513 typename ListContainer<BaseElementType>::ConstIterator 514 ListContainer<BaseElementType>::ConstIterator:: 515 operator++(int unused_post_increment) { 516 ConstIterator tmp = *this; 517 operator++(); 518 return tmp; 519 } 520 521 template <typename BaseElementType> 522 typename ListContainer<BaseElementType>::ConstIterator 523 ListContainer<BaseElementType>::ConstIterator:: 524 operator++() { 525 this->Increment(); 526 return *this; 527 } 528 529 // ListContainer::ReverseIterator 530 ///////////////////////////////////////////////// 531 template <typename BaseElementType> 532 ListContainer<BaseElementType>::ReverseIterator::ReverseIterator( 533 ListContainerCharAllocator* container, 534 size_t vector_ind, 535 char* item_iter) 536 : PositionInListContainerCharAllocator(container, vector_ind, item_iter) { 537 } 538 539 template <typename BaseElementType> 540 ListContainer<BaseElementType>::ReverseIterator::~ReverseIterator() { 541 } 542 543 template <typename BaseElementType> 544 BaseElementType* ListContainer<BaseElementType>::ReverseIterator::operator->() 545 const { 546 return reinterpret_cast<BaseElementType*>(this->item_iterator); 547 } 548 549 template <typename BaseElementType> 550 BaseElementType& ListContainer<BaseElementType>::ReverseIterator::operator*() 551 const { 552 return *(reinterpret_cast<BaseElementType*>(this->item_iterator)); 553 } 554 555 template <typename BaseElementType> 556 typename ListContainer<BaseElementType>::ReverseIterator 557 ListContainer<BaseElementType>::ReverseIterator:: 558 operator++(int unused_post_increment) { 559 ReverseIterator tmp = *this; 560 operator++(); 561 return tmp; 562 } 563 564 template <typename BaseElementType> 565 typename ListContainer<BaseElementType>::ReverseIterator 566 ListContainer<BaseElementType>::ReverseIterator:: 567 operator++() { 568 this->ReverseIncrement(); 569 return *this; 570 } 571 572 // ListContainer::ConstReverseIterator 573 ///////////////////////////////////////////////// 574 template <typename BaseElementType> 575 ListContainer<BaseElementType>::ConstReverseIterator::ConstReverseIterator( 576 const typename ListContainer<BaseElementType>::ReverseIterator& other) 577 : PositionInListContainerCharAllocator(other) { 578 } 579 580 template <typename BaseElementType> 581 ListContainer<BaseElementType>::ConstReverseIterator::ConstReverseIterator( 582 ListContainerCharAllocator* container, 583 size_t vector_ind, 584 char* item_iter) 585 : PositionInListContainerCharAllocator(container, vector_ind, item_iter) { 586 } 587 588 template <typename BaseElementType> 589 ListContainer<BaseElementType>::ConstReverseIterator::~ConstReverseIterator() { 590 } 591 592 template <typename BaseElementType> 593 const BaseElementType* ListContainer<BaseElementType>::ConstReverseIterator:: 594 operator->() const { 595 return reinterpret_cast<const BaseElementType*>(this->item_iterator); 596 } 597 598 template <typename BaseElementType> 599 const BaseElementType& ListContainer<BaseElementType>::ConstReverseIterator:: 600 operator*() const { 601 return *(reinterpret_cast<const BaseElementType*>(this->item_iterator)); 602 } 603 604 template <typename BaseElementType> 605 typename ListContainer<BaseElementType>::ConstReverseIterator 606 ListContainer<BaseElementType>::ConstReverseIterator:: 607 operator++(int unused_post_increment) { 608 ConstReverseIterator tmp = *this; 609 operator++(); 610 return tmp; 611 } 612 613 template <typename BaseElementType> 614 typename ListContainer<BaseElementType>::ConstReverseIterator 615 ListContainer<BaseElementType>::ConstReverseIterator:: 616 operator++() { 617 this->ReverseIncrement(); 618 return *this; 619 } 620 621 template class ListContainer<SharedQuadState>; 622 template class ListContainer<DrawQuad>; 623 624 } // namespace cc 625