blob: 2d877a16adc60e96a78d8fac937dd3e48333da9e [file] [log] [blame]
// Copyright 2015 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.
#ifndef CC_BASE_CONTIGUOUS_CONTAINER_H_
#define CC_BASE_CONTIGUOUS_CONTAINER_H_
#include <stddef.h>
#include <memory>
#include <utility>
#include "base/compiler_specific.h"
#include "base/logging.h"
#include "base/macros.h"
#include "base/stl_util.h"
#include "cc/base/cc_export.h"
namespace cc {
// ContiguousContainer is a container which stores a list of heterogeneous
// objects (in particular, of varying sizes), packed next to one another in
// memory. Objects are never relocated, so it is safe to store pointers to them
// for the lifetime of the container (unless the object is removed).
//
// Memory is allocated in a series of buffers (with exponential growth). When an
// object is allocated, it is given only the space it requires (possibly with
// enough padding to preserve alignment), rather than the maximum possible size.
// This allows small and large objects to coexist without wasting much space.
//
// Since it stores pointers to all of the objects it allocates in a vector, it
// supports efficient iteration and indexing. However, for mutation the
// supported operations are limited to appending to, and removing from, the end
// of the list.
//
// Clients should instantiate ContiguousContainer; ContiguousContainerBase is an
// artifact of the implementation.
class CC_EXPORT ContiguousContainerBase {
protected:
explicit ContiguousContainerBase(size_t max_object_size);
ContiguousContainerBase(size_t max_object_size, size_t initial_size_bytes);
~ContiguousContainerBase();
size_t size() const { return elements_.size(); }
bool empty() const { return !size(); }
size_t GetCapacityInBytes() const;
size_t UsedCapacityInBytes() const;
size_t MemoryUsageInBytes() const;
// These do not invoke constructors or destructors.
void* Allocate(size_t object_size);
void Clear();
void RemoveLast();
void Swap(ContiguousContainerBase& other);
std::vector<void*> elements_;
private:
class Buffer;
Buffer* AllocateNewBufferForNextAllocation(size_t buffer_size);
std::vector<std::unique_ptr<Buffer>> buffers_;
size_t end_index_;
size_t max_object_size_;
DISALLOW_COPY_AND_ASSIGN(ContiguousContainerBase);
};
// For most cases, no alignment stricter than pointer alignment is required. If
// one of the derived classes has stronger alignment requirements (and the
// static_assert fires), set alignment to the least common multiple of the
// derived class alignments. For small structs without pointers, it may be
// possible to reduce alignment for tighter packing.
template <class BaseElementType, unsigned alignment = sizeof(void*)>
class ContiguousContainer : public ContiguousContainerBase {
private:
// Declares itself as a forward iterator, but also supports a few more
// things. The whole random access iterator interface is a bit much.
template <typename BaseIterator, typename ValueType>
class IteratorWrapper
: public std::iterator<std::forward_iterator_tag, ValueType> {
public:
IteratorWrapper() {}
bool operator==(const IteratorWrapper& other) const {
return it_ == other.it_;
}
bool operator!=(const IteratorWrapper& other) const {
return it_ != other.it_;
}
ValueType& operator*() const { return *static_cast<ValueType*>(*it_); }
ValueType* operator->() const { return &operator*(); }
IteratorWrapper operator+(std::ptrdiff_t n) const {
return IteratorWrapper(it_ + n);
}
IteratorWrapper operator++(int) {
IteratorWrapper tmp = *this;
++it_;
return tmp;
}
std::ptrdiff_t operator-(const IteratorWrapper& other) const {
return it_ - other.it_;
}
IteratorWrapper& operator++() {
++it_;
return *this;
}
private:
explicit IteratorWrapper(const BaseIterator& it) : it_(it) {}
BaseIterator it_;
friend class ContiguousContainer;
};
public:
using iterator =
IteratorWrapper<std::vector<void*>::iterator, BaseElementType>;
using const_iterator = IteratorWrapper<std::vector<void*>::const_iterator,
const BaseElementType>;
using reverse_iterator =
IteratorWrapper<std::vector<void*>::reverse_iterator, BaseElementType>;
using const_reverse_iterator =
IteratorWrapper<std::vector<void*>::const_reverse_iterator,
const BaseElementType>;
explicit ContiguousContainer(size_t max_object_size)
: ContiguousContainerBase(Align(max_object_size)) {}
ContiguousContainer(size_t max_object_size, size_t initial_size_bytes)
: ContiguousContainerBase(Align(max_object_size), initial_size_bytes) {}
~ContiguousContainer() {
for (auto& element : *this) {
// MSVC incorrectly reports this variable as unused.
(void)element;
element.~BaseElementType();
}
}
using ContiguousContainerBase::size;
using ContiguousContainerBase::empty;
using ContiguousContainerBase::GetCapacityInBytes;
using ContiguousContainerBase::UsedCapacityInBytes;
using ContiguousContainerBase::MemoryUsageInBytes;
iterator begin() { return iterator(elements_.begin()); }
iterator end() { return iterator(elements_.end()); }
const_iterator begin() const { return const_iterator(elements_.begin()); }
const_iterator end() const { return const_iterator(elements_.end()); }
reverse_iterator rbegin() { return reverse_iterator(elements_.rbegin()); }
reverse_iterator rend() { return reverse_iterator(elements_.rend()); }
const_reverse_iterator rbegin() const {
return const_reverse_iterator(elements_.rbegin());
}
const_reverse_iterator rend() const {
return const_reverse_iterator(elements_.rend());
}
BaseElementType& first() { return *begin(); }
const BaseElementType& first() const { return *begin(); }
BaseElementType& last() { return *rbegin(); }
const BaseElementType& last() const { return *rbegin(); }
BaseElementType& operator[](size_t index) { return *(begin() + index); }
const BaseElementType& operator[](size_t index) const {
return *(begin() + index);
}
template <class DerivedElementType, typename... Args>
DerivedElementType& AllocateAndConstruct(Args&&... args) {
static_assert(alignment % ALIGNOF(DerivedElementType) == 0,
"Derived type requires stronger alignment.");
return *new (AlignedAllocate(sizeof(DerivedElementType)))
DerivedElementType(std::forward<Args>(args)...);
}
void RemoveLast() {
DCHECK(!empty());
last().~BaseElementType();
ContiguousContainerBase::RemoveLast();
}
void Clear() {
for (auto& element : *this) {
// MSVC incorrectly reports this variable as unused.
(void)element;
element.~BaseElementType();
}
ContiguousContainerBase::Clear();
}
void Swap(ContiguousContainer& other) {
ContiguousContainerBase::Swap(other);
}
// Appends a new element using memcpy, then default-constructs a base
// element in its place. Use with care.
BaseElementType& AppendByMoving(BaseElementType* item, size_t size) {
DCHECK_GE(size, sizeof(BaseElementType));
void* new_item = AlignedAllocate(size);
memcpy(new_item, static_cast<void*>(item), size);
new (item) BaseElementType;
return *static_cast<BaseElementType*>(new_item);
}
private:
void* AlignedAllocate(size_t size) {
void* result = ContiguousContainerBase::Allocate(Align(size));
DCHECK_EQ(reinterpret_cast<intptr_t>(result) & (alignment - 1), 0u);
return result;
}
size_t Align(size_t size) {
size_t aligned_size = alignment * ((size + alignment - 1) / alignment);
DCHECK_EQ(aligned_size % alignment, 0u);
DCHECK_GE(aligned_size, size);
DCHECK_LT(aligned_size, size + alignment);
return aligned_size;
}
};
} // namespace cc
#endif // CC_BASE_CONTIGUOUS_CONTAINER_H_