SkTBlockList< T, StartingItems > Class Template Reference

#include <SkTBlockList.h>

Public Types
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 >

Public Member Functions
	SkTBlockList ()
	SkTBlockList (SkBlockAllocator::GrowthPolicy policy)
	SkTBlockList (int itemsPerBlock, SkBlockAllocator::GrowthPolicy policy=SkBlockAllocator::GrowthPolicy::kFixed)
	~SkTBlockList ()
T &	push_back ()
T &	push_back (const T &t)
T &	push_back (T &&t)
template<typename... Args>
T &	emplace_back (Args &&... args)
template<int SI>
void	concat (SkTBlockList< T, SI > &&other)
void	reserve (int n)
void	pop_back ()
void	reset ()
int	count () const
bool	empty () const
T &	front ()
const T &	front () const
T &	back ()
const T &	back () const
T &	item (int i)
const T &	item (int i) const
Iter	items ()
CIter	items () const
RIter	ritems ()
CRIter	ritems () const
template<int SI2>
void	concat (SkTBlockList< T, SI2 > &&other)

Friends
template<typename S , int N>
class	SkTBlockList
class	TBlockListTestAccess

Detailed Description

template<typename T, int StartingItems = 1>
class SkTBlockList< T, StartingItems >

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.

Definition at line 56 of file SkTBlockList.h.

Member Typedef Documentation

CIter

template<typename T , int StartingItems = 1>

using SkTBlockList< T, StartingItems >::CIter = BlockIndexIterator<const T&, true, true, &First, &Last, &Increment, &GetItem>

Definition at line 288 of file SkTBlockList.h.

CRIter

template<typename T , int StartingItems = 1>

using SkTBlockList< T, StartingItems >::CRIter = BlockIndexIterator<const T&, false, true, &Last, &First, &Decrement, &GetItem>

Definition at line 290 of file SkTBlockList.h.

Iter

template<typename T , int StartingItems = 1>

using SkTBlockList< T, StartingItems >::Iter = BlockIndexIterator<T&, true, false, &First, &Last, &Increment, &GetItem>

Definition at line 287 of file SkTBlockList.h.

RIter

template<typename T , int StartingItems = 1>

using SkTBlockList< T, StartingItems >::RIter = BlockIndexIterator<T&, false, false, &Last, &First, &Decrement, &GetItem>

Definition at line 289 of file SkTBlockList.h.

Constructor & Destructor Documentation

SkTBlockList() [1/3]

template<typename T , int StartingItems = 1>

SkTBlockList< T, StartingItems >::SkTBlockList ( )

inline

Create an list that defaults to using StartingItems as heap increment and the kFixed growth policy (e.g. all allocations will match StartingItems).

Definition at line 62 of file SkTBlockList.h.

: SkTBlockList(SkBlockAllocator::GrowthPolicy::kFixed) {}

SkTBlockList() [2/3]

template<typename T , int StartingItems = 1>

SkTBlockList< T, StartingItems >::SkTBlockList ( SkBlockAllocator::GrowthPolicy  policy )

inlineexplicit

Create an list that defaults to using StartingItems as the heap increment, but with the defined growth policy.

Definition at line 68 of file SkTBlockList.h.

            : SkTBlockList(StartingItems, policy) {}

SkTBlockList() [3/3]

template<typename T , int StartingItems = 1>

SkTBlockList< T, StartingItems >::SkTBlockList ( int  itemsPerBlock, SkBlockAllocator::GrowthPolicy  policy = SkBlockAllocator::GrowthPolicy::kFixed  )

inlineexplicit

Create an list.

Parameters

itemsPerBlock	the number of items to allocate at once
policy	the growth policy for subsequent blocks of items

Definition at line 77 of file SkTBlockList.h.

            : fAllocator(policy,
                         SkBlockAllocator::BlockOverhead<alignof(T)>() + sizeof(T)*itemsPerBlock) {}

~SkTBlockList()

template<typename T , int StartingItems = 1>

SkTBlockList< T, StartingItems >::~SkTBlockList ( )

inline

Definition at line 83 of file SkTBlockList.h.

{ this->reset(); }

Member Function Documentation

back() [1/2]

template<typename T , int StartingItems = 1>

T & SkTBlockList< T, StartingItems >::back ( )

inline

Access last item, only call if count() != 0

Definition at line 204 of file SkTBlockList.h.

              {
        SkASSERT(this->count() > 0 && fAllocator->currentBlock()->metadata() > 0);
        return GetItem(fAllocator->currentBlock(), Last(fAllocator->currentBlock()));
    }

back() [2/2]

template<typename T , int StartingItems = 1>

const T & SkTBlockList< T, StartingItems >::back ( ) const

inline

Definition at line 208 of file SkTBlockList.h.

                          {
        SkASSERT(this->count() > 0 && fAllocator->currentBlock()->metadata() > 0);
        return GetItem(fAllocator->currentBlock(), Last(fAllocator->currentBlock()));
    }

concat() [1/2]

template<typename T , int StartingItems = 1>

template<int SI>

void SkTBlockList< T, StartingItems >::concat

(

SkTBlockList< T, SI > &&

other

)

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).

concat() [2/2]

template<typename T , int StartingItems = 1>

template<int SI2>

void SkTBlockList< T, StartingItems >::concat

(

SkTBlockList< T, SI2 > &&

other

)

Definition at line 307 of file SkTBlockList.h.

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

count()

template<typename T , int StartingItems = 1>

int SkTBlockList< T, StartingItems >::count ( ) const

inline

Returns the item count.

Definition at line 167 of file SkTBlockList.h.

                      {
#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();
    }

emplace_back()

template<typename T , int StartingItems = 1>

template<typename... Args>

T & SkTBlockList< T, StartingItems >::emplace_back ( Args &&...  args )

inline

Definition at line 101 of file SkTBlockList.h.

                                    {
        return *new (this->pushItem()) T(std::forward<Args>(args)...);
    }

empty()

template<typename T , int StartingItems = 1>

bool SkTBlockList< T, StartingItems >::empty ( ) const

inline

Is the count 0?

Definition at line 185 of file SkTBlockList.h.

{ return this->count() == 0; }

front() [1/2]

template<typename T , int StartingItems = 1>

T & SkTBlockList< T, StartingItems >::front ( )

inline

Access first item, only call if count() != 0

Definition at line 190 of file SkTBlockList.h.

               {
        // 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()));
    }

front() [2/2]

template<typename T , int StartingItems = 1>

const T & SkTBlockList< T, StartingItems >::front ( ) const

inline

Definition at line 196 of file SkTBlockList.h.

                           {
        SkASSERT(this->count() > 0 && fAllocator->headBlock()->metadata() > 0);
        return GetItem(fAllocator->headBlock(), First(fAllocator->headBlock()));
    }

item() [1/2]

template<typename T , int StartingItems = 1>

T & SkTBlockList< T, StartingItems >::item ( int  i )

inline

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

Definition at line 217 of file SkTBlockList.h.

                   {
        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;
    }

item() [2/2]

template<typename T , int StartingItems = 1>

const T & SkTBlockList< T, StartingItems >::item ( int  i ) const

inline

Definition at line 237 of file SkTBlockList.h.

                               {
        return const_cast<SkTBlockList*>(this)->item(i);
    }

items() [1/2]

template<typename T , int StartingItems = 1>

Iter SkTBlockList< T, StartingItems >::items ( )

inline

Iterate over all items in allocation order (oldest to newest) using a for-range loop:

for (auto&& T : this->items()) {}

Definition at line 297 of file SkTBlockList.h.

{ return Iter(fAllocator.allocator()); }

items() [2/2]

template<typename T , int StartingItems = 1>

CIter SkTBlockList< T, StartingItems >::items ( ) const

inline

Definition at line 298 of file SkTBlockList.h.

{ return CIter(fAllocator.allocator()); }

pop_back()

template<typename T , int StartingItems = 1>

void SkTBlockList< T, StartingItems >::pop_back ( )

inline

Remove the last item, only call if count() != 0

Definition at line 130 of file SkTBlockList.h.

                    {
        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);
    }

push_back() [1/3]

template<typename T , int StartingItems = 1>

T & SkTBlockList< T, StartingItems >::push_back ( )

inline

Adds an item and returns it.

Returns

the added item.

Definition at line 90 of file SkTBlockList.h.

                   {
        return *new (this->pushItem()) T;
    }

push_back() [2/3]

template<typename T , int StartingItems = 1>

T & SkTBlockList< T, StartingItems >::push_back ( const T &  t )

inline

Definition at line 93 of file SkTBlockList.h.

                             {
        return *new (this->pushItem()) T(t);
    }

push_back() [3/3]

template<typename T , int StartingItems = 1>

T & SkTBlockList< T, StartingItems >::push_back ( T &&  t )

inline

Definition at line 96 of file SkTBlockList.h.

                        {
        return *new (this->pushItem()) T(std::move(t));
    }

reserve()

template<typename T , int StartingItems = 1>

void SkTBlockList< T, StartingItems >::reserve ( int  n )

inline

Allocate, if needed, space to hold N more Ts before another malloc will occur.

Definition at line 117 of file SkTBlockList.h.

                        {
        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);
        }
    }

reset()

template<typename T , int StartingItems = 1>

void SkTBlockList< T, StartingItems >::reset ( )

inline

Removes all added items.

Definition at line 153 of file SkTBlockList.h.

                 {
        // 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();
    }

ritems() [1/2]

template<typename T , int StartingItems = 1>

RIter SkTBlockList< T, StartingItems >::ritems ( )

inline

Definition at line 301 of file SkTBlockList.h.

{ return RIter(fAllocator.allocator()); }

ritems() [2/2]

template<typename T , int StartingItems = 1>

CRIter SkTBlockList< T, StartingItems >::ritems ( ) const

inline

Definition at line 302 of file SkTBlockList.h.

{ return CRIter(fAllocator.allocator()); }

Friends And Related Function Documentation

SkTBlockList

template<typename T , int StartingItems = 1>

template<typename S , int N>

friend class SkTBlockList

friend

Definition at line 244 of file SkTBlockList.h.

TBlockListTestAccess

template<typename T , int StartingItems = 1>

friend class TBlockListTestAccess

friend

Definition at line 245 of file SkTBlockList.h.

---

The documentation for this class was generated from the following file:

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