1/*
2 * Copyright 2020 Google LLC
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#ifndef GrBlockAllocator_DEFINED
9#define GrBlockAllocator_DEFINED
10
11#include "include/private/GrTypesPriv.h"
12#include "include/private/SkNoncopyable.h"
13
14#include <memory> // std::unique_ptr
15#include <cstddef> // max_align_t
16
17/**
18 * GrBlockAllocator provides low-level support for a block allocated arena with a dynamic tail that
19 * tracks space reservations within each block. Its APIs provide the ability to reserve space,
20 * resize reservations, and release reservations. It will automatically create new blocks if needed
21 * and destroy all remaining blocks when it is destructed. It assumes that anything allocated within
22 * its blocks has its destructors called externally. It is recommended that GrBlockAllocator is
23 * wrapped by a higher-level allocator that uses the low-level APIs to implement a simpler,
24 * purpose-focused API w/o having to worry as much about byte-level concerns.
25 *
26 * GrBlockAllocator has no limit to its total size, but each allocation is limited to 512MB (which
27 * should be sufficient for Ganesh's use cases). This upper allocation limit allows all internal
28 * operations to be performed using 'int' and avoid many overflow checks. Static asserts are used
29 * to ensure that those operations would not overflow when using the largest possible values.
30 *
31 * Possible use modes:
32 * 1. No upfront allocation, either on the stack or as a field
33 * GrBlockAllocator allocator(policy, heapAllocSize);
34 *
35 * 2. In-place new'd
36 * void* mem = operator new(totalSize);
37 * GrBlockAllocator* allocator = new (mem) GrBlockAllocator(policy, heapAllocSize,
38 * totalSize- sizeof(GrBlockAllocator));
39 * delete allocator;
40 *
41 * 3. Use GrSBlockAllocator to increase the preallocation size
42 * GrSBlockAllocator<1024> allocator(policy, heapAllocSize);
43 * sizeof(allocator) == 1024;
44 */
45class GrBlockAllocator final : SkNoncopyable {
46public:
47 // Largest size that can be requested from allocate(), chosen because it's the largest pow-2
48 // that is less than int32_t::max()/2.
49 static constexpr int kMaxAllocationSize = 1 << 29;
50
51 enum class GrowthPolicy : int {
52 kFixed, // Next block size = N
53 kLinear, // = #blocks * N
54 kFibonacci, // = fibonacci(#blocks) * N
55 kExponential, // = 2^#blocks * N
56 kLast = kExponential
57 };
58 static constexpr int kGrowthPolicyCount = static_cast<int>(GrowthPolicy::kLast) + 1;
59
60 class Block;
61
62 // Tuple representing a range of bytes, marking the unaligned start, the first aligned point
63 // after any padding, and the upper limit depending on requested size.
64 struct ByteRange {
65 Block* fBlock; // Owning block
66 int fStart; // Inclusive byte lower limit of byte range
67 int fAlignedOffset; // >= start, matching alignment requirement (i.e. first real byte)
68 int fEnd; // Exclusive upper limit of byte range
69 };
70
71 class Block final {
72 public:
73 ~Block();
74 void operator delete(void* p) { ::operator delete(p); }
75
76 // Return the maximum allocation size with the given alignment that can fit in this block.
77 template <size_t Align = 1, size_t Padding = 0>
78 int avail() const { return std::max(0, fSize - this->cursor<Align, Padding>()); }
79
80 // Return the aligned offset of the first allocation, assuming it was made with the
81 // specified Align, and Padding. The returned offset does not mean a valid allocation
82 // starts at that offset, this is a utility function for classes built on top to manage
83 // indexing into a block effectively.
84 template <size_t Align = 1, size_t Padding = 0>
85 int firstAlignedOffset() const { return this->alignedOffset<Align, Padding>(kDataStart); }
86
87 // Convert an offset into this block's storage into a usable pointer.
88 void* ptr(int offset) {
89 SkASSERT(offset >= kDataStart && offset < fSize);
90 return reinterpret_cast<char*>(this) + offset;
91 }
92 const void* ptr(int offset) const { return const_cast<Block*>(this)->ptr(offset); }
93
94 // Every block has an extra 'int' for clients to use however they want. It will start
95 // at 0 when a new block is made, or when the head block is reset.
96 int metadata() const { return fMetadata; }
97 void setMetadata(int value) { fMetadata = value; }
98
99 /**
100 * Release the byte range between offset 'start' (inclusive) and 'end' (exclusive). This
101 * will return true if those bytes were successfully reclaimed, i.e. a subsequent allocation
102 * request could occupy the space. Regardless of return value, the provided byte range that
103 * [start, end) represents should not be used until it's re-allocated with allocate<...>().
104 */
105 inline bool release(int start, int end);
106
107 /**
108 * Resize a previously reserved byte range of offset 'start' (inclusive) to 'end'
109 * (exclusive). 'deltaBytes' is the SIGNED change to length of the reservation.
110 *
111 * When negative this means the reservation is shrunk and the new length is (end - start -
112 * |deltaBytes|). If this new length would be 0, the byte range can no longer be used (as if
113 * it were released instead). Asserts that it would not shrink the reservation below 0.
114 *
115 * If 'deltaBytes' is positive, the allocator attempts to increase the length of the
116 * reservation. If 'deltaBytes' is less than or equal to avail() and it was the last
117 * allocation in the block, it can be resized. If there is not enough available bytes to
118 * accommodate the increase in size, or another allocation is blocking the increase in size,
119 * then false will be returned and the reserved byte range is unmodified.
120 */
121 inline bool resize(int start, int end, int deltaBytes);
122
123 private:
124 friend class GrBlockAllocator;
125
126 Block(Block* prev, int allocationSize);
127
128 // Get fCursor, but aligned such that ptr(rval) satisfies Align.
129 template <size_t Align, size_t Padding>
130 int cursor() const { return this->alignedOffset<Align, Padding>(fCursor); }
131
132 template <size_t Align, size_t Padding>
133 int alignedOffset(int offset) const;
134
135 SkDEBUGCODE(int fSentinel;) // known value to check for bad back pointers to blocks
136
137 Block* fNext; // doubly-linked list of blocks
138 Block* fPrev;
139
140 // Each block tracks its own cursor because as later blocks are released, an older block
141 // may become the active tail again.
142 int fSize; // includes the size of the BlockHeader and requested metadata
143 int fCursor; // (this + fCursor) points to next available allocation
144 int fMetadata;
145 };
146
147 // The size of the head block is determined by 'additionalPreallocBytes'. Subsequent heap blocks
148 // are determined by 'policy' and 'blockIncrementBytes', although 'blockIncrementBytes' will be
149 // aligned to std::max_align_t.
150 //
151 // When 'additionalPreallocBytes' > 0, the allocator assumes that many extra bytes immediately
152 // after the allocator can be used by its inline head block. This is useful when the allocator
153 // is in-place new'ed into a larger block of memory, but it should remain set to 0 if stack
154 // allocated or if the class layout does not guarantee that space is present.
155 GrBlockAllocator(GrowthPolicy policy, size_t blockIncrementBytes,
156 size_t additionalPreallocBytes = 0);
157
158 ~GrBlockAllocator() { this->reset(); }
159 void operator delete(void* p) { ::operator delete(p); }
160
161 /**
162 * Helper to calculate the minimum number of bytes needed for heap block size, under the
163 * assumption that Align will be the requested alignment of the first call to allocate().
164 * Ex. To store N instances of T in a heap block, the 'blockIncrementBytes' should be set to
165 * BlockOverhead<alignof(T)>() + N * sizeof(T) when making the GrBlockAllocator.
166 */
167 template<size_t Align = 1, size_t Padding = 0>
168 static constexpr size_t BlockOverhead();
169
170 /**
171 * Helper to calculate the minimum number of bytes needed for a preallocation, under the
172 * assumption that Align will be the requested alignment of the first call to allocate().
173 * Ex. To preallocate a GrSBlockAllocator to hold N instances of T, its arge should be
174 * Overhead<alignof(T)>() + N * sizeof(T)
175 */
176 template<size_t Align = 1, size_t Padding = 0>
177 static constexpr size_t Overhead();
178
179 /**
180 * Return the total number of bytes of the allocator, including its instance overhead, per-block
181 * overhead and space used for allocations.
182 */
183 size_t totalSize() const;
184 /**
185 * Return the total number of bytes usable for allocations. This includes bytes that have
186 * been reserved already by a call to allocate() and bytes that are still available. It is
187 * totalSize() minus all allocator and block-level overhead.
188 */
189 size_t totalUsableSpace() const;
190 /**
191 * Return the total number of usable bytes that have been reserved by allocations. This will
192 * be less than or equal to totalUsableSpace().
193 */
194 size_t totalSpaceInUse() const;
195
196 /**
197 * Return the total number of bytes that were pre-allocated for the GrBlockAllocator. This will
198 * include 'additionalPreallocBytes' passed to the constructor, and represents what the total
199 * size would become after a call to reset().
200 */
201 size_t preallocSize() const {
202 // Don't double count fHead's Block overhead in both sizeof(GrBlockAllocator) and fSize.
203 return sizeof(GrBlockAllocator) + fHead.fSize - BaseHeadBlockSize();
204 }
205 /**
206 * Return the usable size of the inline head block; this will be equal to
207 * 'additionalPreallocBytes' plus any alignment padding that the system had to add to Block.
208 * The returned value represents what could be allocated before a heap block is be created.
209 */
210 size_t preallocUsableSpace() const {
211 return fHead.fSize - kDataStart;
212 }
213
214 /**
215 * Reserve space that will hold 'size' bytes. This will automatically allocate a new block if
216 * there is not enough available space in the current block to provide 'size' bytes. The
217 * returned ByteRange tuple specifies the Block owning the reserved memory, the full byte range,
218 * and the aligned offset within that range to use for the user-facing pointer. The following
219 * invariants hold:
220 *
221 * 1. block->ptr(alignedOffset) is aligned to Align
222 * 2. end - alignedOffset == size
223 * 3. Padding <= alignedOffset - start <= Padding + Align - 1
224 *
225 * Invariant #3, when Padding > 0, allows intermediate allocators to embed metadata along with
226 * the allocations. If the Padding bytes are used for some 'struct Meta', then
227 * ptr(alignedOffset - sizeof(Meta)) can be safely used as a Meta* if Meta's alignment
228 * requirements are less than or equal to the alignment specified in allocate<>. This can be
229 * easily guaranteed by using the pattern:
230 *
231 * allocate<max(UserAlign, alignof(Meta)), sizeof(Meta)>(userSize);
232 *
233 * This ensures that ptr(alignedOffset) will always satisfy UserAlign and
234 * ptr(alignedOffset - sizeof(Meta)) will always satisfy alignof(Meta). Alternatively, memcpy
235 * can be used to read and write values between start and alignedOffset without worrying about
236 * alignment requirements of the metadata.
237 *
238 * For over-aligned allocations, the alignedOffset (as an int) may not be a multiple of Align,
239 * but the result of ptr(alignedOffset) will be a multiple of Align.
240 */
241 template <size_t Align, size_t Padding = 0>
242 ByteRange allocate(size_t size);
243
244 /**
245 * Return a pointer to the start of the current block. This will never be null.
246 */
247 const Block* currentBlock() const { return fTail; }
248 Block* currentBlock() { return fTail; }
249
250 const Block* headBlock() const { return &fHead; }
251 Block* headBlock() { return &fHead; }
252
253 /**
254 * Return the block that owns the allocated 'ptr'. Assuming that earlier, an allocation was
255 * returned as {b, start, alignedOffset, end}, and 'p = b->ptr(alignedOffset)', then a call
256 * to 'owningBlock<Align, Padding>(p, start) == b'.
257 *
258 * If calling code has already made a pointer to their metadata, i.e. 'm = p - Padding', then
259 * 'owningBlock<Align, 0>(m, start)' will also return b, allowing you to recover the block from
260 * the metadata pointer.
261 *
262 * If calling code has access to the original alignedOffset, this function should not be used
263 * since the owning block is just 'p - alignedOffset', regardless of original Align or Padding.
264 */
265 template <size_t Align, size_t Padding = 0>
266 Block* owningBlock(const void* ptr, int start);
267
268 template <size_t Align, size_t Padding = 0>
269 const Block* owningBlock(const void* ptr, int start) const {
270 return const_cast<GrBlockAllocator*>(this)->owningBlock<Align, Padding>(ptr, start);
271 }
272
273 /**
274 * Find the owning block of the allocated pointer, 'p'. Without any additional information this
275 * is O(N) on the number of allocated blocks.
276 */
277 Block* findOwningBlock(const void* ptr);
278 const Block* findOwningBlock(const void* ptr) const {
279 return const_cast<GrBlockAllocator*>(this)->findOwningBlock(ptr);
280 }
281
282 /**
283 * Explicitly free an entire block, invalidating any remaining allocations from the block.
284 * GrBlockAllocator will release all alive blocks automatically when it is destroyed, but this
285 * function can be used to reclaim memory over the lifetime of the allocator. The provided
286 * 'block' pointer must have previously come from a call to currentBlock() or allocate().
287 *
288 * If 'block' represents the inline-allocated head block, its cursor and metadata are instead
289 * reset to their defaults.
290 */
291 void releaseBlock(Block* block);
292
293 /**
294 * Explicitly free all blocks (invalidating all allocations), and resets the head block to its
295 * default state.
296 */
297 void reset();
298
299 template <bool Forward, bool Const> class BlockIter;
300
301 /**
302 * Clients can iterate over all active Blocks in the GrBlockAllocator using for loops:
303 *
304 * Forward iteration from head to tail block (or non-const variant):
305 * for (const Block* b : this->blocks()) { }
306 * Reverse iteration from tail to head block:
307 * for (const Block* b : this->rblocks()) { }
308 */
309 inline BlockIter<true, false> blocks();
310 inline BlockIter<true, true> blocks() const;
311 inline BlockIter<false, false> rblocks();
312 inline BlockIter<false, true> rblocks() const;
313
314#ifdef SK_DEBUG
315 static constexpr int kAssignedMarker = 0xBEEFFACE;
316 static constexpr int kFreedMarker = 0xCAFEBABE;
317
318 void validate() const;
319#endif
320
321private:
322 // Smallest value of fCursor, this will automatically repurpose any alignment padding that
323 // the compiler introduced if the first allocation is aligned less than max_align_t.
324 static constexpr int kDataStart = offsetof(Block, fMetadata) + sizeof(int);
325 static constexpr int kBlockIncrementUnits = alignof(std::max_align_t);
326
327 // Calculates the size of a new Block required to store a kMaxAllocationSize request for the
328 // given alignment and padding bytes. Also represents maximum valid fCursor value in a Block.
329 template<size_t Align, size_t Padding>
330 static constexpr size_t MaxBlockSize();
331
332 static constexpr int BaseHeadBlockSize() {
333 return sizeof(GrBlockAllocator) - offsetof(GrBlockAllocator, fHead);
334 }
335
336 // Append a new block to the end of the block linked list, updating fTail. 'minSize' must
337 // have enough room for sizeof(Block). 'maxSize' is the upper limit of fSize for the new block
338 // that will preserve the static guarantees GrBlockAllocator makes.
339 void addBlock(int minSize, int maxSize);
340
341 Block* fTail; // All non-head blocks are heap allocated; tail will never be null.
342
343 // All remaining state is packed into 64 bits to keep GrBlockAllocator at 16 bytes + head block
344 // (on a 64-bit system).
345
346 // Growth of the block size is controlled by four factors: BlockIncrement, N0 and N1, and a
347 // policy defining how N0 is updated. When a new block is needed, we calculate N1' = N0 + N1.
348 // Depending on the policy, N0' = N0 (no growth or linear growth), or N0' = N1 (Fibonacci), or
349 // N0' = N1' (exponential). The size of the new block is N1' * BlockIncrement * MaxAlign,
350 // after which fN0 and fN1 store N0' and N1' clamped into 23 bits. With current bit allocations,
351 // N1' is limited to 2^24, and assuming MaxAlign=16, then BlockIncrement must be '2' in order to
352 // eventually reach the hard 2^29 size limit of GrBlockAllocator.
353
354 // Next heap block size = (fBlockIncrement * alignof(std::max_align_t) * (fN0 + fN1))
355 uint64_t fBlockIncrement : 16;
356 uint64_t fGrowthPolicy : 2; // GrowthPolicy
357 uint64_t fN0 : 23; // = 1 for linear/exp.; = 0 for fixed/fibonacci, initially
358 uint64_t fN1 : 23; // = 1 initially
359
360 // Inline head block, must be at the end so that it can utilize any additional reserved space
361 // from the initial allocation.
362 alignas(alignof(std::max_align_t)) Block fHead;
363
364 static_assert(kGrowthPolicyCount <= 4);
365};
366
367// A wrapper around GrBlockAllocator that includes preallocated storage for the head block.
368// N will be the preallocSize() reported by the allocator.
369template<size_t N>
370class GrSBlockAllocator : SkNoncopyable {
371public:
372 using GrowthPolicy = GrBlockAllocator::GrowthPolicy;
373
374 GrSBlockAllocator() {
375 new (fStorage) GrBlockAllocator(GrowthPolicy::kFixed, N, N - sizeof(GrBlockAllocator));
376 }
377 explicit GrSBlockAllocator(GrowthPolicy policy) {
378 new (fStorage) GrBlockAllocator(policy, N, N - sizeof(GrBlockAllocator));
379 }
380
381 GrSBlockAllocator(GrowthPolicy policy, size_t blockIncrementBytes) {
382 new (fStorage) GrBlockAllocator(policy, blockIncrementBytes, N - sizeof(GrBlockAllocator));
383 }
384
385 ~GrSBlockAllocator() {
386 this->allocator()->~GrBlockAllocator();
387 }
388
389 GrBlockAllocator* operator->() { return this->allocator(); }
390 const GrBlockAllocator* operator->() const { return this->allocator(); }
391
392 GrBlockAllocator* allocator() { return reinterpret_cast<GrBlockAllocator*>(fStorage); }
393 const GrBlockAllocator* allocator() const {
394 return reinterpret_cast<const GrBlockAllocator*>(fStorage);
395 }
396
397private:
398 static_assert(N >= sizeof(GrBlockAllocator));
399
400 // Will be used to placement new the allocator
401 alignas(GrBlockAllocator) char fStorage[N];
402};
403
404///////////////////////////////////////////////////////////////////////////////////////////////////
405// Template and inline implementations
406
407template<size_t Align, size_t Padding>
408constexpr size_t GrBlockAllocator::BlockOverhead() {
409 return std::max(sizeof(Block), GrAlignTo(kDataStart + Padding, Align));
410}
411
412template<size_t Align, size_t Padding>
413constexpr size_t GrBlockAllocator::Overhead() {
414 return std::max(sizeof(GrBlockAllocator),
415 offsetof(GrBlockAllocator, fHead) + BlockOverhead<Align, Padding>());
416}
417
418template<size_t Align, size_t Padding>
419constexpr size_t GrBlockAllocator::MaxBlockSize() {
420 // Without loss of generality, assumes 'align' will be the largest encountered alignment for the
421 // allocator (if it's not, the largest align will be encountered by the compiler and pass/fail
422 // the same set of static asserts).
423 return BlockOverhead<Align, Padding>() + kMaxAllocationSize;
424}
425
426template <size_t Align, size_t Padding>
427GrBlockAllocator::ByteRange GrBlockAllocator::allocate(size_t size) {
428 // Amount of extra space for a new block to make sure the allocation can succeed.
429 static constexpr int kBlockOverhead = (int) BlockOverhead<Align, Padding>();
430
431 // Ensures 'offset' and 'end' calculations will be valid
432 static_assert((kMaxAllocationSize + GrAlignTo(MaxBlockSize<Align, Padding>(), Align))
433 <= (size_t) std::numeric_limits<int32_t>::max());
434 // Ensures size + blockOverhead + addBlock's alignment operations will be valid
435 static_assert(kMaxAllocationSize + kBlockOverhead + ((1 << 12) - 1) // 4K align for large blocks
436 <= std::numeric_limits<int32_t>::max());
437
438 if (size > kMaxAllocationSize) {
439 SK_ABORT("Allocation too large");
440 }
441
442 int iSize = (int) size;
443 int offset = fTail->cursor<Align, Padding>();
444 int end = offset + iSize;
445 if (end > fTail->fSize) {
446 this->addBlock(iSize + kBlockOverhead, MaxBlockSize<Align, Padding>());
447 offset = fTail->cursor<Align, Padding>();
448 end = offset + iSize;
449 }
450
451 // Check invariants
452 SkASSERT(end <= fTail->fSize);
453 SkASSERT(end - offset == iSize);
454 SkASSERT(offset - fTail->fCursor >= (int) Padding &&
455 offset - fTail->fCursor <= (int) (Padding + Align - 1));
456 SkASSERT(reinterpret_cast<uintptr_t>(fTail->ptr(offset)) % Align == 0);
457
458 int start = fTail->fCursor;
459 fTail->fCursor = end;
460 return {fTail, start, offset, end};
461}
462
463template <size_t Align, size_t Padding>
464GrBlockAllocator::Block* GrBlockAllocator::owningBlock(const void* p, int start) {
465 // 'p' was originally formed by aligning 'block + start + Padding', producing the inequality:
466 // block + start + Padding <= p <= block + start + Padding + Align-1
467 // Rearranging this yields:
468 // block <= p - start - Padding <= block + Align-1
469 // Masking these terms by ~(Align-1) reconstructs 'block' if the alignment of the block is
470 // greater than or equal to Align (since block & ~(Align-1) == (block + Align-1) & ~(Align-1)
471 // in that case). Overalignment does not reduce to inequality unfortunately.
472 if /* constexpr */ (Align <= alignof(std::max_align_t)) {
473 Block* block = reinterpret_cast<Block*>(
474 (reinterpret_cast<uintptr_t>(p) - start - Padding) & ~(Align - 1));
475 SkASSERT(block->fSentinel == kAssignedMarker);
476 return block;
477 } else {
478 // There's not a constant-time expression available to reconstruct the block from 'p',
479 // but this is unlikely to happen frequently.
480 return this->findOwningBlock(p);
481 }
482}
483
484template <size_t Align, size_t Padding>
485int GrBlockAllocator::Block::alignedOffset(int offset) const {
486 static_assert(SkIsPow2(Align));
487 // Aligning adds (Padding + Align - 1) as an intermediate step, so ensure that can't overflow
488 static_assert(MaxBlockSize<Align, Padding>() + Padding + Align - 1
489 <= (size_t) std::numeric_limits<int32_t>::max());
490
491 if /* constexpr */ (Align <= alignof(std::max_align_t)) {
492 // Same as GrAlignTo, but operates on ints instead of size_t
493 return (offset + Padding + Align - 1) & ~(Align - 1);
494 } else {
495 // Must take into account that 'this' may be starting at a pointer that doesn't satisfy the
496 // larger alignment request, so must align the entire pointer, not just offset
497 uintptr_t blockPtr = reinterpret_cast<uintptr_t>(this);
498 uintptr_t alignedPtr = (blockPtr + offset + Padding + Align - 1) & ~(Align - 1);
499 SkASSERT(alignedPtr - blockPtr <= (uintptr_t) std::numeric_limits<int32_t>::max());
500 return (int) (alignedPtr - blockPtr);
501 }
502}
503
504bool GrBlockAllocator::Block::resize(int start, int end, int deltaBytes) {
505 SkASSERT(fSentinel == kAssignedMarker);
506 SkASSERT(start >= kDataStart && end <= fSize && start < end);
507
508 if (deltaBytes > kMaxAllocationSize || deltaBytes < -kMaxAllocationSize) {
509 // Cannot possibly satisfy the resize and could overflow subsequent math
510 return false;
511 }
512 if (fCursor == end) {
513 int nextCursor = end + deltaBytes;
514 SkASSERT(nextCursor >= start);
515 // We still check nextCursor >= start for release builds that wouldn't assert.
516 if (nextCursor <= fSize && nextCursor >= start) {
517 fCursor = nextCursor;
518 return true;
519 }
520 }
521 return false;
522}
523
524// NOTE: release is equivalent to resize(start, end, start - end), and the compiler can optimize
525// most of the operations away, but it wasn't able to remove the unnecessary branch comparing the
526// new cursor to the block size or old start, so release() gets a specialization.
527bool GrBlockAllocator::Block::release(int start, int end) {
528 SkASSERT(fSentinel == kAssignedMarker);
529 SkASSERT(start >= kDataStart && end <= fSize && start < end);
530 if (fCursor == end) {
531 fCursor = start;
532 return true;
533 } else {
534 return false;
535 }
536}
537
538///////// Block iteration
539template <bool Forward, bool Const>
540class GrBlockAllocator::BlockIter {
541public:
542 using BlockT = typename std::conditional<Const, const Block, Block>::type;
543 using AllocatorT =
544 typename std::conditional<Const, const GrBlockAllocator, GrBlockAllocator>::type;
545
546 BlockIter(AllocatorT* allocator) : fAllocator(allocator) {}
547
548 class Item {
549 public:
550 bool operator!=(const Item& other) const { return fBlock != other.fBlock; }
551
552 BlockT* operator*() const { return fBlock; }
553
554 Item& operator++() {
555 fBlock = Forward ? fBlock->fNext : fBlock->fPrev;
556 return *this;
557 }
558
559 private:
560 friend BlockIter;
561
562 Item(BlockT* block) : fBlock(block) {}
563
564 BlockT* fBlock;
565 };
566
567 Item begin() const { return Item(Forward ? &fAllocator->fHead : fAllocator->fTail); }
568 Item end() const { return Item(nullptr); }
569
570private:
571 AllocatorT* fAllocator;
572};
573
574GrBlockAllocator::BlockIter<true, false> GrBlockAllocator::blocks() {
575 return BlockIter<true, false>(this);
576}
577GrBlockAllocator::BlockIter<true, true> GrBlockAllocator::blocks() const {
578 return BlockIter<true, true>(this);
579}
580GrBlockAllocator::BlockIter<false, false> GrBlockAllocator::rblocks() {
581 return BlockIter<false, false>(this);
582}
583GrBlockAllocator::BlockIter<false, true> GrBlockAllocator::rblocks() const {
584 return BlockIter<false, true>(this);
585}
586
587#endif // GrBlockAllocator_DEFINED
588