Home | History | Annotate | Download | only in core 
      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:
     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 
    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>
    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