1/*
2 * Copyright 2010 Google Inc.
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 GrTAllocator_DEFINED
9#define GrTAllocator_DEFINED
10
11#include "src/gpu/GrBlockAllocator.h"
12
13template <typename T, int StartingItems = 1>
14class GrTAllocator {
15public:
16 /**
17 * Create an allocator that defaults to using StartingItems as heap increment.
18 */
19 GrTAllocator()
20 : fTotalCount(0)
21 , fAllocator(GrBlockAllocator::GrowthPolicy::kFixed) {}
22
23 /**
24 * Create an allocator
25 *
26 * @param itemsPerBlock the number of items to allocate at once
27 */
28 explicit GrTAllocator(int itemsPerBlock)
29 : fTotalCount(0)
30 , fAllocator(GrBlockAllocator::GrowthPolicy::kFixed,
31 GrBlockAllocator::BlockOverhead<alignof(T)>() + sizeof(T)*itemsPerBlock) {}
32
33 ~GrTAllocator() { this->reset(); }
34
35 /**
36 * Adds an item and returns it.
37 *
38 * @return the added item.
39 */
40 T& push_back() {
41 return *new (this->pushItem()) T;
42 }
43
44 T& push_back(const T& t) {
45 return *new (this->pushItem()) T(t);
46 }
47
48 T& push_back(T&& t) {
49 return *new (this->pushItem()) T(std::move(t));
50 }
51
52 template <typename... Args>
53 T& emplace_back(Args&&... args) {
54 return *new (this->pushItem()) T(std::forward<Args>(args)...);
55 }
56
57 /**
58 * Remove the last item, only call if count() != 0
59 */
60 void pop_back() {
61 SkASSERT(fTotalCount > 0);
62
63 GrBlockAllocator::Block* block = fAllocator->currentBlock();
64 int newCount = block->metadata() - 1;
65
66 // Run dtor for the popped item
67 int releaseIndex;
68 GetItemAndOffset(block, newCount, &releaseIndex)->~T();
69
70 if (newCount == 0) {
71 fAllocator->releaseBlock(block);
72 } else {
73 // Since this always follows LIFO, the block should always be able to release the memory
74 SkAssertResult(block->release(releaseIndex, releaseIndex + sizeof(T)));
75 block->setMetadata(newCount);
76 }
77
78 fTotalCount--;
79 }
80
81 /**
82 * Removes all added items.
83 */
84 void reset() {
85 // Invoke destructors in reverse order
86 for (const auto* b : fAllocator->rblocks()) {
87 int c = b->metadata();
88 for (int i = c - 1; i >= 0; i--) {
89 GetItem(b, i)->~T();
90 }
91 }
92
93 fAllocator->reset();
94 fTotalCount = 0;
95 }
96
97 /**
98 * Returns the item count.
99 */
100 int count() const {
101#ifdef SK_DEBUG
102 // Confirm total count matches sum of block counts
103 int count = 0;
104 int blockCount = 0;
105 for (const auto* b :fAllocator->blocks()) {
106 count += b->metadata();
107 blockCount++;
108 }
109 SkASSERT(count == fTotalCount);
110#endif
111 return fTotalCount;
112 }
113
114 /**
115 * Is the count 0?
116 */
117 bool empty() const { return this->count() == 0; }
118
119 /**
120 * Access first item, only call if count() != 0
121 */
122 T& front() {
123 // This assumes that the head block actually have room to store the first item.
124 static_assert(StartingItems >= 1);
125 SkASSERT(fTotalCount > 0);
126 return *(GetItem(fAllocator->headBlock(), 0));
127 }
128
129 /**
130 * Access first item, only call if count() != 0
131 */
132 const T& front() const {
133 SkASSERT(fTotalCount > 0);
134 return *(GetItem(fAllocator->headBlock(), 0));
135 }
136
137 /**
138 * Access last item, only call if count() != 0
139 */
140 T& back() {
141 SkASSERT(fTotalCount > 0);
142 int blockCount = fAllocator->currentBlock()->metadata();
143 return *(GetItem(fAllocator->currentBlock(), blockCount - 1));
144 }
145
146 /**
147 * Access last item, only call if count() != 0
148 */
149 const T& back() const {
150 SkASSERT(fTotalCount > 0);
151 int blockCount = fAllocator->currentBlock()->metadata();
152 return *(GetItem(fAllocator->currentBlock(), blockCount - 1));
153 }
154
155 template<bool Const>
156 class Iterator {
157 using BlockIter = typename GrBlockAllocator::BlockIter<true, Const>;
158 using C = typename std::conditional<Const, const T, T>::type;
159 using AllocatorT = typename std::conditional<Const, const GrTAllocator, GrTAllocator>::type;
160 public:
161 Iterator(AllocatorT* allocator) : fBlockIter(allocator->fAllocator.allocator()) {}
162
163 class Item {
164 public:
165 bool operator!=(const Item& other) const {
166 if (other.fBlock != fBlock) {
167 // Treat an empty head block the same as the end block
168 bool blockEmpty = !(*fBlock) || (*fBlock)->metadata() == 0;
169 bool otherEmpty = !(*other.fBlock) || (*other.fBlock)->metadata() == 0;
170 return !blockEmpty || !otherEmpty;
171 } else {
172 // Same block, so differentiate by index into it (unless it's the "end" block
173 // in which case ignore index).
174 return SkToBool(*fBlock) && other.fIndex != fIndex;
175 }
176 }
177
178 C& operator*() const {
179 C* item = const_cast<C*>(static_cast<const C*>((*fBlock)->ptr(fIndex)));
180 SkDEBUGCODE(int offset;)
181 SkASSERT(item == GetItemAndOffset(*fBlock, fItem, &offset) && offset == fIndex);
182 return *item;
183 }
184
185 Item& operator++() {
186 const auto* block = *fBlock;
187 fItem++;
188 fIndex += sizeof(T);
189 if (fItem >= block->metadata()) {
190 ++fBlock;
191 fItem = 0;
192 fIndex = StartingIndex(fBlock);
193 }
194 return *this;
195 }
196
197 private:
198 friend Iterator;
199 using BlockItem = typename BlockIter::Item;
200
201 Item(BlockItem block) : fBlock(block), fItem(0), fIndex(StartingIndex(block)) {}
202
203 static int StartingIndex(const BlockItem& block) {
204 return *block ? (*block)->template firstAlignedOffset<alignof(T)>() : 0;
205 }
206
207 BlockItem fBlock;
208 int fItem;
209 int fIndex;
210 };
211
212 Item begin() const { return Item(fBlockIter.begin()); }
213 Item end() const { return Item(fBlockIter.end()); }
214
215 private:
216 const BlockIter fBlockIter;
217 };
218
219 using Iter = Iterator<false>;
220 using CIter = Iterator<true>;
221
222 /**
223 * Prefer using a for-range loop when iterating over all allocated items, vs. index access.
224 */
225 Iter items() { return Iter(this); }
226 CIter items() const { return CIter(this); }
227
228 /**
229 * Access item by index. Not an operator[] since it should not be considered constant time.
230 */
231 T& item(int i) {
232 // Iterate over blocks until we find the one that contains i.
233 SkASSERT(i >= 0 && i < fTotalCount);
234 for (const auto* b : fAllocator->blocks()) {
235 int blockCount = b->metadata();
236 if (i < blockCount) {
237 return *GetItem(b, i);
238 } else {
239 i -= blockCount;
240 }
241 }
242 SkUNREACHABLE;
243 }
244 const T& item(int i) const {
245 return const_cast<GrTAllocator<T>*>(this)->item(i);
246 }
247
248private:
249 static constexpr size_t StartingSize =
250 GrBlockAllocator::Overhead<alignof(T)>() + StartingItems * sizeof(T);
251
252 static T* GetItemAndOffset(const GrBlockAllocator::Block* block, int index, int* offset) {
253 SkASSERT(index >= 0 && index < block->metadata());
254 *offset = block->firstAlignedOffset<alignof(T)>() + index * sizeof(T);
255 return const_cast<T*>(static_cast<const T*>(block->ptr(*offset)));
256 }
257
258 static T* GetItem(const GrBlockAllocator::Block* block, int index) {
259 int offset;
260 return GetItemAndOffset(block, index, &offset);
261 }
262
263 void* pushItem() {
264 // 'template' required because fAllocator is a template, calling a template member
265 auto br = fAllocator->template allocate<alignof(T)>(sizeof(T));
266 br.fBlock->setMetadata(br.fBlock->metadata() + 1);
267 fTotalCount++;
268 return br.fBlock->ptr(br.fAlignedOffset);
269 }
270
271 // Each Block in the allocator tracks their count of items, but it's convenient to store
272 // the sum of their counts as well.
273 int fTotalCount;
274
275 // N represents the number of items, whereas GrSBlockAllocator takes total bytes, so must
276 // account for the block allocator's size too.
277 GrSBlockAllocator<StartingSize> fAllocator;
278};
279
280#endif
281