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