cc/base/list_container.cc

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