/*

	FreeRTOS.org V4.1.1 - Copyright (C) 2003-2006 Richard Barry.



	This file is part of the FreeRTOS.org distribution.



	FreeRTOS.org is free software; you can redistribute it and/or modify

	it under the terms of the GNU General Public License as published by

	the Free Software Foundation; either version 2 of the License, or

	(at your option) any later version.



	FreeRTOS.org is distributed in the hope that it will be useful,

	but WITHOUT ANY WARRANTY; without even the implied warranty of

	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

	GNU General Public License for more details.



	You should have received a copy of the GNU General Public License

	along with FreeRTOS.org; if not, write to the Free Software

	Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA



	A special exception to the GPL can be applied should you wish to distribute

	a combined work that includes FreeRTOS.org, without being obliged to provide

	the source code for any proprietary components.  See the licensing section

	of http://www.FreeRTOS.org for full details of how and when the exception

	can be applied.



	***************************************************************************

	See http://www.FreeRTOS.org for documentation, latest information, license

	and contact details.  Please ensure to read the configuration and relevant

	port sections of the online documentation.

	***************************************************************************

*/



/*

 * A sample implementation of pvPortMalloc() and vPortFree() that permits

 * allocated blocks to be freed, but does not combine adjacent free blocks

 * into a single larger block.

 *

 * See heap_1.c and heap_3.c for alternative implementations, and the memory

 * management pages of http://www.FreeRTOS.org for more information.

 */

#include <stdlib.h>



#include "FreeRTOS.h"

#include "task.h"



/* Setup the correct byte alignment mask for the defined byte alignment. */

#if portBYTE_ALIGNMENT == 4

	#define heapBYTE_ALIGNMENT_MASK	( ( size_t ) 0x0003 )

#endif



#if portBYTE_ALIGNMENT == 2

	#define heapBYTE_ALIGNMENT_MASK	( ( size_t ) 0x0001 )

#endif



#if portBYTE_ALIGNMENT == 1

	#define heapBYTE_ALIGNMENT_MASK	( ( size_t ) 0x0000 )

#endif



#ifndef heapBYTE_ALIGNMENT_MASK

	#error "Invalid portBYTE_ALIGNMENT definition"

#endif



/* Allocate the memory for the heap.  The struct is used to force byte

alignment without using any non-portable code. */

static struct xRTOS_HEAP

{

	unsigned portLONG ulDummy;

	unsigned portCHAR ucHeap[ configTOTAL_HEAP_SIZE ];

} xHeap;



/* Define the linked list structure.  This is used to link free blocks in order

of their size. */

typedef struct A_BLOCK_LINK

{

	struct A_BLOCK_LINK *pxNextFreeBlock;	/*<< The next free block in the list. */

	size_t xBlockSize;						/*<< The size of the free block. */

} xBlockLink;





static const unsigned portSHORT  heapSTRUCT_SIZE	= ( sizeof( xBlockLink ) + ( sizeof( xBlockLink ) % portBYTE_ALIGNMENT ) );

#define heapMINIMUM_BLOCK_SIZE	( ( size_t ) ( heapSTRUCT_SIZE * 2 ) )



/* Create a couple of list links to mark the start and end of the list. */

static xBlockLink xStart, xEnd;



/* STATIC FUNCTIONS ARE DEFINED AS MACROS TO MINIMIZE THE FUNCTION CALL DEPTH. */



/*

 * Insert a block into the list of free blocks - which is ordered by size of

 * the block.  Small blocks at the start of the list and large blocks at the end

 * of the list.

 */

#define prvInsertBlockIntoFreeList( pxBlockToInsert )								\

{																					\

xBlockLink *pxIterator;																\

size_t xBlockSize;																	\

																					\

	xBlockSize = pxBlockToInsert->xBlockSize;										\

																					\

	/* Iterate through the list until a block is found that has a larger size */	\

	/* than the block we are inserting. */											\

	for( pxIterator = &xStart; pxIterator->pxNextFreeBlock->xBlockSize < xBlockSize; pxIterator = pxIterator->pxNextFreeBlock )	\

	{																				\

		/* There is nothing to do here - just iterate to the correct position. */	\

	}																				\

																					\

	/* Update the list to include the block being inserted in the correct */		\

	/* position. */																	\

	pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;					\

	pxIterator->pxNextFreeBlock = pxBlockToInsert;									\

}

/*-----------------------------------------------------------*/



#define prvHeapInit()																\

{																					\

xBlockLink *pxFirstFreeBlock;														\

																					\

	/* xStart is used to hold a pointer to the first item in the list of free */	\

	/* blocks.  The void cast is used to prevent compiler warnings. */				\

	xStart.pxNextFreeBlock = ( void * ) xHeap.ucHeap;								\

	xStart.xBlockSize = ( size_t ) 0;												\

																					\

	/* xEnd is used to mark the end of the list of free blocks. */					\

	xEnd.xBlockSize = configTOTAL_HEAP_SIZE;										\

	xEnd.pxNextFreeBlock = NULL;													\

																					\

	/* To start with there is a single free block that is sized to take up the		\

	entire heap space. */															\

	pxFirstFreeBlock = ( void * ) xHeap.ucHeap;										\

	pxFirstFreeBlock->xBlockSize = configTOTAL_HEAP_SIZE;							\

	pxFirstFreeBlock->pxNextFreeBlock = &xEnd;										\

}

/*-----------------------------------------------------------*/



void *pvPortMalloc( size_t xWantedSize )

{

xBlockLink *pxBlock, *pxPreviousBlock, *pxNewBlockLink;

static portBASE_TYPE xHeapHasBeenInitialised = pdFALSE;

void *pvReturn = NULL;



	vTaskSuspendAll();

	{

		/* If this is the first call to malloc then the heap will require

		initialisation to setup the list of free blocks. */

		if( xHeapHasBeenInitialised == pdFALSE )

		{

			prvHeapInit();

			xHeapHasBeenInitialised = pdTRUE;

		}



		/* The wanted size is increased so it can contain a xBlockLink

		structure in addition to the requested amount of bytes. */

		if( xWantedSize > 0 )

		{

			xWantedSize += heapSTRUCT_SIZE;



			/* Ensure that blocks are always aligned to the required number of bytes. */

			if( xWantedSize & heapBYTE_ALIGNMENT_MASK )

			{

				/* Byte alignment required. */

				xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & heapBYTE_ALIGNMENT_MASK ) );

			}

		}



		if( ( xWantedSize > 0 ) && ( xWantedSize < configTOTAL_HEAP_SIZE ) )

		{

			/* Blocks are stored in byte order - traverse the list from the start

			(smallest) block until one of adequate size is found. */

			pxPreviousBlock = &xStart;

			pxBlock = xStart.pxNextFreeBlock;

			while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock ) )

			{

				pxPreviousBlock = pxBlock;

				pxBlock = pxBlock->pxNextFreeBlock;

			}



			/* If we found the end marker then a block of adequate size was not found. */

			if( pxBlock != &xEnd )

			{

				/* Return the memory space - jumping over the xBlockLink structure

				at its start. */

				pvReturn = ( void * ) ( ( ( unsigned portCHAR * ) pxPreviousBlock->pxNextFreeBlock ) + heapSTRUCT_SIZE );



				/* This block is being returned for use so must be taken our of the

				list of free blocks. */

				pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;



				/* If the block is larger than required it can be split into two. */

				if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE )

				{

					/* This block is to be split into two.  Create a new block

					following the number of bytes requested. The void cast is

					used to prevent byte alignment warnings from the compiler. */

					pxNewBlockLink = ( void * ) ( ( ( unsigned portCHAR * ) pxBlock ) + xWantedSize );

					

					/* Calculate the sizes of two blocks split from the single

					block. */

					pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;	

					pxBlock->xBlockSize = xWantedSize;			

					

					/* Insert the new block into the list of free blocks. */

					prvInsertBlockIntoFreeList( ( pxNewBlockLink ) );

				}

			}

		}

	}

	xTaskResumeAll();



	return pvReturn;

}

/*-----------------------------------------------------------*/



void vPortFree( void *pv )

{

unsigned portCHAR *puc = ( unsigned portCHAR * ) pv;

xBlockLink *pxLink;



	if( pv )

	{

		/* The memory being freed will have an xBlockLink structure immediately

		before it. */

		puc -= heapSTRUCT_SIZE;



		/* This casting is to keep the compiler from issuing warnings. */

		pxLink = ( void * ) puc;



		vTaskSuspendAll();

		{				

			/* Add this block to the list of free blocks. */

			prvInsertBlockIntoFreeList( ( ( xBlockLink * ) pxLink ) );

		}

		xTaskResumeAll();

	}

}

/*-----------------------------------------------------------*/