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 <cstdlib>   // std::free
#include <memory>    // std::allocator<>, std::unique_ptr<>
#include <stdexcept> // std::logic_error

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 <array>
#include <iostream>
#include <string>
#include <typeinfo>
#include <vector>
#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