source/lib/allocators/DynamicArena.h

   1 /* Copyright (C) 2021 Wildfire Games.
   2  *
   3  * Permission is hereby granted, free of charge, to any person obtaining
   4  * a copy of this software and associated documentation files (the
   5  * "Software"), to deal in the Software without restriction, including
   6  * without limitation the rights to use, copy, modify, merge, publish,
   7  * distribute, sublicense, and/or sell copies of the Software, and to
   8  * permit persons to whom the Software is furnished to do so, subject to
   9  * the following conditions:
  10  *
  11  * The above copyright notice and this permission notice shall be included
  12  * in all copies or substantial portions of the Software.
  13  *
  14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  15  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  16  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  17  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  18  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  19  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  20  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  21  */
  22
  23 #ifndef INCLUDED_ALLOCATORS_DYNAMIC_ARENA
  24 #define INCLUDED_ALLOCATORS_DYNAMIC_ARENA
  25
  26 #include "lib/bits.h"
  27
  28 #include <cstdlib>
  29 #include <new> // bad_alloc
  30 #include <utility>
  31 #include <vector>
  32
  33 namespace Allocators {
  34
  35 /**
  36  * 'Blind' memory allocator. Characteristics:
  37  * - grows dynamically, and linearily, by BLOCK_SIZE
  38  * - no reallocations, pointers remain valid
  39  * - can allocate objects up to BLOCK_SIZE in size
  40  * - can handle any aligment (up to BLOCK_SIZE)
  41  * - Doesn't de-allocate unless cleared or destroyed.
  42  */
  43 template<size_t BLOCK_SIZE>
  44 class DynamicArena
  45 {
  46 protected:
  47         class Block
  48         {
  49         public:
  50                 Block()
  51                 {
  52                         m_Data = static_cast<uint8_t*>(
  53                                 std::malloc(BLOCK_SIZE * sizeof(uint8_t)));
  54                         if (!m_Data)
  55                         {
  56                                 debug_warn("DynamicArena failed to allocate chunk");
  57                                 throw std::bad_alloc();
  58                         }
  59                 }
  60
  61                 ~Block()
  62                 {
  63                         std::free(static_cast<void*>(m_Data));
  64                 }
  65
  66                 Block(const Block& other) = delete;
  67                 Block& operator=(const Block& other) = delete;
  68
  69                 Block(Block&& other)
  70                         : m_Size(other.m_Size), m_Data(other.m_Data)
  71                 {
  72                         other.m_Size = 0;
  73                         other.m_Data = nullptr;
  74                 }
  75
  76                 Block& operator=(Block&& other)
  77                 {
  78                         if (&other == this)
  79                                 return *this;
  80
  81                         Block tmp(std::move(other));
  82                         swap(*this, tmp);
  83
  84                         return *this;
  85                 }
  86
  87                 friend void swap(Block& lhs, Block& rhs)
  88                 {
  89                         using std::swap;
  90
  91                         swap(lhs.m_Size, rhs.m_Size);
  92                         swap(lhs.m_Data, rhs.m_Data);
  93                 }
  94
  95                 bool Available(size_t n, size_t alignment) const
  96                 {
  97                         return n + ROUND_UP(m_Size, alignment) <= BLOCK_SIZE;
  98                 }
  99
 100                 uint8_t* Allocate(size_t n, size_t alignment)
 101                 {
 102                         m_Size = ROUND_UP(m_Size, alignment);
 103                         uint8_t* ptr = &m_Data[m_Size];
 104                         m_Size += n;
 105                         return ptr;
 106                 }
 107
 108         private:
 109                 size_t m_Size = 0;
 110                 uint8_t* m_Data = nullptr;
 111         };
 112
 113         NONCOPYABLE(DynamicArena);
 114 public:
 115         DynamicArena()
 116         {
 117                 m_Blocks.reserve(16);
 118                 AllocateNewBlock();
 119         };
 120
 121         void AllocateNewBlock()
 122         {
 123                 m_Blocks.emplace_back();
 124         }
 125
 126         void* allocate(size_t n, const void*, size_t alignment)
 127         {
 128                 // Safely handle zero-sized allocations (happens with GCC STL - see ticket #909).
 129                 if (n == 0)
 130                         n = 1;
 131
 132                 if (n > BLOCK_SIZE)
 133                 {
 134                         debug_warn("DynamicArena cannot allocate more than chunk size");
 135                         throw std::bad_alloc();
 136                 }
 137
 138                 if (!m_Blocks.back().Available(n, alignment))
 139                         AllocateNewBlock();
 140
 141                 return reinterpret_cast<void*>(m_Blocks.back().Allocate(n, alignment));
 142         }
 143
 144         void deallocate(void* UNUSED(p), size_t UNUSED(n))
 145         {
 146                 // ignored
 147         }
 148
 149         void clear()
 150         {
 151                 m_Blocks.clear();
 152                 AllocateNewBlock();
 153         }
 154
 155 protected:
 156         std::vector<Block> m_Blocks;
 157 };
 158
 159 } // namespace Allocators
 160
 161 #endif // INCLUDED_ALLOCATORS_DYNAMIC_ARENA