chromium/third_party/skia/src/base/SkBlockAllocator.h

/*
 * Copyright 2020 Google LLC
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#ifndef SkBlockAllocator_DEFINED
#define SkBlockAllocator_DEFINED

#include "include/private/base/SkASAN.h"
#include "include/private/base/SkAlign.h"
#include "include/private/base/SkAssert.h"
#include "include/private/base/SkDebug.h"
#include "include/private/base/SkMacros.h"
#include "include/private/base/SkMath.h"
#include "include/private/base/SkNoncopyable.h"

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <new>
#include <type_traits>

/**
 * SkBlockAllocator provides low-level support for a block allocated arena with a dynamic tail that
 * tracks space reservations within each block. Its APIs provide the ability to reserve space,
 * resize reservations, and release reservations. It will automatically create new blocks if needed
 * and destroy all remaining blocks when it is destructed. It assumes that anything allocated within
 * its blocks has its destructors called externally. It is recommended that SkBlockAllocator is
 * wrapped by a higher-level allocator that uses the low-level APIs to implement a simpler,
 * purpose-focused API w/o having to worry as much about byte-level concerns.
 *
 * SkBlockAllocator has no limit to its total size, but each allocation is limited to 512MB (which
 * should be sufficient for Skia's use cases). This upper allocation limit allows all internal
 * operations to be performed using 'int' and avoid many overflow checks. Static asserts are used
 * to ensure that those operations would not overflow when using the largest possible values.
 *
 * Possible use modes:
 * 1. No upfront allocation, either on the stack or as a field
 *    SkBlockAllocator allocator(policy, heapAllocSize);
 *
 * 2. In-place new'd
 *    void* mem = operator new(totalSize);
 *    SkBlockAllocator* allocator = new (mem) SkBlockAllocator(policy, heapAllocSize,
 *                                                             totalSize- sizeof(SkBlockAllocator));
 *    delete allocator;
 *
 * 3. Use SkSBlockAllocator to increase the preallocation size
 *    SkSBlockAllocator<1024> allocator(policy, heapAllocSize);
 *    sizeof(allocator) == 1024;
 */
// TODO(michaelludwig) - While API is different, this shares similarities to SkArenaAlloc and
// SkFibBlockSizes, so we should work to integrate them.
class SkBlockAllocator final : SkNoncopyable { … };

// A wrapper around SkBlockAllocator that includes preallocated storage for the head block.
// N will be the preallocSize() reported by the allocator.
template<size_t N>
class SkSBlockAllocator : SkNoncopyable { … };

///////////////////////////////////////////////////////////////////////////////////////////////////
// Template and inline implementations

SK_MAKE_BITFIELD_OPS(SkBlockAllocator::ReserveFlags)

template<size_t Align, size_t Padding>
constexpr size_t SkBlockAllocator::BlockOverhead() { … }

template<size_t Align, size_t Padding>
constexpr size_t SkBlockAllocator::Overhead() { … }

template<size_t Align, size_t Padding>
constexpr size_t SkBlockAllocator::MaxBlockSize() { … }

template<size_t Align, size_t Padding>
void SkBlockAllocator::reserve(size_t size, ReserveFlags flags) { … }

template <size_t Align, size_t Padding>
SkBlockAllocator::ByteRange SkBlockAllocator::allocate(size_t size) { … }

template <size_t Align, size_t Padding>
SkBlockAllocator::Block* SkBlockAllocator::owningBlock(const void* p, int start) { … }

template <size_t Align, size_t Padding>
int SkBlockAllocator::Block::alignedOffset(int offset) const { … }

bool SkBlockAllocator::Block::resize(int start, int end, int deltaBytes) { … }

// NOTE: release is equivalent to resize(start, end, start - end), and the compiler can optimize
// most of the operations away, but it wasn't able to remove the unnecessary branch comparing the
// new cursor to the block size or old start, so release() gets a specialization.
bool SkBlockAllocator::Block::release(int start, int end) { … }

///////// Block iteration
template <bool Forward, bool Const>
class SkBlockAllocator::BlockIter { … };

SkBlockAllocator::BlockIter<true, false> SkBlockAllocator::blocks() { … }
SkBlockAllocator::BlockIter<true, true> SkBlockAllocator::blocks() const { … }
SkBlockAllocator::BlockIter<false, false> SkBlockAllocator::rblocks() { … }
SkBlockAllocator::BlockIter<false, true> SkBlockAllocator::rblocks() const { … }

#endif // SkBlockAllocator_DEFINED