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     bool IsEmpty() const { return !size; }
  57     bool IsFull() { return capacity == size; }
  58     size_t NumElementsAvailable() const { return capacity - size; }
  59
  60     void* AddElement() {
  61       DCHECK_LT(size, capacity);
  62       ++size;
  63       return LastElement();
  64     }
  65
  66     void RemoveLast() {
  67       DCHECK(!IsEmpty());
  68       --size;
  69     }
  70
  71     char* Begin() const { return data.get(); }
  72     char* End() const { return data.get() + size * step; }
  73     char* LastElement() const { return data.get() + (size - 1) * step; }
  74     char* ElementAt(size_t index) const { return data.get() + index * step; }
  75
  76    private:
  77     DISALLOW_COPY_AND_ASSIGN(InnerList);
  78   };
  79
  80   explicit ListContainerCharAllocator(size_t element_size)
  81       : element_size_(element_size),
  82         size_(0),
  83         last_list_index_(0),
  84         last_list_(NULL) {
  85     AllocateNewList(kDefaultNumElementTypesToReserve);
  86     last_list_ = storage_[last_list_index_];
  87   }
  88
  89   ListContainerCharAllocator(size_t element_size, size_t element_count)
  90       : element_size_(element_size),
  91         size_(0),
  92         last_list_index_(0),
  93         last_list_(NULL) {
  94     AllocateNewList(element_count > 0 ? element_count
  95                                       : kDefaultNumElementTypesToReserve);
  96     last_list_ = storage_[last_list_index_];
  97   }
  98
  99   ~ListContainerCharAllocator() {}
 100
 101   void* Allocate() {
 102     if (last_list_->IsFull()) {
 103       // Only allocate a new list if there isn't a spare one still there from
 104       // previous usage.
 105       if (last_list_index_ + 1 >= storage_.size())
 106         AllocateNewList(last_list_->capacity * 2);
 107
 108       ++last_list_index_;
 109       last_list_ = storage_[last_list_index_];
 110     }
 111
 112     ++size_;
 113     return last_list_->AddElement();
 114   }
 115
 116   size_t element_size() const { return element_size_; }
 117   size_t list_count() const { return storage_.size(); }
 118   size_t size() const { return size_; }
 119   bool IsEmpty() const { return size() == 0; }
 120
 121   size_t Capacity() const {
 122     size_t capacity_sum = 0;
 123     for (ScopedPtrVector<InnerList>::const_iterator iter = storage_.begin();
 124          iter != storage_.end(); ++iter) {
 125       capacity_sum += (*iter)->capacity;
 126     }
 127     return capacity_sum;
 128   }
 129
 130   void Clear() {
 131     size_t initial_allocation_size = storage_.front()->capacity;
 132     storage_.clear();
 133     last_list_ = NULL;
 134     last_list_index_ = 0;
 135     size_ = 0;
 136     AllocateNewList(initial_allocation_size);
 137     last_list_ = storage_[last_list_index_];
 138   }
 139
 140   void RemoveLast() {
 141     DCHECK(!IsEmpty());
 142     last_list_->RemoveLast();
 143     if (last_list_->IsEmpty() && last_list_index_ > 0) {
 144       --last_list_index_;
 145       last_list_ = storage_[last_list_index_];
 146
 147       // If there are now two empty inner lists, free one of them.
 148       if (last_list_index_ + 2 < storage_.size())
 149         storage_.pop_back();
 150     }
 151     --size_;
 152   }
 153
 154   void Erase(PositionInListContainerCharAllocator position) {
 155     DCHECK_EQ(this, position.ptr_to_container);
 156     storage_[position.vector_index]->Erase(position.item_iterator);
 157     // TODO(weiliangc): Free the InnerList if it is empty.
 158     --size_;
 159   }
 160
 161   InnerList* InnerListById(size_t id) const {
 162     DCHECK_LT(id, storage_.size());
 163     return storage_[id];
 164   }
 165
 166   size_t FirstInnerListId() const {
 167     // |size_| > 0 means that at least one vector in |storage_| will be
 168     // non-empty.
 169     DCHECK_GT(size_, 0u);
 170     size_t id = 0;
 171     while (storage_[id]->size == 0)
 172       ++id;
 173     return id;
 174   }
 175
 176   size_t LastInnerListId() const {
 177     // |size_| > 0 means that at least one vector in |storage_| will be
 178     // non-empty.
 179     DCHECK_GT(size_, 0u);
 180     size_t id = storage_.size() - 1;
 181     while (storage_[id]->size == 0)
 182       --id;
 183     return id;
 184   }
 185
 186   size_t NumAvailableElementsInLastList() const {
 187     return last_list_->NumElementsAvailable();
 188   }
 189
 190  private:
 191   void AllocateNewList(size_t list_size) {
 192     scoped_ptr<InnerList> new_list(new InnerList);
 193     new_list->capacity = list_size;
 194     new_list->size = 0;
 195     new_list->step = element_size_;
 196     new_list->data.reset(new char[list_size * element_size_]);
 197     storage_.push_back(new_list.Pass());
 198   }
 199
 200   ScopedPtrVector<InnerList> storage_;
 201   const size_t element_size_;
 202
 203   // The number of elements in the list.
 204   size_t size_;
 205
 206   // The index of the last list to have had elements added to it, or the only
 207   // list if the container has not had elements added since being cleared.
 208   size_t last_list_index_;
 209
 210   // This is equivalent to |storage_[last_list_index_]|.
 211   InnerList* last_list_;
 212
 213   DISALLOW_COPY_AND_ASSIGN(ListContainerCharAllocator);
 214 };
 215
 216 // PositionInListContainerCharAllocator
 217 //////////////////////////////////////////////////////
 218 ListContainerBase::PositionInListContainerCharAllocator::
 219     PositionInListContainerCharAllocator(
 220         const ListContainerBase::PositionInListContainerCharAllocator& other)
 221     : ptr_to_container(other.ptr_to_container),
 222       vector_index(other.vector_index),
 223       item_iterator(other.item_iterator) {
 224 }
 225
 226 ListContainerBase::PositionInListContainerCharAllocator::
 227     PositionInListContainerCharAllocator(
 228         ListContainerBase::ListContainerCharAllocator* container,
 229         size_t vector_ind,
 230         char* item_iter)
 231     : ptr_to_container(container),
 232       vector_index(vector_ind),
 233       item_iterator(item_iter) {
 234 }
 235
 236 bool ListContainerBase::PositionInListContainerCharAllocator::operator==(
 237     const ListContainerBase::PositionInListContainerCharAllocator& other)
 238     const {
 239   DCHECK_EQ(ptr_to_container, other.ptr_to_container);
 240   return vector_index == other.vector_index &&
 241          item_iterator == other.item_iterator;
 242 }
 243
 244 bool ListContainerBase::PositionInListContainerCharAllocator::operator!=(
 245     const ListContainerBase::PositionInListContainerCharAllocator& other)
 246     const {
 247   return !(*this == other);
 248 }
 249
 250 ListContainerBase::PositionInListContainerCharAllocator
 251 ListContainerBase::PositionInListContainerCharAllocator::Increment() {
 252   ListContainerCharAllocator::InnerList* list =
 253       ptr_to_container->InnerListById(vector_index);
 254   if (item_iterator == list->LastElement()) {
 255     ++vector_index;
 256     while (vector_index < ptr_to_container->list_count()) {
 257       if (ptr_to_container->InnerListById(vector_index)->size != 0)
 258         break;
 259       ++vector_index;
 260     }
 261     if (vector_index < ptr_to_container->list_count())
 262       item_iterator = ptr_to_container->InnerListById(vector_index)->Begin();
 263     else
 264       item_iterator = NULL;
 265   } else {
 266     item_iterator += list->step;
 267   }
 268   return *this;
 269 }
 270
 271 ListContainerBase::PositionInListContainerCharAllocator
 272 ListContainerBase::PositionInListContainerCharAllocator::ReverseIncrement() {
 273   ListContainerCharAllocator::InnerList* list =
 274       ptr_to_container->InnerListById(vector_index);
 275   if (item_iterator == list->Begin()) {
 276     --vector_index;
 277     // Since |vector_index| is unsigned, we compare < list_count() instead of
 278     // comparing >= 0, as the variable will wrap around when it goes out of
 279     // range (below 0).
 280     while (vector_index < ptr_to_container->list_count()) {
 281       if (ptr_to_container->InnerListById(vector_index)->size != 0)
 282         break;
 283       --vector_index;
 284     }
 285     if (vector_index < ptr_to_container->list_count()) {
 286       item_iterator =
 287           ptr_to_container->InnerListById(vector_index)->LastElement();
 288     } else {
 289       item_iterator = NULL;
 290     }
 291   } else {
 292     item_iterator -= list->step;
 293   }
 294   return *this;
 295 }
 296
 297 // ListContainerBase
 298 ////////////////////////////////////////////
 299 ListContainerBase::ListContainerBase(size_t max_size_for_derived_class)
 300     : data_(new ListContainerCharAllocator(max_size_for_derived_class)) {
 301 }
 302
 303 ListContainerBase::ListContainerBase(size_t max_size_for_derived_class,
 304                                      size_t num_of_elements_to_reserve_for)
 305     : data_(new ListContainerCharAllocator(max_size_for_derived_class,
 306                                            num_of_elements_to_reserve_for)) {
 307 }
 308
 309 ListContainerBase::~ListContainerBase() {
 310 }
 311
 312 void ListContainerBase::RemoveLast() {
 313   data_->RemoveLast();
 314 }
 315
 316 void ListContainerBase::EraseAndInvalidateAllPointers(
 317     ListContainerBase::Iterator position) {
 318   data_->Erase(position);
 319 }
 320
 321 ListContainerBase::ConstReverseIterator ListContainerBase::crbegin() const {
 322   if (data_->IsEmpty())
 323     return crend();
 324
 325   size_t id = data_->LastInnerListId();
 326   return ConstReverseIterator(data_.get(), id,
 327                               data_->InnerListById(id)->LastElement(), 0);
 328 }
 329
 330 ListContainerBase::ConstReverseIterator ListContainerBase::crend() const {
 331   return ConstReverseIterator(data_.get(), static_cast<size_t>(-1), NULL,
 332                               size());
 333 }
 334
 335 ListContainerBase::ReverseIterator ListContainerBase::rbegin() {
 336   if (data_->IsEmpty())
 337     return rend();
 338
 339   size_t id = data_->LastInnerListId();
 340   return ReverseIterator(data_.get(), id,
 341                          data_->InnerListById(id)->LastElement(), 0);
 342 }
 343
 344 ListContainerBase::ReverseIterator ListContainerBase::rend() {
 345   return ReverseIterator(data_.get(), static_cast<size_t>(-1), NULL, size());
 346 }
 347
 348 ListContainerBase::ConstIterator ListContainerBase::cbegin() const {
 349   if (data_->IsEmpty())
 350     return cend();
 351
 352   size_t id = data_->FirstInnerListId();
 353   return ConstIterator(data_.get(), id, data_->InnerListById(id)->Begin(), 0);
 354 }
 355
 356 ListContainerBase::ConstIterator ListContainerBase::cend() const {
 357   if (data_->IsEmpty())
 358     return ConstIterator(data_.get(), 0, NULL, size());
 359
 360   size_t id = data_->list_count();
 361   return ConstIterator(data_.get(), id, NULL, size());
 362 }
 363
 364 ListContainerBase::Iterator ListContainerBase::begin() {
 365   if (data_->IsEmpty())
 366     return end();
 367
 368   size_t id = data_->FirstInnerListId();
 369   return Iterator(data_.get(), id, data_->InnerListById(id)->Begin(), 0);
 370 }
 371
 372 ListContainerBase::Iterator ListContainerBase::end() {
 373   if (data_->IsEmpty())
 374     return Iterator(data_.get(), 0, NULL, size());
 375
 376   size_t id = data_->list_count();
 377   return Iterator(data_.get(), id, NULL, size());
 378 }
 379
 380 ListContainerBase::ConstIterator ListContainerBase::IteratorAt(
 381     size_t index) const {
 382   DCHECK_LT(index, size());
 383   size_t original_index = index;
 384   size_t list_index;
 385   for (list_index = 0; list_index < data_->list_count(); ++list_index) {
 386     size_t current_size = data_->InnerListById(list_index)->size;
 387     if (index < current_size)
 388       break;
 389     index -= current_size;
 390   }
 391   return ConstIterator(data_.get(), list_index,
 392                        data_->InnerListById(list_index)->ElementAt(index),
 393                        original_index);
 394 }
 395
 396 ListContainerBase::Iterator ListContainerBase::IteratorAt(size_t index) {
 397   DCHECK_LT(index, size());
 398   size_t original_index = index;
 399   size_t list_index;
 400   for (list_index = 0; list_index < data_->list_count(); ++list_index) {
 401     size_t current_size = data_->InnerListById(list_index)->size;
 402     if (index < current_size)
 403       break;
 404     index -= current_size;
 405   }
 406   return Iterator(data_.get(), list_index,
 407                   data_->InnerListById(list_index)->ElementAt(index),
 408                   original_index);
 409 }
 410
 411 void* ListContainerBase::Allocate(size_t size_of_actual_element_in_bytes) {
 412   DCHECK_LE(size_of_actual_element_in_bytes, data_->element_size());
 413   return data_->Allocate();
 414 }
 415
 416 size_t ListContainerBase::size() const {
 417   return data_->size();
 418 }
 419
 420 bool ListContainerBase::empty() const {
 421   return data_->IsEmpty();
 422 }
 423
 424 size_t ListContainerBase::MaxSizeForDerivedClass() const {
 425   return data_->element_size();
 426 }
 427
 428 void ListContainerBase::clear() {
 429   data_->Clear();
 430 }
 431
 432 size_t ListContainerBase::AvailableSizeWithoutAnotherAllocationForTesting()
 433     const {
 434   return data_->NumAvailableElementsInLastList();
 435 }
 436
 437 // ListContainerBase::Iterator
 438 /////////////////////////////////////////////////
 439 ListContainerBase::Iterator::Iterator(ListContainerCharAllocator* container,
 440                                       size_t vector_ind,
 441                                       char* item_iter,
 442                                       size_t index)
 443     : PositionInListContainerCharAllocator(container, vector_ind, item_iter),
 444       index_(index) {
 445 }
 446
 447 ListContainerBase::Iterator::~Iterator() {
 448 }
 449
 450 size_t ListContainerBase::Iterator::index() const {
 451   return index_;
 452 }
 453
 454 // ListContainerBase::ConstIterator
 455 /////////////////////////////////////////////////
 456 ListContainerBase::ConstIterator::ConstIterator(
 457     const ListContainerBase::Iterator& other)
 458     : PositionInListContainerCharAllocator(other), index_(other.index()) {
 459 }
 460
 461 ListContainerBase::ConstIterator::ConstIterator(
 462     ListContainerCharAllocator* container,
 463     size_t vector_ind,
 464     char* item_iter,
 465     size_t index)
 466     : PositionInListContainerCharAllocator(container, vector_ind, item_iter),
 467       index_(index) {
 468 }
 469
 470 ListContainerBase::ConstIterator::~ConstIterator() {
 471 }
 472
 473 size_t ListContainerBase::ConstIterator::index() const {
 474   return index_;
 475 }
 476
 477 // ListContainerBase::ReverseIterator
 478 /////////////////////////////////////////////////
 479 ListContainerBase::ReverseIterator::ReverseIterator(
 480     ListContainerCharAllocator* container,
 481     size_t vector_ind,
 482     char* item_iter,
 483     size_t index)
 484     : PositionInListContainerCharAllocator(container, vector_ind, item_iter),
 485       index_(index) {
 486 }
 487
 488 ListContainerBase::ReverseIterator::~ReverseIterator() {
 489 }
 490
 491 size_t ListContainerBase::ReverseIterator::index() const {
 492   return index_;
 493 }
 494
 495 // ListContainerBase::ConstReverseIterator
 496 /////////////////////////////////////////////////
 497 ListContainerBase::ConstReverseIterator::ConstReverseIterator(
 498     const ListContainerBase::ReverseIterator& other)
 499     : PositionInListContainerCharAllocator(other), index_(other.index()) {
 500 }
 501
 502 ListContainerBase::ConstReverseIterator::ConstReverseIterator(
 503     ListContainerCharAllocator* container,
 504     size_t vector_ind,
 505     char* item_iter,
 506     size_t index)
 507     : PositionInListContainerCharAllocator(container, vector_ind, item_iter),
 508       index_(index) {
 509 }
 510
 511 ListContainerBase::ConstReverseIterator::~ConstReverseIterator() {
 512 }
 513
 514 size_t ListContainerBase::ConstReverseIterator::index() const {
 515   return index_;
 516 }
 517
 518 }  // namespace cc