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