/*---------------------------------------------------------------------------*
  Project:     MEM library
  File:        mem_heapCommon.c
  Programmers: Takano Makoto

  Copyright 2005 Nintendo. 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.
 *---------------------------------------------------------------------------*/

#include <revolution/mem.h>
#include "heapCommoni.h"

/* ========================================================================
    static variables
   ======================================================================== */

/* ------------------------------------------------------------------------
    list related
   ------------------------------------------------------------------------ */

static MEMList   sRootList;                      // root heap list
static BOOL      sRootListInitialized = FALSE;   // if sRootList is initialized, true
static OSMutex   sRootMutex;                     // multi-heap management exclusion controls (24B)

/* ------------------------------------------------------------------------
    fill related
   ------------------------------------------------------------------------ */

#if defined(_DEBUG)

static u32 sFillVals[ MEM_HEAP_FILL_MAX ] =
{
    0xC3C3C3C3, // Value to fill with when creating heap
    0xF3F3F3F3, // Value to fill with when allocating memory block
    0xD3D3D3D3, // Value to fill with when deallocating memory block
};

// #if defined(_DEBUG)
#endif


/* ========================================================================
    static functions
   ======================================================================== */

/* ------------------------------------------------------------------------
    list related
   ------------------------------------------------------------------------ */

/*---------------------------------------------------------------------------*
  Name:         FindContainHeap_

  Description:  Recursively searches the heap containing the specified memory block from the list.
                

  Arguments:    pList: 	pointer to list
                memBlock: 	pointer to memory block

  Returns:      If the heap that allocated the specified memory block is found, returns a pointer to that heap.
                
                Returns NULL if it is not found.
 *---------------------------------------------------------------------------*/
static MEMiHeapHead*
FindContainHeap_(
    MEMList*         pList,
    const void*      memBlock
)
{
    MEMiHeapHead* pHeapHd = NULL;
    while ( NULL != ( pHeapHd = (MEMiHeapHead*)MEMGetNextListObject(pList, pHeapHd) ) )
    {
        if ( GetUIntPtr( pHeapHd->heapStart ) <= GetUIntPtr( memBlock )
             &&  GetUIntPtr( memBlock ) < GetUIntPtr( pHeapHd->heapEnd )
        )
        {
            MEMiHeapHead* pChildHeapHd = FindContainHeap_( &pHeapHd->childList, memBlock );
            if ( pChildHeapHd )
            {
                return pChildHeapHd;
            }
            return pHeapHd;
        }
    }
    return NULL;
}


/*---------------------------------------------------------------------------*
  Name:         FindParentHeap_

  Description:  Searches for the parent heap for the specified heap, under the node indicated in the arguments.
  Arguments:    pNodeHeap:
                pTargetHeap:

  Returns:      Returns a pointer to the heap's header when the parent heap is found.
                Returns NULL if not found.
 *---------------------------------------------------------------------------*/
static MEMiHeapHead*
FindParentHeap_(
    MEMiHeapHead*       pNodeHeap,
    const MEMiHeapHead* pTargetHeap
)
{
    MEMList*       pList   = &pNodeHeap->childList;
    MEMiHeapHead*  pHeapHd = NULL;
    
    while ( NULL != ( pHeapHd = (MEMiHeapHead*)MEMGetNextListObject(pList, pHeapHd) ) )
    {
        if ( pHeapHd == pTargetHeap )
        {
            // is a parent heap if the child heap member and target match
            return pNodeHeap;
        }
        
        // continues the search for children if the target address is included
        if ( GetUIntPtr( pHeapHd->heapStart ) <= GetUIntPtr( pTargetHeap )
             &&  GetUIntPtr( pTargetHeap ) < GetUIntPtr( pHeapHd->heapEnd )
        )
        {
            return FindParentHeap_( pHeapHd, pTargetHeap );
        }
    }
    return NULL;
}

/*---------------------------------------------------------------------------*
  Name:         FindListContainHeap_

  Description:  Searches the parent heap that contains the heap, and returns a pointer to the parent heap list.
                

  Arguments:    pHeapHd: 	Pointer to the header of search target heap.

  Returns:      Returns a pointer to the child list of the parent heap if a parent heap containing the specified heap was found.
                
                If the parent heap is not found, a pointer to the root list is returned.
 *---------------------------------------------------------------------------*/
static MEMList*
FindListContainHeap_( const MEMiHeapHead* pHeapHd )
{
    MEMList* pList = &sRootList;
    
    MEMiHeapHead* pContainHeap = FindContainHeap_( &sRootList, pHeapHd );
    
    if ( pContainHeap )
    {
        pList = &pContainHeap->childList;
    }
    
    return pList;
}

/*---------------------------------------------------------------------------*
  Name:         ListContainsHeap_

  Description:  Checks whether the specified heap is inside the list.

  Arguments:    list:    	Pointer to the heap list structure
                heap:    	Pointer to the heap to be searched for

  Returns:      If the list includes the specified heap, TRUE.
                If the list does not have the specified heap, FALSE.
 *---------------------------------------------------------------------------*/
static BOOL
ListContainsHeap_( MEMList* list, const MEMiHeapHead* heap )
{
    MEMiHeapHead* pHeapHd = NULL;
    
    while ( NULL != ( pHeapHd = (MEMiHeapHead*)MEMGetNextListObject(list, pHeapHd) ) )
    {
        if ( pHeapHd == heap )
        {
            return TRUE;
        }
    }
    return FALSE;
}


/* ========================================================================
    External Functions (Non-Public)
   ======================================================================== */

/*---------------------------------------------------------------------------*
  Name:         MEMiInitHeapHead

  Description:  Initializes the heap header.

  Arguments:    pHeapHd:    	Pointer to the heap header.
                signature: 	The signature.
                heapStart: 	The start address of heap memory.
                heapEnd: 	The end address +1 of heap memory.
                optFlag: 	The heap option.

  Returns:      None.
 *---------------------------------------------------------------------------*/
void
MEMiInitHeapHead(
    MEMiHeapHead*   pHeapHd,
    u32             signature,
    void*           heapStart,
    void*           heapEnd,
    u16             optFlag
)
{
    pHeapHd->signature = signature;
    
    pHeapHd->heapStart = heapStart;
    pHeapHd->heapEnd   = heapEnd;
    
    pHeapHd->attribute.val = 0;
    
    SetOptForHeap( pHeapHd, optFlag );
    
    FillNoUseMemory(
            pHeapHd,
            heapStart,
            GetOffsetFromPtr( heapStart, heapEnd )
    );
    
    MEM_INIT_LIST( &pHeapHd->childList, MEMiHeapHead, link );
    
    // performs initialization when the heap list is first created
    if ( ! sRootListInitialized )
    {
        MEM_INIT_LIST( &sRootList, MEMiHeapHead, link );
        OSInitMutex( &sRootMutex );
        sRootListInitialized = TRUE;
    }
    
    // Mutex initialization
    OSInitMutex( &pHeapHd->mutex );
    
    // addition to the multi-heap list
    OSLockMutex( &sRootMutex );
    MEMAppendListObject( FindListContainHeap_( pHeapHd ), pHeapHd );
    OSUnlockMutex( &sRootMutex );
    
}

/*---------------------------------------------------------------------------*
  Name:         MEMiFinalizeHeap

  Description:  Performs common heap cleanup.

  Arguments:    pHeapHd: 	Pointer to the heap header.

  Returns:      None.
 *---------------------------------------------------------------------------*/
void
MEMiFinalizeHeap( MEMiHeapHead* pHeapHd )
{
    MEMList* pList;
    
    // deletion from the multi-heap list
    OSLockMutex( &sRootMutex );
    
    pList = FindListContainHeap_( pHeapHd );
    ASSERT( ListContainsHeap_( pList, pHeapHd ) );   // Check whether the heap is inside the tree
    MEMRemoveListObject( pList, pHeapHd );
    OSUnlockMutex( &sRootMutex );
    pHeapHd->signature = 0;
}


/*---------------------------------------------------------------------------*
  Name:         MEMiDumpHeapHead

  Description:  Displays heap header information.

  Arguments:    pHeapHd: 	Pointer to the heap header.

  Returns:      None.
 *---------------------------------------------------------------------------*/
void
MEMiDumpHeapHead( MEMiHeapHead* pHeapHd )
{
    OSReport("[OS Foundation ");
    
    switch ( pHeapHd->signature )
    {
    case MEMi_EXPHEAP_SIGNATURE: { OSReport("Exp");   break; }
    case MEMi_FRMHEAP_SIGNATURE: { OSReport("Frame"); break; }
    case MEMi_UNTHEAP_SIGNATURE: { OSReport("Unit");  break; }
    default:
        ASSERT( FALSE );
    }
    
    OSReport(" Heap]\n");
    
    OSReport("    whole [%p - %p)\n", pHeapHd, pHeapHd->heapEnd);
}



/* ========================================================================
    External functions (public)
   ======================================================================== */

/*---------------------------------------------------------------------------*
  Name:         MEMFindContainHeap

  Description:  Searches for the heap containing the memory block.

  Arguments:    memBlock: 	The memory block to be searched for.

  Returns:      If a heap containing the specified memory block was found, returns that heap's handle.
                
                Returns HEAP_INVALID_HANDLE if not found.
 *---------------------------------------------------------------------------*/
MEMHeapHandle
MEMFindContainHeap( const void* memBlock )
{
    return FindContainHeap_( &sRootList, memBlock );
}


/*---------------------------------------------------------------------------*
  Name:         MEMFindParentHeap

  Description:  Searches for the parent heap.

  Arguments:    memBlock: 	The memory block to be searched for.

  Returns:      If a heap containing the specified memory block was found, returns that heap's handle.
                
                Returns HEAP_INVALID_HANDLE if not found.
 *---------------------------------------------------------------------------*/
MEMHeapHandle
MEMFindParentHeap( MEMHeapHandle heap )
{
    MEMiHeapHead* pHeapHd = NULL;
    
    while ( NULL != ( pHeapHd = (MEMiHeapHead*)MEMGetNextListObject(&sRootList, pHeapHd) ) )
    {
        if ( pHeapHd == heap )
        {
            return MEM_HEAP_INVALID_HANDLE;
        }
        // searches for children if the target address is included
        if ( GetUIntPtr( pHeapHd->heapStart ) <= GetUIntPtr( heap )
             &&  GetUIntPtr( heap ) < GetUIntPtr( pHeapHd->heapEnd )
        )
        {
            return FindParentHeap_( pHeapHd, heap );
        }
    }
    return MEM_HEAP_INVALID_HANDLE;
}


#if defined(_DEBUG)

/*---------------------------------------------------------------------------*
  Name:         MEMDumpHeap

  Description:  Displays the information in the heap.
                This function is used for debugging.

  Arguments:    heap: 	Handle for the frame heap

  Returns:      None.
 *---------------------------------------------------------------------------*/

void
MEMDumpHeap( MEMHeapHandle heap )
{
    MEMiHeapHead* pHeapHd = heap;
    switch ( pHeapHd->signature )
    {
    case MEMi_EXPHEAP_SIGNATURE:
        {
            LockHeap( heap );
            MEMiDumpExpHeap(heap);  
            UnlockHeap( heap );
        }
        break;
    case MEMi_FRMHEAP_SIGNATURE: 
        { 
            LockHeap( heap );
            MEMiDumpFrmHeap(heap);
            UnlockHeap( heap );
        }
        break;
    case MEMi_UNTHEAP_SIGNATURE: 
        { 
            LockHeap( heap );
            MEMiDumpUnitHeap(heap); 
            UnlockHeap( heap );
        }
        break; 
    default:
        OSReport("[OS Foundation] dump heap : unknown heap. - %p\n", heap);
    }
}


/*---------------------------------------------------------------------------*
  Name:         MEMSetFillValForHeap

  Description:  Sets the fill value used when creating the heap and allocating/deallocating memory blocks.
                
                This function is for use in debugging.
                Always returns 0 in the final ROM version library.

  Arguments:    type: 	the type of value to get
                val: 	the value to set

  Returns:      Returns the previous value that was set in memory when the memory block was allocated.
 *---------------------------------------------------------------------------*/
u32
MEMSetFillValForHeap(
    int     type,
    u32     val
)
{
    ASSERT( type < MEM_HEAP_FILL_MAX );
    
    {
        u32 oldVal = sFillVals[type];
        sFillVals[type] = val;
        return oldVal;
    }
}


/*---------------------------------------------------------------------------*
  Name:         MEMGetFillValForHeap

  Description:  Gets the fill value used when creating the heap and allocating/deallocating memory blocks.
                
                This function is for use in debugging.
                Always returns 0 in the final ROM version library.

  Arguments:    type: 	the type of value to get

  Returns:      Returns the value set in the memory of the type specified.
 *---------------------------------------------------------------------------*/
u32
MEMGetFillValForHeap( int type )
{
    ASSERT( type < MEM_HEAP_FILL_MAX );
    
    return sFillVals[ type ];
}

// #if defined(_DEBUG)
#endif