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