| OLD | NEW |
| 1 // Copyright 2014 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #include "cc/base/list_container_helper.h" | 5 #include "cc/base/list_container_helper.h" |
| 6 | 6 |
| 7 #include <algorithm> | 7 #include <algorithm> |
| 8 #include <vector> | 8 #include <vector> |
| 9 | 9 |
| 10 #include "cc/base/scoped_ptr_vector.h" | 10 #include "base/logging.h" |
| 11 | 11 |
| 12 namespace { | 12 namespace { |
| 13 const size_t kDefaultNumElementTypesToReserve = 32; | 13 const size_t kDefaultNumElementTypesToReserve = 32; |
| 14 } // namespace | 14 } // namespace |
| 15 | 15 |
| 16 namespace cc { | 16 namespace cc { |
| 17 | 17 |
| 18 // CharAllocator | 18 // CharAllocator |
| 19 //////////////////////////////////////////////////// | 19 //////////////////////////////////////////////////// |
| 20 // This class deals only with char* and void*. It does allocation and passing | 20 // This class deals only with char* and void*. It does allocation and passing |
| (...skipping 75 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 96 char* ElementAt(size_t index) const { return data.get() + index * step; } | 96 char* ElementAt(size_t index) const { return data.get() + index * step; } |
| 97 | 97 |
| 98 private: | 98 private: |
| 99 DISALLOW_COPY_AND_ASSIGN(InnerList); | 99 DISALLOW_COPY_AND_ASSIGN(InnerList); |
| 100 }; | 100 }; |
| 101 | 101 |
| 102 explicit CharAllocator(size_t element_size) | 102 explicit CharAllocator(size_t element_size) |
| 103 : element_size_(element_size), | 103 : element_size_(element_size), |
| 104 size_(0), | 104 size_(0), |
| 105 last_list_index_(0), | 105 last_list_index_(0), |
| 106 last_list_(NULL) { | 106 last_list_(nullptr) { |
| 107 AllocateNewList(kDefaultNumElementTypesToReserve); | 107 AllocateNewList(kDefaultNumElementTypesToReserve); |
| 108 last_list_ = storage_[last_list_index_]; | 108 last_list_ = storage_[last_list_index_].get(); |
| 109 } | 109 } |
| 110 | 110 |
| 111 CharAllocator(size_t element_size, size_t element_count) | 111 CharAllocator(size_t element_size, size_t element_count) |
| 112 : element_size_(element_size), | 112 : element_size_(element_size), |
| 113 size_(0), | 113 size_(0), |
| 114 last_list_index_(0), | 114 last_list_index_(0), |
| 115 last_list_(NULL) { | 115 last_list_(nullptr) { |
| 116 AllocateNewList(element_count > 0 ? element_count | 116 AllocateNewList(element_count > 0 ? element_count |
| 117 : kDefaultNumElementTypesToReserve); | 117 : kDefaultNumElementTypesToReserve); |
| 118 last_list_ = storage_[last_list_index_]; | 118 last_list_ = storage_[last_list_index_].get(); |
| 119 } | 119 } |
| 120 | 120 |
| 121 ~CharAllocator() {} | 121 ~CharAllocator() {} |
| 122 | 122 |
| 123 void* Allocate() { | 123 void* Allocate() { |
| 124 if (last_list_->IsFull()) { | 124 if (last_list_->IsFull()) { |
| 125 // Only allocate a new list if there isn't a spare one still there from | 125 // Only allocate a new list if there isn't a spare one still there from |
| 126 // previous usage. | 126 // previous usage. |
| 127 if (last_list_index_ + 1 >= storage_.size()) | 127 if (last_list_index_ + 1 >= storage_.size()) |
| 128 AllocateNewList(last_list_->capacity * 2); | 128 AllocateNewList(last_list_->capacity * 2); |
| 129 | 129 |
| 130 ++last_list_index_; | 130 ++last_list_index_; |
| 131 last_list_ = storage_[last_list_index_]; | 131 last_list_ = storage_[last_list_index_].get(); |
| 132 } | 132 } |
| 133 | 133 |
| 134 ++size_; | 134 ++size_; |
| 135 return last_list_->AddElement(); | 135 return last_list_->AddElement(); |
| 136 } | 136 } |
| 137 | 137 |
| 138 size_t element_size() const { return element_size_; } | 138 size_t element_size() const { return element_size_; } |
| 139 size_t list_count() const { return storage_.size(); } | 139 size_t list_count() const { return storage_.size(); } |
| 140 size_t size() const { return size_; } | 140 size_t size() const { return size_; } |
| 141 bool IsEmpty() const { return size() == 0; } | 141 bool IsEmpty() const { return size() == 0; } |
| 142 | 142 |
| 143 size_t Capacity() const { | 143 size_t Capacity() const { |
| 144 size_t capacity_sum = 0; | 144 size_t capacity_sum = 0; |
| 145 for (const auto& inner_list : storage_) | 145 for (const auto& inner_list : storage_) |
| 146 capacity_sum += inner_list->capacity; | 146 capacity_sum += inner_list->capacity; |
| 147 return capacity_sum; | 147 return capacity_sum; |
| 148 } | 148 } |
| 149 | 149 |
| 150 void Clear() { | 150 void Clear() { |
| 151 // Remove all except for the first InnerList. | 151 // Remove all except for the first InnerList. |
| 152 DCHECK(!storage_.empty()); | 152 DCHECK(!storage_.empty()); |
| 153 storage_.erase(storage_.begin() + 1, storage_.end()); | 153 storage_.erase(storage_.begin() + 1, storage_.end()); |
| 154 last_list_index_ = 0; | 154 last_list_index_ = 0; |
| 155 last_list_ = storage_[0]; | 155 last_list_ = storage_[0].get(); |
| 156 last_list_->size = 0; | 156 last_list_->size = 0; |
| 157 size_ = 0; | 157 size_ = 0; |
| 158 } | 158 } |
| 159 | 159 |
| 160 void RemoveLast() { | 160 void RemoveLast() { |
| 161 DCHECK(!IsEmpty()); | 161 DCHECK(!IsEmpty()); |
| 162 last_list_->RemoveLast(); | 162 last_list_->RemoveLast(); |
| 163 if (last_list_->IsEmpty() && last_list_index_ > 0) { | 163 if (last_list_->IsEmpty() && last_list_index_ > 0) { |
| 164 --last_list_index_; | 164 --last_list_index_; |
| 165 last_list_ = storage_[last_list_index_]; | 165 last_list_ = storage_[last_list_index_].get(); |
| 166 | 166 |
| 167 // If there are now two empty inner lists, free one of them. | 167 // If there are now two empty inner lists, free one of them. |
| 168 if (last_list_index_ + 2 < storage_.size()) | 168 if (last_list_index_ + 2 < storage_.size()) |
| 169 storage_.pop_back(); | 169 storage_.pop_back(); |
| 170 } | 170 } |
| 171 --size_; | 171 --size_; |
| 172 } | 172 } |
| 173 | 173 |
| 174 void Erase(PositionInCharAllocator* position) { | 174 void Erase(PositionInCharAllocator* position) { |
| 175 DCHECK_EQ(this, position->ptr_to_container); | 175 DCHECK_EQ(this, position->ptr_to_container); |
| 176 | 176 |
| 177 // Update |position| to point to the element after the erased element. | 177 // Update |position| to point to the element after the erased element. |
| 178 InnerList* list = storage_[position->vector_index]; | 178 InnerList* list = storage_[position->vector_index].get(); |
| 179 char* item_iterator = position->item_iterator; | 179 char* item_iterator = position->item_iterator; |
| 180 if (item_iterator == list->LastElement()) | 180 if (item_iterator == list->LastElement()) |
| 181 position->Increment(); | 181 position->Increment(); |
| 182 | 182 |
| 183 list->Erase(item_iterator); | 183 list->Erase(item_iterator); |
| 184 // TODO(weiliangc): Free the InnerList if it is empty. | 184 // TODO(weiliangc): Free the InnerList if it is empty. |
| 185 --size_; | 185 --size_; |
| 186 } | 186 } |
| 187 | 187 |
| 188 void InsertBefore(ListContainerHelper::Iterator* position, size_t count) { | 188 void InsertBefore(ListContainerHelper::Iterator* position, size_t count) { |
| (...skipping 12 matching lines...) Expand all Loading... |
| 201 Allocate(); | 201 Allocate(); |
| 202 } else { | 202 } else { |
| 203 storage_[position->vector_index]->InsertBefore(&position->item_iterator, | 203 storage_[position->vector_index]->InsertBefore(&position->item_iterator, |
| 204 count); | 204 count); |
| 205 size_ += count; | 205 size_ += count; |
| 206 } | 206 } |
| 207 } | 207 } |
| 208 | 208 |
| 209 InnerList* InnerListById(size_t id) const { | 209 InnerList* InnerListById(size_t id) const { |
| 210 DCHECK_LT(id, storage_.size()); | 210 DCHECK_LT(id, storage_.size()); |
| 211 return storage_[id]; | 211 return storage_[id].get(); |
| 212 } | 212 } |
| 213 | 213 |
| 214 size_t FirstInnerListId() const { | 214 size_t FirstInnerListId() const { |
| 215 // |size_| > 0 means that at least one vector in |storage_| will be | 215 // |size_| > 0 means that at least one vector in |storage_| will be |
| 216 // non-empty. | 216 // non-empty. |
| 217 DCHECK_GT(size_, 0u); | 217 DCHECK_GT(size_, 0u); |
| 218 size_t id = 0; | 218 size_t id = 0; |
| 219 while (storage_[id]->size == 0) | 219 while (storage_[id]->size == 0) |
| 220 ++id; | 220 ++id; |
| 221 return id; | 221 return id; |
| (...skipping 16 matching lines...) Expand all Loading... |
| 238 private: | 238 private: |
| 239 void AllocateNewList(size_t list_size) { | 239 void AllocateNewList(size_t list_size) { |
| 240 scoped_ptr<InnerList> new_list(new InnerList); | 240 scoped_ptr<InnerList> new_list(new InnerList); |
| 241 new_list->capacity = list_size; | 241 new_list->capacity = list_size; |
| 242 new_list->size = 0; | 242 new_list->size = 0; |
| 243 new_list->step = element_size_; | 243 new_list->step = element_size_; |
| 244 new_list->data.reset(new char[list_size * element_size_]); | 244 new_list->data.reset(new char[list_size * element_size_]); |
| 245 storage_.push_back(new_list.Pass()); | 245 storage_.push_back(new_list.Pass()); |
| 246 } | 246 } |
| 247 | 247 |
| 248 ScopedPtrVector<InnerList> storage_; | 248 std::vector<scoped_ptr<InnerList>> storage_; |
| 249 const size_t element_size_; | 249 const size_t element_size_; |
| 250 | 250 |
| 251 // The number of elements in the list. | 251 // The number of elements in the list. |
| 252 size_t size_; | 252 size_t size_; |
| 253 | 253 |
| 254 // The index of the last list to have had elements added to it, or the only | 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. | 255 // list if the container has not had elements added since being cleared. |
| 256 size_t last_list_index_; | 256 size_t last_list_index_; |
| 257 | 257 |
| 258 // This is equivalent to |storage_[last_list_index_]|. | 258 // This is equivalent to |storage_[last_list_index_]|. |
| (...skipping 287 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 546 : PositionInCharAllocator(container, vector_ind, item_iter), | 546 : PositionInCharAllocator(container, vector_ind, item_iter), |
| 547 index_(index) {} | 547 index_(index) {} |
| 548 | 548 |
| 549 ListContainerHelper::ConstReverseIterator::~ConstReverseIterator() {} | 549 ListContainerHelper::ConstReverseIterator::~ConstReverseIterator() {} |
| 550 | 550 |
| 551 size_t ListContainerHelper::ConstReverseIterator::index() const { | 551 size_t ListContainerHelper::ConstReverseIterator::index() const { |
| 552 return index_; | 552 return index_; |
| 553 } | 553 } |
| 554 | 554 |
| 555 } // namespace cc | 555 } // namespace cc |
| OLD | NEW |