BulkAllocator.h

Go to the documentation of this file.

//--- BEGIN issue #19494 -------------------------------------------------------
// We are leaving it here because, being a header, it will not bother unless
// explicitly invoked. Note that there is a unit test for it too.
#error ("BulkAllocator.h is currently broken; see issue #19494.")
//--- END issue #19494 ---------------------------------------------------------


#ifndef BULKALLOCATOR_H
#define BULKALLOCATOR_H

// interface include
#include <memory> // std::allocator<>, std::unique_ptr<>
#include <stdexcept> // std::logic_error
#include <cstdlib> // std::free

namespace lar {
  namespace details {
    namespace bulk_allocator {
      template <typename T>
      class BulkAllocatorBase;
    } // namespace bulk_allocator
  } // namespace details


  class memory_error: public std::bad_alloc {
      public:
    memory_error(): std::bad_alloc() {}
    memory_error(const char* message): std::bad_alloc(), msg(message) {}
    
    virtual const char* what() const throw() override { return msg; }
    
      private:
    const char* msg = nullptr;
  }; // class memory_error
  
  template <typename T>
  class BulkAllocator: public std::allocator<T> {
      public:
    using BaseAllocator_t = std::allocator<T>;
    
    // import types from the STL allocator
    typedef typename BaseAllocator_t::size_type size_type;
    typedef typename BaseAllocator_t::difference_type difference_type;
    
    typedef typename BaseAllocator_t::value_type value_type;
    
    typedef typename BaseAllocator_t::pointer pointer;
    typedef typename BaseAllocator_t::const_pointer const_pointer;
    
    typedef typename BaseAllocator_t::reference reference;
    typedef typename BaseAllocator_t::const_reference const_reference;
    
    template<typename U>
    struct rebind {
      typedef BulkAllocator<U> other;
    };
    
    BulkAllocator() noexcept: BulkAllocator(GetChunkSize(), false) {}
    
    BulkAllocator(size_type ChunkSize, bool bPreallocate = false) noexcept
      { CreateGlobalAllocator(ChunkSize, bPreallocate); }
    
    BulkAllocator(const BulkAllocator &a) noexcept = default;
    
    BulkAllocator(BulkAllocator &&a) noexcept = default;
    
    template <class U>
    BulkAllocator(const BulkAllocator<U> &a) noexcept:
      BaseAllocator_t(a) { SetChunkSize(a.GetChunkSize()); }
    
    BulkAllocator& operator = (const BulkAllocator &a) = default;
    
    BulkAllocator& operator = (BulkAllocator &&a) = default;
    
    ~BulkAllocator() { GlobalAllocator.RemoveUser(); }
    
    pointer allocate(size_type n, const void* /* hint */ = 0);
    
    void deallocate(pointer p, size_type n);
    
    static void Free() { GlobalAllocator.Free(); }
    
    static size_type GetChunkSize() { return GlobalAllocator.GetChunkSize(); }
    
    static void SetChunkSize(size_type ChunkSize)
      { GlobalAllocator.SetChunkSize(ChunkSize); }
    
      private:
    typedef details::bulk_allocator::BulkAllocatorBase<T>
      SharedAllocator_t; 
    
    void CreateGlobalAllocator(size_type ChunkSize, bool bPreallocate = false);
    
    static SharedAllocator_t GlobalAllocator;
    
    
  }; // class BulkAllocator<>
  
} // namespace lar


//------------------------------------------------------------------------------
#include <algorithm> // std::max()
#include <vector>
#include <iostream>
#include <array>
#include <typeinfo>
#include <string>
#ifdef __GNUG__
# include <cxxabi.h>
#endif // __GNUG__

namespace lar {
  namespace details {

    template <typename T>
    std::string demangle() {
      std::string name = typeid(T).name();
      #ifdef __GNUG__
        int status; // some arbitrary value to eliminate the compiler warning
        std::unique_ptr<char, void(*)(void*)> res
          { abi::__cxa_demangle(name.c_str(), NULL, NULL, &status), std::free };
        return (status==0) ? res.get() : name ;
      #else // !__GNUG__
        return name;
      #endif // ?__GNUG__
    } // demangle()
    
    template <typename T>
    inline std::string demangle(const T&) { return demangle<T>(); }
    
    namespace bulk_allocator {
      constexpr bool bDebug = false;

      class ReferenceCounter {
          public:
        typedef unsigned int Counter_t; 
        
        bool hasUsers() const { return counter > 0; }
        
        Counter_t Count() const { return counter; }
        
        void AddUser() { ++counter; }
        
        bool RemoveUser()
          { if (!counter) return false; --counter; return true; }
        
          private:
        Counter_t counter = 0;
      }; // class ReferenceCounter
      
      
      template <typename T>
      class BulkAllocatorBase: public ReferenceCounter {
          public:
        typedef size_t size_type;
        typedef T value_type;
        typedef T* pointer;
        
        BulkAllocatorBase(
          size_type NewChunkSize = DefaultChunkSize, bool bPreallocate = false
          );
        
        ~BulkAllocatorBase() { Free(); }
        
        void Free();
        
        pointer Get(size_type n);
        
        void Release(pointer) {}
        
        void AddUser() { ReferenceCounter::AddUser(); }
        
        void AddUser(size_type NewChunkSize, bool bPreallocate = false);
        
        bool RemoveUser();
        
        size_type AllocatedCount() const;
        
        size_type UsedCount() const;
        
        size_type FreeCount() const;
        
        size_type NChunks() const { return MemoryPool.size(); }
        
        std::array<size_type, 2> GetCounts() const;
        
        void SetChunkSize(size_type NewChunkSize, bool force = false);
        
        size_type GetChunkSize() const { return ChunkSize; }
        
        void Preallocate() { Preallocate(ChunkSize); }
        
          private:
        typedef std::allocator<T> Allocator_t;
        typedef typename Allocator_t::difference_type difference_type;
        
        Allocator_t allocator; 
        
        class MemoryChunk_t {
            public:
          Allocator_t* allocator; 
          
          pointer begin = nullptr; 
          pointer end = nullptr; 
          pointer free = nullptr; 
          
          MemoryChunk_t(Allocator_t& alloc, size_type n): allocator(&alloc)
            {
              begin = n? allocator->allocate(n): nullptr;
              end = begin + n;
              free = begin;
            } // MemoryChunk_t()
          MemoryChunk_t(const MemoryChunk_t&) = delete; 
          MemoryChunk_t(MemoryChunk_t&&); 
          
          ~MemoryChunk_t() { allocator->deallocate(begin, size()); }
          
          MemoryChunk_t& operator=(const MemoryChunk_t&) = delete;
          MemoryChunk_t& operator=(MemoryChunk_t&&); 
          
          size_type size() const { return end - begin; }
          
          size_type available() const { return end - free; }
          
          size_type used() const { return free - begin; }
          
          bool full() const { return !available(); }
          
          pointer get() { return (free != end)? free++: nullptr; }
          
          pointer get(size_t n)
            {
              pointer ptr = free;
              if ((free += n) <= end) return ptr;
              free = ptr;
              return nullptr;
            }
          
            private:
          MemoryChunk_t(): allocator(nullptr) {}
          
        }; // class MemoryChunk_t
        
        typedef std::vector<MemoryChunk_t> MemoryPool_t;
        
        size_type ChunkSize; 
        MemoryPool_t MemoryPool; 
        
        static size_type DefaultChunkSize;
        
        void Preallocate(size_type n);
        
      }; // class BulkAllocatorBase<>
      
      
      template <typename T>
      BulkAllocatorBase<T>::MemoryChunk_t::MemoryChunk_t(MemoryChunk_t&& from) {
        std::swap(allocator, from.allocator);
        std::swap(begin, from.begin);
        std::swap(end, from.end);
        std::swap(free, from.free);
      } // BulkAllocatorBase<T>::MemoryChunk_t::MemoryChunk_t(MemoryChunk_t&&)
      
      template <typename T>
      typename BulkAllocatorBase<T>::MemoryChunk_t&
        BulkAllocatorBase<T>::MemoryChunk_t::operator= (MemoryChunk_t&& from)
      {
        std::swap(allocator, from.allocator);
        std::swap(begin, from.begin);
        std::swap(end, from.end);
        std::swap(free, from.free);
        return *this;
      } // BulkAllocatorBase<T>::MemoryChunk_t::operator= (MemoryChunk_t&&)
      
      
      template <typename T>
      typename BulkAllocatorBase<T>::size_type
        BulkAllocatorBase<T>::DefaultChunkSize = 10000;
      
      template <typename T>
      BulkAllocatorBase<T>::BulkAllocatorBase
        (size_type NewChunkSize, bool bPreallocate /* = false */):
        ChunkSize(NewChunkSize), MemoryPool()
      {
        Preallocate(bPreallocate? ChunkSize: 0);
        if (bDebug) {
          std::cout << "BulkAllocatorBase[" << ((void*) this)
            << "] created for type " << demangle<value_type>()
            << " with chunk size " << GetChunkSize()
            << " x" << sizeof(value_type) << " byte => "
            << (GetChunkSize()*sizeof(value_type)) << " bytes/chunk"
            << std::endl;
        } // if debug
      } // BulkAllocatorBase<T>::BulkAllocatorBase()
      
      
      template <typename T>
      void BulkAllocatorBase<T>::Free() {
        if (bDebug) {
          std::cout << "BulkAllocatorBase[" << ((void*) this) << "] freeing "
            << NChunks() << " memory chunks with " << AllocatedCount()
            << " elements" << std::endl;
        } // if debug
        MemoryPool.clear();
      } // BulkAllocatorBase<T>::Free()
      
      
      template <typename T>
      bool BulkAllocatorBase<T>::RemoveUser() {
        ReferenceCounter::RemoveUser();
        if (hasUsers()) return true;
        Free();
        return false;
      } // BulkAllocatorBase<T>::RemoveUser()
      
      
      template <typename T>
      void BulkAllocatorBase<T>::AddUser
        (size_type NewChunkSize, bool bPreallocate /* = false */)
      {
        AddUser();
        SetChunkSize(NewChunkSize);
        Preallocate(bPreallocate? ChunkSize: 0);
      } // BulkAllocatorBase<T>::AddUser(size_type, bool )
      
      
      template <typename T>
      void BulkAllocatorBase<T>::Preallocate(size_type n) {
        if (MemoryPool.empty() || (MemoryPool.front().available() < n))
          MemoryPool.emplace_back(allocator, n);
      } // BulkAllocatorBase<T>::RemoveUser()
      
      
      template <typename T>
      typename BulkAllocatorBase<T>::size_type
        BulkAllocatorBase<T>::AllocatedCount() const
      {
        size_type n = 0;
        for (const auto& chunk: MemoryPool) n += chunk.size();
        return n;
      } // AllocatedCount()
      
      
      template <typename T>
      typename BulkAllocatorBase<T>::size_type
        BulkAllocatorBase<T>::UsedCount() const
      {
        size_type n = 0;
        for (const auto& chunk: MemoryPool) n += chunk.used();
        return n;
      } // BulkAllocatorBase<T>::UsedCount()
      
      
      template <typename T>
      std::array<typename BulkAllocatorBase<T>::size_type, 2>
        BulkAllocatorBase<T>::GetCounts() const
      {
        // BUG the double brace syntax is required to work around clang bug 21629
        // (https://bugs.llvm.org/show_bug.cgi?id=21629)
        std::array<BulkAllocatorBase<T>::size_type, 2> stats = {{ 0U, 0U }};
        for (const auto& chunk: MemoryPool) {
          stats[0] += chunk.used();
          stats[1] += chunk.available();
        } // for
        return stats;
      } // BulkAllocatorBase<T>::GetCounts()
      
      
      template <typename T>
      void BulkAllocatorBase<T>::SetChunkSize
        (size_type NewChunkSize, bool force /* = false */)
      {
        if ((GetChunkSize() == NewChunkSize) && !force) return;
        if (bDebug) {
          std::cout << "BulkAllocatorBase[" << ((void*) this) << "]"
            << " changing chunk size: " << GetChunkSize() << " => "
            << NewChunkSize << ": x" << sizeof(value_type) << " byte => "
            << (NewChunkSize*sizeof(value_type)) << " bytes/chunk"
            << std::endl;
        }
        ChunkSize = NewChunkSize;
      } // BulkAllocatorBase<T>::SetChunkSize()
      
      
      template <typename T>
      inline typename BulkAllocatorBase<T>::pointer BulkAllocatorBase<T>::Get
        (size_type n)
      {
        if (n == 0) return nullptr;
        // get the free pointer from the latest chunk (#0)
        pointer ptr = MemoryPool.front().get(n);
        if (ptr) return ptr;
        // no free element left in that chunk:
        // - create a new one in the first position of the pool (move the rest)
        // - return the pointer from the new pool
        //   (if it fails, it fails... but how could that happen?)
        if (bDebug) {
          std::array<size_type, 2> stats = GetCounts();
          std::cout << "BulkAllocatorBase[" << ((void*) this)
            << "] allocating " << std::max(ChunkSize, n)
            << " more elements (on top of the current " << (stats[0] + stats[1])
            << " elements, " << stats[1] << " unused)" << std::endl;
        } // if debug
        return MemoryPool.emplace
          (MemoryPool.begin(), allocator, std::max(ChunkSize, n))->get(n);
      } // BulkAllocatorBase<T>::Get()
      
      
    } // namespace bulk_allocator
  } // namespace details
  
  
  template <typename T>
  typename BulkAllocator<T>::SharedAllocator_t
    BulkAllocator<T>::GlobalAllocator;

  template <typename T>
  void BulkAllocator<T>::CreateGlobalAllocator
    (size_type ChunkSize, bool bPreallocate /* = false */)
  {
    GlobalAllocator.AddUser(ChunkSize, bPreallocate);
  } // BulkAllocator<T>::CreateGlobalAllocator()
  
  template <typename T>
  inline typename BulkAllocator<T>::pointer BulkAllocator<T>::allocate
    (size_type n, const void * /* hint = 0 */)
    { return GlobalAllocator.Get(n); }
  
  template <typename T>
  inline void BulkAllocator<T>::deallocate(pointer p, size_type n) {
    return GlobalAllocator.Release(p);
  } // BulkAllocator<T>::deallocate()
} // namespace lar


#endif // BULKALLOCATOR_H