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