Line data    Source code

       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           6 : class DynamicArena
      45             : {
      46             : protected:
      47             :     class Block
      48             :     {
      49             :     public:
      50          10 :         Block()
      51          10 :         {
      52          10 :             m_Data = static_cast<uint8_t*>(
      53          10 :                 std::malloc(BLOCK_SIZE * sizeof(uint8_t)));
      54          10 :             if (!m_Data)
      55             :             {
      56           0 :                 debug_warn("DynamicArena failed to allocate chunk");
      57           0 :                 throw std::bad_alloc();
      58             :             }
      59          10 :         }
      60             : 
      61          10 :         ~Block()
      62             :         {
      63          10 :             std::free(static_cast<void*>(m_Data));
      64          10 :         }
      65             : 
      66             :         Block(const Block& other) = delete;
      67             :         Block& operator=(const Block& other) = delete;
      68             : 
      69           0 :         Block(Block&& other)
      70           0 :             : m_Size(other.m_Size), m_Data(other.m_Data)
      71             :         {
      72           0 :             other.m_Size = 0;
      73           0 :             other.m_Data = nullptr;
      74           0 :         }
      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          21 :         bool Available(size_t n, size_t alignment) const
      96             :         {
      97          21 :             return n + ROUND_UP(m_Size, alignment) <= BLOCK_SIZE;
      98             :         }
      99             : 
     100          21 :         uint8_t* Allocate(size_t n, size_t alignment)
     101             :         {
     102          21 :             m_Size = ROUND_UP(m_Size, alignment);
     103          21 :             uint8_t* ptr = &m_Data[m_Size];
     104          21 :             m_Size += n;
     105          21 :             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           6 :     DynamicArena()
     116           6 :     {
     117           6 :         m_Blocks.reserve(16);
     118           6 :         AllocateNewBlock();
     119           6 :     };
     120             : 
     121          10 :     void AllocateNewBlock()
     122             :     {
     123          10 :         m_Blocks.emplace_back();
     124          10 :     }
     125             : 
     126          21 :     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          21 :         if (n == 0)
     130           1 :             n = 1;
     131             : 
     132          21 :         if (n > BLOCK_SIZE)
     133             :         {
     134           0 :             debug_warn("DynamicArena cannot allocate more than chunk size");
     135           0 :             throw std::bad_alloc();
     136             :         }
     137             : 
     138          21 :         if (!m_Blocks.back().Available(n, alignment))
     139           4 :             AllocateNewBlock();
     140             : 
     141          21 :         return reinterpret_cast<void*>(m_Blocks.back().Allocate(n, alignment));
     142             :     }
     143             : 
     144           8 :     void deallocate(void* UNUSED(p), size_t UNUSED(n))
     145             :     {
     146             :         // ignored
     147           8 :     }
     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