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