blob: 88e91a92bb3c6392d22341551a6242fef2712330 [file] [log] [blame]
/*
* Copyright 2010 Google Inc.
*
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
#ifndef SkTBlockList_DEFINED
#define SkTBlockList_DEFINED
#include "include/private/base/SkAssert.h"
#include "include/private/base/SkDebug.h"
#include "include/private/base/SkTo.h"
#include "src/base/SkBlockAllocator.h"
#include <algorithm>
#include <cstring>
#include <type_traits>
#include <utility>
// Forward declarations for the iterators used by SkTBlockList
using IndexFn = int (*)(const SkBlockAllocator::Block*);
using NextFn = int (*)(const SkBlockAllocator::Block*, int);
template<typename T, typename B> using ItemFn = T (*)(B*, int);
template <typename T, bool Forward, bool Const, IndexFn Start, IndexFn End, NextFn Next,
ItemFn<T, typename std::conditional<Const, const SkBlockAllocator::Block,
SkBlockAllocator::Block>::type> Resolve>
class BlockIndexIterator;
/**
* SkTBlockList manages dynamic storage for instances of T, reserving fixed blocks such that
* allocation is amortized across every N instances. In this way it is a hybrid of an array-based
* vector and a linked-list. T can be any type and non-trivial destructors are automatically
* invoked when the SkTBlockList is destructed. The addresses of instances are guaranteed
* not to move except when a list is concatenated to another.
*
* The collection supports storing a templated number of elements inline before heap-allocated
* blocks are made to hold additional instances. By default, the heap blocks are sized to hold the
* same number of items as the inline block. A common pattern is to have the inline size hold only
* a small number of items for the common case and then allocate larger blocks when needed.
*
* If the size of a collection is N, and its block size is B, the complexity of the common
* operations are:
* - push_back()/emplace_back(): O(1), with malloc O(B)
* - pop_back(): O(1), with free O(B)
* - front()/back(): O(1)
* - reset(): O(N) for non-trivial types, O(N/B) for trivial types
* - concat(): O(B)
* - random access: O(N/B)
* - iteration: O(1) at each step
*
* These characteristics make it well suited for allocating items in a LIFO ordering, or otherwise
* acting as a stack, or simply using it as a typed allocator.
*/
template <typename T, int StartingItems = 1>
class SkTBlockList {
public:
/**
* Create an allocator that defaults to using StartingItems as heap increment.
*/
SkTBlockList() : SkTBlockList(StartingItems) {}
/**
* Create an allocator
*
* @param itemsPerBlock the number of items to allocate at once
*/
explicit SkTBlockList(int itemsPerBlock,
SkBlockAllocator::GrowthPolicy policy =
SkBlockAllocator::GrowthPolicy::kFixed)
: fAllocator(policy,
SkBlockAllocator::BlockOverhead<alignof(T)>() + sizeof(T)*itemsPerBlock) {}
~SkTBlockList() { this->reset(); }
/**
* Adds an item and returns it.
*
* @return the added item.
*/
T& push_back() {
return *new (this->pushItem()) T;
}
T& push_back(const T& t) {
return *new (this->pushItem()) T(t);
}
T& push_back(T&& t) {
return *new (this->pushItem()) T(std::move(t));
}
template <typename... Args>
T& emplace_back(Args&&... args) {
return *new (this->pushItem()) T(std::forward<Args>(args)...);
}
/**
* Move all items from 'other' to the end of this collection. When this returns, 'other' will
* be empty. Items in 'other' may be moved as part of compacting the pre-allocated start of
* 'other' into this list (using T's move constructor or memcpy if T is trivially copyable), but
* this is O(StartingItems) and not O(N). All other items are concatenated in O(1).
*/
template <int SI>
void concat(SkTBlockList<T, SI>&& other);
/**
* Allocate, if needed, space to hold N more Ts before another malloc will occur.
*/
void reserve(int n) {
int avail = fAllocator->currentBlock()->template avail<alignof(T)>() / sizeof(T);
if (n > avail) {
int reserved = n - avail;
// Don't consider existing bytes since we've already determined how to split the N items
fAllocator->template reserve<alignof(T)>(
reserved * sizeof(T), SkBlockAllocator::kIgnoreExistingBytes_Flag);
}
}
/**
* Remove the last item, only call if count() != 0
*/
void pop_back() {
SkASSERT(this->count() > 0);
SkBlockAllocator::Block* block = fAllocator->currentBlock();
// Run dtor for the popped item
int releaseIndex = Last(block);
GetItem(block, releaseIndex).~T();
if (releaseIndex == First(block)) {
fAllocator->releaseBlock(block);
} else {
// Since this always follows LIFO, the block should always be able to release the memory
SkAssertResult(block->release(releaseIndex, releaseIndex + sizeof(T)));
block->setMetadata(Decrement(block, releaseIndex));
}
fAllocator->setMetadata(fAllocator->metadata() - 1);
}
/**
* Removes all added items.
*/
void reset() {
// Invoke destructors in reverse order if not trivially destructible
if constexpr (!std::is_trivially_destructible<T>::value) {
for (T& t : this->ritems()) {
t.~T();
}
}
fAllocator->reset();
}
/**
* Returns the item count.
*/
int count() const {
#ifdef SK_DEBUG
// Confirm total count matches sum of block counts
int count = 0;
for (const auto* b :fAllocator->blocks()) {
if (b->metadata() == 0) {
continue; // skip empty
}
count += (sizeof(T) + Last(b) - First(b)) / sizeof(T);
}
SkASSERT(count == fAllocator->metadata());
#endif
return fAllocator->metadata();
}
/**
* Is the count 0?
*/
bool empty() const { return this->count() == 0; }
/**
* Access first item, only call if count() != 0
*/
T& front() {
// This assumes that the head block actually have room to store the first item.
static_assert(StartingItems >= 1);
SkASSERT(this->count() > 0 && fAllocator->headBlock()->metadata() > 0);
return GetItem(fAllocator->headBlock(), First(fAllocator->headBlock()));
}
const T& front() const {
SkASSERT(this->count() > 0 && fAllocator->headBlock()->metadata() > 0);
return GetItem(fAllocator->headBlock(), First(fAllocator->headBlock()));
}
/**
* Access last item, only call if count() != 0
*/
T& back() {
SkASSERT(this->count() > 0 && fAllocator->currentBlock()->metadata() > 0);
return GetItem(fAllocator->currentBlock(), Last(fAllocator->currentBlock()));
}
const T& back() const {
SkASSERT(this->count() > 0 && fAllocator->currentBlock()->metadata() > 0);
return GetItem(fAllocator->currentBlock(), Last(fAllocator->currentBlock()));
}
/**
* Access item by index. Not an operator[] since it should not be considered constant time.
* Use for-range loops by calling items() or ritems() instead to access all added items in order
*/
T& item(int i) {
SkASSERT(i >= 0 && i < this->count());
// Iterate over blocks until we find the one that contains i.
for (auto* b : fAllocator->blocks()) {
if (b->metadata() == 0) {
continue; // skip empty
}
int start = First(b);
int end = Last(b) + sizeof(T); // exclusive
int index = start + i * sizeof(T);
if (index < end) {
return GetItem(b, index);
} else {
i -= (end - start) / sizeof(T);
}
}
SkUNREACHABLE;
}
const T& item(int i) const {
return const_cast<SkTBlockList*>(this)->item(i);
}
private:
// Let other SkTBlockLists have access (only ever used when T and S are the same but you
// cannot have partial specializations declared as a friend...)
template<typename S, int N> friend class SkTBlockList;
friend class TBlockListTestAccess; // for fAllocator
inline static constexpr size_t StartingSize =
SkBlockAllocator::Overhead<alignof(T)>() + StartingItems * sizeof(T);
static T& GetItem(SkBlockAllocator::Block* block, int index) {
return *static_cast<T*>(block->ptr(index));
}
static const T& GetItem(const SkBlockAllocator::Block* block, int index) {
return *static_cast<const T*>(block->ptr(index));
}
static int First(const SkBlockAllocator::Block* b) {
return b->firstAlignedOffset<alignof(T)>();
}
static int Last(const SkBlockAllocator::Block* b) {
return b->metadata();
}
static int Increment(const SkBlockAllocator::Block* b, int index) {
return index + sizeof(T);
}
static int Decrement(const SkBlockAllocator::Block* b, int index) {
return index - sizeof(T);
}
void* pushItem() {
// 'template' required because fAllocator is a template, calling a template member
auto br = fAllocator->template allocate<alignof(T)>(sizeof(T));
SkASSERT(br.fStart == br.fAlignedOffset ||
br.fAlignedOffset == First(fAllocator->currentBlock()));
br.fBlock->setMetadata(br.fAlignedOffset);
fAllocator->setMetadata(fAllocator->metadata() + 1);
return br.fBlock->ptr(br.fAlignedOffset);
}
// N represents the number of items, whereas SkSBlockAllocator takes total bytes, so must
// account for the block allocator's size too.
//
// This class uses the SkBlockAllocator's metadata to track total count of items, and per-block
// metadata to track the index of the last allocated item within each block.
SkSBlockAllocator<StartingSize> fAllocator;
public:
using Iter = BlockIndexIterator<T&, true, false, &First, &Last, &Increment, &GetItem>;
using CIter = BlockIndexIterator<const T&, true, true, &First, &Last, &Increment, &GetItem>;
using RIter = BlockIndexIterator<T&, false, false, &Last, &First, &Decrement, &GetItem>;
using CRIter = BlockIndexIterator<const T&, false, true, &Last, &First, &Decrement, &GetItem>;
/**
* Iterate over all items in allocation order (oldest to newest) using a for-range loop:
*
* for (auto&& T : this->items()) {}
*/
Iter items() { return Iter(fAllocator.allocator()); }
CIter items() const { return CIter(fAllocator.allocator()); }
// Iterate from newest to oldest using a for-range loop.
RIter ritems() { return RIter(fAllocator.allocator()); }
CRIter ritems() const { return CRIter(fAllocator.allocator()); }
};
template <typename T, int SI1>
template <int SI2>
void SkTBlockList<T, SI1>::concat(SkTBlockList<T, SI2>&& other) {
// Optimize the common case where the list to append only has a single item
if (other.empty()) {
return;
} else if (other.count() == 1) {
this->push_back(other.back());
other.pop_back();
return;
}
// Manually move all items in other's head block into this list; all heap blocks from 'other'
// will be appended to the block linked list (no per-item moves needed then).
int headItemCount = 0;
SkBlockAllocator::Block* headBlock = other.fAllocator->headBlock();
SkDEBUGCODE(int oldCount = this->count();)
if (headBlock->metadata() > 0) {
int headStart = First(headBlock);
int headEnd = Last(headBlock) + sizeof(T); // exclusive
headItemCount = (headEnd - headStart) / sizeof(T);
int avail = fAllocator->currentBlock()->template avail<alignof(T)>() / sizeof(T);
if (headItemCount > avail) {
// Make sure there is extra room for the items beyond what's already avail. Use the
// kIgnoreGrowthPolicy_Flag to make this reservation as tight as possible since
// 'other's heap blocks will be appended after it and any extra space is wasted.
fAllocator->template reserve<alignof(T)>((headItemCount - avail) * sizeof(T),
SkBlockAllocator::kIgnoreExistingBytes_Flag |
SkBlockAllocator::kIgnoreGrowthPolicy_Flag);
}
if constexpr (std::is_trivially_copy_constructible<T>::value) {
// memcpy all items at once (or twice between current and reserved space).
SkASSERT(std::is_trivially_destructible<T>::value);
auto copy = [](SkBlockAllocator::Block* src, int start, SkBlockAllocator* dst, int n) {
auto target = dst->template allocate<alignof(T)>(n * sizeof(T));
memcpy(target.fBlock->ptr(target.fAlignedOffset), src->ptr(start), n * sizeof(T));
target.fBlock->setMetadata(target.fAlignedOffset + (n - 1) * sizeof(T));
};
if (avail > 0) {
// Copy 0 to avail items into existing tail block
copy(headBlock, headStart, fAllocator.allocator(), std::min(headItemCount, avail));
}
if (headItemCount > avail) {
// Copy (head count - avail) into the extra reserved space
copy(headBlock, headStart + avail * sizeof(T),
fAllocator.allocator(), headItemCount - avail);
}
fAllocator->setMetadata(fAllocator->metadata() + headItemCount);
} else {
// Move every item over one at a time
for (int i = headStart; i < headEnd; i += sizeof(T)) {
T& toMove = GetItem(headBlock, i);
this->push_back(std::move(toMove));
// Anything of interest should have been moved, but run this since T isn't
// a trusted type.
toMove.~T(); // NOLINT(bugprone-use-after-move): calling dtor always allowed
}
}
other.fAllocator->releaseBlock(headBlock);
}
// other's head block must have been fully copied since it cannot be stolen
SkASSERT(other.fAllocator->headBlock()->metadata() == 0 &&
fAllocator->metadata() == oldCount + headItemCount);
fAllocator->stealHeapBlocks(other.fAllocator.allocator());
fAllocator->setMetadata(fAllocator->metadata() +
(other.fAllocator->metadata() - headItemCount));
other.fAllocator->setMetadata(0);
}
/**
* BlockIndexIterator provides a reusable iterator template for collections built on top of a
* SkBlockAllocator, where each item is of the same type, and the index to an item can be iterated
* over in a known manner. It supports const and non-const, and forward and reverse, assuming it's
* provided with proper functions for starting, ending, and advancing.
*/
template <typename T, // The element type (including any modifiers)
bool Forward, // Are indices within a block increasing or decreasing with iteration?
bool Const, // Whether or not T is const
IndexFn Start, // Returns the index of the first valid item in a block
IndexFn End, // Returns the index of the last valid item (so it is inclusive)
NextFn Next, // Returns the next index given the current index
ItemFn<T, typename std::conditional<Const, const SkBlockAllocator::Block,
SkBlockAllocator::Block>::type> Resolve>
class BlockIndexIterator {
using BlockIter = typename SkBlockAllocator::BlockIter<Forward, Const>;
public:
BlockIndexIterator(BlockIter iter) : fBlockIter(iter) {}
class Item {
public:
bool operator!=(const Item& other) const {
return other.fBlock != fBlock || (SkToBool(*fBlock) && other.fIndex != fIndex);
}
T operator*() const {
SkASSERT(*fBlock);
return Resolve(*fBlock, fIndex);
}
Item& operator++() {
const auto* block = *fBlock;
SkASSERT(block && block->metadata() > 0);
SkASSERT((Forward && Next(block, fIndex) > fIndex) ||
(!Forward && Next(block, fIndex) < fIndex));
fIndex = Next(block, fIndex);
if ((Forward && fIndex > fEndIndex) || (!Forward && fIndex < fEndIndex)) {
++fBlock;
this->setIndices();
}
return *this;
}
private:
friend BlockIndexIterator;
using BlockItem = typename BlockIter::Item;
Item(BlockItem block) : fBlock(block) {
this->setIndices();
}
void setIndices() {
// Skip empty blocks
while(*fBlock && (*fBlock)->metadata() == 0) {
++fBlock;
}
if (*fBlock) {
fIndex = Start(*fBlock);
fEndIndex = End(*fBlock);
} else {
fIndex = 0;
fEndIndex = 0;
}
SkASSERT((Forward && fIndex <= fEndIndex) || (!Forward && fIndex >= fEndIndex));
}
BlockItem fBlock;
int fIndex;
int fEndIndex;
};
Item begin() const { return Item(fBlockIter.begin()); }
Item end() const { return Item(fBlockIter.end()); }
private:
BlockIter fBlockIter;
};
#endif