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