1 /*
2  * Copyright 2014 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 GrTRecorder_DEFINED
9 #define GrTRecorder_DEFINED
10 
11 #include "SkTypes.h"
12 
13 template<typename TBase, typename TAlign> class GrTRecorder;
14 template<typename TItem> struct GrTRecorderAllocWrapper;
15 
16 /**
17  * Records a list of items with a common base type, optional associated data, and
18  * permanent memory addresses.
19  *
20  * This class preallocates its own chunks of memory for hosting objects, so new items can
21  * be created without excessive calls to malloc().
22  *
23  * To create a new item and append it to the back of the list, use the following macros:
24  *
25  *     GrNEW_APPEND_TO_RECORDER(recorder, SubclassName, (args))
26  *     GrNEW_APPEND_WITH_DATA_TO_RECORDER(recorder, SubclassName, (args), sizeOfData)
27  *
28  * Upon reset or delete, the items are destructed in the same order they were received,
29  * not reverse (stack) order.
30  *
31  * @param TBase   Common base type of items in the list. If TBase is not a class with a
32  *                virtual destructor, the client is responsible for invoking any necessary
33  *                destructors.
34  *
35  *                For now, any subclass used in the list must have the same start address
36  *                as TBase (or in other words, the types must be convertible via
37  *                reinterpret_cast<>). Classes with multiple inheritance (or any subclass
38  *                on an obscure compiler) may not be compatible. This is runtime asserted
39  *                in debug builds.
40  *
41  * @param TAlign  A type whose size is the desired memory alignment for object allocations.
42  *                This should be the largest known alignment requirement for all objects
43  *                that may be stored in the list.
44  */
45 template<typename TBase, typename TAlign> class GrTRecorder : SkNoncopyable {
46 public:
47     class Iter;
48     class ReverseIter;
49 
50     /**
51      * Create a recorder.
52      *
53      * @param initialSizeInBytes  The amount of memory reserved by the recorder initially,
54                                   and after calls to reset().
55      */
56     GrTRecorder(int initialSizeInBytes)
57         : fHeadBlock(MemBlock::Alloc(LengthOf(initialSizeInBytes), nullptr)),
58           fTailBlock(fHeadBlock),
59           fLastItem(nullptr) {}
60 
61     ~GrTRecorder() {
62         this->reset();
63         MemBlock::Free(fHeadBlock);
64     }
65 
66     bool empty() { return !fLastItem; }
67 
68     TBase& back() {
69         SkASSERT(!this->empty());
70         return *reinterpret_cast<TBase*>(fLastItem);
71     }
72 
73     /**
74      * Removes and destroys the last block added to the recorder. It may not be called when the
75      * recorder is empty.
76      */
77     void pop_back();
78 
79     /**
80      * Destruct all items in the list and reset to empty.
81      */
82     void reset();
83 
84     /**
85      * Retrieve the extra data associated with an item that was allocated using
86      * GrNEW_APPEND_WITH_DATA_TO_RECORDER().
87      *
88      * @param item  The item whose data to retrieve. The pointer must be of the same type
89      *              that was allocated initally; it can't be a pointer to a base class.
90      *
91      * @return The item's associated data.
92      */
93     template<typename TItem> static const void* GetDataForItem(const TItem* item) {
94         const TAlign* ptr = reinterpret_cast<const TAlign*>(item);
95         return &ptr[length_of<TItem>::kValue];
96     }
97     template<typename TItem> static void* GetDataForItem(TItem* item) {
98         TAlign* ptr = reinterpret_cast<TAlign*>(item);
99         return &ptr[length_of<TItem>::kValue];
100     }
101 
102 private:
103     template<typename TItem> struct length_of {
104         enum { kValue = (sizeof(TItem) + sizeof(TAlign) - 1) / sizeof(TAlign) };
105     };
106     static int LengthOf(int bytes) { return (bytes + sizeof(TAlign) - 1) / sizeof(TAlign); }
107 
108     struct Header {
109         int fTotalLength; // The length of an entry including header, item, and data in TAligns.
110         int fPrevLength;  // Same but for the previous entry. Used for iterating backwards.
111     };
112     template<typename TItem> void* alloc_back(int dataLength);
113 
114     struct MemBlock : SkNoncopyable {
115         /** Allocates a new block and appends it to prev if not nullptr. The length param is in units
116             of TAlign. */
117         static MemBlock* Alloc(int length, MemBlock* prev) {
118             MemBlock* block = reinterpret_cast<MemBlock*>(
119                 sk_malloc_throw(sizeof(TAlign) * (length_of<MemBlock>::kValue + length)));
120             block->fLength = length;
121             block->fBack = 0;
122             block->fNext = nullptr;
123             block->fPrev = prev;
124             if (prev) {
125                 SkASSERT(nullptr == prev->fNext);
126                 prev->fNext = block;
127             }
128             return block;
129         }
130 
131         // Frees from this block forward. Also adjusts prev block's next ptr.
132         static void Free(MemBlock* block) {
133             if (block && block->fPrev) {
134                 SkASSERT(block->fPrev->fNext == block);
135                 block->fPrev->fNext = nullptr;
136             }
137             while (block) {
138                 MemBlock* next = block->fNext;
139                 sk_free(block);
140                 block = next;
141             }
142         }
143 
144         TAlign& operator [](int i) {
145             return reinterpret_cast<TAlign*>(this)[length_of<MemBlock>::kValue + i];
146         }
147 
148         int       fLength; // Length in units of TAlign of the block.
149         int       fBack;   // Offset, in TAligns, to unused portion of the memory block.
150         MemBlock* fNext;
151         MemBlock* fPrev;
152     };
153     MemBlock* const fHeadBlock;
154     MemBlock* fTailBlock;
155 
156     void*    fLastItem; // really a ptr to TBase
157 
158     template<typename TItem> friend struct GrTRecorderAllocWrapper;
159 
160     template <typename UBase, typename UAlign, typename UItem>
161     friend void* operator new(size_t, GrTRecorder<UBase, UAlign>&,
162                               const GrTRecorderAllocWrapper<UItem>&);
163 
164     friend class Iter;
165     friend class ReverseIter;
166 };
167 
168 ////////////////////////////////////////////////////////////////////////////////
169 
170 template<typename TBase, typename TAlign>
171 void GrTRecorder<TBase, TAlign>::pop_back() {
172     SkASSERT(fLastItem);
173     Header* header = reinterpret_cast<Header*>(
174         reinterpret_cast<TAlign*>(fLastItem) - length_of<Header>::kValue);
175     fTailBlock->fBack -= header->fTotalLength;
176     reinterpret_cast<TBase*>(fLastItem)->~TBase();
177 
178     int lastItemLength = header->fPrevLength;
179 
180     if (!header->fPrevLength) {
181         // We popped the first entry in the recorder.
182         SkASSERT(0 == fTailBlock->fBack);
183         fLastItem = nullptr;
184         return;
185     }
186     while (!fTailBlock->fBack) {
187         // We popped the last entry in a block that isn't the head block. Move back a block but
188         // don't free it since we'll probably grow into it shortly.
189         fTailBlock = fTailBlock->fPrev;
190         SkASSERT(fTailBlock);
191     }
192     fLastItem = &(*fTailBlock)[fTailBlock->fBack - lastItemLength + length_of<Header>::kValue];
193 }
194 
195 template<typename TBase, typename TAlign>
196 template<typename TItem>
197 void* GrTRecorder<TBase, TAlign>::alloc_back(int dataLength) {
198     // Find the header of the previous entry and get its length. We need to store that in the new
199     // header for backwards iteration (pop_back()).
200     int prevLength = 0;
201     if (fLastItem) {
202         Header* lastHeader = reinterpret_cast<Header*>(
203             reinterpret_cast<TAlign*>(fLastItem) - length_of<Header>::kValue);
204         prevLength = lastHeader->fTotalLength;
205     }
206 
207     const int totalLength = length_of<Header>::kValue + length_of<TItem>::kValue + dataLength;
208 
209     // Check if there is room in the current block and if not walk to next (allocating if
210     // necessary). Note that pop_back() and reset() can leave the recorder in a state where it
211     // has preallocated blocks hanging off the tail that are currently unused.
212     while (fTailBlock->fBack + totalLength > fTailBlock->fLength) {
213         if (!fTailBlock->fNext) {
214             fTailBlock = MemBlock::Alloc(SkTMax(2 * fTailBlock->fLength, totalLength), fTailBlock);
215         } else {
216             fTailBlock = fTailBlock->fNext;
217         }
218         SkASSERT(0 == fTailBlock->fBack);
219     }
220 
221     Header* header = reinterpret_cast<Header*>(&(*fTailBlock)[fTailBlock->fBack]);
222     void* rawPtr = &(*fTailBlock)[fTailBlock->fBack + length_of<Header>::kValue];
223 
224     header->fTotalLength = totalLength;
225     header->fPrevLength = prevLength;
226     fLastItem = rawPtr;
227     fTailBlock->fBack += totalLength;
228 
229     // FIXME: We currently require that the base and subclass share the same start address.
230     // This is not required by the C++ spec, and is likely to not be true in the case of
231     // multiple inheritance or a base class that doesn't have virtual methods (when the
232     // subclass does). It would be ideal to find a more robust solution that comes at no
233     // extra cost to performance or code generality.
234     SkDEBUGCODE(void* baseAddr = fLastItem;
235                 void* subclassAddr = rawPtr);
236     SkASSERT(baseAddr == subclassAddr);
237 
238     return rawPtr;
239 }
240 
241 /**
242  * Iterates through a recorder from front to back. The initial state of the iterator is
243  * to not have the front item loaded yet; next() must be called first. Usage model:
244  *
245  *    GrTRecorder<TBase, TAlign>::Iter iter(recorder);
246  *    while (iter.next()) {
247  *        iter->doSomething();
248  *    }
249  */
250 template<typename TBase, typename TAlign>
251 class GrTRecorder<TBase, TAlign>::Iter {
252 public:
253     Iter(GrTRecorder& recorder) : fBlock(recorder.fHeadBlock), fPosition(0), fItem(nullptr) {}
254 
255     bool next() {
256         while (fPosition >= fBlock->fBack) {
257             SkASSERT(fPosition == fBlock->fBack);
258             if (!fBlock->fNext) {
259                 return false;
260             }
261             fBlock = fBlock->fNext;
262             fPosition = 0;
263         }
264 
265         Header* header = reinterpret_cast<Header*>(&(*fBlock)[fPosition]);
266         fItem = reinterpret_cast<TBase*>(&(*fBlock)[fPosition + length_of<Header>::kValue]);
267         fPosition += header->fTotalLength;
268         return true;
269     }
270 
271     TBase* get() const {
272         SkASSERT(fItem);
273         return fItem;
274     }
275 
276     TBase* operator->() const { return this->get(); }
277 
278 private:
279     MemBlock* fBlock;
280     int       fPosition;
281     TBase*    fItem;
282 };
283 
284 /**
285  * Iterates through a recorder in reverse, from back to front. This version mirrors "Iter",
286  * so the initial state is to have recorder.back() loaded already. (Note that this will
287  * assert if the recorder is empty.) Usage model:
288  *
289  *    GrTRecorder<TBase, TAlign>::ReverseIter reverseIter(recorder);
290  *    do {
291  *        reverseIter->doSomething();
292  *    } while (reverseIter.previous());
293  */
294 template<typename TBase, typename TAlign>
295 class GrTRecorder<TBase, TAlign>::ReverseIter {
296 public:
297     ReverseIter(GrTRecorder& recorder)
298         : fBlock(recorder.fTailBlock),
299           fItem(&recorder.back()) {
300         Header* lastHeader = reinterpret_cast<Header*>(
301             reinterpret_cast<TAlign*>(fItem) - length_of<Header>::kValue);
302         fPosition = fBlock->fBack - lastHeader->fTotalLength;
303     }
304 
305     bool previous() {
306         Header* header = reinterpret_cast<Header*>(&(*fBlock)[fPosition]);
307 
308         while (0 == fPosition) {
309             if (!fBlock->fPrev) {
310                 // We've reached the front of the recorder.
311                 return false;
312             }
313             fBlock = fBlock->fPrev;
314             fPosition = fBlock->fBack;
315         }
316 
317         fPosition -= header->fPrevLength;
318         SkASSERT(fPosition >= 0);
319 
320         fItem = reinterpret_cast<TBase*>(&(*fBlock)[fPosition + length_of<Header>::kValue]);
321         return true;
322     }
323 
324     TBase* get() const { return fItem; }
325     TBase* operator->() const { return this->get(); }
326 
327 private:
328     MemBlock* fBlock;
329     int       fPosition;
330     TBase*    fItem;
331 };
332 
333 template<typename TBase, typename TAlign>
334 void GrTRecorder<TBase, TAlign>::reset() {
335     Iter iter(*this);
336     while (iter.next()) {
337         iter->~TBase();
338     }
339 
340     // Assume the next time this recorder fills up it will use approximately the same
341     // amount of space as last time. Leave enough space for up to ~50% growth; free
342     // everything else.
343     if (fTailBlock->fBack <= fTailBlock->fLength / 2) {
344         MemBlock::Free(fTailBlock->fNext);
345     } else if (fTailBlock->fNext) {
346         MemBlock::Free(fTailBlock->fNext->fNext);
347         fTailBlock->fNext->fNext = nullptr;
348     }
349 
350     for (MemBlock* block = fHeadBlock; block; block = block->fNext) {
351         block->fBack = 0;
352     }
353 
354     fTailBlock = fHeadBlock;
355     fLastItem = nullptr;
356 }
357 
358 ////////////////////////////////////////////////////////////////////////////////
359 
360 template<typename TItem> struct GrTRecorderAllocWrapper {
361     GrTRecorderAllocWrapper() : fDataLength(0) {}
362 
363     template <typename TBase, typename TAlign>
364     GrTRecorderAllocWrapper(const GrTRecorder<TBase, TAlign>&, int sizeOfData)
365         : fDataLength(GrTRecorder<TBase, TAlign>::LengthOf(sizeOfData)) {}
366 
367     const int fDataLength;
368 };
369 
370 template <typename TBase, typename TAlign, typename TItem>
371 void* operator new(size_t size, GrTRecorder<TBase, TAlign>& recorder,
372                    const GrTRecorderAllocWrapper<TItem>& wrapper) {
373     SkASSERT(size == sizeof(TItem));
374     return recorder.template alloc_back<TItem>(wrapper.fDataLength);
375 }
376 
377 template <typename TBase, typename TAlign, typename TItem>
378 void operator delete(void*, GrTRecorder<TBase, TAlign>&, const GrTRecorderAllocWrapper<TItem>&) {
379     // We only provide an operator delete to work around compiler warnings that can come
380     // up for an unmatched operator new when compiling with exceptions.
381     SK_ABORT("Invalid Operation");
382 }
383 
384 #define GrNEW_APPEND_TO_RECORDER(recorder, type_name, args) \
385     (new (recorder, GrTRecorderAllocWrapper<type_name>()) type_name args)
386 
387 #define GrNEW_APPEND_WITH_DATA_TO_RECORDER(recorder, type_name, args, size_of_data) \
388     (new (recorder, GrTRecorderAllocWrapper<type_name>(recorder, size_of_data)) type_name args)
389 
390 #endif
391