heap_allocator.h

Go to the documentation of this file.

#ifndef _RHEOLEF_HEAP_ALLOCATOR_H
#define _RHEOLEF_HEAP_ALLOCATOR_H
 
#include <memory>
#include <limits>
#include "rheolef/compiler.h"
#include "rheolef/pretty_name.h"
 
namespace rheolef {
 
/*Class:man
NAME: heap_allocator - heap-based allocator
DESCRIPTION:
  Heap allocators are generally used when there is a lot of allocation and deallocation 
  of small objects.
  For instance, this is often the case when dealing with @code{std::list} and @code{std::map}.
 
  Heap-based allocator is conform to the STL specification of allocators.
  It does not "free" the memory until the heap is destroyed.
 
  This allocator handles an a priori unlimited area of memory: a sequence
  of growing chunks are allocated.
  For a limited memory handler in the same spirit, see "stack_allocator"(9).
EXAMPLE:
 @example
    typedef map <size_t, double, less<size_t>, heap_allocator<pair<size_t,double> > >  map_type;
    map_type a;
    a.insert (make_pair (0, 3.14));
    a.insert (make_pair (1, 1.17));
    for (map_type::iterator iter = a.begin(), last = a.end(); iter != last; iter++) @{
      cout << (*iter).first << " " << (*iter).second << endl;
    @}
 @end example
SEE ALSO: "stack_allocator"(9).
AUTHORS:
    LJK-IMAG, 38041 Grenoble cedex 9, France
   | Pierre.Saramito@imag.fr
DATE: 15 december 2010
End:
*/
} // namespace rheolef
 
#ifndef  _RHEOLEF_USE_HEAP_ALLOCATOR
namespace rheolef {
template<class T> using heap_allocator = std::allocator<T>;
} // namespace rheolef
#else // _RHEOLEF_USE_HEAP_ALLOCATOR
 
namespace rheolef {
 
//<verbatim:
template <typename T>
class heap_allocator {
protected:
    struct handler_type; // forward declaration:
public:
 
// typedefs:
 
    typedef size_t         size_type;
    typedef std::ptrdiff_t difference_type;
    typedef T*             pointer;
    typedef const T*       const_pointer;
    typedef T&             reference;
    typedef const T&       const_reference;
    typedef T              value_type;
 
// constructors:
 
    heap_allocator() throw()
      : handler (new handler_type)
    {
    }
    heap_allocator (const heap_allocator& ha) throw()
      : handler (ha.handler)
    {
        ++handler->reference_count;
    }
    template <typename U>
    heap_allocator (const heap_allocator<U>& ha) throw()
      : handler ((typename heap_allocator<T>::handler_type*)(ha.handler))
    {
        ++handler->reference_count;
    }
    ~heap_allocator() throw()
    {
        check_macro (handler != NULL, "unexpected null mem_info");
        if (--handler->reference_count == 0) delete handler;
    }
    // Rebind to allocators of other types
    template <typename U>
    struct rebind {
        typedef heap_allocator<U> other;
    };
 
// assignment:
 
    heap_allocator& operator= (const heap_allocator& ha)
    {
        handler = ha.handler;
        ++handler->reference_count;
        return *this;
    }
 
// utility functions:
 
    pointer       address (reference r)       const { return &r; } 
    const_pointer address (const_reference c) const { return &c; }
    size_type     max_size() const { return std::numeric_limits<size_t>::max() / sizeof(T); }
 
// in-place construction/destruction
 
    void construct (pointer p, const_reference c)
    {
        // placement new operator:
        new( reinterpret_cast<void*>(p) ) T(c);
    }
    // C++ 2011: default construct a value of type T at the location referenced by p
    void construct (pointer p) { new ( reinterpret_cast<void*>(p) ) T(); }
 
    void destroy (pointer p)
    {
        // call destructor directly:
        (p)->~T();
    }
 
// allocate raw memory
 
    pointer allocate (size_type n, const void* = NULL)
    {
        return pointer (handler->raw_allocate (n*sizeof(T)));
    }
    void deallocate (pointer p, size_type n)
    {
        // No need to free heap memory
    }
    const handler_type* get_handler() const {
        return handler;
    }
 
// data:
 
protected:
    handler_type* handler;
    template <typename U> friend class heap_allocator;
};
//>verbatim:
 
// Comparison
template <typename T1>
bool operator== (const heap_allocator<T1>& lhs, const heap_allocator<T1>& rhs) throw()
{
    return lhs.get_handler() == rhs.get_handler();
}
template <typename T1>
bool operator!= (const heap_allocator<T1>& lhs, const heap_allocator<T1>& rhs) throw()
{
    return lhs.get_handler() != rhs.get_handler();
}
 
// ==========================================================================
// heap_allocation::handler class implementation
// ==========================================================================
template<class T>
struct heap_allocator<T>::handler_type {
 
// cstors:
    handler_type ();
    ~handler_type();
// modifier:
    unsigned char* raw_allocate (size_type size);
// data:
    std::list<std::vector<unsigned char> > heap;
    size_type                              heap_block_size;
    size_type                              heap_block_last_free;
    size_type                              reference_count;
    static const size_type                 heap_block_size_init = 512*sizeof(T);
};
template<class T>
inline
heap_allocator<T>::handler_type::handler_type()
  : heap (),
    heap_block_size (heap_block_size_init),
    heap_block_last_free (0),
    reference_count (1)
{
    heap.push_front (std::vector<unsigned char>(heap_block_size));
}
template<class T>
inline
unsigned char*
heap_allocator<T>::handler_type::raw_allocate (size_type size)
{
    if (heap_block_last_free + size > heap_block_size) {
      heap_block_size = std::max (size, 2*heap_block_size);
      heap.push_front (std::vector<unsigned char>(heap_block_size));
      heap_block_last_free = 0;
    }
    std::vector<unsigned char>& block = *(heap.begin());
    unsigned char* p  = &(block [heap_block_last_free]);
    heap_block_last_free += size;
    return p;
}
template<class T>
inline
heap_allocator<T>::handler_type::~handler_type()
{
    heap.erase (heap.begin(), heap.end());
}
 
}// namespace rheolef
 
// ==========================================================================
// std::allocator_traits 
// ==========================================================================
namespace std {
 
template <class T>
struct allocator_traits<rheolef::heap_allocator<T>> {
// typedefs
 
  using allocator_type = rheolef::heap_allocator<T>;
  using value_type     = T;
  using pointer        = T*;
  using const_pointer      = typename std::pointer_traits<pointer>::rebind<const value_type>;
  using void_pointer       = typename std::pointer_traits<pointer>::rebind<void>;
  using const_void_pointer = typename std::pointer_traits<pointer>::rebind<const void>;
  using difference_type    = typename std::pointer_traits<pointer>::difference_type;
  using size_type          = typename std::make_unsigned<difference_type>::type;
  using propagate_on_container_copy_assignment = std::false_type;
  using propagate_on_container_move_assignment = std::false_type;
  using propagate_on_container_swap            = std::false_type;
  using is_always_equal    = typename std::is_empty<rheolef::heap_allocator<T>>::type;
  template <class U>
  using rebind_alloc = rheolef::heap_allocator<U>;
 
// members
 
   static pointer allocate (allocator_type& a, size_type n) { return a.allocate(n); }
   static void  deallocate (allocator_type& a, pointer p, size_type n) { a.deallocate (p, n); }
   static void construct   (allocator_type& a, pointer p) { a.construct (p); }
   static void construct   (allocator_type& a, pointer p, const T& c) { a.construct (p,c); }
   template <class U>
   static void destroy     (allocator_type& a, U* p) {}
   static size_type max_size(const allocator_type& a ) { return std::numeric_limits<size_type>::mqx(); }allocator_type&
};
 
} // namespace std
#endif // _RHEOLEF_USE_HEAP_ALLOCATOR
#endif // _RHEOLEF_HEAP_ALLOCATOR_H