blob: 319f0d6c0b7f9d70157781bf8bf87f8ed4f89b40 [file] [log] [blame]
// Copyright 2014 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "cc/base/list_container_helper.h"
#include <stddef.h>
#include <algorithm>
#include <cstring>
#include <utility>
#include <vector>
#include "base/check_op.h"
#include "base/memory/aligned_memory.h"
namespace {
const size_t kDefaultNumElementTypesToReserve = 32;
} // namespace
namespace cc {
// CharAllocator
////////////////////////////////////////////////////
// This class deals only with char* and void*. It does allocation and passing
// out raw pointers, as well as memory deallocation when being destroyed.
class ListContainerHelper::CharAllocator {
public:
// CharAllocator::InnerList
/////////////////////////////////////////////
// This class holds the raw memory chunk, as well as information about its
// size and availability.
struct InnerList {
InnerList(size_t capacity, size_t element_size, size_t alignment)
: data(static_cast<char*>(
base::AlignedAlloc(capacity * element_size, alignment))),
capacity(capacity),
size(0),
step(element_size) {}
InnerList(InnerList&& other) = default;
InnerList& operator=(InnerList&& other) = default;
std::unique_ptr<char[], base::AlignedFreeDeleter> data;
// The number of elements in total the memory can hold. The difference
// between capacity and size is the how many more elements this list can
// hold.
size_t capacity;
// The number of elements have been put into this list.
size_t size;
// The size of each element is in bytes. This is used to move from between
// elements' memory locations.
size_t step;
void Erase(char* position) {
// Confident that destructor is called by caller of this function. Since
// CharAllocator does not handle construction after
// allocation, it doesn't handle desctrution before deallocation.
DCHECK_LE(position, LastElement());
DCHECK_GE(position, Begin());
char* start = position + step;
std::copy(start, End(), position);
--size;
// Decrease capacity to avoid creating not full not last InnerList.
--capacity;
}
void InsertBefore(size_t alignment, char** position, size_t count) {
DCHECK_LE(*position, LastElement() + step);
DCHECK_GE(*position, Begin());
// Adjust the size and capacity
size_t old_size = size;
size += count;
capacity = size;
// Allocate the new data and update the iterator's pointer.
std::unique_ptr<char[], base::AlignedFreeDeleter> new_data(
static_cast<char*>(base::AlignedAlloc(size * step, alignment)));
size_t position_offset = *position - Begin();
*position = new_data.get() + position_offset;
// Copy the data before the inserted segment
memcpy(new_data.get(), data.get(), position_offset);
// Copy the data after the inserted segment.
memcpy(new_data.get() + position_offset + count * step,
data.get() + position_offset, old_size * step - position_offset);
data = std::move(new_data);
}
bool IsEmpty() const { return !size; }
bool IsFull() { return capacity == size; }
size_t NumElementsAvailable() const { return capacity - size; }
void* AddElement() {
DCHECK_LT(size, capacity);
++size;
return LastElement();
}
void RemoveLast() {
DCHECK(!IsEmpty());
--size;
}
char* Begin() const { return data.get(); }
char* End() const { return data.get() + size * step; }
char* LastElement() const { return data.get() + (size - 1) * step; }
char* ElementAt(size_t index) const { return data.get() + index * step; }
};
CharAllocator(size_t alignment, size_t element_size, size_t element_count)
// base::AlignedAlloc does not accept alignment less than sizeof(void*).
: alignment_(std::max(sizeof(void*), alignment)),
element_size_(element_size),
size_(0),
last_list_index_(0),
last_list_(nullptr) {
// If this fails, then alignment of elements after the first could be wrong,
// and we need to pad sizes to fix that.
DCHECK_EQ(element_size % alignment, 0u);
AllocateNewList(element_count > 0 ? element_count
: kDefaultNumElementTypesToReserve);
last_list_ = &storage_[last_list_index_];
}
CharAllocator(const CharAllocator&) = delete;
~CharAllocator() = default;
CharAllocator& operator=(const CharAllocator&) = delete;
void* Allocate() {
if (last_list_->IsFull()) {
// Only allocate a new list if there isn't a spare one still there from
// previous usage.
if (last_list_index_ + 1 >= storage_.size())
AllocateNewList(last_list_->capacity * 2);
++last_list_index_;
last_list_ = &storage_[last_list_index_];
}
++size_;
return last_list_->AddElement();
}
size_t alignment() const { return alignment_; }
size_t element_size() const { return element_size_; }
size_t list_count() const { return storage_.size(); }
size_t size() const { return size_; }
bool IsEmpty() const { return size() == 0; }
size_t Capacity() const {
size_t capacity_sum = 0;
for (const auto& inner_list : storage_)
capacity_sum += inner_list.capacity;
return capacity_sum;
}
void Clear() {
// Remove all except for the first InnerList.
DCHECK(!storage_.empty());
storage_.erase(storage_.begin() + 1, storage_.end());
last_list_index_ = 0;
last_list_ = &storage_[0];
last_list_->size = 0;
size_ = 0;
}
void RemoveLast() {
DCHECK(!IsEmpty());
last_list_->RemoveLast();
if (last_list_->IsEmpty() && last_list_index_ > 0) {
--last_list_index_;
last_list_ = &storage_[last_list_index_];
// If there are now two empty inner lists, free one of them.
if (last_list_index_ + 2 < storage_.size())
storage_.pop_back();
}
--size_;
}
void Erase(PositionInCharAllocator* position) {
DCHECK_EQ(this, position->ptr_to_container);
// Update |position| to point to the element after the erased element.
InnerList& list = storage_[position->vector_index];
char* item_iterator = position->item_iterator;
if (item_iterator == list.LastElement())
position->Increment();
list.Erase(item_iterator);
// TODO(weiliangc): Free the InnerList if it is empty.
--size_;
}
void InsertBefore(ListContainerHelper::Iterator* position, size_t count) {
if (!count)
return;
// If |position| is End(), then append |count| elements at the end. This
// will happen to not invalidate any iterators or memory.
if (!position->item_iterator) {
// Set |position| to be the first inserted element.
Allocate();
position->vector_index = storage_.size() - 1;
position->item_iterator = storage_[position->vector_index].LastElement();
// Allocate the rest.
for (size_t i = 1; i < count; ++i)
Allocate();
} else {
storage_[position->vector_index].InsertBefore(
alignment_, &position->item_iterator, count);
size_ += count;
}
}
const InnerList& InnerListById(size_t id) const {
DCHECK_LT(id, storage_.size());
return storage_[id];
}
size_t FirstInnerListId() const {
// |size_| > 0 means that at least one vector in |storage_| will be
// non-empty.
DCHECK_GT(size_, 0u);
size_t id = 0;
while (storage_[id].size == 0)
++id;
return id;
}
size_t LastInnerListId() const {
// |size_| > 0 means that at least one vector in |storage_| will be
// non-empty.
DCHECK_GT(size_, 0u);
size_t id = storage_.size() - 1;
while (storage_[id].size == 0)
--id;
return id;
}
size_t NumAvailableElementsInLastList() const {
return last_list_->NumElementsAvailable();
}
private:
void AllocateNewList(size_t list_size) {
storage_.emplace_back(list_size, element_size_, alignment_);
}
std::vector<InnerList> storage_;
const size_t alignment_;
const size_t element_size_;
// The number of elements in the list.
size_t size_;
// The index of the last list to have had elements added to it, or the only
// list if the container has not had elements added since being cleared.
size_t last_list_index_;
// This is equivalent to |storage_[last_list_index_]|.
//
// `last_list_` is not a raw_ptr<...> for performance reasons (based on
// analysis of sampling profiler data and tab_search:top100:2020).
InnerList* last_list_;
};
// PositionInCharAllocator
//////////////////////////////////////////////////////
ListContainerHelper::PositionInCharAllocator::PositionInCharAllocator(
const ListContainerHelper::PositionInCharAllocator& other) = default;
ListContainerHelper::PositionInCharAllocator&
ListContainerHelper::PositionInCharAllocator::operator=(
const ListContainerHelper::PositionInCharAllocator& other) = default;
ListContainerHelper::PositionInCharAllocator::PositionInCharAllocator(
ListContainerHelper::CharAllocator* container,
size_t vector_ind,
char* item_iter)
: ptr_to_container(container),
vector_index(vector_ind),
item_iterator(item_iter) {}
bool ListContainerHelper::PositionInCharAllocator::operator==(
const ListContainerHelper::PositionInCharAllocator& other) const {
DCHECK_EQ(ptr_to_container, other.ptr_to_container);
return vector_index == other.vector_index &&
item_iterator == other.item_iterator;
}
bool ListContainerHelper::PositionInCharAllocator::operator!=(
const ListContainerHelper::PositionInCharAllocator& other) const {
return !(*this == other);
}
ListContainerHelper::PositionInCharAllocator
ListContainerHelper::PositionInCharAllocator::Increment() {
const auto& list = ptr_to_container->InnerListById(vector_index);
if (item_iterator == list.LastElement()) {
++vector_index;
while (vector_index < ptr_to_container->list_count()) {
if (ptr_to_container->InnerListById(vector_index).size != 0)
break;
++vector_index;
}
if (vector_index < ptr_to_container->list_count())
item_iterator = ptr_to_container->InnerListById(vector_index).Begin();
else
item_iterator = nullptr;
} else {
item_iterator += list.step;
}
return *this;
}
ListContainerHelper::PositionInCharAllocator
ListContainerHelper::PositionInCharAllocator::ReverseIncrement() {
const auto& list = ptr_to_container->InnerListById(vector_index);
if (item_iterator == list.Begin()) {
--vector_index;
// Since |vector_index| is unsigned, we compare < list_count() instead of
// comparing >= 0, as the variable will wrap around when it goes out of
// range (below 0).
while (vector_index < ptr_to_container->list_count()) {
if (ptr_to_container->InnerListById(vector_index).size != 0)
break;
--vector_index;
}
if (vector_index < ptr_to_container->list_count()) {
item_iterator =
ptr_to_container->InnerListById(vector_index).LastElement();
} else {
item_iterator = nullptr;
}
} else {
item_iterator -= list.step;
}
return *this;
}
// ListContainerHelper
////////////////////////////////////////////
ListContainerHelper::ListContainerHelper(size_t alignment,
size_t max_size_for_derived_class,
size_t num_of_elements_to_reserve_for)
: data_(std::make_unique<CharAllocator>(alignment,
max_size_for_derived_class,
num_of_elements_to_reserve_for)) {}
ListContainerHelper::~ListContainerHelper() = default;
void ListContainerHelper::RemoveLast() {
data_->RemoveLast();
}
void ListContainerHelper::EraseAndInvalidateAllPointers(
ListContainerHelper::Iterator* position) {
data_->Erase(position);
}
void ListContainerHelper::InsertBeforeAndInvalidateAllPointers(
ListContainerHelper::Iterator* position,
size_t count) {
data_->InsertBefore(position, count);
}
ListContainerHelper::ConstReverseIterator ListContainerHelper::crbegin() const {
if (data_->IsEmpty())
return crend();
size_t id = data_->LastInnerListId();
return ConstReverseIterator(data_.get(), id,
data_->InnerListById(id).LastElement(), 0);
}
ListContainerHelper::ConstReverseIterator ListContainerHelper::crend() const {
return ConstReverseIterator(data_.get(), static_cast<size_t>(-1), nullptr,
size());
}
ListContainerHelper::ReverseIterator ListContainerHelper::rbegin() {
if (data_->IsEmpty())
return rend();
size_t id = data_->LastInnerListId();
return ReverseIterator(data_.get(), id,
data_->InnerListById(id).LastElement(), 0);
}
ListContainerHelper::ReverseIterator ListContainerHelper::rend() {
return ReverseIterator(data_.get(), static_cast<size_t>(-1), nullptr, size());
}
ListContainerHelper::ConstIterator ListContainerHelper::cbegin() const {
if (data_->IsEmpty())
return cend();
size_t id = data_->FirstInnerListId();
return ConstIterator(data_.get(), id, data_->InnerListById(id).Begin(), 0);
}
ListContainerHelper::ConstIterator ListContainerHelper::cend() const {
if (data_->IsEmpty())
return ConstIterator(data_.get(), 0, nullptr, size());
size_t id = data_->list_count();
return ConstIterator(data_.get(), id, nullptr, size());
}
ListContainerHelper::Iterator ListContainerHelper::begin() {
if (data_->IsEmpty())
return end();
size_t id = data_->FirstInnerListId();
return Iterator(data_.get(), id, data_->InnerListById(id).Begin(), 0);
}
ListContainerHelper::Iterator ListContainerHelper::end() {
if (data_->IsEmpty())
return Iterator(data_.get(), 0, nullptr, size());
size_t id = data_->list_count();
return Iterator(data_.get(), id, nullptr, size());
}
ListContainerHelper::ConstIterator ListContainerHelper::IteratorAt(
size_t index) const {
DCHECK_LT(index, size());
size_t original_index = index;
size_t list_index;
for (list_index = 0; list_index < data_->list_count(); ++list_index) {
size_t current_size = data_->InnerListById(list_index).size;
if (index < current_size)
break;
index -= current_size;
}
return ConstIterator(data_.get(), list_index,
data_->InnerListById(list_index).ElementAt(index),
original_index);
}
ListContainerHelper::Iterator ListContainerHelper::IteratorAt(size_t index) {
DCHECK_LT(index, size());
size_t original_index = index;
size_t list_index;
for (list_index = 0; list_index < data_->list_count(); ++list_index) {
size_t current_size = data_->InnerListById(list_index).size;
if (index < current_size)
break;
index -= current_size;
}
return Iterator(data_.get(), list_index,
data_->InnerListById(list_index).ElementAt(index),
original_index);
}
void* ListContainerHelper::Allocate(size_t alignment,
size_t size_of_actual_element_in_bytes) {
DCHECK_LE(alignment, data_->alignment());
DCHECK_LE(size_of_actual_element_in_bytes, data_->element_size());
return data_->Allocate();
}
size_t ListContainerHelper::size() const {
return data_->size();
}
bool ListContainerHelper::empty() const {
return data_->IsEmpty();
}
size_t ListContainerHelper::MaxSizeForDerivedClass() const {
return data_->element_size();
}
size_t ListContainerHelper::GetCapacityInBytes() const {
return data_->Capacity() * data_->element_size();
}
void ListContainerHelper::clear() {
data_->Clear();
}
size_t ListContainerHelper::AvailableSizeWithoutAnotherAllocationForTesting()
const {
return data_->NumAvailableElementsInLastList();
}
// ListContainerHelper::Iterator
/////////////////////////////////////////////////
ListContainerHelper::Iterator::Iterator(CharAllocator* container,
size_t vector_ind,
char* item_iter,
size_t index)
: PositionInCharAllocator(container, vector_ind, item_iter),
index_(index) {}
ListContainerHelper::Iterator::~Iterator() = default;
size_t ListContainerHelper::Iterator::index() const {
return index_;
}
// ListContainerHelper::ConstIterator
/////////////////////////////////////////////////
ListContainerHelper::ConstIterator::ConstIterator(
const ListContainerHelper::Iterator& other)
: PositionInCharAllocator(other), index_(other.index()) {}
ListContainerHelper::ConstIterator::ConstIterator(CharAllocator* container,
size_t vector_ind,
char* item_iter,
size_t index)
: PositionInCharAllocator(container, vector_ind, item_iter),
index_(index) {}
ListContainerHelper::ConstIterator::~ConstIterator() = default;
size_t ListContainerHelper::ConstIterator::index() const {
return index_;
}
// ListContainerHelper::ReverseIterator
/////////////////////////////////////////////////
ListContainerHelper::ReverseIterator::ReverseIterator(CharAllocator* container,
size_t vector_ind,
char* item_iter,
size_t index)
: PositionInCharAllocator(container, vector_ind, item_iter),
index_(index) {}
ListContainerHelper::ReverseIterator::~ReverseIterator() = default;
size_t ListContainerHelper::ReverseIterator::index() const {
return index_;
}
// ListContainerHelper::ConstReverseIterator
/////////////////////////////////////////////////
ListContainerHelper::ConstReverseIterator::ConstReverseIterator(
const ListContainerHelper::ReverseIterator& other)
: PositionInCharAllocator(other), index_(other.index()) {}
ListContainerHelper::ConstReverseIterator::ConstReverseIterator(
CharAllocator* container,
size_t vector_ind,
char* item_iter,
size_t index)
: PositionInCharAllocator(container, vector_ind, item_iter),
index_(index) {}
ListContainerHelper::ConstReverseIterator::~ConstReverseIterator() = default;
size_t ListContainerHelper::ConstReverseIterator::index() const {
return index_;
}
} // namespace cc