/**
 *  @file   mem1_allocator.h
 *  @brief  固定領域から固定サイズのメモリを１つづアロケートするアロケータ
 *  @author tenk*
 *  @date   2004,2010
 *  @note
 *  -   mem1_pool_alloc<SIZE,ALN> は、指定したアドレスからの固定のメモリを
 *      プールとして、特定サイズのメモリを１つづつ取得するアロケータ.
 *  -   static_mem1_allocator<T,BYTES,ALN> は、mem1_pool_allocを使って
 *      BYTESバイトのstatic配列を確保してT型のメモリを取得する
 *      std::allocator風のアロケータ
 *  -   Public Domain Software
 */
#ifndef MEM1_ALLOCATOR_H
#define MEM1_ALLOCATOR_H

#include <cstring>
#ifndef assert
#include <cassert>
#endif


// ============================================================================
//
// ============================================================================

#ifndef MEM1_POOL_ALLOC_DEFINED
#define MEM1_POOL_ALLOC_DEFINED

/** bufからbufSzバイトのメモリから、cellSzバイトのメモリをアロケートする.
 *  - セルサイズ/アライメントは、最小で sizeof(void*) バイトになる.
 *  - ALN は、sizeof(void*)より大きなアライメントにしたい場合用(doubleなりint64_tなり).
 */
template<typename SIZE=unsigned, typename ALN=void* >
class mem1_pool_alloc {
public:
    mem1_pool_alloc (std::size_t cellSz=0, void* buf=0, std::size_t bufSz=0) throw();
    void        init(std::size_t cellSz=0, void* buf=0, std::size_t bufSz=0) throw();

    void*       alloc();                            ///< cellSzバイトのメモリ取得.
    bool        dealloc(void* p);                   ///< alloc()で取得したメモリの開放.
    std::size_t alloc_bytes() const;                ///< 1アロケートのサイズ(バイト数).
    std::size_t capacity() const {return cellNum_;} ///< 最大アロケート数.
    bool        isAllocPtr(const void* p) const;    ///< pはこれでallocしたポインタか?
    void        CHECK_PTR(const void *p) const;     ///< ポインタの正当性チェック.

private:
    /// 空きメモリをリンクして管理するための型
    union Unit {
        Unit*   link_;                  ///< リンク.
        ALN     aln_;                   ///< アライメント用.
    };
    Unit*       unitBuf_;               ///< unit単位で管理するメモリ.
    Unit*       unitBufEnd_;            ///< unit単位で管理するメモリ.
    Unit*       base_;                  ///< 空きメモリ管理の基点.
    SIZE        cellUnits_;             ///< 1要素のUnit単位の値.
    SIZE        cellNum_;               ///< 確保可能な要素数.
};



/** デバッグ・コンパイル時の、ポインタの正当性チェック.
 */
template<typename SIZE, typename ALN>
inline void mem1_pool_alloc<SIZE, ALN>::CHECK_PTR(const void *p) const {
  #ifndef NDEBUG
    const Unit  *cur = reinterpret_cast<const Unit*>(p);
    assert(unitBuf_ <= cur && cur < unitBufEnd_);
    assert((cur-unitBuf_) % cellUnits_ == 0);
  #endif
}


/// 1アロケートのサイズ(バイト数).
template<typename SIZE, typename ALN>
inline std::size_t mem1_pool_alloc<SIZE,ALN>::alloc_bytes() const {
    return sizeof(Unit) * cellUnits_;
}


/// 1アロケートのサイズ(バイト数).
template<typename SIZE, typename ALN> inline
bool    mem1_pool_alloc<SIZE,ALN>::isAllocPtr(const void* p) const {
    return (char*)unitBuf_ <= (char*)p && (char*)p < (char*)unitBufEnd_;
}


/** コンストラクタ.
 */
template<typename SIZE, typename ALN>
mem1_pool_alloc<SIZE,ALN>::mem1_pool_alloc( std::size_t cellSz, void* buf, std::size_t bufSz ) throw()
    : unitBuf_(0), unitBufEnd_(0), base_(0), cellUnits_(0), cellNum_(0)
{
    if (buf != 0)
        init(cellSz, buf, bufSz);
}


/** 初期化. アドレスbufからのbufSzバイトを、cellSzバイト単位に管理.
 */
template<typename SIZE, typename ALN>
void mem1_pool_alloc<SIZE,ALN>::init( std::size_t cellSz, void* buf, std::size_t bufSz ) throw()
{
    if (unitBuf_ != 0)
        return;
    assert( (std::size_t(buf) % sizeof(Unit)) == 0 );       // アライメントチェック
    assert( cellSz >= sizeof(Unit) || (cellSz == 0 && buf == 0 && bufSz == 0) );
    assert( bufSz >= cellSz  || bufSz == 0  );

    unitBuf_        = reinterpret_cast<Unit*>(buf);
    cellNum_        = cellSz > 0 ? bufSz / cellSz : 0;
    cellUnits_      = (cellSz + sizeof(Unit)-1) / sizeof(Unit);
    std::size_t cellBytes = alloc_bytes();
    assert( cellSz == cellBytes );
    base_           = 0;
    unitBufEnd_     = &unitBuf_[ cellUnits_ * cellNum_ ];

    if (buf && cellNum_ > 0) {
        using std::memset;
        memset(buf, 0, bufSz);
        base_       = &unitBuf_[0];
        for (std::size_t i = 0; i < cellNum_-1; ++i) {
            unitBuf_[i * cellUnits_].link_ = &unitBuf_[(i+1) * cellUnits_];
        }
        unitBuf_[(cellNum_-1) * cellUnits_].link_ = NULL;
    }
}


/** 1つ分メモリ(cellSzバイト)をアロケート.
 */
template<typename SIZE, typename ALN>
inline void* mem1_pool_alloc<SIZE,ALN>::alloc() {
    Unit*   p   = base_;
    if (p) {
      #ifndef NDEBUG
        CHECK_PTR( p );
        if ( p->link_ ) CHECK_PTR(p->link_);
      #endif
        base_ = p->link_;
    }
    return p;
}


/** alloc()されてたメモリを開放.
 */
template<typename SIZE, typename ALN>
inline bool mem1_pool_alloc<SIZE,ALN>::dealloc(void* p) {
    if (p) {
        Unit*   u    = reinterpret_cast<Unit*>(p);
      #ifndef NDEBUG
        CHECK_PTR( p );
      #endif
        u->link_     = base_;
        base_        = u;
        return 1;
    }
    return 0;
}


#endif  // MEM1_POOL_ALLOC_DEFINED




// ============================================================================
//
// ============================================================================

/// メモリ不足時にエラー扱いするためのクラス.
template< typename T >
class mem1_allocator_no_mem {
public:
    static T*   allocate(std::size_t) {assert(0&&"not enough memory");return 0;}
    static void deallocate(T*)        {assert(0&&"bad pointer"); }
};



// ============================================================================
//
// ============================================================================

/// 固定領域から固定サイズのメモリを１つづアロケートするアロケータ.
/// BYTES分のメモリを予めstaticに確保し、そこからアロケートする.
/// ※アプリケーション内で使う量が一定範囲とわかっている場合用.
/// Aに別のallocatorを指定すればメモリ不足時、そちらから確保する.
template< typename T, unsigned BYTES, class A=mem1_allocator_no_mem<T> >
class static_mem1_allocator : public A {
public:
    typedef T               value_type;
    typedef T*              pointer;
    typedef const T*        const_pointer;
    typedef T&              reference;
    typedef const T&        const_reference;
    typedef std::size_t     size_type;
    //typedef unsigned      size_type;
    typedef A               base_type;
    typedef std::ptrdiff_t  difference_type;

    static_mem1_allocator() { s_mem1_pool_.init(sizeof(T), s_buf_, BYTES); }
    static_mem1_allocator(const static_mem1_allocator&) {}
    ~static_mem1_allocator() throw() {}

    static pointer          address(reference       x) {return &x;}
    static const_pointer    address(const_reference x) {return &x;}

    static pointer allocate(size_type n,const void *) {return allocate(n);}

    static pointer allocate(size_type n) {
        assert(n == 1);
        pointer  p = (pointer)s_mem1_pool_.alloc();
        if (p == 0)
            p = base_type::allocate(n);
        return p;
    }

    static void deallocate(pointer p, size_type)    {deallocate(p);}

    static void deallocate(pointer p) {
        if (s_mem1_pool_.isAllocPtr(p))
            s_mem1_pool_.dealloc(p);
        else
            base_type::deallocate(p);
    }

    static void construct(pointer p, const T& val)  {new((void*)p) T(val);}
    static void construct(pointer p)                {new((void*)p) T;}
    static void destroy(pointer p)                  {p->~T();}

    static size_type max_size() throw() {return ~0; }

    bool operator ==(const static_mem1_allocator& r) const {return true;}
    bool operator !=(const static_mem1_allocator& r) const {return !(*this == r);}

private:
    static mem1_pool_alloc<>    s_mem1_pool_;
    static double               s_buf_[ (BYTES+sizeof(double)-1) / sizeof(double) ];
};


template< typename T, unsigned BYTES, class A >
mem1_pool_alloc<> static_mem1_allocator<T,BYTES,A>::s_mem1_pool_;

template< typename T, unsigned BYTES, class A >
double            static_mem1_allocator<T,BYTES,A>::s_buf_[ (BYTES+sizeof(double)-1) / sizeof(double) ];


#endif  // MEM1_ALLOCATOR_H