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

  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 when creating heap
    0xF3F3F3F3, // Value to fill when allocating memory block
    0xD3D3D3D3, // Value to fill when releasing 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.
                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 of 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.
                the nth block header, where n = "idx".

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

  Returns:      If the parent heap that includes the specified heap is found:
                Returns a pointer to the parent heap's child list.
                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;
}


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

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

  Description:  Initializes heap header.

  Arguments:    pHeapHd:    Pointer to the heap header.
                signature:  signature.
                heapStart:  start address of heap memory.
                heapEnd:    end address +1 of heap memory.
                optFlag:    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:  Takes care of the heap common.

  Arguments:    pHeapHd:  Pointer to the heap header.

  Returns:      None.
 *---------------------------------------------------------------------------*/
void
MEMiFinalizeHeap( MEMiHeapHead* pHeapHd )
{
    // deletion from the multi-heap list
    OSLockMutex( &sRootMutex );
    MEMRemoveListObject( FindListContainHeap_( pHeapHd ), 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 heap containing memory block.

  Arguments:    memBlock:  memory block to be searched.

  Returns:      If the heap that includes the specified memory block is found,
                returns a handle to that heap.
                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:  memory block to be searched.

  Returns:      If the heap that includes the specified memory block is found,
                returns a handle to that heap.
                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 for debugging.

  Arguments:    heap :    Handle for 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:  Gets the value that is placed in memory when creating the heap and allocating/freeing memory blocks.
                Sets the value to be set.
                This function is for use in debugging.
                Always returns 0 in the final ROM version library.

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

  Returns:      Returns the previous value that was set in memory when 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 value that is placed in memory when creating the heap and allocating/freeing memory blocks.
                Gets the value to be set.
                This function is for use in debugging.
                Always returns 0 in the final ROM version library.

  Arguments:    type:  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