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

  Copyright (C) 2005-2006 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/expHeap.h>
#include "heapCommoni.h"
#include <stdlib.h>


/* ========================================================================
    Macro Constants
   ======================================================================== */

// Free memory block signature
#define MBLOCK_FREE_SIGNATURE   ('FR')

// Signature for the memory block being used
#define MBLOCK_USED_SIGNATURE   ('UD')

// Maximum group ID value
#define MAX_GROUPID             0xff

// Default value for the group ID
#define DEFAULT_GROUPID         0

// Minimum alignment value
#define MIN_ALIGNMENT           4

// Default memory allocation mode
#define DEFAULT_ALLOC_MODE      MEM_EXPHEAP_ALLOC_MODE_FIRST

// minimum size for registration as a free block (exclusive of header)
#define MIN_FREE_BLOCK_SIZE     4
// #define MIN_FREE_BLOCK_SIZE 16

/* ========================================================================
    structure definitions
   ======================================================================== */

typedef struct MemRegion MemRegion;

struct MemRegion
{
    void*       start;
    void*       end;
};

/* ========================================================================
    Macro Functions
   ======================================================================== */

#if defined(_DEBUG)

// For outputting warnings when checking the heap
#define HEAP_WARNING(exp, ...) \
            (void) ((exp) && (OSReport(__VA_ARGS__), 0))

// #if defined(_DEBUG)
#endif


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

/* ------------------------------------------------------------------------
    Pointer Operations
   ------------------------------------------------------------------------ */

/*---------------------------------------------------------------------------*
  Name:         MaxPtr_

  Description:  Gets the larger of two pointers' addresses.

  Arguments:    a, b:      Pointers to be compared

  Returns:      a:     If the a address is larger
                b:     if the b address is larger
 *---------------------------------------------------------------------------*/
static inline void*
MaxPtr_( void* a, void* b )
{
    return GetUIntPtr(a) > GetUIntPtr(b) ? a: b;
}

/*---------------------------------------------------------------------------*
  Name:         IsValidExpHeapHandle_

  Description:  Checks the signature to determine whether the expansion heap handle is valid.

  Arguments:    handle:    The heap handle

  Returns:      TRUE:      The heap handle is valid
                FALSE:     The heap handle is not valid
 *---------------------------------------------------------------------------*/
static inline BOOL
IsValidExpHeapHandle_( MEMHeapHandle handle )
{
    if ( handle == MEM_HEAP_INVALID_HANDLE )
    {
        return FALSE;
    }

    {
        MEMiHeapHead* pHeapHd = handle;
        return pHeapHd->signature == MEMi_EXPHEAP_SIGNATURE;
    }
}

/*---------------------------------------------------------------------------*
  Name:         GetExpHeapHeadPtrFromHeapHead_

  Description:  Gets the pointer to the expanded heap header from the pointer to the heap header.

  Arguments:    pHHead:    Pointer to the heap header.

  Returns:      Returns the pointer to the expanded heap header.
 *---------------------------------------------------------------------------*/
static inline MEMiExpHeapHead*
GetExpHeapHeadPtrFromHeapHead_( MEMiHeapHead* pHHead )
{
    return (MEMiExpHeapHead*)AddU32ToPtr( pHHead, sizeof(MEMiHeapHead) );
}

/*---------------------------------------------------------------------------*
  Name:         GetHeapHeadPtrFromExpHeapHead_

  Description:  Gets the pointer to the heap header from the pointer to the expanded heap header.

  Arguments:    pEHHead:    Pointer to the expanded heap header.

  Returns:      Returns the pointer to the heap header.
 *---------------------------------------------------------------------------*/
static inline MEMiHeapHead*
GetHeapHeadPtrFromExpHeapHead_( MEMiExpHeapHead* pEHHead )
{
    return (MEMiHeapHead*)SubU32ToPtr( pEHHead, sizeof(MEMiHeapHead) );
}

/*---------------------------------------------------------------------------*
  Name:         GetExpHeapHeadPtrFromHandle_

  Description:  Gets the pointer to the expanded heap header from the expanded heap handle.

  Arguments:    heap:    Expanded heap handle.

  Returns:      Returns the pointer to the expanded heap header.
 *---------------------------------------------------------------------------*/
static inline MEMiExpHeapHead*
GetExpHeapHeadPtrFromHandle_( MEMHeapHandle heap )
{
    return (MEMiExpHeapHead*)GetExpHeapHeadPtrFromHeapHead_( heap );
}

/*---------------------------------------------------------------------------*
  Name:         GetMemPtrForMBlock_

  Description:  Gets the pointer to the memory block from the pointer to the MEMiExpHeapMBlockHead structure.
                

  Arguments:    pMBlkHd:  Pointer to the MEMiExpHeapMBlockHead structure

  Returns:      Returns the pointer to the memory block.
 *---------------------------------------------------------------------------*/
static inline void*
GetMemPtrForMBlock_( MEMiExpHeapMBlockHead* pMBlkHd )
{
    return AddU32ToPtr( pMBlkHd, sizeof(MEMiExpHeapMBlockHead) );
}

static inline const void*
GetMemCPtrForMBlock_( const MEMiExpHeapMBlockHead* pMBlkHd )
{
    return AddU32ToCPtr( pMBlkHd, sizeof(MEMiExpHeapMBlockHead) );
}

/*---------------------------------------------------------------------------*
  Name:         GetMBlockHeadPtr_

  Description:  Gets the pointer to the MEMiExpHeapMBlockHead structure from the pointer to the memory block.
                
                Gets the pointer to the memory block.

  Arguments:    memBlock:    Pointer to the memory block.

  Returns:      Returns the pointer to the MEMiExpHeapMBlockHead structure.
 *---------------------------------------------------------------------------*/
static inline MEMiExpHeapMBlockHead*
GetMBlockHeadPtr_( void* memBlock )
{
    return (MEMiExpHeapMBlockHead*)SubU32ToPtr(memBlock, sizeof(MEMiExpHeapMBlockHead));
}

static inline const MEMiExpHeapMBlockHead*
GetMBlockHeadCPtr_( const void* memBlock )
{
    return (const MEMiExpHeapMBlockHead*)SubU32ToCPtr(memBlock, sizeof(MEMiExpHeapMBlockHead));
}

/*---------------------------------------------------------------------------*
  Name:         GetMBlockEndAddr_

  Description:  Gets the ending memory address from the pointer to the memory block.
                

  Arguments:    pMBHead:    Pointer to the MEMiExpHeapMBlockHead structure

  Returns:      Returns the terminal address of the memory block.
 *---------------------------------------------------------------------------*/
static inline void*
GetMBlockEndAddr_( MEMiExpHeapMBlockHead* pMBHead )
{
    return AddU32ToPtr( GetMemPtrForMBlock_(pMBHead), pMBHead->blockSize );
}

/* ------------------------------------------------------------------------
    MEMiExpHeapMBlockHead Structure Access Functions
   ------------------------------------------------------------------------ */

/*---------------------------------------------------------------------------*
  Name:         GetAlignmentForMBlock_

  Description:  Gets the alignment value for the MEMiExpHeapMBlockHead structure.

  Arguments:    pMBlkHd:    Pointer to the MEMiExpHeapMBlockHead structure

  Returns:      Returns the alignment value for the MEMiExpHeapMBlockHead structure.
 *---------------------------------------------------------------------------*/
static inline u16
GetAlignmentForMBlock_( const MEMiExpHeapMBlockHead* pMBlkHd )
{
    return pMBlkHd->attribute.fields.alignment;
}

/*---------------------------------------------------------------------------*
  Name:         SetAlignmentForMBlock_

  Description:  Sets the alignment value for the MEMiExpHeapMBlockHead structure.

  Arguments:    pMBlkHd:      Pointer to the MEMiExpHeapMBlockHead structure
                alignment:    Alignment value to be set

  Returns:      None.
 *---------------------------------------------------------------------------*/
static inline void
SetAlignmentForMBlock_(
    MEMiExpHeapMBlockHead*    pMBlkHd,
    u16                       alignment
)
{
    pMBlkHd->attribute.fields.alignment = alignment;
}


/*---------------------------------------------------------------------------*
  Name:         GetGroupIDForMBlock_

  Description:  Gets the group ID for the MEMiExpHeapMBlockHead structure.

  Arguments:    pMBlkHd:      Pointer to the MEMiExpHeapMBlockHead structure

  Returns:      Returns the group ID value.
 *---------------------------------------------------------------------------*/
static inline u16
GetGroupIDForMBlock_( const MEMiExpHeapMBlockHead* pMBHead )
{
    return pMBHead->attribute.fields.groupID;
}

/*---------------------------------------------------------------------------*
  Name:         SetGroupIDForMBlock_

  Description:  Sets the group ID for the MEMiExpHeapMBlockHead structure.

  Arguments:    pMBlkHd:      Pointer to the MEMiExpHeapMBlockHead structure
                id:           The group ID value to be set

  Returns:      None.
 *---------------------------------------------------------------------------*/
static inline void
SetGroupIDForMBlock_(
    MEMiExpHeapMBlockHead*    pMBHead,
    u16                       id
)
{
    pMBHead->attribute.fields.groupID = (u8)id;
}


/*---------------------------------------------------------------------------*
  Name:         GetAllocDirForMBlock_

  Description:  Gets the memory allocation direction for the MEMiExpHeapMBlockHead structure.

  Arguments:    pMBlkHd:      Pointer to the MEMiExpHeapMBlockHead structure

  Returns:      Returns the direction for memory allocation.
 *---------------------------------------------------------------------------*/
static inline u16
GetAllocDirForMBlock_( const MEMiExpHeapMBlockHead* pMBHead )
{
    return pMBHead->attribute.fields.allocDir;
}


/*---------------------------------------------------------------------------*
  Name:         SetAllocDirForMBlock_

  Description:  Sets the memory allocation direction for the MEMiExpHeapMBlockHead structure.

  Arguments:    pMBlkHd:      Pointer to the MEMiExpHeapMBlockHead structure
                mode:   the memory allocation direction to be set

  Returns:      None.
 *---------------------------------------------------------------------------*/
static inline void
SetAllocDirForMBlock_(
    MEMiExpHeapMBlockHead*    pMBHead,
    u16                       mode
)
{
    pMBHead->attribute.fields.allocDir = mode;
}


/* ------------------------------------------------------------------------
    MEMiExpHeapHead Structure Access Functions
   ------------------------------------------------------------------------ */

/*---------------------------------------------------------------------------*
  Name:         GetAllocMode_

  Description:  Gets the memory allocation mode for the expanded heap.

  Arguments:    pEHHead:    Pointer to the expanded heap header.

  Returns:      Returns the memory allocation mode for the expanded heap.
 *---------------------------------------------------------------------------*/
static inline u16
GetAllocMode_( MEMiExpHeapHead* pEHHead )
{
    return pEHHead->feature.fields.allocMode;
}

/*---------------------------------------------------------------------------*
  Name:         SetAllocMode_

  Description:  Sets the memory allocation mode for the expanded heap.

  Arguments:    pEHHead:    Pointer to the expanded heap header.
                mode:       Memory allocation mode.

  Returns:      None.
 *---------------------------------------------------------------------------*/
static inline void
SetAllocMode_(
    MEMiExpHeapHead*      pEHHead,
    u16                   mode
)
{
    pEHHead->feature.fields.allocMode = mode;
}


/*---------------------------------------------------------------------------*
  Name:         GetRegionOfMBlock_

  Description:  Generates the region data from the MEMiExpHeapMBlockHead structure.

  Arguments:    region:    Pointer to the region data to be generated
                block:     Pointer to the memory block header

  Returns:      None.
 *---------------------------------------------------------------------------*/
static void
GetRegionOfMBlock_(
    MemRegion*                region,
    MEMiExpHeapMBlockHead*    block
)
{
    region->start = SubU32ToPtr( block, GetAlignmentForMBlock_(block) );
    region->end   = GetMBlockEndAddr_(block);
}


/* ------------------------------------------------------------------------
    Memory Block List Operations
   ------------------------------------------------------------------------ */

/*---------------------------------------------------------------------------*
  Name:         RemoveMBlock_

  Description:  Deletes the specified memory block from the memory block list.

  Arguments:    list:      Pointer to the block list
                block:     Pointer to the memory block to be deleted

  Returns:      Pointer to the prior memory block
 *---------------------------------------------------------------------------*/
static MEMiExpHeapMBlockHead*
RemoveMBlock_(
    MEMiExpMBlockList*       list,
    MEMiExpHeapMBlockHead*   block
)
{
    MEMiExpHeapMBlockHead *const prev = block->pMBHeadPrev;
    MEMiExpHeapMBlockHead *const next = block->pMBHeadNext;
    
    // previous reference link
    if ( prev )
    {
        prev->pMBHeadNext = next;
    }
    else
    {
        list->head = next;
    }
    
    // next reference link
    if ( next )
    {
        next->pMBHeadPrev = prev;
    }
    else
    {
        list->tail = prev;
    }
    
    return prev;
}

/*---------------------------------------------------------------------------*
  Name:         InsertMBlock_

  Description:  Inserts a memory block into the memory block list.

  Arguments:    list:      Pointer to the memory block list
                target:    Pointer to the memory block to be inserted
                prev:      Pointer to the block at which the memory block will be inserted

  Returns:      Pointer to the target
 *---------------------------------------------------------------------------*/
static MEMiExpHeapMBlockHead*
InsertMBlock_(
    MEMiExpMBlockList*       list,
    MEMiExpHeapMBlockHead*   target,
    MEMiExpHeapMBlockHead*   prev
)
{
    MEMiExpHeapMBlockHead* next;

    // previous reference link
    target->pMBHeadPrev = prev;
    if ( prev )
    {
        next = prev->pMBHeadNext;
        prev->pMBHeadNext = target;
    }
    else
    {
        next = list->head;
        list->head = target;
    }

    // next reference link
    target->pMBHeadNext = next;
    if ( next )
    {
        next->pMBHeadPrev = target;
    }
    else
    {
        list->tail = target;
    }

    return target;
}

/*---------------------------------------------------------------------------*
  Name:         AppendMBlock_

  Description:  Adds a memory block to the end of the list.

  Arguments:    link:     The list to be added to
                block:    The memory block to add

  Returns:      None.
 *---------------------------------------------------------------------------*/
static inline void
AppendMBlock_(
    MEMiExpMBlockList*       list,
    MEMiExpHeapMBlockHead*   block
)
{
    (void)InsertMBlock_( list, block, list->tail );
}

/*---------------------------------------------------------------------------*
  Name:         InitMBlock_

  Description:  Initializes the memory block.

  Arguments:    pRegion:      Pointer to the structure representing the region used for the memory block.
                signature:    Memory block signature

  Returns:      Returns the pointer to the initialized memory block.
 *---------------------------------------------------------------------------*/
static MEMiExpHeapMBlockHead*
InitMBlock_(
    MemRegion*              pRegion,
    u16                     signature
)
{
    MEMiExpHeapMBlockHead* block = (MEMiExpHeapMBlockHead*)pRegion->start;
    
    block->signature = signature;   /* embeds the signature */
    block->attribute.val = 0;       /* clears the attribute parameters */
    
    // sets the size from the memory block's starting position to the next region as blockSize
    block->blockSize = GetOffsetFromPtr( GetMemPtrForMBlock_(block), pRegion->end );
    
    block->pMBHeadPrev = NULL;
    block->pMBHeadNext = NULL;
    
    return block;
}

/*---------------------------------------------------------------------------*
  Name:         InitFreeMBlock_

  Description:  Initializes the memory block for use as a free block.

  Arguments:    pRegion:      Pointer to the structure representing the region used for the memory block.

  Returns:      Returns the pointer to the initialized memory block.
 *---------------------------------------------------------------------------*/
static inline MEMiExpHeapMBlockHead*
InitFreeMBlock_( MemRegion* pRegion )
{
    return InitMBlock_( pRegion, MBLOCK_FREE_SIGNATURE );
}

/*---------------------------------------------------------------------------*
  Name:         InitExpHeap_

  Description:  Initializes the expanded heap.

  Arguments:    startAddress:    Memory start address for the expanded heap.
                endAddress:      The memory terminal address for the expanded heap incremented by one.
                optFlag:         Option flag.

  Returns:      Returns the pointer to the heap header.
 *---------------------------------------------------------------------------*/
static MEMiHeapHead*
InitExpHeap_(
    void*   startAddress,
    void*   endAddress,
    u16     optFlag
)
{
    MEMiHeapHead*    pHeapHd    = (MEMiHeapHead*)startAddress;
    MEMiExpHeapHead* pExpHeapHd = GetExpHeapHeadPtrFromHeapHead_( pHeapHd );

    MEMiInitHeapHead(           // Heap common initialization
        pHeapHd,
        MEMi_EXPHEAP_SIGNATURE,
        AddU32ToPtr( pExpHeapHd, sizeof(MEMiExpHeapHead) ),    // heapStart
        endAddress,                                            // heapEnd
        optFlag );

    pExpHeapHd->groupID = DEFAULT_GROUPID;      // Group ID
    pExpHeapHd->feature.val = 0;
    SetAllocMode_( pExpHeapHd, DEFAULT_ALLOC_MODE );

    // Creates a free block
    {
        MEMiExpHeapMBlockHead* pMBHead;
        MemRegion region;
        
        region.start = pHeapHd->heapStart;
        region.end   = pHeapHd->heapEnd;
        pMBHead = InitFreeMBlock_( &region );
        
        // Block list
        pExpHeapHd->mbFreeList.head = pMBHead;
        pExpHeapHd->mbFreeList.tail = pMBHead;
        pExpHeapHd->mbUsedList.head = NULL;
        pExpHeapHd->mbUsedList.tail = NULL;

        return pHeapHd;
    }
}

/*---------------------------------------------------------------------------*
  Name:         AllocUsedBlockFromFreeBlock_

  Description:  Allocates a new memory block from the free blocks.

  Arguments:    pEHHead:      Pointer to the expanded heap header.
                pMBHeadFree:  Pointer to the free block header.
                mblock:       Address for the memory block to be allocated.
                size:         Size of the memory block to be allocated.
                direction:    Allocation direction.

  Returns:      Returns a pointer to the top of the allocated memory block.
 *---------------------------------------------------------------------------*/
static void*
AllocUsedBlockFromFreeBlock_(
    MEMiExpHeapHead*          pEHHead,
    MEMiExpHeapMBlockHead*    pMBHeadFree,
    void*                     mblock,
    u32                       size,
    u16                       direction
)
{
    MemRegion freeRgnT;
    MemRegion freeRgnB;
    MEMiExpHeapMBlockHead* pMBHeadFreePrev;

    GetRegionOfMBlock_( &freeRgnT, pMBHeadFree );
    freeRgnB.end   = freeRgnT.end;
    freeRgnB.start = AddU32ToPtr( mblock, size );
    freeRgnT.end   = SubU32ToPtr( mblock, sizeof(MEMiExpHeapMBlockHead) );

    pMBHeadFreePrev = RemoveMBlock_( &pEHHead->mbFreeList, pMBHeadFree );  // Deletes the free block for the time being

    // If there is no space for creating a free block
    if ( GetOffsetFromPtr(freeRgnT.start, freeRgnT.end) < sizeof(MEMiExpHeapMBlockHead) + MIN_FREE_BLOCK_SIZE )
    {
        freeRgnT.end = freeRgnT.start;  // Includes the alignment value for the block being used
    }
    else
    {
        pMBHeadFreePrev = InsertMBlock_( &pEHHead->mbFreeList, InitFreeMBlock_(&freeRgnT), pMBHeadFreePrev );
    }

    // If there is no space for creating a free block
    if ( GetOffsetFromPtr(freeRgnB.start, freeRgnB.end) < sizeof(MEMiExpHeapMBlockHead) + MIN_FREE_BLOCK_SIZE )
    {
        freeRgnB.start= freeRgnB.end;   // Includes the block being used
    }
    else
    {
        (void)InsertMBlock_( &pEHHead->mbFreeList, InitFreeMBlock_(&freeRgnB), pMBHeadFreePrev );
    }

    // Fills the memory for debugging
    FillAllocMemory( 
            GetHeapHeadPtrFromExpHeapHead_(pEHHead), 
            freeRgnT.end, 
            GetOffsetFromPtr(freeRgnT.end, freeRgnB.start) 
    );

    // Creates a new block
    {
        MEMiExpHeapMBlockHead* pMBHeadNewUsed;
        MemRegion region;
        
        region.start = SubU32ToPtr( mblock, sizeof(MEMiExpHeapMBlockHead) );
        region.end   = freeRgnB.start;
        
        pMBHeadNewUsed = InitMBlock_(&region, MBLOCK_USED_SIGNATURE );
        SetAllocDirForMBlock_( pMBHeadNewUsed, direction );
        SetAlignmentForMBlock_( pMBHeadNewUsed, (u16)GetOffsetFromPtr(freeRgnT.end, pMBHeadNewUsed) );
        SetGroupIDForMBlock_( pMBHeadNewUsed, pEHHead->groupID );
        AppendMBlock_( &pEHHead->mbUsedList, pMBHeadNewUsed );
    }
    
    return mblock;
}

/*---------------------------------------------------------------------------*
  Name:         AllocFromHead_

  Description:  Allocates the memory block from the top of the heap.

  Arguments:    pHeapHd:    Pointer to the heap header.
                size:       Size of the memory block to be allocated.
                alignment:  Alignment value.

  Returns:      Returns the pointer to the allocated memory block if the memory block was successfully allocated.
                
                If the operation fails, NULL is returned.
 *---------------------------------------------------------------------------*/
static void*
AllocFromHead_(
    MEMiHeapHead*   pHeapHd,
    u32             size,
    int             alignment
)
{
    MEMiExpHeapHead* pExpHeapHd = GetExpHeapHeadPtrFromHeapHead_(pHeapHd);

    // Allocate the first one found?
    const BOOL bAllocFirst = GetAllocMode_(pExpHeapHd) == MEM_EXPHEAP_ALLOC_MODE_FIRST;

    MEMiExpHeapMBlockHead* pMBlkHd      = NULL;
    MEMiExpHeapMBlockHead* pMBlkHdFound = NULL;
    u32 foundSize = 0xffffffff;
    void* foundMBlock = NULL;

    // Search for free block
    for ( pMBlkHd = pExpHeapHd->mbFreeList.head; pMBlkHd; pMBlkHd = pMBlkHd->pMBHeadNext )
    {
        void *const mblock    = GetMemPtrForMBlock_(pMBlkHd);
        void *const reqMBlock = RoundUpPtr( mblock, alignment );
        const u32 offset      = GetOffsetFromPtr( mblock, reqMBlock );    // Generated offset

        if ( pMBlkHd->blockSize >= size + offset
             &&  foundSize > pMBlkHd->blockSize )
        {
            pMBlkHdFound  = pMBlkHd;
            foundSize     = pMBlkHd->blockSize;
            foundMBlock   = reqMBlock;

            if ( bAllocFirst || foundSize == size )
            {
                break;
            }
        }
    }

    if ( ! pMBlkHdFound ) // No blocks matching the conditions were found
    {
        return NULL;
    }

    return AllocUsedBlockFromFreeBlock_( // Allocates a region from the free block that was found
                    pExpHeapHd,
                    pMBlkHdFound,
                    foundMBlock,
                    size,
                    MEM_EXPHEAP_ALLOC_DIR_FRONT 
           );
}

/*---------------------------------------------------------------------------*
  Name:         AllocFromTail_

  Description:  Allocates a memory block from the end of the heap.

  Arguments:    pHeapHd:    Pointer to the heap header.
                size:       Size of the memory block to be allocated.
                alignment:  Alignment value.

  Returns:      Returns the pointer to the allocated memory block if the memory block was successfully allocated.
                
                If the operation fails, NULL is returned.
 *---------------------------------------------------------------------------*/
static void*
AllocFromTail_(
    MEMiHeapHead*   pHeapHd,
    u32             size,
    int             alignment
)
{
    MEMiExpHeapHead* pExpHeapHd = GetExpHeapHeadPtrFromHeapHead_(pHeapHd);

    // Allocate the first one found?
    const BOOL bAllocFirst = GetAllocMode_(pExpHeapHd) == MEM_EXPHEAP_ALLOC_MODE_FIRST;

    MEMiExpHeapMBlockHead* pMBlkHd      = NULL;
    MEMiExpHeapMBlockHead* pMBlkHdFound = NULL;
    u32 foundSize = 0xffffffff;
    void* foundMBlock = NULL;

    // Search for free block
    for ( pMBlkHd = pExpHeapHd->mbFreeList.tail; pMBlkHd; pMBlkHd = pMBlkHd->pMBHeadPrev )
    {
        void *const mblock    = GetMemPtrForMBlock_(pMBlkHd);
        void *const mblockEnd = AddU32ToPtr( mblock, pMBlkHd->blockSize );
        void *const reqMBlock = RoundDownPtr( SubU32ToPtr(mblockEnd, size), alignment );  // Aligned address
        
        if ( ComparePtr( reqMBlock, mblock ) >= 0
             &&  foundSize > pMBlkHd->blockSize )
        {
            pMBlkHdFound = pMBlkHd;
            foundSize    = pMBlkHd->blockSize;
            foundMBlock  = reqMBlock;
            
            if ( bAllocFirst || foundSize == size )
            {
                break;
            }
        }
    }

    if ( ! pMBlkHdFound ) // No blocks matching the conditions were found
    {
        return NULL;
    }

    return AllocUsedBlockFromFreeBlock_( // Allocates a region from the free block that was found
                    pExpHeapHd,
                    pMBlkHdFound,
                    foundMBlock,
                    size,
                    MEM_EXPHEAP_ALLOC_DIR_REAR 
           );
}

/*---------------------------------------------------------------------------*
  Name:         RecycleRegion_

  Description:  Inserts an empty region in the free memory block.
                If it is adjacent to the free block it expands the free block.
                If there is no adjacent block, or the block is not large enough to be used as a free block, the alignment value of the used block adjacent to the end of the memory space is used.
                
                If there is no used block next to the end of the free block the function fails.

  Arguments:    pEHHead:  Pointer to the expanded heap header.
                pRegion:  Pointer to the free region.

  Returns:      Returns TRUE if the function is successful.
                Returns FALSE if it fails.
 *---------------------------------------------------------------------------*/
static BOOL
RecycleRegion_(
    MEMiExpHeapHead*    pEHHead,
    const MemRegion*    pRegion
)
{
    MEMiExpHeapMBlockHead* pBlkPrFree  = NULL;   // Immediately preceding free block
    MemRegion freeRgn = *pRegion;

    // Searches for free area next to the specified one.
    {
        MEMiExpHeapMBlockHead* pBlk;

        for ( pBlk = pEHHead->mbFreeList.head; pBlk; pBlk = pBlk->pMBHeadNext )
        {
            if ( pBlk < pRegion->start )
            {
                pBlkPrFree = pBlk;
                continue;
            }

            if ( pBlk == pRegion->end )   // Is the block next to the end?
            {
                // Combines the available regions
                freeRgn.end = GetMBlockEndAddr_(pBlk);
                (void)RemoveMBlock_( &pEHHead->mbFreeList, pBlk );

                // Pads the header with NoUse
                FillNoUseMemory( GetHeapHeadPtrFromExpHeapHead_(pEHHead), pBlk, sizeof(MEMiExpHeapMBlockHead) );
            }
            break;
        }
    }

    // Is the immediately preceding free block adjacent to the front?
    if ( pBlkPrFree && GetMBlockEndAddr_(pBlkPrFree) == pRegion->start )
    {
        // Combines the available regions
        freeRgn.start = pBlkPrFree;
        pBlkPrFree = RemoveMBlock_(&pEHHead->mbFreeList, pBlkPrFree);
    }

    if ( GetOffsetFromPtr(freeRgn.start, freeRgn.end) < sizeof(MEMiExpHeapMBlockHead) ) // Size not suitable for use as a block
    {
        return FALSE;   // Control reaches this point if an attempt is made to shrink a small-size block using ResizeForMBlockExpHeap() and if there are no free blocks at the end
                        // 
    }

    // Fills the memory for debugging
    FillFreeMemory( GetHeapHeadPtrFromExpHeapHead_(pEHHead), pRegion->start, GetOffsetFromPtr(pRegion->start, pRegion->end) );

    (void)InsertMBlock_(
                &pEHHead->mbFreeList,
                InitFreeMBlock_(&freeRgn),   // Creates the free block
                pBlkPrFree
          );

    return TRUE;
}





/* ========================================================================
    operation checking functions
   ======================================================================== */
#if defined(_DEBUG)

/*---------------------------------------------------------------------------*
  Name:         CheckMBlock_

  Description:  Checks whether the header contents for the memory block are appropriate.

  Arguments:    pMBHead:    Pointer to the header for the memory block to be checked.
                pHeapHd:    Pointer to the expanded heap header.
                signature:  Memory block signature
                heapType:   Memory block type (used or free)
                flag:       Flag.

  Returns:      Returns TRUE if the header contents for the memory block are appropriate, and FALSE otherwise.
                
 *---------------------------------------------------------------------------*/
static BOOL
CheckMBlock_(
    const MEMiExpHeapMBlockHead*    pMBHead,
    MEMiHeapHead*                   pHeapHd,
    u16                             signature,
    const char*                     heapType,
    u32                             flag
)
{
    const BOOL bPrint = ( 0 != (flag & MEM_HEAP_ERROR_PRINT) );
    const void *const memBlock = GetMemCPtrForMBlock_(pMBHead);

    if ( pHeapHd )
    {
        if ( GetUIntPtr(pMBHead) < GetUIntPtr(pHeapHd->heapStart)
             || GetUIntPtr(memBlock) > GetUIntPtr(pHeapHd->heapEnd)
        )
        {
            HEAP_WARNING(bPrint, "[OS Foundation " "Exp" " Heap]" " Bad %s memory block address. - address %08X, heap area [%08X - %08X)\n",
                         heapType, memBlock, pHeapHd->heapStart, pHeapHd->heapEnd);
            return FALSE;
        }
    }
    else
    {
        if ( GetUIntPtr(pMBHead) < 0x80000000 )
        {
            HEAP_WARNING(bPrint, "[OS Foundation " "Exp" " Heap]" " Bad %s memory block address. - address %08X\n",
                         heapType, memBlock);
            return FALSE;
        }
    }

    if ( pMBHead->signature != signature )    // Is the signature different?
    {
        HEAP_WARNING(bPrint, "[OS Foundation " "Exp" " Heap]" " Bad %s memory block signature. - address %08X, signature %04X\n",
                     heapType, memBlock, pMBHead->signature);
        return FALSE;
    }

    if ( pMBHead->blockSize >= 0x08000000 )   // Size too big? (128MB or more)
    {
        HEAP_WARNING(bPrint, "[OS Foundation " "Exp" " Heap]" " Too large %s memory block. - address %08X, block size %08X\n",
                     heapType, memBlock, pMBHead->blockSize);
        return FALSE;
    }

    if ( pHeapHd )
    {
        if ( GetUIntPtr(memBlock) + pMBHead->blockSize > GetUIntPtr(pHeapHd->heapEnd) )
        {
            HEAP_WARNING(bPrint, "[OS Foundation " "Exp" " Heap]" " wrong size %s memory block. - address %08X, block size %08X\n",
                         heapType, memBlock, pMBHead->blockSize);
            return FALSE;
        }
    }

    return TRUE;
}


/*---------------------------------------------------------------------------*
  Name:         CheckUsedMBlock_

  Description:  Checks whether the header contents for the memory block being used are appropriate.

  Arguments:    pMBHead:    Pointer to the header for the memory block to be checked.
                pHeapHd:   Pointer to the expanded heap header.
                flag:   Flag.

  Returns:      Returns TRUE if the header contents for the memory block are appropriate, and FALSE otherwise.
                
 *---------------------------------------------------------------------------*/
static inline BOOL
CheckUsedMBlock_(
    const MEMiExpHeapMBlockHead*    pMBHead,
    MEMiHeapHead*                   pHeapHd,
    u32                             flag
)
{
    if ( pHeapHd )
    {
        MEMiExpHeapHead* pExpHeapHd = GetExpHeapHeadPtrFromHeapHead_(pHeapHd);
        MEMiExpHeapMBlockHead* pMBlkHd      = NULL;
        for ( pMBlkHd = pExpHeapHd->mbUsedList.head; pMBlkHd; pMBlkHd = pMBlkHd->pMBHeadNext )
        {
            if ( pMBHead == pMBlkHd )
            {
                break;
            }
        }
        if ( pMBlkHd == NULL )
        {
            return FALSE;
        }
    }
    return CheckMBlock_( pMBHead, pHeapHd, MBLOCK_USED_SIGNATURE, "used", flag );
}

/*---------------------------------------------------------------------------*
  Name:         CheckFreeMBlock_

  Description:  Checks whether the header contents for the free memory block are appropriate.

  Arguments:    pMBHead:  Pointer to the header for the memory block to be checked.
                pHeapHd:  Pointer to the expanded heap header.
                flag:     Flag.

  Returns:      Returns TRUE if the header contents for the memory block are appropriate, and FALSE otherwise.
                
 *---------------------------------------------------------------------------*/
static inline BOOL
CheckFreeMBlock_(
    const MEMiExpHeapMBlockHead*    pMBHead,
    MEMiHeapHead*                   pHeapHd,
    u32                             flag
)
{
    return CheckMBlock_( pMBHead, pHeapHd, MBLOCK_FREE_SIGNATURE, "free", flag );
}


/*---------------------------------------------------------------------------*
  Name:         CheckMBlockPrevPtr_

  Description:  Checks whether the link to the previous memory block is correct.

  Arguments:    pMBHead:      Pointer to the header for the memory block to be checked.
                pMBHeadPrev:  Pointer to the header for the memory block before the one to be checked.
                flag:         Flag.

  Returns:      Returns TRUE if the link to the previous memory block is correct, and FALSE otherwise.
                
 *---------------------------------------------------------------------------*/
static BOOL
CheckMBlockPrevPtr_(
    const MEMiExpHeapMBlockHead*    pMBHead,
    const MEMiExpHeapMBlockHead*    pMBHeadPrev,
    u32                             flag
)
{
    const BOOL bPrint = ( 0 != (flag & MEM_HEAP_ERROR_PRINT) );

    if ( pMBHead->pMBHeadPrev != pMBHeadPrev )
    {
        HEAP_WARNING(bPrint, "[OS Foundation " "Exp" " Heap]" " Wrong link memory block. - address %08X, previous address %08X != %08X\n",
                     GetMemCPtrForMBlock_(pMBHead), pMBHead->pMBHeadPrev, pMBHeadPrev);
        return FALSE;
    }

    return TRUE;
}


/*---------------------------------------------------------------------------*
  Name:         CheckMBlockNextPtr_

  Description:  Checks whether the link to the next memory block is correct.

  Arguments:    pMBHead:      Pointer to the header for the memory block to be checked.
                pMBHeadNext:  Pointer to the header for the memory block after the one to be checked.
                flag:         Flag.

  Returns:      Returns TRUE if the link to the next memory block is correct, and FALSE otherwise.
                
 *---------------------------------------------------------------------------*/
static BOOL
CheckMBlockNextPtr_(
    const MEMiExpHeapMBlockHead*   pMBHead,
    const MEMiExpHeapMBlockHead*   pMBHeadNext,
    u32                            flag
)
{
    const BOOL bPrint = ( 0 != (flag & MEM_HEAP_ERROR_PRINT) );

    if (pMBHead->pMBHeadNext != pMBHeadNext)
    {
        HEAP_WARNING(bPrint, "[OS Foundation " "Exp" " Heap]" " Wrong link memory block. - address %08X, next address %08X != %08X\n",
                     GetMemCPtrForMBlock_(pMBHead), pMBHead->pMBHeadNext, pMBHeadNext);
        return FALSE;
    }

    return TRUE;
}


/*---------------------------------------------------------------------------*
  Name:         CheckMBlockLinkTail_

  Description:  Checks whether the memory block pointer is at the head or tail of the memory block list.

  Arguments:    pMBHead:      Pointer to the header for the memory block to be checked.
                pMBHeadTail:  Pointer to the memory block at the head or tail of the memory block list.
                headType:     String indicating the head or tail.
                flag:         Flag.

  Returns:      Returns TRUE if the pointer to the memory block is at the head or tail of the memory block list, and FALSE otherwise.
                
 *---------------------------------------------------------------------------*/
static BOOL
CheckMBlockLinkTail_(
    const MEMiExpHeapMBlockHead*    pMBHead,
    const MEMiExpHeapMBlockHead*    pMBHeadTail,
    const char*                     heapType,
    u32                             flag
)
{
    const BOOL bPrint = 0 != (flag & MEM_HEAP_ERROR_PRINT);

    if ( pMBHead != pMBHeadTail )
    {
        HEAP_WARNING(bPrint, "[OS Foundation " "Exp" " Heap]" " Wrong memory brock list %s pointer. - address %08X, %s address %08X != %08X\n",
                     heapType, GetMemCPtrForMBlock_(pMBHead), heapType, pMBHead, pMBHeadTail);
        return FALSE;
    }

    return TRUE;
}


/*---------------------------------------------------------------------------*
  Name:         IsValidUsedMBlock_

  Description:  Checks whether the memory block being used is appropriate.

  Arguments:    memBlock:  The memory block to be checked.
                heap:      The handle for the expanded heap containing the memory block.
                           If NULL is specified, no check is run to see whether the memory block is included in the heap.
                           

  Returns:      Returns TRUE if there is no problem with the specified memory block.
                Returns FALSE if there is a problem.
 *---------------------------------------------------------------------------*/
static BOOL
IsValidUsedMBlock_(
    const void*       memBlock,
    MEMHeapHandle     heap
)
{
    MEMiHeapHead* pHeapHd = heap;

    if ( ! memBlock)
    {
        return FALSE;
    }

    return CheckUsedMBlock_(GetMBlockHeadCPtr_(memBlock), pHeapHd, 0);
}

// #if defined(_DEBUG)
#endif



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

/*---------------------------------------------------------------------------*
  Name:         MEMiDumpExpHeap

  Description:  Shows internal expanded heap information.
                This function is used for debugging.

  Arguments:    heap:    Handle for expanded heap

  Returns:      None.
 *---------------------------------------------------------------------------*/
#if defined(_DEBUG)

void
MEMiDumpExpHeap( MEMHeapHandle heap )
{
    ASSERT(IsValidExpHeapHandle_(heap));
    
    {
        u32  usedSize = 0;
        u32  usedCnt = 0;
        u32  freeSize = 0;
        u32  freeCnt = 0;

        MEMiHeapHead* pHeapHd = heap;
        MEMiExpHeapHead* pExpHeapHd = GetExpHeapHeadPtrFromHandle_(pHeapHd);

        MEMiDumpHeapHead(pHeapHd);

        OSReport("     attr  address:   size    gid aln   prev_ptr next_ptr\n");   // Header line

        // ---------------- UsedBlock Dump ----------------
        OSReport("    (Used Blocks)\n" );

        if ( pExpHeapHd->mbUsedList.head == NULL )
        {
            OSReport("     NONE\n");
        }
        else
        {
            MEMiExpHeapMBlockHead* pMBHead;

            for ( pMBHead = pExpHeapHd->mbUsedList.head; pMBHead; pMBHead = pMBHead->pMBHeadNext )
            {
                if ( pMBHead->signature != MBLOCK_USED_SIGNATURE )
                {
                    OSReport("    xxxxx %08x: --------  --- ---  (-------- --------)\nabort\n", pMBHead);
                    break;
                }

                OSReport("    %s %08x: %8d  %3d %3d  (%08x %08x)\n",
                    GetAllocDirForMBlock_(pMBHead) == MEM_EXPHEAP_ALLOC_DIR_REAR ? " rear" : "front",
                    GetMemPtrForMBlock_(pMBHead),
                    pMBHead->blockSize,
                    GetGroupIDForMBlock_( pMBHead ),
                    GetAlignmentForMBlock_( pMBHead ),
                    pMBHead->pMBHeadPrev ? GetMemPtrForMBlock_(pMBHead->pMBHeadPrev): NULL,
                    pMBHead->pMBHeadNext ? GetMemPtrForMBlock_(pMBHead->pMBHeadNext): NULL
                );

                // ---- Amount Used
                usedSize += sizeof(MEMiExpHeapMBlockHead) + pMBHead->blockSize + GetAlignmentForMBlock_(pMBHead);

                usedCnt ++;
            }
        }

        // ---------------- FreeBlock Dump ----------------
        OSReport("    (Free Blocks)\n" );

        if ( pExpHeapHd->mbFreeList.head == NULL )
        {
            OSReport("     NONE\n" );
        }
        else
        {
            MEMiExpHeapMBlockHead* pMBHead;

            for ( pMBHead = pExpHeapHd->mbFreeList.head; pMBHead; pMBHead = pMBHead->pMBHeadNext )
            {
                if ( pMBHead->signature != MBLOCK_FREE_SIGNATURE )
                {
                    OSReport("    xxxxx %08x: --------  --- ---  (-------- --------)\nabort\n", pMBHead);
                    break;
                }

                OSReport("    %s %08x: %8d  %3d %3d  (%08x %08x)\n",
                    " free",
                    GetMemPtrForMBlock_(pMBHead),
                    pMBHead->blockSize,
                    GetGroupIDForMBlock_( pMBHead ),
                    GetAlignmentForMBlock_( pMBHead ),
                    pMBHead->pMBHeadPrev ? GetMemPtrForMBlock_(pMBHead->pMBHeadPrev): NULL,
                    pMBHead->pMBHeadNext ? GetMemPtrForMBlock_(pMBHead->pMBHeadNext): NULL
                );

                freeCnt ++;
            }
        }

        OSReport("\n");

        {
            u32 heapSize  = GetOffsetFromPtr(pHeapHd->heapStart, pHeapHd->heapEnd); // Heap size (data region size)
            OSReport("    %d / %d bytes (%6.2f%%) used (U:%d F:%d)\n",
                               usedSize, heapSize, 100.0 * usedSize / heapSize, usedCnt, freeCnt);
        }

        OSReport("\n");
    }
}

// #if defined(_DEBUG)
#endif



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

/*---------------------------------------------------------------------------*
  Name:         MEMCreateExpHeapEx

  Description:  Creates an expanded heap.

  Arguments:    startAddress: Start address of heap area
                size:         Size of heap area
                optFlag:      Option flag.

  Returns:      If the function succeeds, a handle for the created expanded heap is returned.
                If the function fails, MEM_HEAP_INVALID_HANDLE is returned.
 *---------------------------------------------------------------------------*/
MEMHeapHandle
MEMCreateExpHeapEx(
    void*   startAddress,
    u32     size,
    u16     optFlag
)
{
    void* endAddress;

    ASSERT(startAddress != NULL);

    endAddress   = RoundDownPtr(AddU32ToPtr(startAddress, size), MIN_ALIGNMENT);
    startAddress = RoundUpPtr(startAddress, MIN_ALIGNMENT);

    if ( GetUIntPtr(startAddress) > GetUIntPtr(endAddress)
         ||  GetOffsetFromPtr(startAddress, endAddress) < 
                    sizeof(MEMiHeapHead) + sizeof(MEMiExpHeapHead) + sizeof(MEMiExpHeapMBlockHead) + MIN_ALIGNMENT
    )
    {
        return MEM_HEAP_INVALID_HANDLE;
    }

    {   // Initialization for the Expanded heap
        MEMiHeapHead* pHeapHd = InitExpHeap_( startAddress, endAddress, optFlag );
        return pHeapHd;  // The pointer to the heap header is used as the handle value.
    }
}

/*---------------------------------------------------------------------------*
  Name:         MEMDestroyExpHeap

  Description:  Destroys the expanded heap.

  Arguments:    heap:   Handle for expanded heap

  Returns:      Returns a pointer to the region occupied by the destroyed heap.
 *---------------------------------------------------------------------------*/
void*
MEMDestroyExpHeap( MEMHeapHandle heap )
{
    ASSERT( IsValidExpHeapHandle_(heap) );

    MEMiFinalizeHeap( heap );
    return (void*)heap;
}

/*---------------------------------------------------------------------------*
  Name:         MEMAllocFromExpHeapEx

  Description:  Allocates a memory block from the expanded heap.
                The memory block alignment can be specified.
                If a negative alignment value is specified, an available region is searched for from the back of the heap.

  Arguments:    heap:      Handle for expanded heap
                size:      Size of the memory block to be allocated (in bytes)
                alignment: Alignment of the memory block to be allocated
                           The following values can be specified: + or - 4, + or - 8, + or - 16, + or - 32, + or - 64, + or - 128, ...

  Returns:      Returns the pointer to the allocated memory block if the memory block was successfully allocated.
                
                If the operation fails, NULL is returned.
 *---------------------------------------------------------------------------*/
void*
MEMAllocFromExpHeapEx(
    MEMHeapHandle   heap,
    u32             size,
    int             alignment
)
{
    void* memory = NULL;

    ASSERT( IsValidExpHeapHandle_(heap) );

    // alignment check
    ASSERT(alignment % MIN_ALIGNMENT == 0);
    ASSERT((abs(alignment) & (abs(alignment) - 1)) == 0);
    ASSERT(MIN_ALIGNMENT <= abs(alignment));

    if ( size == 0 )
    {
        size = 1;
    }
    
    size = RoundUp( size, MIN_ALIGNMENT );    // The size actually allocated
    
    LockHeap( heap );
    
    if ( alignment >= 0 )     // Allocates from the front
    {
        memory = AllocFromHead_( heap, size, alignment );
    }
    else                    // Allocates from the back
    {
        memory = AllocFromTail_( heap, size, -alignment );
    }
    
    UnlockHeap( heap );
    
    return memory;
}

/*---------------------------------------------------------------------------*
  Name:         MEMResizeForMBlockExpHeap

  Description:  Changes the size of the memory block allocated from the expanded heap.

  Arguments:    heap:     Handle for expanded heap
                memBlock: Pointer to the memory block to be resized.
                size:     The new size to be allocated (in bytes).

  Returns:      Returns the size of the resized memory block (in bytes) if the function is successful.
                Returns 0 if the function fails.
 *---------------------------------------------------------------------------*/
u32
MEMResizeForMBlockExpHeap(
    MEMHeapHandle   heap,
    void*           memBlock,
    u32             size
)
{
    MEMiExpHeapHead       *pEHHead;
    MEMiExpHeapMBlockHead *pMBHead;
    
    ASSERT(IsValidExpHeapHandle_(heap));
    ASSERT(IsValidUsedMBlock_(memBlock, heap));
    
    pEHHead = GetExpHeapHeadPtrFromHandle_(heap);
    pMBHead = GetMBlockHeadPtr_(memBlock);
    
    size = RoundUp( size, MIN_ALIGNMENT );
    if ( size == pMBHead->blockSize )  // If the block size is not changed
    {
        return size;
    }
    
    LockHeap( heap );
    
    // For expanding the new area
    if ( size > pMBHead->blockSize )
    {
        void* crUsedEnd = GetMBlockEndAddr_(pMBHead);   // The end address for the block currently being used
        MEMiExpHeapMBlockHead* block;
        
        // Searches for the next free block
        for ( block = pEHHead->mbFreeList.head; block; block = block->pMBHeadNext )
        {
            if ( block == crUsedEnd )
            {
                break;
            }
        }
        
        // There is no next free block or the size is inadequate
        if ( ! block || size > pMBHead->blockSize + sizeof(MEMiExpHeapMBlockHead) + block->blockSize)
        {
            UnlockHeap( heap );
            return 0;
        }
        
        {
            MemRegion         rgnNewFree;
            void              *oldFreeStart;
            MEMiExpHeapMBlockHead *nextBlockPrev;
            
            // Gets the free block region and temporarily removes the free block
            GetRegionOfMBlock_( &rgnNewFree, block );
            nextBlockPrev = RemoveMBlock_( &pEHHead->mbFreeList, block );
            
            oldFreeStart = rgnNewFree.start;
            rgnNewFree.start = AddU32ToPtr( memBlock, size ); // The region position to be newly freed
            
            // If the remainder is smaller than the memory block size
            if ( GetOffsetFromPtr(rgnNewFree.start, rgnNewFree.end) < sizeof(MEMiExpHeapMBlockHead) )
            {
                rgnNewFree.start = rgnNewFree.end;  // It is absorbed into the block being used
            }
            
            pMBHead->blockSize = GetOffsetFromPtr(memBlock, rgnNewFree.start);  // Changes the target block size
            
            // If the remainder is equal to or larger than the memory block size
            if ( GetOffsetFromPtr(rgnNewFree.start, rgnNewFree.end) >= sizeof(MEMiExpHeapMBlockHead) )
            {
                (void)InsertMBlock_(&pEHHead->mbFreeList, InitFreeMBlock_(&rgnNewFree), nextBlockPrev);   // Creates a new free block
            }
            
            FillAllocMemory(  // Extended partial fill
                heap,
                oldFreeStart,
                GetOffsetFromPtr(oldFreeStart, rgnNewFree.start));
        }
    }
    // When shrinking the new area
    else
    {
        MemRegion rgnNewFree;
        const u32 oldBlockSize = pMBHead->blockSize;
        
        rgnNewFree.start = AddU32ToPtr(memBlock, size); // The region position to be newly freed
        rgnNewFree.end   = GetMBlockEndAddr_(pMBHead);   // The end address for the block currently being used
        
        pMBHead->blockSize = size;  // Changes the target block size
        
        if ( ! RecycleRegion_(pEHHead, &rgnNewFree) )    // Tries returning the free list
        {
            pMBHead->blockSize = oldBlockSize;  // Restores to original form if failed
        }
    }
    
    UnlockHeap( heap );
    
    return pMBHead->blockSize;
}

/*---------------------------------------------------------------------------*
  Name:         MEMFreeToExpHeap

  Description:  Returns the memory block to the expanded heap.

  Arguments:    heap:     Handle for expanded heap
                memBlock: Pointer to the memory block to be returned.

  Returns:      None.
 *---------------------------------------------------------------------------*/
void
MEMFreeToExpHeap(
    MEMHeapHandle   heap,
    void*           memBlock
)
{
    ASSERT(IsValidExpHeapHandle_(heap));
    if ( memBlock == NULL )
    {
        return;
    }
    
    ASSERT(IsValidUsedMBlock_(memBlock, heap));
    
    {
        MEMiHeapHead          *pHeapHd    = heap;
        MEMiExpHeapHead       *pExpHeapHd = GetExpHeapHeadPtrFromHandle_( pHeapHd );
        MEMiExpHeapMBlockHead *pMBHead    = GetMBlockHeadPtr_( memBlock );
        MemRegion             region;
        
        // Is it included in this heap?
        ASSERT( pHeapHd->heapStart <= memBlock && memBlock < pHeapHd->heapEnd );
        
        LockHeap( heap );
        
        GetRegionOfMBlock_( &region, pMBHead );
        (void)RemoveMBlock_( &pExpHeapHd->mbUsedList, pMBHead );   // Remove from the list being used
        (void)RecycleRegion_( pExpHeapHd, &region );   // Add the specified size from the specified address to the free region
        
        UnlockHeap( heap );
    }
}

/*---------------------------------------------------------------------------*
  Name:         MEMGetTotalFreeSizeForExpHeap

  Description:  Gets the total size of the available regions of the expanded heap.

  Arguments:    heap:     Handle for expanded heap

  Returns:      Returns the total size of the available regions in the expanded heap (in bytes).
 *---------------------------------------------------------------------------*/
u32
MEMGetTotalFreeSizeForExpHeap( MEMHeapHandle heap )
{
    u32     sumSize  = 0;
    
    ASSERT(IsValidExpHeapHandle_(heap));
    
    LockHeap( heap );
    
    {
        MEMiExpHeapHead       *pEHHead = GetExpHeapHeadPtrFromHandle_(heap);
        MEMiExpHeapMBlockHead *pMBHead;
        
        for ( pMBHead = pEHHead->mbFreeList.head; pMBHead; pMBHead = pMBHead->pMBHeadNext )
        {
            sumSize += pMBHead->blockSize;
        }
    }
    
    UnlockHeap( heap );
    return sumSize;
}

/*---------------------------------------------------------------------------*
  Name:         MEMGetAllocatableSizeForExpHeapEx

  Description:  Gets a memory block of the maximum allocatable size from the expanded heap.
                The memory block alignment can be specified.

  Arguments:    heap:      Handle for expanded heap
                alignment: Alignment of the memory block to be allocated
                           The following values can be specified: + or - 4, + or - 8, + or - 16, + or - 32, + or - 64, + or - 128, ...

  Returns:      Returns the maximum allocatable size from the expanded heap (in bytes).
 *---------------------------------------------------------------------------*/
u32
MEMGetAllocatableSizeForExpHeapEx(
    MEMHeapHandle   heap,
    int             alignment
)
{
    ASSERT(IsValidExpHeapHandle_(heap));
    
    // alignment check
    ASSERT(alignment % MIN_ALIGNMENT == 0);
    ASSERT((abs(alignment) & (abs(alignment) - 1)) == 0);
    ASSERT(MIN_ALIGNMENT <= abs(alignment));
    
    alignment = abs(alignment); // Convert to a positive value just to be sure
    
    LockHeap( heap );
    
    {
        MEMiExpHeapHead       *pEHHead  = GetExpHeapHeadPtrFromHandle_(heap);
        MEMiExpHeapMBlockHead *pMBlkHd;
        u32                   maxSize   = 0;
        u32                   offsetMin = 0xFFFFFFFF;
        
        for ( pMBlkHd = pEHHead->mbFreeList.head; pMBlkHd; pMBlkHd = pMBlkHd->pMBHeadNext )
        {
            // Memory block position including the alignment
            void* baseAddress = RoundUpPtr(GetMemPtrForMBlock_(pMBlkHd), alignment);
            
            if ( GetUIntPtr(baseAddress) < GetUIntPtr(GetMBlockEndAddr_(pMBlkHd)) )
            {
                const u32 blockSize = GetOffsetFromPtr(baseAddress, GetMBlockEndAddr_(pMBlkHd));
                // Empty area due to the alignment
                const u32 offset = GetOffsetFromPtr(GetMemPtrForMBlock_(pMBlkHd), baseAddress);
                
                /*
                    If the size is large or the size is the same but wasted space is small, the memory block is updated.
                    
                 */
                if ( maxSize < blockSize
                     ||  (maxSize == blockSize && offsetMin > offset)
                )
                {
                    maxSize = blockSize;
                    offsetMin= offset;
                }
            }
        }
        
        UnlockHeap( heap );
        
        return maxSize;
    }
}


/*---------------------------------------------------------------------------*
  Name:         MEMiIsEmptyExpHeap

  Description:  Checks whether the allocated block exists in the expanded heap.

  Arguments:    heap:  Handle for expanded heap

  Returns:      If it doesn't exist, returns TRUE; otherwise returns FALSE.
                
 *---------------------------------------------------------------------------*/
BOOL        
MEMiIsEmptyExpHeap( MEMHeapHandle heap )
{
    MEMiExpHeapHead     *pExpHeapHd = GetExpHeapHeadPtrFromHeapHead_( heap );
    BOOL                ret;
    
    LockHeap( heap );
    
    ret = (pExpHeapHd->mbFreeList.head == NULL);
    
    UnlockHeap( heap );
    
    return ret;
}

/*---------------------------------------------------------------------------*
  Name:         MEMSetAllocModeForExpHeap

  Description:  Sets the memory allocation mode for the expanded heap.

  Arguments:    heap:  Handle for expanded heap
                mode:  Memory allocation mode.

  Returns:      Returns the memory allocation mode for the previous expanded heap.
 *---------------------------------------------------------------------------*/
u16
MEMSetAllocModeForExpHeap(
    MEMHeapHandle     heap,
    u16               mode
)
{
    BOOL enabled;
    u16  beforeMode;
    
    ASSERT(IsValidExpHeapHandle_(heap));
    
    enabled = OSDisableInterrupts();
    {
        MEMiExpHeapHead *const pEHHead = GetExpHeapHeadPtrFromHandle_(heap);
        beforeMode = GetAllocMode_(pEHHead);
        SetAllocMode_(pEHHead, mode);
    }
    (void)OSRestoreInterrupts( enabled );
    
    return beforeMode;
}

/*---------------------------------------------------------------------------*
  Name:         MEMGetAllocModeForExpHeap

  Description:  Gets the memory allocation mode for the expanded heap.

  Arguments:    heap:    Handle for expanded heap

  Returns:      Returns the memory allocation mode for the expanded heap.
 *---------------------------------------------------------------------------*/
u16
MEMGetAllocModeForExpHeap( MEMHeapHandle heap )
{
    ASSERT(IsValidExpHeapHandle_(heap));
    return GetAllocMode_(GetExpHeapHeadPtrFromHandle_(heap));
}

/*---------------------------------------------------------------------------*
  Name:         MEMSetGroupIDForExpHeap

  Description:  Sets the group ID for the expanded heap.

  Arguments:    heap:    Handle for expanded heap
                groupID: The group ID value to be set.

  Returns:      Returns the previous group ID value.
 *---------------------------------------------------------------------------*/
u16
MEMSetGroupIDForExpHeap(
    MEMHeapHandle   heap,
    u16             groupID 
)
{
    u16  beforeGroupID;
    BOOL enabled;
    
    ASSERT(IsValidExpHeapHandle_(heap));
    ASSERT(groupID <= MAX_GROUPID);
    
    enabled = OSDisableInterrupts();
    {
        MEMiExpHeapHead* pEHHead = GetExpHeapHeadPtrFromHandle_(heap);
        beforeGroupID = pEHHead->groupID;
        pEHHead->groupID = groupID;
        
    }
    (void)OSRestoreInterrupts( enabled );
    
    return beforeGroupID;
}

/*---------------------------------------------------------------------------*
  Name:         MEMGetGroupIDForExpHeap

  Description:  Gets the group ID for the expanded heap.

  Arguments:    heap:    Handle for expanded heap

  Returns:      Returns the group ID value.
 *---------------------------------------------------------------------------*/
u16
MEMGetGroupIDForExpHeap( MEMHeapHandle heap )
{
    ASSERT(IsValidExpHeapHandle_(heap));
    
    return GetExpHeapHeadPtrFromHandle_(heap)->groupID;
}

/*---------------------------------------------------------------------------*
  Name:         MEMVisitAllocatedForExpHeap

  Description:  Causes the function specified by the user to be called for all the memory blocks allocated from the expanded heap.
                
                The visitor function is called on these memory blocks in the order they were allocated.

                The visitor type HeapVisitor is defined as below.

                    typedef void (*HeapVisitor)(
                                    void*               memBlock,
                                    MEMHeapHandle    heap,
                                    u32                 userParam);

                                        memBlock:   Pointer to the memory block.
                                        heap:       Heap including the memory block.
                                        userParam:  User parameter.

  Arguments:    heap:       Handle for expanded heap
                visitor:    Function called for each memory block.
                userParam:  User-specified parameter to be passed to the visitor function

  Returns:      None.
 *---------------------------------------------------------------------------*/
void
MEMVisitAllocatedForExpHeap(
    MEMHeapHandle      heap,
    MEMHeapVisitor     visitor,
    u32                userParam
)
{
    ASSERT(IsValidExpHeapHandle_(heap));
    ASSERT(visitor != NULL);
    
    LockHeap( heap );
    {
        MEMiExpHeapMBlockHead* pMBHead = GetExpHeapHeadPtrFromHandle_(heap)->mbUsedList.head;
        
        while ( pMBHead )
        {
            MEMiExpHeapMBlockHead* pMBHeadNext = pMBHead->pMBHeadNext;
            (*visitor)(GetMemPtrForMBlock_(pMBHead), heap, userParam);
            pMBHead = pMBHeadNext;
        }
    }
    UnlockHeap( heap );
}

/*---------------------------------------------------------------------------*
  Name:         MEMGetSizeForMBlockExpHeap

  Description:  Gets the size of the memory block that was allocated from the expanded heap.

  Arguments:    memBlock:  Pointer to the memory block for getting the size.

  Returns:      Returns the size of the specified memory block (in bytes).
 *---------------------------------------------------------------------------*/
u32
MEMGetSizeForMBlockExpHeap( const void* memBlock )
{
    ASSERT(IsValidUsedMBlock_(memBlock, NULL));
    
    return GetMBlockHeadCPtr_( memBlock )->blockSize;
}

/*---------------------------------------------------------------------------*
  Name:         MEMGetGroupIDForMBlockExpHeap

  Description:  Gets the group ID for the memory block allocated from the expanded heap.

  Arguments:    memBlock:  Pointer to the memory block for getting the group ID.

  Returns:      Returns the group ID for the specified memory block.
 *---------------------------------------------------------------------------*/
u16
MEMGetGroupIDForMBlockExpHeap( const void* memBlock )
{
    ASSERT(IsValidUsedMBlock_(memBlock, NULL));
    
    return GetGroupIDForMBlock_( GetMBlockHeadCPtr_(memBlock) );
}

/*---------------------------------------------------------------------------*
  Name:         MEMGetAllocDirForMBlockExpHeap

  Description:  Gets the allocation direction for the memory block allocated from the expanded heap.

  Arguments:    memBlock:  Pointer to the memory block.

  Returns:      Returns the allocation direction for the specified memory block.
 *---------------------------------------------------------------------------*/
u16
MEMGetAllocDirForMBlockExpHeap( const void* memBlock )
{
    ASSERT(IsValidUsedMBlock_( memBlock, NULL ));
    
    return GetAllocDirForMBlock_( GetMBlockHeadCPtr_(memBlock) );
}


/*---------------------------------------------------------------------------*
  Name:         MEMAdjustExpHeap

  Description:  Deallocates the expanded heap's available region, and reduces the memory available for the expanded heap.
                There must not be memory blocks allocated from the back of heap memory.

  Arguments:    heap:      Handle for expanded heap

  Returns:      Returns the overall expanded heap size after reduction if successful.
                (Including the header portion.)
                Returns 0 if unsuccessful. 

 *---------------------------------------------------------------------------*/
u32
MEMAdjustExpHeap( MEMHeapHandle heap )
{
    ASSERT( IsValidExpHeapHandle_(heap) );
    
    {
        MEMiHeapHead            *pHeapHd    = heap;
        MEMiExpHeapHead         *pExpHeapHd = GetExpHeapHeadPtrFromHeapHead_( heap );
        MEMiExpHeapMBlockHead   *pMBlkHd;
        u32                     retVal;
        
        LockHeap( heap );
        
        pMBlkHd  = pExpHeapHd->mbFreeList.tail;
        
        // fails if there are no available regions
        if ( pMBlkHd == NULL )
        {
            retVal = 0;
            goto ret_;
        }
        
        {
            void * const pMBlk      = GetMemPtrForMBlock_( pMBlkHd );
            void * const pMBlkEnd   = AddU32ToPtr( pMBlk, pMBlkHd->blockSize );
            u32 blockSize;
            
            // fails if there are any memory blocks allocated from the end
            if ( pMBlkEnd != MEMGetHeapEndAddress( heap ) )
            {
                retVal = 0;
                goto ret_;
            }
            
            // Delete deallocated free block from the free list
            (void)RemoveMBlock_( &pExpHeapHd->mbFreeList, pMBlkHd );
            
            blockSize = pMBlkHd->blockSize + sizeof( MEMiExpHeapMBlockHead );
            pHeapHd->heapEnd = SubU32ToPtr( pHeapHd->heapEnd, blockSize );
            
            retVal = GetOffsetFromPtr( pHeapHd, pHeapHd->heapEnd );
        }
ret_:   
        UnlockHeap( heap );
        
        return retVal;
    }
}


#if defined(_DEBUG)

/*---------------------------------------------------------------------------*
  Name:         MEMCheckExpHeap

  Description:  Checks whether the expanded heap has been destroyed.

  Arguments:    heap:     Handle for expanded heap
                optFlag:  Flag.

  Returns:      Returns TRUE if the heap is normal.
                Returns FALSE if the heap has an error.
 *---------------------------------------------------------------------------*/
BOOL
MEMCheckExpHeap(
    MEMHeapHandle     heap,
    u32               optFlag
)
{
    const BOOL bPrint = 0 != (optFlag & MEM_HEAP_ERROR_PRINT);
    u32        totalBytes  = 0;
    BOOL       retVal;
    
    if ( ! IsValidExpHeapHandle_(heap) )
    {
        HEAP_WARNING(bPrint, "[OS Foundation " "Exp" " Heap]" " Invalid heap handle. - %08X\n", heap);
        return FALSE;
    }
    
    LockHeap( heap );
    {
        MEMiHeapHead *const    pHeapHd     = heap;
        MEMiExpHeapHead *const pExpHeapHd  = GetExpHeapHeadPtrFromHeapHead_(pHeapHd);
        MEMiExpHeapMBlockHead* pMBHead     = NULL;
        MEMiExpHeapMBlockHead* pMBHeadPrev = NULL;
        
        // Block used
        for ( pMBHead = pExpHeapHd->mbUsedList.head; pMBHead; pMBHeadPrev = pMBHead, pMBHead = pMBHead->pMBHeadNext )
        {
            if ( ! CheckUsedMBlock_(pMBHead, pHeapHd, optFlag)
              || ! CheckMBlockPrevPtr_(pMBHead, pMBHeadPrev, optFlag)   // Is the pointer to the previous block the same as the pointer to the memory block in the previous loop?
            )
            {
                retVal = FALSE;
                goto ret_;
            }
            
            // calculates size occupied
            totalBytes += sizeof(MEMiExpHeapMBlockHead) + pMBHead->blockSize + GetAlignmentForMBlock_(pMBHead);
        }
        
        if ( ! CheckMBlockLinkTail_(pMBHeadPrev, pExpHeapHd->mbUsedList.tail, "tail", optFlag))  // Is the last block referring to the pointer to the final block?
        {
            retVal = FALSE;
            goto ret_;
        }
        
        // free block
        pMBHead = NULL;
        pMBHeadPrev = NULL;
        for ( pMBHead = pExpHeapHd->mbFreeList.head; pMBHead; pMBHeadPrev = pMBHead, pMBHead = pMBHead->pMBHeadNext )
        {
            if ( ! CheckFreeMBlock_(pMBHead, pHeapHd, optFlag)
                 || ! CheckMBlockPrevPtr_(pMBHead, pMBHeadPrev, optFlag)   // Is the pointer to the previous block the same as the pointer to the memory block in the previous loop?
            )
            {
                retVal = FALSE;
                goto ret_;
            }
            
            // calculates size occupied
            totalBytes += sizeof(MEMiExpHeapMBlockHead) + pMBHead->blockSize;
        }
        
        if ( ! CheckMBlockLinkTail_(pMBHeadPrev, pExpHeapHd->mbFreeList.tail, "tail", optFlag) )  // Is the last block referring to the pointer to the final block?
        {
            retVal = FALSE;
            goto ret_;
        }
        
        // Display all results.
        if ( totalBytes != GetOffsetFromPtr(pHeapHd->heapStart, pHeapHd->heapEnd) )
        {
            HEAP_WARNING(bPrint, "[OS Foundation " "Exp" " Heap]" " Incorrect total memory block size. - heap size %08X, sum size %08X\n",
                GetOffsetFromPtr(pHeapHd->heapStart, pHeapHd->heapEnd), totalBytes);
            retVal = FALSE;
            goto ret_;
        }
        retVal = TRUE;
    }
ret_:
    UnlockHeap( heap );
    return retVal;
}


/*---------------------------------------------------------------------------*
  Name:         MEMCheckForMBlockExpHeap

  Description:  This function checks if the memory block of the expanded heap was destroyed.

  Arguments:    memBlock:  Pointer to the memory block checked.
                heap:      Handle for expanded heap
                optFlag:   Flag.

  Returns:      If the memory block is valid, returns TRUE.
                If the memory block has an error, returns FALSE.
 *---------------------------------------------------------------------------*/
BOOL
MEMCheckForMBlockExpHeap(
    const void*     memBlock,
    MEMHeapHandle   heap,
    u32             optFlag
)
{
    const MEMiExpHeapMBlockHead* pMBHead = NULL;
    MEMiHeapHead *const          pHeapHd = heap;
    
    if ( ! memBlock )
    {
        return FALSE;
    }
    
    pMBHead = GetMBlockHeadCPtr_( memBlock );
    
    if ( ! CheckUsedMBlock_( pMBHead, pHeapHd, optFlag ) )
    {
        return FALSE;
    }
    
    if ( pMBHead->pMBHeadPrev )
    {
        if ( ! CheckUsedMBlock_(pMBHead->pMBHeadPrev, pHeapHd, optFlag)        // Check of signature and size of previous block.
             || ! CheckMBlockNextPtr_(pMBHead->pMBHeadPrev, pMBHead, optFlag)  // Is the previous block's pointer to the next block pointing to the current block?
        )
        {
            return FALSE;
        }
    }
    else
    {
        if ( pHeapHd )
        {
            // If prev is NULL the head pointer of the list should be pointing to current (block).
            if ( ! CheckMBlockLinkTail_(pMBHead, GetExpHeapHeadPtrFromHeapHead_(pHeapHd)->mbUsedList.head, "head", optFlag) )
            {
                return FALSE;
            }
        }
    }
    
    if ( pMBHead->pMBHeadNext )
    {
        if ( ! CheckUsedMBlock_(pMBHead->pMBHeadNext, pHeapHd, optFlag)        // Check of signature and size of next block.
             || ! CheckMBlockPrevPtr_(pMBHead->pMBHeadNext, pMBHead, optFlag)  // Is the next block's pointer to the previous block pointing to current block?
        )
        {
            return FALSE;
        }
    }
    else
    {
        if ( pHeapHd )
        {
            // If next is NULL the tail pointer of the list should be pointing to current (block).
            if ( ! CheckMBlockLinkTail_(pMBHead, GetExpHeapHeadPtrFromHeapHead_(pHeapHd)->mbUsedList.tail, "tail", optFlag) )
            {
                return FALSE;
            }
        }
    }
    
    return TRUE;
}

// #if defined(_DEBUG)
#endif