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 */
27template<uint32_t kMaxObjects, size_t kTotalBytes>
28class SkSmallAllocator : SkNoncopyable {
29public:
30    SkSmallAllocator()
31    : fStorageUsed(0)
32    , fNumObjects(0)
33    {}
34
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>
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     */
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
114private:
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>
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