lft.c

嵌入式常用的Buffer 算法 List。 可以直接使用已完成接口。

/****************************************************************************************************************
File Name  :	lft.c
Content	   :	list for test
Date	   :	2007/05/xx
Discription:	
Compiler   :	GNU C Compiler
Copyright  :	
****************************************************************************************************************/
/****************Include  Section  Begin**********************************************************/
#include "lft.h"
/****************Include  Section  End************************************************************/

/****************Marco	Definition Section Begin**************************************************/
#define CHECKVALCODE			0xCAFEBABE
#define HEADSIZE				(((sizeof(LISTNODE) + 3) / 4) * 4)
#define BUILD_CHECK_VAL(pNode)	((pNode)->size ^CHECKVALCODE)
#define CHECK_CHECK_VAL(pNode)	assert(((pNode)->checkVal == BUILD_CHECK_VAL(pNode)) &&	\
									((UCHAR*)buf <= (UCHAR*)(pNode)) && 				\
									((UCHAR*)(pNode) < (UCHAR*)buf + bufSize) )
#define SET_SIZE(pNode, valSize)	do {											\
										pNode->size = valSize;						\
										assert(valSize % 4 == 0);						\
										(pNode)->checkVal = BUILD_CHECK_VAL(pNode); \
									} while(0)
#define GET_BufTopNode()		getBufTopNode(buf, bufSize, buf)
#define GET_Next(node)			getNextNode(buf, bufSize, node)
/****************Marco	Definition Section End****************************************************/

/****************Static function Definition Section Begin****************************************/
/******************************************************************************
* Function Name : getBufTopNode                                               *
* Description  	: 取得 buffer 的头结点					                      *
* Date   	:                                                                 *
* Parameter     :					                                          *
* Return Code  	: static LISTNODE*                                            *
* Author   	:                                                                 *
******************************************************************************/
static LISTNODE* getBufTopNode(ULONG* buf, LONG bufSize, ULONG* point)
{
	CHECK_CHECK_VAL((LISTNODE*)point);
	return (LISTNODE*)point;
}

/******************************************************************************
* Function Name : getNextNode												  *
* Description  	: 取得 buffer 的Next结点					                  *
* Date   	:                                                                 *
* Parameter     :					                                          *
* Return Code  	: static LISTNODE*                                            *
* Author   	:                                                                 *
******************************************************************************/
static LISTNODE* getNextNode(ULONG* buf, LONG bufSize, LISTNODE* node)	
{
	CHECK_CHECK_VAL(node);
	node = node->next;
	if (node == NULL){
		return NULL;
	}
	CHECK_CHECK_VAL(node);
	
	return node;
}

/******************************************************************************
* Function Name : getLastNode												  *
* Description  	: 取得 buffer 的尾结点						                  *
* Date   	:                                                                 *
* Parameter     :					                                          *
* Return Code  	: static LISTNODE*                                            *
* Author   	:                                                                 *
******************************************************************************/
static LISTNODE* getLastNode(ULONG* buf, LONG bufSize)
{
	LISTNODE* node;
	
	node = GET_BufTopNode();
	while (node->next != NULL){
		node = GET_Next(node);
	}

	return node;
}

/******************************************************************************
* Function Name : memmov_LshiftAndLongOnly									  *
* Description  	: 取得 buffer 的尾结点						                  *
* Date   	:                                                                 *
* Parameter     :					                                          *
* Return Code  	:					                                          *
* Author   	:                                                                 *
******************************************************************************/
static void memmov_LshiftAndLongOnly( LONG* dest, LONG* src, LONG qsize )
{
	for ( ; qsize != 0 ; qsize--){
		*dest++ = *src++;
	}
}

/******************************************************************************
* Function Name : leftShiftNode												  *
* Description  	: 左面移动一个节点							                  *
* Date   	:                                                                 *
* Parameter     :					                                          *
* Return Code  	: static LISTNODE*                                            *
* Author   	:                                                                 *
******************************************************************************/
static LISTNODE* leftShiftNode( LISTNODE* node, LONG shift)
{
	UCHAR* dest;
	LONG size = 0L;
	
	assert( 0 < shift );
	dest = (UCHAR*)(node - shift);
	size = node->size;
	assert(0 == size % 4);
	size /= 4;
	memmov_LshiftAndLongOnly((LONG*)dest, (LONG*)node, size);
	
	return (LISTNODE*)dest;
}

/******************************************************************************
* Function Name : defrag													  *
* Description  	: 填充节点间的碎片间隙							              *
* Date   	:                                                                 *
* Parameter     :					                                          *
* Return Code  	: static void		                                          *
* Author   	:                                                                 *
******************************************************************************/
static void defrag(ULONG* buf, LONG bufSize)
{
	LISTNODE* node;
	LISTNODE* nextNode;
	LONG nextDistance = 0L;
	LONG garbage = 0L;
	
	for (node = GET_BufTopNode() ; node->next != NULL ; node = GET_Next(node)){
		nextNode = GET_Next(node);
		nextDistance = (UCHAR*)(nextNode) - (UCHAR*)node;
		garbage = nextDistance - (node->size);
		if ( garbage != 0 ){
			node->next = leftShiftNode(nextNode, garbage);
		}
	}
}
/****************Static function Definition Section End******************************************/

/****************Function Prototype Declaration Section Begin*************************************/
/******************************************************************************
* Function Name : lft_listInitialize										  *
* Description  	: list初始化									              *
* Date   	:                                                                 *
* Parameter     :					                                          *
* Return Code  	: static void		                                          *
* Author   	:                                                                 *
******************************************************************************/
void lft_listInitialize(ULONG* buf, LONG bufSize)
{
	LISTNODE* node;
	
	assert((buf != NULL) && (bufSize % 4 == 0));
	assert( HEADSIZE <= bufSize );
	
	node = (LISTNODE*)buf;
	node->next = NULL;
	SET_SIZE(node, HEADSIZE);
}

/******************************************************************************
* Function Name : lft_listInitialize										  *
* Description  	: list创建节点，如果不能创建，返回NUll			              *
* Date   	:                                                                 *
* Parameter     :					                                          *
* Return Code  	: LISTNODE*			                                          *
* Author   	:                                                                 *
******************************************************************************/
LISTNODE* lft_listCreateNode(ULONG* buf, LONG bufSize, LONG demSize)
{
	LISTNODE*	lastNode;
	LISTNODE*	newNode;
	LONG		nodeSize = 0L;
	LONG		space = 0L;
	
	assert(demSize % 4 == 0);
	nodeSize = HEADSIZE + demSize;
	
	defrag(buf, bufSize);
	lastNode = getLastNode(buf, bufSize);
	
	newNode = (LISTNODE*)((CHAR*)lastNode + lastNode->size);
	space = ((CHAR*)buf + bufSize) - (CHAR*)newNode;
	
	if (space < nodeSize){
		return NULL;
	}
	
	lastNode->next = newNode;
	newNode->next = NULL;
	SET_SIZE(newNode, nodeSize);
	
	return newNode;
}

/******************************************************************************
* Function Name : lft_listDestroyNode										  *
* Description  	: 删除一个节点，返回该节点									  *
* Date   	:                                                                 *
* Parameter     :					                                          *
* Return Code  	: LISTNODE*			                                          *
* Author   	:                                                                 *
******************************************************************************/
LISTNODE* lft_listDestroyNode(ULONG* buf, LONG bufSize, LISTNODE* delNode)
{
	LISTNODE* node;
	LISTNODE* nextNode;
	
	CHECK_CHECK_VAL(delNode);
	
	for ( node = GET_BufTopNode() ; node->next != NULL ; node = GET_Next(node) ){
		nextNode = GET_Next(node);
		if (nextNode == delNode){
			node->next = GET_Next(nextNode);
			nextNode->size = 0;
			return node->next;
		}
	}
	
	return NULL;
}

/******************************************************************************
* Function Name : lft_listGetNextNode										  *
* Description  	: 取得下一个节点											  *
* Date   	:                                                                 *
* Parameter     :					                                          *
* Return Code  	: LISTNODE*			                                          *
* Author   	:                                                                 *
******************************************************************************/
LISTNODE* lft_listGetNextNode(ULONG* buf, LONG bufSize, LISTNODE* node)
{
	return GET_Next(node);
}

/******************************************************************************
* Function Name : lft_listGetTopNode										  *
* Description  	: 取得头节点												  *
* Date   	:                                                                 *
* Parameter     :					                                          *
* Return Code  	: LISTNODE*			                                          *
* Author   	:                                                                 *
******************************************************************************/
LISTNODE* lft_listGetTopNode(ULONG* buf, LONG bufSize)
{
	return GET_Next((LISTNODE*)buf);
}

/******************************************************************************
* Function Name : lft_listGetData											  *
* Description  	: 取得节点所在的数据										  *
* Date   	:                                                                 *
* Parameter     :					                                          *
* Return Code  	: ULONG*			                                          *
* Author   	:                                                                 *
******************************************************************************/
ULONG* lft_listGetData(ULONG* buf, LONG bufSize, LISTNODE* node)
{
	ULONG* data;
	
	CHECK_CHECK_VAL(node);
	data = (ULONG*)((UCHAR*)node + HEADSIZE);
	return data;
}

/******************************************************************************
* Function Name : lft_listGetDataSize										  *
* Description  	: 取得该节点的size											  *
* Date   	:                                                                 *
* Parameter     :					                                          *
* Return Code  	: LISTNODE*			                                          *
* Author   	:                                                                 *
******************************************************************************/
LONG lft_listGetDataSize(ULONG* buf, LONG bufSize, LISTNODE* node)
{
	CHECK_CHECK_VAL(node);
	return (node->size - HEADSIZE);
}
/****************Function Prototype Declaration Section End***************************************/