text: /*
   * Copyright 2016 Google Inc.
   *
   * Use of this source code is governed by a BSD-style license that can be
   * found in the LICENSE file.
   */
  #ifndef SkArenaAlloc_DEFINED
  #  define SkArenaAlloc_DEFINED
  #  include "include/private/SkTFitsIn.h"
  #  include <cassert>
  #  include <cstddef>
  #  include <cstdint>
  #  include <cstdlib>
  #  include <cstring>
  #  include <limits>
  #  include <new>
  #  include <type_traits>
  #  include <utility>
  #  include <vector>
  // SkArenaAlloc allocates object and destroys the allocated objects when destroyed. It's designed
  // to minimize the number of underlying block allocations. SkArenaAlloc allocates first out of an
  // (optional) user-provided block of memory, and when that's exhausted it allocates on the heap,
  // starting with an allocation of firstHeapAllocation bytes.  If your data (plus a small overhead)
  // fits in the user-provided block, SkArenaAlloc never uses the heap, and if it fits in
  // firstHeapAllocation bytes, it'll use the heap only once. If 0 is specified for
  // firstHeapAllocation, then blockSize is used unless that too is 0, then 1024 is used.
  //
  // Examples:
  //
  //   char block[mostCasesSize];
  //   SkArenaAlloc arena(block, mostCasesSize);
  //
  // If mostCasesSize is too large for the stack, you can use the following pattern.
  //
  //   std::unique_ptr<char[]> block{new char[mostCasesSize]};
  //   SkArenaAlloc arena(block.get(), mostCasesSize, almostAllCasesSize);
  //
  // If the program only sometimes allocates memory, use the following pattern.
  //
  //   SkArenaAlloc arena(nullptr, 0, almostAllCasesSize);
  //
  // The storage does not necessarily need to be on the stack. Embedding the storage in a class also
  // works.
  //
  //   class Foo {
  //       char storage[mostCasesSize];
  //       SkArenaAlloc arena (storage, mostCasesSize);
  //   };
  //
  // In addition, the system is optimized to handle POD data including arrays of PODs (where
  // POD is really data with no destructors). For POD data it has zero overhead per item, and a
  // typical per block overhead of 8 bytes. For non-POD objects there is a per item overhead of 4
  // bytes. For arrays of non-POD objects there is a per array overhead of typically 8 bytes. There
  // is an addition overhead when switching from POD data to non-POD data of typically 8 bytes.
  //
  // If additional blocks are needed they are increased exponentially. This strategy bounds the
  // recursion of the RunDtorsOnBlock to be limited to O(log size-of-memory). Block size grow using
  // the Fibonacci sequence which means that for 2^32 memory there are 48 allocations, and for 2^48
  // there are 71 allocations.
  class SkArenaAlloc
  {
  public:
    SkArenaAlloc(char* block, size_t blockSize, size_t firstHeapAllocation);
    explicit SkArenaAlloc(size_t firstHeapAllocation)
      : SkArenaAlloc(nullptr, 0, firstHeapAllocation)
    {
    }
    ~SkArenaAlloc();
    template <typename T, typename... Args>
    T* make(Args&&... args)
    {
      uint32_t size = ToU32(sizeof(T));
      uint32_t alignment = ToU32(alignof(T));
      char* objStart;
      if (std::is_trivially_destructible<T>::value)
      {
        objStart = this->allocObject(size, alignment);
        fCursor = objStart + size;
      }
      else 
      {
        objStart = this->allocObjectWithFooter(size + sizeof(Footer), alignment);
              // Can never be UB because max value is alignof(T).
        uint32_t padding = ToU32(objStart - fCursor);
              // Advance to end of object to install footer.
        fCursor = objStart + size;
        FooterAction* releaser = ;
        this->installFooter(releaser, padding);
      }
          // This must be last to make objects with nested use of this allocator work.
      return new (objStart) T(std::forward<Args>(args)...);
    }
    template <typename T>
    T* makeArrayDefault(size_t count)
    {
      AssertRelease(SkTFitsIn<uint32_t>(count));
      uint32_t safeCount = ToU32(count);
      T* array = (T*) this->commonArrayAlloc<T>(safeCount);
          // If T is primitive then no initialization takes place.
      for (size_t i = 0; i < safeCount; i++)
      {
        new (&array[i]) T;
      }
      return array;
    }
    template <typename T>
    T* makeArray(size_t count)
    {
      AssertRelease(SkTFitsIn<uint32_t>(count));
      uint32_t safeCount = ToU32(count);
      T* array = (T*) this->commonArrayAlloc<T>(safeCount);
          // If T is primitive then the memory is initialized. For example, an array of chars will
          // be zeroed.
      for (size_t i = 0; i < safeCount; i++)
      {
        new (&array[i]) T();
      }
      return array;
    }
      // Only use makeBytesAlignedTo if none of the typed variants are impractical to use.
    void* makeBytesAlignedTo(size_t size, size_t align)
    {
      AssertRelease(SkTFitsIn<uint32_t>(size));
      auto objStart = this->allocObject(ToU32(size), ToU32(align));
      fCursor = objStart + size;
      return objStart;
    }
      // Destroy all allocated objects, free any heap allocations.
    void reset();
  private:
    static void AssertRelease(bool cond)
    {
      if (!cond)
      {
        ::abort();
      }
    }
    static uint32_t ToU32(size_t v)
    {
      assert(SkTFitsIn<uint32_t>(v));
      return (uint32_t) v;
    }
    using Footer = int64_t;
    using FooterAction = char* (*) (char*);
  ;
    static char* SkipPod(char* footerEnd);
    static void RunDtorsOnBlock(char* footerEnd);
    static char* NextBlock(char* footerEnd);
    void installFooter(FooterAction* releaser, uint32_t padding);
    void installUint32Footer(FooterAction* action, uint32_t value, uint32_t padding);
    void installPtrFooter(FooterAction* action, char* ptr, uint32_t padding);
    void ensureSpace(uint32_t size, uint32_t alignment);
    char* allocObject(uint32_t size, uint32_t alignment)
    {
      uintptr_t mask = alignment - 1;
      uintptr_t alignedOffset = (~reinterpret_cast<uintptr_t>(fCursor) + 1) & mask;
      uintptr_t totalSize = size + alignedOffset;
      AssertRelease(totalSize >= size);
      if (totalSize > static_cast<uintptr_t>(fEnd - fCursor))
      {
        this->ensureSpace(size, alignment);
        alignedOffset = (~reinterpret_cast<uintptr_t>(fCursor) + 1) & mask;
      }
      return fCursor + alignedOffset;
    }
    char* allocObjectWithFooter(uint32_t sizeIncludingFooter, uint32_t alignment);
    template <typename T>
    char* commonArrayAlloc(uint32_t count)
    {
      char* objStart;
      AssertRelease(count <= std::numeric_limits<uint32_t>::max() / sizeof(T));
      uint32_t arraySize = ToU32(count * sizeof(T));
      uint32_t alignment = ToU32(alignof(T));
      if (std::is_trivially_destructible<T>::value)
      {
        objStart = this->allocObject(arraySize, alignment);
        fCursor = objStart + arraySize;
      }
      else 
      {
        constexpr uint32_t overhead = sizeof(Footer) + sizeof(uint32_t);
        AssertRelease(arraySize <= std::numeric_limits<uint32_t>::max() - overhead);
        uint32_t totalSize = arraySize + overhead;
        objStart = this->allocObjectWithFooter(totalSize, alignment);
              // Can never be UB because max value is alignof(T).
        uint32_t padding = ToU32(objStart - fCursor);
              // Advance to end of array to install footer.?
        fCursor = objStart + arraySize;
        this->installUint32Footer(, ToU32(count), padding);
      }
      return objStart;
    }
    char* fDtorCursor;
    char* fCursor;
    char* fEnd;
    char* const fFirstBlock;
    const uint32_t fFirstSize;
    const uint32_t fFirstHeapAllocationSize;
      // Use the Fibonacci sequence as the growth factor for block size. The size of the block
      // allocated is fFib0 * fFirstHeapAllocationSize. Using 2 ^ n * fFirstHeapAllocationSize
      // had too much slop for Android.
    uint32_t fFib0{1}, fFib1;
  };
  // Helper for defining allocators with inline/reserved storage.
  // For argument declarations, stick to the base type (SkArenaAlloc).
  template <size_t InlineStorageSize>
  class SkSTArenaAlloc : public SkArenaAlloc
  {
  public:
    explicit SkSTArenaAlloc(size_t firstHeapAllocation = InlineStorageSize)
      : INHERITED(fInlineStorage, InlineStorageSize, firstHeapAllocation)
    {
    }
  private:
    char fInlineStorage[InlineStorageSize];
    using INHERITED = SkArenaAlloc;
  };
  #endif
  