1、简介
本文依据的freeRTOS版本是V9.0.0版本,本文将分析链表文件的结构体,主要根据其list.c和list.h文件;
2、list.h文件解析
#ifndef INC_FREERTOS_H
#error FreeRTOS.h must be included before list.h
#endif
#ifndef LIST_H
#define LIST_H
#ifndef configLIST_VOLATILE
#define configLIST_VOLATILE
#endif
#ifdef __cplusplus
extern "C" {
#endif
#if( configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES == 0 )
#define listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE
#define listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE
#define listFIRST_LIST_INTEGRITY_CHECK_VALUE
#define listSECOND_LIST_INTEGRITY_CHECK_VALUE
#define listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem )
#define listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem )
#define listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList )
#define listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList )
#define listTEST_LIST_ITEM_INTEGRITY( pxItem )
#define listTEST_LIST_INTEGRITY( pxList )
#else
#define listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE TickType_t xListItemIntegrityValue1;
#define listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE TickType_t xListItemIntegrityValue2;
#define listFIRST_LIST_INTEGRITY_CHECK_VALUE TickType_t xListIntegrityValue1;
#define listSECOND_LIST_INTEGRITY_CHECK_VALUE TickType_t xListIntegrityValue2;
#define listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem ) ( pxItem )->xListItemIntegrityValue1 = pdINTEGRITY_CHECK_VALUE
#define listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem ) ( pxItem )->xListItemIntegrityValue2 = pdINTEGRITY_CHECK_VALUE
#define listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList ) ( pxList )->xListIntegrityValue1 = pdINTEGRITY_CHECK_VALUE
#define listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList ) ( pxList )->xListIntegrityValue2 = pdINTEGRITY_CHECK_VALUE
#define listTEST_LIST_ITEM_INTEGRITY( pxItem ) configASSERT( ( ( pxItem )->xListItemIntegrityValue1 == pdINTEGRITY_CHECK_VALUE ) && ( ( pxItem )->xListItemIntegrityValue2 == pdINTEGRITY_CHECK_VALUE ) )
#define listTEST_LIST_INTEGRITY( pxList ) configASSERT( ( ( pxList )->xListIntegrityValue1 == pdINTEGRITY_CHECK_VALUE ) && ( ( pxList )->xListIntegrityValue2 == pdINTEGRITY_CHECK_VALUE ) )
#endif
struct xLIST_ITEM
{
listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE
configLIST_VOLATILE TickType_t xItemValue;
struct xLIST_ITEM * configLIST_VOLATILE pxNext;
struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;
void * pvOwner;
void * configLIST_VOLATILE pvContainer;
listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE
};
typedef struct xLIST_ITEM ListItem_t;
struct xMINI_LIST_ITEM
{
listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE
configLIST_VOLATILE TickType_t xItemValue;
struct xLIST_ITEM * configLIST_VOLATILE pxNext;
struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;
};
typedef struct xMINI_LIST_ITEM MiniListItem_t;
typedef struct xLIST
{
listFIRST_LIST_INTEGRITY_CHECK_VALUE
configLIST_VOLATILE UBaseType_t uxNumberOfItems;
ListItem_t * configLIST_VOLATILE pxIndex;
MiniListItem_t xListEnd;
listSECOND_LIST_INTEGRITY_CHECK_VALUE
} List_t;
#define listSET_LIST_ITEM_OWNER( pxListItem, pxOwner ) ( ( pxListItem )->pvOwner = ( void * ) ( pxOwner ) )
#define listGET_LIST_ITEM_OWNER( pxListItem ) ( ( pxListItem )->pvOwner )
#define listSET_LIST_ITEM_VALUE( pxListItem, xValue ) ( ( pxListItem )->xItemValue = ( xValue ) )
#define listGET_LIST_ITEM_VALUE( pxListItem ) ( ( pxListItem )->xItemValue )
#define listGET_ITEM_VALUE_OF_HEAD_ENTRY( pxList ) ( ( ( pxList )->xListEnd ).pxNext->xItemValue )
#define listGET_HEAD_ENTRY( pxList ) ( ( ( pxList )->xListEnd ).pxNext )
#define listGET_NEXT( pxListItem ) ( ( pxListItem )->pxNext )
#define listGET_END_MARKER( pxList ) ( ( ListItem_t const * ) ( &( ( pxList )->xListEnd ) ) )
#define listLIST_IS_EMPTY( pxList ) ( ( BaseType_t ) ( ( pxList )->uxNumberOfItems == ( UBaseType_t ) 0 ) )
#define listCURRENT_LIST_LENGTH( pxList ) ( ( pxList )->uxNumberOfItems )
#define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList ) \
{ \
List_t * const pxConstList = ( pxList ); \
\
\
( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext; \
if( ( void * ) ( pxConstList )->pxIndex == ( void * ) &( ( pxConstList )->xListEnd ) ) \
{ \
( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext; \
} \
( pxTCB ) = ( pxConstList )->pxIndex->pvOwner; \
}
#define listGET_OWNER_OF_HEAD_ENTRY( pxList ) ( (&( ( pxList )->xListEnd ))->pxNext->pvOwner )
#define listIS_CONTAINED_WITHIN( pxList, pxListItem ) ( ( BaseType_t ) ( ( pxListItem )->pvContainer == ( void * ) ( pxList ) ) )
#define listLIST_ITEM_CONTAINER( pxListItem ) ( ( pxListItem )->pvContainer )
#define listLIST_IS_INITIALISED( pxList ) ( ( pxList )->xListEnd.xItemValue == portMAX_DELAY )
void vListInitialise( List_t * const pxList ) PRIVILEGED_FUNCTION;
void vListInitialiseItem( ListItem_t * const pxItem ) PRIVILEGED_FUNCTION;
void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem ) PRIVILEGED_FUNCTION;
void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem ) PRIVILEGED_FUNCTION;
UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove ) PRIVILEGED_FUNCTION;
#ifdef __cplusplus
}
#endif
#endif
上面的代码是freeRTOS v9.0.0的list.h文件,上面的文件经过简化如下,下面展示的是数据结构:
struct xLIST_ITEM
{
configLIST_VOLATILE TickType_t xItemValue;
struct xLIST_ITEM * configLIST_VOLATILE pxNext;
struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;
void * pvOwner;
void * configLIST_VOLATILE pvContainer;
};
typedef struct xLIST_ITEM ListItem_t;
struct xMINI_LIST_ITEM
{
configLIST_VOLATILE TickType_t xItemValue;
struct xLIST_ITEM * configLIST_VOLATILE pxNext;
struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;
};
typedef struct xMINI_LIST_ITEM MiniListItem_t;
typedef struct xLIST
{
configLIST_VOLATILE UBaseType_t uxNumberOfItems;
ListItem_t * configLIST_VOLATILE pxIndex;
MiniListItem_t xListEnd;
} List_t;
list文件中比较主要的几个函数如下(初始化、插入和删除):
void vListInitialise( List_t * const pxList ) PRIVILEGED_FUNCTION;
void vListInitialiseItem( ListItem_t * const pxItem ) PRIVILEGED_FUNCTION;
void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem ) PRIVILEGED_FUNCTION;
void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem ) PRIVILEGED_FUNCTION;
UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove ) PRIVILEGED_FUNCTION;
根据list头文件我们可以看到其链表是双向链表,其数据结构的组织形式如下所示:
ListItem_t:
List_t:
MiniListItem_t:
3、list.c文件解析
list.c文件如下:
#include <stdlib.h>
#include "FreeRTOS.h"
#include "list.h"
void vListInitialise( List_t * const pxList )
{
pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );
pxList->xListEnd.xItemValue = portMAX_DELAY;
pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );
pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );
pxList->uxNumberOfItems = ( UBaseType_t ) 0U;
listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );
listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );
}
void vListInitialiseItem( ListItem_t * const pxItem )
{
pxItem->pvContainer = NULL;
listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
}
void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
{
ListItem_t * const pxIndex = pxList->pxIndex;
listTEST_LIST_INTEGRITY( pxList );
listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );
pxNewListItem->pxNext = pxIndex;
pxNewListItem->pxPrevious = pxIndex->pxPrevious;
mtCOVERAGE_TEST_DELAY();
pxIndex->pxPrevious->pxNext = pxNewListItem;
pxIndex->pxPrevious = pxNewListItem;
pxNewListItem->pvContainer = ( void * ) pxList;
( pxList->uxNumberOfItems )++;
}
void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )
{
ListItem_t *pxIterator;
const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;
listTEST_LIST_INTEGRITY( pxList );
listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );
if( xValueOfInsertion == portMAX_DELAY )
{
pxIterator = pxList->xListEnd.pxPrevious;
}
else
{
for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd ); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext )
{
}
}
pxNewListItem->pxNext = pxIterator->pxNext;
pxNewListItem->pxNext->pxPrevious = pxNewListItem;
pxNewListItem->pxPrevious = pxIterator;
pxIterator->pxNext = pxNewListItem;
pxNewListItem->pvContainer = ( void * ) pxList;
( pxList->uxNumberOfItems )++;
}
UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
{
List_t * const pxList = ( List_t * ) pxItemToRemove->pvContainer;
pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
mtCOVERAGE_TEST_DELAY();
if( pxList->pxIndex == pxItemToRemove )
{
pxList->pxIndex = pxItemToRemove->pxPrevious;
}
else
{
mtCOVERAGE_TEST_MARKER();
}
pxItemToRemove->pvContainer = NULL;
( pxList->uxNumberOfItems )--;
return pxList->uxNumberOfItems;
}
- void vListInitialise( List_t * const pxList )简化如下:
void vListInitialise( List_t * const pxList )
{
pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );
pxList->xListEnd.xItemValue = portMAX_DELAY;
pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );
pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );
pxList->uxNumberOfItems = ( UBaseType_t ) 0U;
}
其对应的图示:
- void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
- void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
{
ListItem_t * const pxIndex = pxList->pxIndex;
pxNewListItem->pxNext = pxIndex;
pxNewListItem->pxPrevious = pxIndex->pxPrevious;
pxIndex->pxPrevious->pxNext = pxNewListItem;
pxIndex->pxPrevious = pxNewListItem;
pxNewListItem->pvContainer = ( void * ) pxList;
( pxList->uxNumberOfItems )++;
}
其示意图如下所示:
- void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )
void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )
{
ListItem_t *pxIterator;
const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;
if( xValueOfInsertion == portMAX_DELAY )
{
pxIterator = pxList->xListEnd.pxPrevious;
}
else
{
for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd ); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext )
{
}
}
pxNewListItem->pxNext = pxIterator->pxNext;
pxNewListItem->pxNext->pxPrevious = pxNewListItem;
pxNewListItem->pxPrevious = pxIterator;
pxIterator->pxNext = pxNewListItem;
pxNewListItem->pvContainer = ( void * ) pxList;
( pxList->uxNumberOfItems )++;
}
其示意图如下:
- UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
{
List_t * const pxList = ( List_t * ) pxItemToRemove->pvContainer;
pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
mtCOVERAGE_TEST_DELAY();
if( pxList->pxIndex == pxItemToRemove )
{
pxList->pxIndex = pxItemToRemove->pxPrevious;
}
else
{
mtCOVERAGE_TEST_MARKER();
}
pxItemToRemove->pvContainer = NULL;
( pxList->uxNumberOfItems )--;
return pxList->uxNumberOfItems;
}
4、总结:
链表作为 C 语言中一种基础的数据结构,在freeRTOS系统中的作用非常重要,因此这一块内容必须要要完全掌握,以便深入阅读freeRTOS的内核代码。
参考资料:
《FreeRTOS内核实现与应用开发实战指南—基于野火 STM32 全系列(M3/4/7)开发板》
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)