cc/base/list_container_helper.cc

// Copyright 2014 The Chromium Authors
// 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"
#include "base/memory/raw_ptr_exclusion.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).
  RAW_PTR_EXCLUSION 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