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.
16template<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 */
31template<uint32_t kMaxObjects, size_t kTotalBytes>
32class SkSmallAllocator : SkNoncopyable {
33public:
34    SkSmallAllocator()
35    : fStorageUsed(0)
36    , fNumObjects(0)
37    {}
38
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>
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
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>
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>
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>
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     */
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
160private:
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