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 SkSmallAllocator_DEFINED 9 #define SkSmallAllocator_DEFINED 10 11 #include "SkTDArray.h" 12 #include "SkTypes.h" 13 14 #include <new> 15 16 /* 17 * Template class for allocating small objects without additional heap memory 18 * allocations. kMaxObjects is a hard limit on the number of objects that can 19 * be allocated using this class. After that, attempts to create more objects 20 * with this class will assert and return nullptr. 21 * kTotalBytes is the total number of bytes provided for storage for all 22 * objects created by this allocator. If an object to be created is larger 23 * than the storage (minus storage already used), it will be allocated on the 24 * heap. This class's destructor will handle calling the destructor for each 25 * object it allocated and freeing its memory. 26 */ 27 template<uint32_t kMaxObjects, size_t kTotalBytes> 28 class SkSmallAllocator : SkNoncopyable { 29 public: SkSmallAllocator()30 SkSmallAllocator() 31 : fStorageUsed(0) 32 , fNumObjects(0) 33 {} 34 ~SkSmallAllocator()35 ~SkSmallAllocator() { 36 // Destruct in reverse order, in case an earlier object points to a 37 // later object. 38 while (fNumObjects > 0) { 39 fNumObjects--; 40 Rec* rec = &fRecs[fNumObjects]; 41 rec->fKillProc(rec->fObj); 42 // Safe to do if fObj is in fStorage, since fHeapStorage will 43 // point to nullptr. 44 sk_free(rec->fHeapStorage); 45 } 46 } 47 48 /* 49 * Create a new object of type T. Its lifetime will be handled by this 50 * SkSmallAllocator. 51 * Note: If kMaxObjects have been created by this SkSmallAllocator, nullptr 52 * will be returned. 53 */ 54 template<typename T, typename... Args> createT(const Args &...args)55 T* createT(const Args&... args) { 56 void* buf = this->reserveT<T>(); 57 if (nullptr == buf) { 58 return nullptr; 59 } 60 return new (buf) T(args...); 61 } 62 63 /* 64 * Reserve a specified amount of space (must be enough space for one T). 65 * The space will be in fStorage if there is room, or on the heap otherwise. 66 * Either way, this class will call ~T() in its destructor and free the heap 67 * allocation if necessary. 68 * Unlike createT(), this method will not call the constructor of T. 69 */ 70 template<typename T> void* reserveT(size_t storageRequired = sizeof(T)) { 71 SkASSERT(fNumObjects < kMaxObjects); 72 SkASSERT(storageRequired >= sizeof(T)); 73 if (kMaxObjects == fNumObjects) { 74 return nullptr; 75 } 76 const size_t storageRemaining = SkAlign4(kTotalBytes) - fStorageUsed; 77 storageRequired = SkAlign4(storageRequired); 78 Rec* rec = &fRecs[fNumObjects]; 79 if (storageRequired > storageRemaining) { 80 // Allocate on the heap. Ideally we want to avoid this situation, 81 // but we're not sure we can catch all callers, so handle it but 82 // assert false in debug mode. 83 SkASSERT(false); 84 rec->fStorageSize = 0; 85 rec->fHeapStorage = sk_malloc_throw(storageRequired); 86 rec->fObj = static_cast<void*>(rec->fHeapStorage); 87 } else { 88 // There is space in fStorage. 89 rec->fStorageSize = storageRequired; 90 rec->fHeapStorage = nullptr; 91 SkASSERT(SkIsAlign4(fStorageUsed)); 92 rec->fObj = static_cast<void*>(fStorage + (fStorageUsed / 4)); 93 fStorageUsed += storageRequired; 94 } 95 rec->fKillProc = DestroyT<T>; 96 fNumObjects++; 97 return rec->fObj; 98 } 99 100 /* 101 * Free the memory reserved last without calling the destructor. 102 * Can be used in a nested way, i.e. after reserving A and B, calling 103 * freeLast once will free B and calling it again will free A. 104 */ freeLast()105 void freeLast() { 106 SkASSERT(fNumObjects > 0); 107 Rec* rec = &fRecs[fNumObjects - 1]; 108 sk_free(rec->fHeapStorage); 109 fStorageUsed -= rec->fStorageSize; 110 111 fNumObjects--; 112 } 113 114 private: 115 struct Rec { 116 size_t fStorageSize; // 0 if allocated on heap 117 void* fObj; 118 void* fHeapStorage; 119 void (*fKillProc)(void*); 120 }; 121 122 // Used to call the destructor for allocated objects. 123 template<typename T> DestroyT(void * ptr)124 static void DestroyT(void* ptr) { 125 static_cast<T*>(ptr)->~T(); 126 } 127 128 // Number of bytes used so far. 129 size_t fStorageUsed; 130 // Pad the storage size to be 4-byte aligned. 131 uint32_t fStorage[SkAlign4(kTotalBytes) >> 2]; 132 uint32_t fNumObjects; 133 Rec fRecs[kMaxObjects]; 134 }; 135 136 #endif // SkSmallAllocator_DEFINED 137