1a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org/* 2a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org * Copyright 2014 Google, Inc 3a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org * 4a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org * Use of this source code is governed by a BSD-style license that can be 5a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org * found in the LICENSE file. 6a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org */ 7a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org 8a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org#ifndef SkSmallAllocator_DEFINED 9a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org#define SkSmallAllocator_DEFINED 10a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org 11a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org#include "SkTDArray.h" 12a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org#include "SkTypes.h" 13a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org 14a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org// Used by SkSmallAllocator to call the destructor for objects it has 15a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org// allocated. 16a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.orgtemplate<typename T> void destroyT(void* ptr) { 17a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org static_cast<T*>(ptr)->~T(); 18a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org} 19a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org 20a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org/* 21a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org * Template class for allocating small objects without additional heap memory 22a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org * allocations. kMaxObjects is a hard limit on the number of objects that can 23a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org * be allocated using this class. After that, attempts to create more objects 24a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org * with this class will assert and return NULL. 25a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org * kTotalBytes is the total number of bytes provided for storage for all 26a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org * objects created by this allocator. If an object to be created is larger 27a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org * than the storage (minus storage already used), it will be allocated on the 28a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org * heap. This class's destructor will handle calling the destructor for each 29a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org * object it allocated and freeing its memory. 30a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org */ 31a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.orgtemplate<uint32_t kMaxObjects, size_t kTotalBytes> 32e3beb6bd7de7fa211681abbb0be58e80b19885e0commit-bot@chromium.orgclass SkSmallAllocator : SkNoncopyable { 33a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.orgpublic: 34a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org SkSmallAllocator() 35a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org : fStorageUsed(0) 36a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org , fNumObjects(0) 37a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org {} 38a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org 39a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org ~SkSmallAllocator() { 40a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org // Destruct in reverse order, in case an earlier object points to a 41a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org // later object. 42a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org while (fNumObjects > 0) { 43a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org fNumObjects--; 44a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org Rec* rec = &fRecs[fNumObjects]; 45a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org rec->fKillProc(rec->fObj); 46a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org // Safe to do if fObj is in fStorage, since fHeapStorage will 47a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org // point to NULL. 48a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org sk_free(rec->fHeapStorage); 49a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org } 50a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org } 51a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org 52a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org /* 53a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org * Create a new object of type T. Its lifetime will be handled by this 54a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org * SkSmallAllocator. 55a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org * Each version behaves the same but takes a different number of 56a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org * arguments. 57a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org * Note: If kMaxObjects have been created by this SkSmallAllocator, NULL 58a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org * will be returned. 59a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org */ 60a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org template<typename T> 61a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org T* createT() { 62a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org void* buf = this->reserveT<T>(); 63a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org if (NULL == buf) { 64a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org return NULL; 65a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org } 66a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org SkNEW_PLACEMENT(buf, T); 67a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org return static_cast<T*>(buf); 68a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org } 69a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org 70a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org template<typename T, typename A1> T* createT(const A1& a1) { 71a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org void* buf = this->reserveT<T>(); 72a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org if (NULL == buf) { 73a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org return NULL; 74a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org } 75a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org SkNEW_PLACEMENT_ARGS(buf, T, (a1)); 76a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org return static_cast<T*>(buf); 77a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org } 78a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org 79a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org template<typename T, typename A1, typename A2> 80a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org T* createT(const A1& a1, const A2& a2) { 81a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org void* buf = this->reserveT<T>(); 82a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org if (NULL == buf) { 83a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org return NULL; 84a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org } 85a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org SkNEW_PLACEMENT_ARGS(buf, T, (a1, a2)); 86a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org return static_cast<T*>(buf); 87a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org } 88a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org 89a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org template<typename T, typename A1, typename A2, typename A3> 90a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org T* createT(const A1& a1, const A2& a2, const A3& a3) { 91a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org void* buf = this->reserveT<T>(); 92a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org if (NULL == buf) { 93a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org return NULL; 94a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org } 95a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org SkNEW_PLACEMENT_ARGS(buf, T, (a1, a2, a3)); 96a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org return static_cast<T*>(buf); 97a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org } 98a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org 999c9005a347e9996f357bd79591bd34f74f8bbc66commit-bot@chromium.org template<typename T, typename A1, typename A2, typename A3, typename A4> 1009c9005a347e9996f357bd79591bd34f74f8bbc66commit-bot@chromium.org T* createT(const A1& a1, const A2& a2, const A3& a3, const A4& a4) { 1019c9005a347e9996f357bd79591bd34f74f8bbc66commit-bot@chromium.org void* buf = this->reserveT<T>(); 1029c9005a347e9996f357bd79591bd34f74f8bbc66commit-bot@chromium.org if (NULL == buf) { 1039c9005a347e9996f357bd79591bd34f74f8bbc66commit-bot@chromium.org return NULL; 1049c9005a347e9996f357bd79591bd34f74f8bbc66commit-bot@chromium.org } 1059c9005a347e9996f357bd79591bd34f74f8bbc66commit-bot@chromium.org SkNEW_PLACEMENT_ARGS(buf, T, (a1, a2, a3, a4)); 1069c9005a347e9996f357bd79591bd34f74f8bbc66commit-bot@chromium.org return static_cast<T*>(buf); 1079c9005a347e9996f357bd79591bd34f74f8bbc66commit-bot@chromium.org } 1089c9005a347e9996f357bd79591bd34f74f8bbc66commit-bot@chromium.org 109a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org /* 11079fbb40bca9d815ef79b896b31ba6ee736817e0fcommit-bot@chromium.org * Reserve a specified amount of space (must be enough space for one T). 11179fbb40bca9d815ef79b896b31ba6ee736817e0fcommit-bot@chromium.org * The space will be in fStorage if there is room, or on the heap otherwise. 11279fbb40bca9d815ef79b896b31ba6ee736817e0fcommit-bot@chromium.org * Either way, this class will call ~T() in its destructor and free the heap 11379fbb40bca9d815ef79b896b31ba6ee736817e0fcommit-bot@chromium.org * allocation if necessary. 11479fbb40bca9d815ef79b896b31ba6ee736817e0fcommit-bot@chromium.org * Unlike createT(), this method will not call the constructor of T. 115a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org */ 11679fbb40bca9d815ef79b896b31ba6ee736817e0fcommit-bot@chromium.org template<typename T> void* reserveT(size_t storageRequired = sizeof(T)) { 117a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org SkASSERT(fNumObjects < kMaxObjects); 11879fbb40bca9d815ef79b896b31ba6ee736817e0fcommit-bot@chromium.org SkASSERT(storageRequired >= sizeof(T)); 119a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org if (kMaxObjects == fNumObjects) { 120a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org return NULL; 121a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org } 122a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org const size_t storageRemaining = SkAlign4(kTotalBytes) - fStorageUsed; 12379fbb40bca9d815ef79b896b31ba6ee736817e0fcommit-bot@chromium.org storageRequired = SkAlign4(storageRequired); 124a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org Rec* rec = &fRecs[fNumObjects]; 125a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org if (storageRequired > storageRemaining) { 126a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org // Allocate on the heap. Ideally we want to avoid this situation, 127a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org // but we're not sure we can catch all callers, so handle it but 128a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org // assert false in debug mode. 129a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org SkASSERT(false); 13087fcd950198a16211b3988610beebb5ca5bcf323commit-bot@chromium.org rec->fStorageSize = 0; 131a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org rec->fHeapStorage = sk_malloc_throw(storageRequired); 132a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org rec->fObj = static_cast<void*>(rec->fHeapStorage); 133a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org } else { 134a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org // There is space in fStorage. 13587fcd950198a16211b3988610beebb5ca5bcf323commit-bot@chromium.org rec->fStorageSize = storageRequired; 136a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org rec->fHeapStorage = NULL; 137a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org SkASSERT(SkIsAlign4(fStorageUsed)); 138a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org rec->fObj = static_cast<void*>(fStorage + (fStorageUsed / 4)); 139a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org fStorageUsed += storageRequired; 140a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org } 141a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org rec->fKillProc = destroyT<T>; 142a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org fNumObjects++; 143a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org return rec->fObj; 144a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org } 145a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org 14687fcd950198a16211b3988610beebb5ca5bcf323commit-bot@chromium.org /* 14787fcd950198a16211b3988610beebb5ca5bcf323commit-bot@chromium.org * Free the memory reserved last without calling the destructor. 14887fcd950198a16211b3988610beebb5ca5bcf323commit-bot@chromium.org * Can be used in a nested way, i.e. after reserving A and B, calling 14987fcd950198a16211b3988610beebb5ca5bcf323commit-bot@chromium.org * freeLast once will free B and calling it again will free A. 15087fcd950198a16211b3988610beebb5ca5bcf323commit-bot@chromium.org */ 15187fcd950198a16211b3988610beebb5ca5bcf323commit-bot@chromium.org void freeLast() { 15287fcd950198a16211b3988610beebb5ca5bcf323commit-bot@chromium.org SkASSERT(fNumObjects > 0); 15387fcd950198a16211b3988610beebb5ca5bcf323commit-bot@chromium.org Rec* rec = &fRecs[fNumObjects - 1]; 15487fcd950198a16211b3988610beebb5ca5bcf323commit-bot@chromium.org sk_free(rec->fHeapStorage); 15587fcd950198a16211b3988610beebb5ca5bcf323commit-bot@chromium.org fStorageUsed -= rec->fStorageSize; 15687fcd950198a16211b3988610beebb5ca5bcf323commit-bot@chromium.org 15787fcd950198a16211b3988610beebb5ca5bcf323commit-bot@chromium.org fNumObjects--; 15887fcd950198a16211b3988610beebb5ca5bcf323commit-bot@chromium.org } 15987fcd950198a16211b3988610beebb5ca5bcf323commit-bot@chromium.org 160a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.orgprivate: 161a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org struct Rec { 16287fcd950198a16211b3988610beebb5ca5bcf323commit-bot@chromium.org size_t fStorageSize; // 0 if allocated on heap 16387fcd950198a16211b3988610beebb5ca5bcf323commit-bot@chromium.org void* fObj; 16487fcd950198a16211b3988610beebb5ca5bcf323commit-bot@chromium.org void* fHeapStorage; 16587fcd950198a16211b3988610beebb5ca5bcf323commit-bot@chromium.org void (*fKillProc)(void*); 166a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org }; 167a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org 168a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org // Number of bytes used so far. 169a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org size_t fStorageUsed; 170a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org // Pad the storage size to be 4-byte aligned. 171a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org uint32_t fStorage[SkAlign4(kTotalBytes) >> 2]; 172a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org uint32_t fNumObjects; 173a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org Rec fRecs[kMaxObjects]; 174a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org}; 175a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org 176a5572e5bb2a2bbeeb59de0741c2527869d365a0ccommit-bot@chromium.org#endif // SkSmallAllocator_DEFINED 177