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

/*
 * 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
IndexFn;
NextFn;
ItemFn;
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 { … };

template <typename T, int SI1>
template <int SI2>
void SkTBlockList<T, SI1>::concat(SkTBlockList<T, SI2>&& other) { … }

/**
 * 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 { … };

#endif