FreeRTOS系列学习笔记三---FreeRTOS内核详解LIST（9.0版本）

傷城~ 2022-06-10 02:42 324阅读 0赞

在此推荐原子FreeRTOS的视频和资料，有兴趣的可以看看。

一、List\_t，作用类似表头，指向一个链表

/*
     * Definition of the type of queue used by the scheduler.
     */
    typedef struct xLIST
    {
    	listFIRST_LIST_INTEGRITY_CHECK_VALUE				/*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
    	configLIST_VOLATILE UBaseType_t uxNumberOfItems;
    	ListItem_t * configLIST_VOLATILE pxIndex;			/*< Used to walk through the list.  Points to the last item returned by a call to listGET_OWNER_OF_NEXT_ENTRY (). */
    	MiniListItem_t xListEnd;							/*< List item that contains the maximum possible item value meaning it is always at the end of the list and is therefore used as a marker. */
    	listSECOND_LIST_INTEGRITY_CHECK_VALUE				/*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
    } List_t;

说明：

1、listFIRST\_LIST\_INTEGRITY\_CHECK\_VALUE和listSECOND\_LIST\_INTEGRITY\_CHECK\_VALUE是头和尾保护，防止越界（其实就是写特定数据），需 要把configUSE\_LIST\_DATA\_INTEGRITY\_CHECK\_BYTES配置为1；

2、uxNumberOfItems 本List\_t中有多少个项；

3、pxIndex 用于遍历。指向由listGET\_OWNER\_OF\_NEXT\_ENTRY ()函数返回的项；

4、xListEnd指向最后一项，类型为MiniListItem\_t，

二、ListItem\_t项

/*
     * Definition of the only type of object that a list can contain.
     */
    struct xLIST_ITEM
    {
    	listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE			/*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
    	configLIST_VOLATILE TickType_t xItemValue;			/*< The value being listed.  In most cases this is used to sort the list in descending order. */
    	struct xLIST_ITEM * configLIST_VOLATILE pxNext;		/*< Pointer to the next ListItem_t in the list. */
    	struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;	/*< Pointer to the previous ListItem_t in the list. */
    	void * pvOwner;										/*< Pointer to the object (normally a TCB) that contains the list item.  There is therefore a two way link between the object containing the list item and the list item itself. */
    	void * configLIST_VOLATILE pvContainer;				/*< Pointer to the list in which this list item is placed (if any). */
    	listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE			/*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
    };
    typedef struct xLIST_ITEM ListItem_t;					/* For some reason lint wants this as two separate definitions. */

说明：

1、listFIRST\_LIST\_ITEM\_INTEGRITY\_CHECK\_VALUE和listSECOND\_LIST\_ITEM\_INTEGRITY\_CHECK\_VALUE保护，需要把configUSE\_LIST\_DATA\_INTEGRITY\_CHECK\_BYTES配置为1；

2、xItemValue 本ListItem\_t项的值，大多数用于排序，比如延时；

3、pxNext指向下一项；

4、pxPrevious指向前一项；  
5、pvOwner指向拥有者，一般是TCB；

6、pvContainer指向所属的链表；

7、可以组成双向链表或者循环表；

三、MiniListItem\_t项

struct xMINI_LIST_ITEM
    {
    	listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE			/*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
    	configLIST_VOLATILE TickType_t xItemValue;
    	struct xLIST_ITEM * configLIST_VOLATILE pxNext;
    	struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;
    };
    typedef struct xMINI_LIST_ITEM MiniListItem_t;

说明：

1、只是少了pvOwner和pvContainer，一般用于链表的结尾，表示结束；

四、listGET\_OWNER\_OF\_NEXT\_ENTRY ()

#define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList )										\
    {																							\
    List_t * const pxConstList = ( pxList );													\
    	/* Increment the index to the next item and return the item, ensuring */				\
    	/* we don't return the marker used at the end of the list.  */							\
    	( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;							\
    	if( ( void * ) ( pxConstList )->pxIndex == ( void * ) &( ( pxConstList )->xListEnd ) )	\
    	{																						\
    		( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;						\
    	}																						\
    	( pxTCB ) = ( pxConstList )->pxIndex->pvOwner;											\
    }

说明：

1、if( ( void \* ) ( pxConstList )->pxIndex == ( void \* ) &( ( pxConstList )->xListEnd ) ）判断是否到达链表末尾；

2、每次调用后，( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;修改pxNext；

3、每次返回( pxTCB ) = ( pxConstList )->pxIndex->pvOwner;（这里有个疑问，当只有MiniListItem\_t项时候，怎么处理？）

五、初始化List\_t

void vListInitialise( List_t * const pxList )
    {
    	/* The list structure contains a list item which is used to mark the
    	end of the list.  To initialise the list the list end is inserted
    	as the only list entry. */
    	pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );			/*lint !e826 !e740 The mini list structure is used as the list end to save RAM.  This is checked and valid. */
    
    	/* The list end value is the highest possible value in the list to
    	ensure it remains at the end of the list. */
    	pxList->xListEnd.xItemValue = portMAX_DELAY;
    
    	/* The list end next and previous pointers point to itself so we know
    	when the list is empty. */
    	pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );	/*lint !e826 !e740 The mini list structure is used as the list end to save RAM.  This is checked and valid. */
    	pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );/*lint !e826 !e740 The mini list structure is used as the list end to save RAM.  This is checked and valid. */
    
    	pxList->uxNumberOfItems = ( UBaseType_t ) 0U;
    
    	/* Write known values into the list if
    	configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
    	listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );
    	listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );
    }

说明：

1、pxList->pxIndex = ( ListItem\_t \* ) &( pxList->xListEnd );指向最后一个；

2、pxList->xListEnd.xItemValue = portMAX\_DELAY;值设置为最大；

3、pxList->xListEnd.pxNext = ( ListItem\_t \* ) &( pxList->xListEnd );//循环链表，指向最后一个项  
pxList->xListEnd.pxPrevious = ( ListItem\_t \* ) &( pxList->xListEnd );//

4、pxList->uxNumberOfItems = ( UBaseType\_t ) 0U;数初始化为0

六、初始化Item

void vListInitialiseItem( ListItem_t * const pxItem )
    {
    	/* Make sure the list item is not recorded as being on a list. */
    	pxItem->pvContainer = NULL;
    
    	/* Write known values into the list item if
    	configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
    	listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
    	listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
    }

说明：

1、pxItem->pvContainer = NULL;把属于哪个链表设置为NULL；

七、插入

插入到末尾：

void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
    {
    ListItem_t * const pxIndex = pxList->pxIndex;
    
    	/* Only effective when configASSERT() is also defined, these tests may catch
    	the list data structures being overwritten in memory.  They will not catch
    	data errors caused by incorrect configuration or use of FreeRTOS. */
    	listTEST_LIST_INTEGRITY( pxList );
    	listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );
    
    	/* Insert a new list item into pxList, but rather than sort the list,
    	makes the new list item the last item to be removed by a call to
    	listGET_OWNER_OF_NEXT_ENTRY(). */
    	pxNewListItem->pxNext = pxIndex;
    	pxNewListItem->pxPrevious = pxIndex->pxPrevious;
    
    	/* Only used during decision coverage testing. */
    	mtCOVERAGE_TEST_DELAY();
    
    	pxIndex->pxPrevious->pxNext = pxNewListItem;
    	pxIndex->pxPrevious = pxNewListItem;
    
    	/* Remember which list the item is in. */
    	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;
    
    	/* Only effective when configASSERT() is also defined, these tests may catch
    	the list data structures being overwritten in memory.  They will not catch
    	data errors caused by incorrect configuration or use of FreeRTOS. */
    	listTEST_LIST_INTEGRITY( pxList );
    	listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );
    
    	/* Insert the new list item into the list, sorted in xItemValue order.
    
    	If the list already contains a list item with the same item value then the
    	new list item should be placed after it.  This ensures that TCB's which are
    	stored in ready lists (all of which have the same xItemValue value) get a
    	share of the CPU.  However, if the xItemValue is the same as the back marker
    	the iteration loop below will not end.  Therefore the value is checked
    	first, and the algorithm slightly modified if necessary. */
    	if( xValueOfInsertion == portMAX_DELAY )
    	{
    		pxIterator = pxList->xListEnd.pxPrevious;
    	}
    	else
    	{
    		/* *** NOTE ***********************************************************
    		If you find your application is crashing here then likely causes are
    		listed below.  In addition see http://www.freertos.org/FAQHelp.html for
    		more tips, and ensure configASSERT() is defined!
    		http://www.freertos.org/a00110.html#configASSERT
    
    			1) Stack overflow -
    			   see http://www.freertos.org/Stacks-and-stack-overflow-checking.html
    			2) Incorrect interrupt priority assignment, especially on Cortex-M
    			   parts where numerically high priority values denote low actual
    			   interrupt priorities, which can seem counter intuitive.  See
    			   http://www.freertos.org/RTOS-Cortex-M3-M4.html and the definition
    			   of configMAX_SYSCALL_INTERRUPT_PRIORITY on
    			   http://www.freertos.org/a00110.html
    			3) Calling an API function from within a critical section or when
    			   the scheduler is suspended, or calling an API function that does
    			   not end in "FromISR" from an interrupt.
    			4) Using a queue or semaphore before it has been initialised or
    			   before the scheduler has been started (are interrupts firing
    			   before vTaskStartScheduler() has been called?).
    		**********************************************************************/
    
    		for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd ); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext ) /*lint !e826 !e740 The mini list structure is used as the list end to save RAM.  This is checked and valid. */
    		{
    			/* There is nothing to do here, just iterating to the wanted
    			insertion position. */
    		}
    	}
    
    	pxNewListItem->pxNext = pxIterator->pxNext;
    	pxNewListItem->pxNext->pxPrevious = pxNewListItem;
    	pxNewListItem->pxPrevious = pxIterator;
    	pxIterator->pxNext = pxNewListItem;
    
    	/* Remember which list the item is in.  This allows fast removal of the
    	item later. */
    	pxNewListItem->pvContainer = ( void * ) pxList;
    
    	( pxList->uxNumberOfItems )++;
    }

八、移除

UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
    {
    /* The list item knows which list it is in.  Obtain the list from the list
    item. */
    List_t * const pxList = ( List_t * ) pxItemToRemove->pvContainer;
    
    	pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
    	pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
    
    	/* Only used during decision coverage testing. */
    	mtCOVERAGE_TEST_DELAY();
    
    	/* Make sure the index is left pointing to a valid item. */
    	if( pxList->pxIndex == pxItemToRemove )
    	{
    		pxList->pxIndex = pxItemToRemove->pxPrevious;
    	}
    	else
    	{
    		mtCOVERAGE_TEST_MARKER();
    	}
    
    	pxItemToRemove->pvContainer = NULL;
    	( pxList->uxNumberOfItems )--;
    
    	return pxList->uxNumberOfItems;
    }