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

  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
   ======================================================================== */

// signature for free memory block
#define MBLOCK_FREE_SIGNATURE   ('FR')

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

// maximum value for the group ID
#define MAX_GROUPID             0xff

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

// minimum value for alignment
#define MIN_ALIGNMENT           4

// default memory allocation mode
#define DEFAULT_ALLOC_MODE      MEM_EXPHEAP_ALLOC_MODE_FIRST

// minimum size to register as a free block (size not including 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 warning output 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:  Get the larger address for two pointers

  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 a pointer to a memory block from a pointer to a 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 a pointer to a MEMiExpHeapMBlockHead structure from a pointer to a memory block.
                
                Gets the pointer to the memory block.

  Arguments:    memBlock:  pointer to the memory block

  Returns:      Returns a pointer to a 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 terminal memory address from a memory block pointer.
                

  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 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 information 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 a 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 where the memory block will be inserted

  Returns:      Pointer to 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:   list to be added to
                block:  memory block to add

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

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

  Description:  Initializes a 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;   /* Embed the signature */
    block->attribute.val = 0;       /* Clear the attribute parameters */
    
    // Set 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:    terminal address for the memory 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(           // common heap initializations
        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 );

    // create 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 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 start 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 );  // delete the free block for the time being

    // when there is no space for creating a free block
    if ( ( GetOffsetFromPtr(freeRgnT.start, freeRgnT.end) < sizeof(MEMiExpHeapMBlockHead) + MIN_FREE_BLOCK_SIZE ) ||
         ( direction == MEM_EXPHEAP_ALLOC_DIR_FRONT && !pEHHead->feature.fields.useMarginOfAlign                ) )
    {
        freeRgnT.end = freeRgnT.start;  // include the alignment value for the block being used
    }
    else
    {
        pMBHeadFreePrev = InsertMBlock_( &pEHHead->mbFreeList, InitFreeMBlock_(&freeRgnT), pMBHeadFreePrev );
    }
    
    // when there is no space for creating a free block
    if ( ( GetOffsetFromPtr(freeRgnB.start, freeRgnB.end) < sizeof(MEMiExpHeapMBlockHead) + MIN_FREE_BLOCK_SIZE ) ||
         ( direction == MEM_EXPHEAP_ALLOC_DIR_REAR && !pEHHead->feature.fields.useMarginOfAlign                 ) )
    {
        freeRgnB.start= freeRgnB.end;   // include the block being used
    }
    else
    {
        (void)InsertMBlock_( &pEHHead->mbFreeList, InitFreeMBlock_(&freeRgnB), pMBHeadFreePrev );
    }
    
    // fill the memory for debugging
    FillAllocMemory( 
            GetHeapHeadPtrFromExpHeapHead_(pEHHead), 
            freeRgnT.end, 
            GetOffsetFromPtr(freeRgnT.end, freeRgnB.start) 
    );
    
    // create 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 start of the heap.

  Arguments:    pHeapHd:    pointer to the heap header
                size:       size of the memory block to be allocated
                alignment:  alignment value

  Returns:      Returns a pointer to the allocated memory block if it 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_( // allocate 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 a pointer to the allocated memory block if it 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_( // allocate a region from the free block that was found
                    pExpHeapHd,
                    pMBlkHdFound,
                    foundMBlock,
                    size,
                    MEM_EXPHEAP_ALLOC_DIR_REAR 
           );
}

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

  Description:  Incorporates an empty region into a free memory block.
                If it is adjacent to a free block, the free block is expanded.
                If it is not adjacent to a free block nor large enough to be used as a free block, the size of this empty region will be set as the alignment value for the used block adjacent to the end of it.
                
                
                If there is no used block adjacent to the end of the empty region, the function fails.
                

  Arguments:    pEHHead:  pointer to the expanded heap header
                pRegion:  pointer to the empty 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;

    // search 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 adjacent to the end?
            {
                // combine the available regions
                freeRgn.end = GetMBlockEndAddr_(pBlk);
                (void)RemoveMBlock_( &pEHHead->mbFreeList, pBlk );

                // pad 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 )
    {
        // combine the available regions
        freeRgn.start = pBlkPrFree;
        pBlkPrFree = RemoveMBlock_(&pEHHead->mbFreeList, pBlkPrFree);
    }

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

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

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

    return TRUE;
}





/* ========================================================================
    Functions to Check Operations
   ======================================================================== */
#if defined(_DEBUG)

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

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

  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 contents of the memory block header are valid, 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 )   // Too large? (128 MB or greater)
    {
        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 valid.

  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 contents of the memory block header are valid, 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 valid.

  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 contents of the memory block header are valid, 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 prior to the one being 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 being 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 start or end 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 start or end of the memory block list
                headType:     string indicating the start or end
                flag:         flag

  Returns:      Returns TRUE if the memory block pointer is at the start or end 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:  memory block to be checked
                heap:      handle for the expanded heap containing the memory block
                           If NULL is specified, no check is run to see if 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;
    BOOL ret;
    
    if ( ! memBlock)
    {
        return FALSE;
    }
    
    if ( heap ) { LockHeap( heap );   }
    
    ret = CheckUsedMBlock_(GetMBlockHeadCPtr_(memBlock), pHeapHd, 0);
    
    if ( heap ) { UnlockHeap( heap ); }
    
    return ret;
}

// #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 the 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 of 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 the 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 the 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 a pointer to the allocated memory block if it was successfully allocated.
                
                If the operation fails, NULL is returned.
 *---------------------------------------------------------------------------*/
void*
MEMAllocFromExpHeapEx(
    MEMHeapHandle   heap,
    u32             size,
    int             alignment
)
{
    void* memory = NULL;

    ASSERT( IsValidExpHeapHandle_(heap) );

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

    if ( size == 0 )
    {
        size = 1;
    }
    
    size = RoundUp( size, MIN_ALIGNMENT );    // size actually allocated
    
    LockHeap( heap );
    
    if ( alignment >= 0 )     // allocate from the front
    {
        memory = AllocFromHead_( heap, size, alignment );
    }
    else                    // allocate 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 the expanded heap.
                memBlock: Pointer to the memory block to be resized
                size:     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(memBlock != NULL);
    
    pEHHead = GetExpHeapHeadPtrFromHandle_(heap);
    pMBHead = GetMBlockHeadPtr_(memBlock);
    
    size = RoundUp( size, MIN_ALIGNMENT );
    if ( size == pMBHead->blockSize )  // when the block size is not changed
    {
        return size;
    }
    
    LockHeap( heap );
    
    ASSERT(IsValidUsedMBlock_(memBlock, heap));
    
    // for expanding the new area
    if ( size > pMBHead->blockSize )
    {
        void* crUsedEnd = GetMBlockEndAddr_(pMBHead);   // end address for the used block
        MEMiExpHeapMBlockHead* block;
        
        // search 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;
            
            // get the free block region, and temporarily remove the free block
            GetRegionOfMBlock_( &rgnNewFree, block );
            nextBlockPrev = RemoveMBlock_( &pEHHead->mbFreeList, block );
            
            oldFreeStart = rgnNewFree.start;
            rgnNewFree.start = AddU32ToPtr( memBlock, size ); // region position to be newly freed
            
            // when the remainder is smaller than the memory block size
            if ( GetOffsetFromPtr(rgnNewFree.start, rgnNewFree.end) < sizeof(MEMiExpHeapMBlockHead) )
            {
                rgnNewFree.start = rgnNewFree.end;  // absorbed into the used block
            }
            
            pMBHead->blockSize = GetOffsetFromPtr(memBlock, rgnNewFree.start);  // change the target block size
            
            // when 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);   // create a new free block
            }
            
            FillAllocMemory(  // expanded portion fill
                heap,
                oldFreeStart,
                GetOffsetFromPtr(oldFreeStart, rgnNewFree.start));
        }
    }
    // when the new area is reduced
    else
    {
        MemRegion rgnNewFree;
        const u32 oldBlockSize = pMBHead->blockSize;
        
        rgnNewFree.start = AddU32ToPtr(memBlock, size); // region position to be newly freed
        rgnNewFree.end   = GetMBlockEndAddr_(pMBHead);   // end address for the used block
        
        pMBHead->blockSize = size;  // change the target block size
        
        if ( ! RecycleRegion_(pEHHead, &rgnNewFree) )    // try to return to the free list
        {
            pMBHead->blockSize = oldBlockSize;  // restore 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 the 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;
    }
    
    LockHeap( heap );
    {
        MEMiHeapHead          *pHeapHd    = heap;
        MEMiExpHeapHead       *pExpHeapHd = GetExpHeapHeadPtrFromHandle_( pHeapHd );
        MEMiExpHeapMBlockHead *pMBHead    = GetMBlockHeadPtr_( memBlock );
        MemRegion             region;
        
        ASSERT(IsValidUsedMBlock_(memBlock, heap));
        
        // Is it included in this heap?
        ASSERT( pHeapHd->heapStart <= memBlock && memBlock < pHeapHd->heapEnd );
        
        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 the 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 the 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));
    
    // check alignment
    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 giving consideration to 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);
                
                /*
                    when the size is large, or if the size is the same but the wasted space is smaller, 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 the expanded heap.

  Returns:      TRUE if it does not exist and FALSE otherwise.
                
 *---------------------------------------------------------------------------*/
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 the 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 the expanded heap.

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


/*---------------------------------------------------------------------------*
  Name:         MEMUseMarginOfAlignmentForExpHeap

  Description:  Configures whether regions should be reused in the gaps that occur during alignment.
                
                Set to FALSE by default.
                
                If this is set to TRUE, it is possible to use small memory regions effectively. However, there is a risk that a large number of free blocks will be created and performance could degrade when memory is allocated.
                
                
                

  Arguments:    heap:    Expanded heap handle
                reuse:   If TRUE, reuse regions that are generated during alignment.
                         If FALSE, do not reuse.

  Returns:      Returns the value of the previous setting.
 *---------------------------------------------------------------------------*/
BOOL
MEMUseMarginOfAlignmentForExpHeap( MEMHeapHandle heap, BOOL reuse )
{
    MEMiExpHeapHead *const pEHHead = GetExpHeapHeadPtrFromHandle_(heap);
    BOOL before;
    
    ASSERT( IsValidExpHeapHandle_(heap) );
    
    before = pEHHead->feature.fields.useMarginOfAlign;
    pEHHead->feature.fields.useMarginOfAlign = reuse;
    
    return before;
}


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

  Description:  Sets the group ID for the expanded heap.

  Arguments:    heap:    Handle for the expanded heap.
                groupID: 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 the 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 order of the memory blocks called by the visitor function is the order in which 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 that includes the memory block
                                        userParam:  user parameter

  Arguments:    heap:       Handle for the expanded heap.
                visitor:    Function called for each memory block
                userParam:  User-specified parameter 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 region that is available for use by the expanded heap.
                There must not be memory blocks allocated from the back of heap memory.

  Arguments:    heap:      Handle for the 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;
        
        // Fail 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;
            
            // Fail if there exist 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 the 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;
        
        // used block
        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_;
            }
            
            // calculate size occupied
            totalBytes += sizeof(MEMiExpHeapMBlockHead) + pMBHead->blockSize + GetAlignmentForMBlock_(pMBHead);
        }
        
        if ( ! CheckMBlockLinkTail_(pMBHeadPrev, pExpHeapHd->mbUsedList.tail, "tail", optFlag))  // Is the last block indicating 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_;
            }
            
            // calculate size occupied
            totalBytes += sizeof(MEMiExpHeapMBlockHead) + pMBHead->blockSize;
        }
        
        if ( ! CheckMBlockLinkTail_(pMBHeadPrev, pExpHeapHd->mbFreeList.tail, "tail", optFlag) )  // Is the last block indicating 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 to be checked.
                heap:      Handle for the expanded heap.
                optFlag:   Flag.

  Returns:      Returns TRUE if the memory block is valid.
                Returns FALSE if the memory block has an error.
 *---------------------------------------------------------------------------*/
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 indicating the current block?
        )
        {
            return FALSE;
        }
    }
    else
    {
        if ( pHeapHd )
        {
            // When prev is NULL, the head pointer of the list should indicate the 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 indicating the current block?
        )
        {
            return FALSE;
        }
    }
    else
    {
        if ( pHeapHd )
        {
            // When next is NULL, the tail pointer of the list should indicate the current (block).
            if ( ! CheckMBlockLinkTail_(pMBHead, GetExpHeapHeadPtrFromHeapHead_(pHeapHd)->mbUsedList.tail, "tail", optFlag) )
            {
                return FALSE;
            }
        }
    }
    
    return TRUE;
}

// #if defined(_DEBUG)
#endif