/*---------------------------------------------------------------------------*
  Project:  Horizon
  File:     fnd_ExpHeap.h

  Copyright (C)2009 Nintendo Co., Ltd.  All rights reserved.

  These coded instructions, statements, and computer programs contain
  proprietary information of Nintendo of America Inc. and/or Nintendo
  Company Ltd., and are protected by Federal copyright law.  They may
  not be disclosed to third parties or copied or duplicated in any form,
  in whole or in part, without the prior written consent of Nintendo.

  $Rev: 29622 $
 *---------------------------------------------------------------------------*/

/*! @file
  @brief    拡張ヒープに関するAPIの宣言

*/

#ifndef NN_FND_FND_EXPHEAP_H_
#define NN_FND_FND_EXPHEAP_H_

#include <nn/types.h>
#include <nn/fnd/fnd_HeapBase.h>
#include <nn/fnd/fnd_MemoryRange.h>
#include <nn/fnd/fnd_Allocator.h>
#include <nn/util/util_TypeTraits.h>
#include <nn/util/detail/util_CLibImpl.h>
#include <nn/util/util_SizedEnum.h>
#include <nn/fnd/detail/fnd_DetailHeapHead.h>
#include <nn/os.h>

#define NN_FND_EXPHEAP_ALLOCATION_MODE_FIRST_FIT 0
#define NN_FND_EXPHEAP_ALLOCATION_MODE_BEST_FIT 1

#define NN_FND_EXPHEAP_ALLOCATION_DIRECTION_FRONT 0
#define NN_FND_EXPHEAP_ALLOCATION_DIRECTION_REAR 1

#ifdef __cplusplus

namespace nn { namespace fnd {

/*!
    @brief    拡張ヒープのベースクラスです。
              
              このクラスのインスタンスを直接作成することはできません。
 */
class ExpHeapBase : public HeapBase
{
public:

    /*!
        @brief メモリブロック確保のモードです。
     */
    enum AllocationMode
    {
        /*!
            @brief 確保しようとしているメモリブロックのサイズ以上の大きさを持つ、最初に見つかった空き領域からメモリブロックを確保します。
         */
        ALLOCATION_MODE_FIRST_FIT = NN_FND_EXPHEAP_ALLOCATION_MODE_FIRST_FIT,
        /*!
            @brief 確保しようとしているメモリブロックのサイズに一番近いサイズの空き領域を探し、その空き領域からメモリブロックを確保します。
         */
        ALLOCATION_MODE_BEST_FIT  = NN_FND_EXPHEAP_ALLOCATION_MODE_BEST_FIT
    };

    /*!
        @brief メモリブロック確保の方向を指定するための定数です。
     */
    enum AllocationDirection
    {
        /*!
            @brief メモリブロックの確保時に、ヒープの空き領域の前方から確保します。
         */
        ALLOCATION_DIRECTION_FRONT = NN_FND_EXPHEAP_ALLOCATION_DIRECTION_FRONT,
        /*!
            @brief メモリブロックの確保時に、ヒープの空き領域の後方から確保します。
         */
        ALLOCATION_DIRECTION_REAR  = NN_FND_EXPHEAP_ALLOCATION_DIRECTION_REAR
    };

    /*!
        @brief ブロックを巡るときに呼び出されるコールバック関数の型です。
    */
    typedef void (*BlockVisitor)(void* pBlock, const ExpHeapBase* heap, uptr param);

    /*!
        @brief 拡張ヒープから確保したメモリブロックのサイズを取得します。

        @param[in] pBlock メモリブロックの先頭アドレスを指定します。

        @return 拡張ヒープから確保したメモリブロックのサイズを返します。ここで返される値は、アラインメントなどの制約により、確保時のサイズより大きい値を返すことがあります。
     */
    size_t GetSizeOf(const void* pBlock) const;

    /*!
        @brief 拡張ヒープから確保したメモリブロックのグループIDを取得します。

        @param[in] pBlock メモリブロックの先頭アドレスを指定します。

        @return 拡張ヒープから確保したメモリブロックのグループIDを返します。
     */
    bit8 GetGroupIdOf(const void* pBlock) const;

    /*!
        @brief 拡張ヒープから確保したメモリブロックのメモリ確保の方向を取得します。

        @param[in] pBlock メモリブロックの先頭アドレスを指定します。

        @return 拡張ヒープから確保したメモリブロックのメモリ確保の方向を返します。
     */
    AllocationDirection GetDirectionOf(const void* pBlock) const;
    
protected:

	ExpHeapBase() : m_AllocCount(0) {}

    template <class MemoryBlock>
    explicit ExpHeapBase(const MemoryBlock& block, bit32 option) { Initialize(block.GetAddress(), block.GetSize(), option); }

    ExpHeapBase(uptr addr, size_t size, bit32 option) { Initialize(addr, size, option); }

    void Initialize(uptr addr, size_t size, bit32 option);

    void Invalidate();

    void Finalize();

    virtual ~ExpHeapBase() { Finalize(); }

    void* Allocate(size_t byteSize, s32 alignment = DEFAULT_ALIGNMENT, bit8 groupId = 0, AllocationMode mode = ALLOCATION_MODE_FIRST_FIT, bool reuse = false);

    void Free(void* p);

    virtual void FreeV(void* p) { Free(p); }

    size_t ResizeBlock(void* p, size_t newSize);

    void VisitAllBlocks(BlockVisitor visitor, uptr param);

    virtual void* GetStartAddress() const;

    virtual size_t GetTotalSize() const;

    size_t GetTotalFreeSize() const;

    size_t GetAllocatableSize(s32 alignment = DEFAULT_ALIGNMENT) const;

    u32 Adjust();

    MemoryRange Adjust(HeapAdjustMode mode);

    bool CheckHeap(bit32 option = OPTION_ERROR_PRINT) const;

    bool CheckBlock(const void* p, bit32 option = OPTION_ERROR_PRINT) const;

    virtual void Dump() const;

    virtual bool HasAddress(const void* addr) const;

private:

    detail::ExpHeapImpl m_ExpHeapImpl;

    size_t m_AllocCount;
    
};

/*!
    @brief    拡張ヒープのためのクラステンプレートです。
    
              このクラステンプレートを実体化したクラスでは、
              指定したロックポリシーによって、排他制御が行われます。
              ロックポリシーは @ref nn::os::LockPolicy クラスの内部で宣言される
              クラスもしくはクラステンプレートを実体化したクラスを指定することができます。
              上述のクラス以外を LockPolicy に指定した場合の動作・互換性は保障されません。
              
              ロックされるのは、ヒープ内の操作に対してのみであり、
              ヒープの階層化に対する操作などを行う場合は、適切な排他処理などが別途必要となります。
    
    @tparam   LockPolicy ヒープに対する操作を行うときのロックポリシーを指定します。
 */
template <class LockPolicy>
class ExpHeapTemplate : public ExpHeapBase, private LockPolicy::LockObject
{
private:
    typedef ExpHeapBase Base;
    typedef typename LockPolicy::LockObject LockObject;
    typedef typename LockPolicy::ScopedLock ScopedLock;
public:

    /*!
        :overload NotInitialize

        @brief コンストラクタです。
        
        初期化は行いません。
     */
    ExpHeapTemplate() {}

    /*!
        :overload WithMemoryBlock

        @brief コンストラクタです。
        
        @param[in] block    ヒープに割り当てるメモリブロックを指定します。
        @param[in] option   オプションを指定します。
        
        ヒープの初期化を行います。

        Bug: option パラメータは未実装です。
     */
    template <class MemoryBlock>
    explicit ExpHeapTemplate(const MemoryBlock& block, bit32 option = 0)
    {
        Initialize(block.GetAddress(), block.GetSize(), option);
    }

    /*!
        :overload WithAddress

        @brief コンストラクタです。
      
        @param[in] addr     ヒープに割り当てるメモリブロックの先頭アドレスを指定します。
        @param[in] size     ヒープに割り当てるメモリブロックのサイズを指定します。
        @param[in] option   オプションを指定します。

        ヒープの初期化を行います。
        
        Bug: option パラメータは未実装です。
     */
    ExpHeapTemplate(uptr addr, size_t size, bit32 option = 0)
    {
        Initialize(addr, size, option);
    }

    /*!
        @brief ヒープの初期化を行います。
      
        @param[in] addr     ヒープに割り当てるメモリブロックの先頭アドレスを指定します。
        @param[in] size     ヒープに割り当てるメモリブロックのサイズを指定します。
        @param[in] option   オプションを指定します。
        
        Bug: option パラメータは未実装です。

        @return 無し。
     */
    void Initialize(uptr addr, size_t size, bit32 option = 0)
    {
        Base::Initialize(addr, size, option);
        LockObject::Initialize();
    }

    /*!
        @brief  ヒープ内に拡張ヒープを作成します。

                この関数で作成したヒープは @ref HeapBase::Destroy により破壊してください。

                ExpHeap自身をaddrとsizeで指定した領域内に作成します。
                このため、指定した領域の大きさから sizeof(ExpHeap) の大きさだけ少ない領域をヒープとして割り当てます。
                
                placementによりExpHeapオブジェクト自身の配置場所を指定します。
                placementに HEAP_INFOPLACEMENT_HEAD を指定すると領域の先頭（addr から addr+sizeof(ExpHeap) までの領域）にExpHeapオブジェクト自身を配置します。
                placementに HEAP_INFOPLACEMENT_TAIL を指定すると領域の末尾（addr+size-sizeof(ExpHeap) から addr+size までの領域）にExpHeapオブジェクト自身を配置します。

        @param[in] parent       addr を領域内に持つ親のヒープを指定します。
        @param[in] addr         ヒープに割り当てるメモリブロックの先頭アドレスを指定します。
        @param[in] size         ヒープに割り当てるメモリブロックのサイズを指定します。
        @param[in] option       オプションを指定します。
        @param[in] placement    管理領域(ExpHeapオブジェクト)の配置場所を指定します。
    */
    static ExpHeapTemplate* Create(HeapBase* parent, void* addr, size_t size, bit32 option = 0, bit32 placement = HEAP_INFOPLACEMENT_HEAD);

    /*!
        @brief ヒープを無効にします。

        @return 無し。
     */
    void Invalidate() { Base::Invalidate(); }

    /*!
        @brief ヒープが有効ならば破棄します。

        @return 無し。
     */
    void Finalize()
    {
        LockObject::Finalize();
        Base::Finalize();
    }

    /*!
        @brief デストラクタです。内部でFinalize()を呼びます。

        @return 無し。
     */
    virtual ~ExpHeapTemplate() {}

    /*!
        @brief 拡張ヒープからメモリを確保します。

        alignment に指定可能な値は、-128, -64, -32, -16, -8, -4, 4, 8, 16, 32, 64, 128 のいずれかの値です。

        alignment に正の値を指定すると、ヒープ領域の先頭から探索して見つけた空き領域を確保して、負の値を指定すると、ヒープ領域の後方から探索して見つけた空き領域を確保します。

        @param[in] byteSize         確保するメモリブロックのサイズ（バイト）を指定します。
        @param[in] alignment        アラインメントを指定します。-128 <= alignment <= 128 の範囲で絶対数が4以上の2のべき乗になる値を指定できます。
        @param[in] groupId          グループIDを指定します。
        @param[in] mode             メモリブロック確保のモードを指定します。
        @param[in] reuse            アラインメントの際に発生する隙間の領域を再利用するかどうかを指定します。

        @return 確保したメモリブロックの先頭アドレスを返します。
     */
    void* Allocate(size_t byteSize, s32 alignment = DEFAULT_ALIGNMENT, bit8 groupId = 0, AllocationMode mode = ALLOCATION_MODE_FIRST_FIT, bool reuse = false)
    {
        ScopedLock lk(*this);
        return Base::Allocate(byteSize, alignment, groupId, mode, reuse);
    }

    /*!
        @brief 拡張ヒープから確保したメモリブロックを解放します。

        @param[in] p    解放するメモリブロックの先頭アドレスを指定します。

        @return 無し。
     */
    void Free(void* p)
    {
        ScopedLock lk(*this);
        Base::Free(p);
    }

    /*!
        @brief          拡張ヒープから確保したメモリブロックを解放します。

                        仮想メンバ関数であるため、HeapBaseから解放できます。

        @param[in] p    解放するメモリブロックの先頭アドレスを指定します。

        @return         無し。
    */
    virtual void FreeV(void* p) { Free(p); }

    /*!
        @brief 拡張ヒープから確保したメモリブロックのサイズを変更します。

        @param[in] p        サイズを変更するメモリブロックの先頭アドレスを指定します。
        @param[in] newSize  変更後のメモリブロックのサイズ（バイト）を指定します。

        @return 関数が成功した場合、変更後のメモリブロックのサイズ(バイト)を返します。 関数が失敗した場合、0 を返します。
     */
    size_t ResizeBlock(void* p, size_t newSize)
    {
        ScopedLock lk(*this);
        return Base::ResizeBlock(p, newSize);
    }

    /*!
        @brief 拡張ヒープから確保した全てのメモリブロックに対し、ユーザが指定した関数 visitor を呼びます。

        @param[in] visitor  各メモリブロックに対して呼ぶ関数を指定します。
        @param[in] param    visitor関数に渡す引数を指定します。

        @return 無し。
     */
    void VisitAllBlocks(BlockVisitor visitor, uptr param)
    {
        ScopedLock lk(*this);
        return Base::VisitAllBlocks(visitor, param);
    }

    /*!
        @brief 拡張ヒープのメモリ領域の開始アドレスを取得します。

        @return 拡張ヒープのメモリ領域の開始アドレスをを返します。
     */
    virtual void* GetStartAddress() const
    {
        ScopedLock lk(*this);
        return Base::GetStartAddress();
    }

    /*!
        @brief 拡張ヒープに割り当てられているメモリサイズを取得します。

        @return 拡張ヒープに割り当てられているメモリサイズを返します。
     */
    virtual size_t GetTotalSize() const
    {
        ScopedLock lk(*this);
        return Base::GetTotalSize();
    }

    /*!
        @brief 拡張ヒープの空きメモリサイズを取得します。

        @return 拡張ヒープの空きメモリの合計を返します。
     */
    size_t GetTotalFreeSize() const
    {
        ScopedLock lk(*this);
        return Base::GetTotalFreeSize();
    }

    /*!
        @brief 拡張ヒープから確保可能なメモリブロックのサイズを取得します。

        @param[in] alignment    アラインメントを指定します。

        @return 拡張ヒープから確保可能なメモリブロックのサイズを返します。
     */
    size_t GetAllocatableSize(s32 alignment = DEFAULT_ALIGNMENT) const
    {
        ScopedLock lk(*this);
        return Base::GetAllocatableSize(alignment);
    }

    /*!
        :overload deprecated

        @brief  この関数の使用は推奨されません。拡張ヒープの末尾側の空き領域を開放し、拡張ヒープが使用するメモリを縮小します。

                この関数の戻り値は、Adjust に失敗した場合の0と、何も Allocate されていないために、
                縮小後のヒープのサイズが0になった場合を区別できません。

        @return 関数が成功した場合は縮小後の拡張ヒープの全体サイズを、失敗した場合は 0 を返します。
     */
    u32 Adjust()
    {
        ScopedLock lk(*this);
        return Base::Adjust();
    }

    /*!
        :overload withmode

        @brief              拡張ヒープの空き領域を開放し、拡張ヒープが使用するメモリを縮小します。

        @param[in] mode     末尾(HEAP_ADJUST_TAIL)から縮小するか、先頭(HEAP_ADJUST_HEAD)から縮小するかを指定します。

        @return             ヒープが縮小されることにより空いたメモリ領域の範囲を返します。
                            縮小できない場合の戻り値のMemoryRangeの大きさは0になります。
     */
    MemoryRange Adjust(HeapAdjustMode mode)
    {
        ScopedLock lk(*this);
        return Base::Adjust(mode);
    }

    /*!
        @brief 拡張ヒープが破壊されていないかどうかをチェックします。

        @param[in] option   オプションを指定します。

        @return チェックが成功するとtrue、失敗するとfalseを返します。
     */
    bool CheckHeap(bit32 option = OPTION_ERROR_PRINT) const
    {
        ScopedLock lk(*this);
        return Base::CheckHeap(option);
    }

    /*!
        @brief 拡張ヒープから確保したメモリブロックのチェックを行います。

        @param[in] p        メモリブロックの先頭アドレスを指定します。
        @param[in] option   オプションを指定します。

        @return チェックが成功するとtrue、失敗するとfalseを返します。
     */
    bool CheckBlock(const void* p, bit32 option = OPTION_ERROR_PRINT) const
    {
        ScopedLock lk(*this);
        return Base::CheckBlock(p, option);
    }
    
    /*!
        @brief  指定したアドレスがヒープに含まれているか調べます。

        @param[in]  addr    調べたいアドレスを指定します。

        @return ヒープに含まれていれば true を返し、含まれていなければ false を返します。
    */
    virtual bool HasAddress(const void* addr) const
    {
        ScopedLock lk(*this);
        return Base::HasAddress(addr);
    }

    /*!
        @brief ヒープ内部の情報を表示します。（デバッグ用）

        @return 無し。
     */
    virtual void Dump() const
    {
        ScopedLock lk(*this);
        Base::Dump();
    }

    class Allocator;
    
};

/*!
    @brief 拡張ヒープ用のアロケータクラスです。
 */
template <class LockPolicy>
class ExpHeapTemplate<LockPolicy>::Allocator : public IAllocator
{
public:
    
    /*!
        @brief 拡張ヒープとアロケートオプションを指定したコンストラクタです。
        
        @param[in] heap             拡張ヒープを指定します。
        @param[in] groupId          グループ ID を指定します。
        @param[in] mode             メモリブロック確保のモードを指定します。
        @param[in] reuse            アラインメントの際に発生する隙間の領域を再利用するかどうかを指定します。
     */
    Allocator(ExpHeapTemplate<LockPolicy>& heap, bit8 groupId = 0, AllocationMode mode = ExpHeapBase::ALLOCATION_MODE_FIRST_FIT, bool reuse = false) : m_Heap(0) { Initialize(heap, groupId, mode, reuse); }

    /*!
        @brief 初期化をしないコンストラクタです。
     */
    Allocator() : m_Heap(0) {}

    /*!
        @brief 初期化されていないアロケータを初期化します。
        
        @param[in] heap             拡張ヒープを指定します。
        @param[in] groupId          グループ ID を指定します。
        @param[in] mode             メモリブロック確保のモードを指定します。
        @param[in] reuse            アラインメントの際に発生する隙間の領域を再利用するかどうかを指定します。
     */
    void Initialize(ExpHeapTemplate<LockPolicy>& heap, bit8 groupId = 0, AllocationMode mode = ExpHeapBase::ALLOCATION_MODE_FIRST_FIT, bool reuse = false)
    {
        NN_TASSERT_(!this->m_Heap);
        this->m_Heap = &heap;
        this->m_GroupId = groupId;
        this->m_AllocationMode = mode;
        this->m_Reuse = reuse;
    }
    
    /*!
        @brief アロケータにセットされている拡張ヒープを返します。
        @return アロケータにセットされている拡張ヒープ
     */
    ExpHeapTemplate<LockPolicy>* GetHeap() { return m_Heap; }
    
    /*!
        @brief アロケータにセットされている拡張ヒープを返します。
        @return アロケータにセットされている拡張ヒープ
     */
    const ExpHeapTemplate<LockPolicy>* GetHeap() const { return m_Heap; }

    /*!
        @brief 指定したサイズとアラインメントでメモリ領域を確保します。
        
        @param[in] size 確保するメモリのサイズ
        @param[in] alignment 確保するメモリのアラインメント
        
        @return 確保したメモリ領域の先頭へのポインタ
    */
    virtual void* Allocate(size_t size, s32 alignment) { return m_Heap->Allocate(size, alignment, m_GroupId, m_AllocationMode, m_Reuse); }
    
    /*!
        @brief メモリ領域を解放します。
        @param[in] p 確保されているメモリ領域の先頭へのポインタ
    */
    virtual void Free(void* p) { m_Heap->Free(p); }

    /*!
        @brief メモリ確保時のグループ ID を取得します。
        @return メモリ確保時のグループ ID
     */
    bit8 GetGroupId() const { return m_GroupId; }
    
    /*!
        @brief メモリ確保時のグループ ID を設定します。
        @param[in] groupId グループ ID を指定します。
     */
    void SetGroupId(bit8 groupId) { this->m_GroupId = groupId; }

    /*!
        @brief メモリ確保時のモードを取得します。
        @return メモリ確保時のモード
     */
    AllocationMode GetAllocationMode() const { return m_AllocationMode; }
    
    /*!
        @brief メモリ確保時のモードを設定します。
        @param[in] allocationMode メモリ確保時のモード
     */
    void SetAllocationMode(AllocationMode allocationMode) { this->m_AllocationMode = allocationMode; }

    /*!
        @brief メモリ確保の際に、アラインメントの際に発生する隙間の領域を再利用するかどうかを指定します。
        @return アラインメントの際に発生する隙間の領域を再利用するなら ture 、しないなら false
     */
    bool GetUseMarginOfAlignment() const { return m_Reuse; }
    
    /*!
        @brief アラインメントの際に発生する隙間の領域を再利用するかどうかを設定します。
        @param[in] reuse アラインメントの際に発生する隙間の領域を再利用するかどうか
     */
    void SetUseMarginOfAlignment(bool reuse) { m_Reuse = reuse; }

private:
    ExpHeapTemplate<LockPolicy>* m_Heap;
    bit8 m_GroupId;
    nn::util::SizedEnum1<AllocationMode> m_AllocationMode;
    bool m_Reuse;
    NN_PADDING1;
};

/*!
    @brief ロック操作をしないスレッドアンセーフな拡張ヒープを表す型です。
*/
typedef ExpHeapTemplate<nn::os::LockPolicy::NoLock> ExpHeap;

/*!
    @brief ヒープごとに用意されるクリティカルセクションで保護された、スレッドセーフな拡張ヒープを表す型です。
*/
typedef ExpHeapTemplate<nn::os::LockPolicy::Object<nn::os::CriticalSection> > ThreadSafeExpHeap;

template <class LockPolicy>
ExpHeapTemplate<LockPolicy>* ExpHeapTemplate<LockPolicy>::Create(HeapBase* parent, void* addr, size_t size, bit32 option, bit32 placement)
{
    ExpHeapTemplate* heap;

    if ( parent->FindHeap(addr) != parent ) return 0;
    
    if ( placement == HEAP_INFOPLACEMENT_HEAD )
    {
        heap = new (addr) ExpHeapTemplate(reinterpret_cast<uptr>(addr)+sizeof(ExpHeapTemplate), static_cast<size_t>(size - sizeof(ExpHeapTemplate)), option);
    }
    else if ( placement == HEAP_INFOPLACEMENT_TAIL )
    {
        void* placeaddr = reinterpret_cast<void*>(reinterpret_cast<uptr>(addr)+static_cast<size_t>(size - sizeof(ExpHeapTemplate)));
        heap = new (placeaddr) ExpHeapTemplate(reinterpret_cast<uptr>(addr), static_cast<size_t>(size - sizeof(ExpHeapTemplate)), option);
    }
    else
    {
        return 0;
    }
    
    heap->SetParent(parent);
    
    return heap;
}

}}

#endif

#endif