preface

Lists and list items are a data structure of FreeRTOS. FreeRTOS makes extensive use of lists and list items. It is the cornerstone of FreeRTOS.

1. Basic concepts

1.1 list

List is a data structure in FreeRTOS. It is conceptually similar to linked list. List is used to track tasks in FreeRTOS. On the list H defines a list_ The structure of T is as follows

typedef struct xLIST
{
listFIRST_LIST_INTEGRITY_CHECK_VALUE (1)
configLIST_VOLATILE UBaseType_t uxNumberOfItems; (2)
ListItem_t * configLIST_VOLATILE pxIndex; (3)
MiniListItem_t xListEnd; (4)
listSECOND_LIST_INTEGRITY_CHECK_VALUE (5)
} List_t;

(1) And (5), both of which are used to check the integrity of the list. Configuse required_ LIST_ DATA_ INTEGRITY_ CHECK_ When bytes is set to 1, a variable xListIntegrityValue1 and xListIntegrityValue2 will be added to these two places respectively. A special value will be written to these two variables when initializing the list. This function is not enabled by default.
(2) , uxNumberOfItems are used to record the number of list items in the list.
(3) pxIndex is used to record the current list item.
(4) . the last list item in the list is used to indicate the end of the list. This variable type is MiniListItem_t.

1.2 list items

1.2.1 list items

List items are items stored in the list. FreeRTOS provides two kinds of list items: list items and mini list items.

struct xLIST_ITEM
{
	listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE (1)
	configLIST_VOLATILE TickType_t xItemValue; (2)
	struct xLIST_ITEM * configLIST_VOLATILE pxNext; (3)
	struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; (4)
	void * pvOwner; (5)
	void * configLIST_VOLATILE pvContainer; (6)
	listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE (7)
};
typedef struct xLIST_ITEM ListItem_t;

(1) Like (7), usage and list, it is used to check the integrity of list items.
(2) , xItemValue are list item values.
(3) , pxNext points to the next list item.
(4) And pxPrevious point to the previous list item, and cooperate with pxNext to realize the function similar to two-way linked list.
(5) pvOwner records who owns this linked list item, usually the task control block.
(6) pvContainer is used to record which list this list item belongs to. TCB_ There are two variables xStateListItem and xEventListItem in t
The type of is ListItem_t. That is, both member variables are list items. Take xStateListItem as an example. After a task is created, the pvOwner variable of xStateListItem points to the task control block of the task, indicating that xSateListItem belongs to the task. When the task is ready, the variable pvContainer of xStateListItem points to the ready list, indicating that the list item is in the ready list.

1.2.2 Mini list items

The mini list item is in the file list H is defined as follows:

struct xMINI_LIST_ITEM
{
	listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE (1)
	configLIST_VOLATILE TickType_t xItemValue; (2)
	struct xLIST_ITEM * configLIST_VOLATILE pxNext; (3)
	struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; (4)
};
typedef struct xMINI_LIST_ITEM MiniListItem_t;

(1) . used to check the integrity of mini list items.
(2) , xItemValue record list item value.
(3) , pxNext points to the next list item.
(4) , pxPrevious points to the previous list item.
The meaning of mini list items:
Because in some cases, we don't need the full function of list items. We may only need some member variables. If we use list items at this time, it will be difficult
Cause memory waste! For example, the above list structure is list_ The member variable xListEnd representing the last list item in t is
MiniListItem_ Type T.

2. Operation

2.1 list initialization

List initialization is actually initializing the list structure list_ For each member variable in T, the initialization of the list is completed by making the function vlistinitialize(), which is in list It is defined in C, and the function is as follows:

void vListInitialise( List_t * const pxList )
{
	pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd ); (1)
	pxList->xListEnd.xItemValue = portMAX_DELAY; (2)
	pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd ); (3)
	pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd ); (4)
	pxList->uxNumberOfItems = ( UBaseType_t ) 0U; (5)
	listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList ); (6)
	listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList ); (7)
}

(1) xListEnd is used to indicate the end of the list. At this time, there is only one list item in the list, that is xListEnd, so pxIndex points to xListEnd
(2) The list item value of,, xListEnd is initialized to portMAX_DELAY， portMAX_DELAY is a macro in the file portmacro Defined in H. Depending on the MCU used, portmax_ The delay value is also different. It can be 0xffff or 0xfffffful. In this tutorial, it is 0xfffffful.
(3) . initialize the pxNext variable of the list item xListEnd. Because there is only one list item xListEnd in the list, pxNext can only point to itself.
(4) As in (3), initialize the pxPrevious variable of xListEnd and point to xListEnd itself.
(5) . because there are no other list items at this time, uxNumberOfItems is 0. Note that xListEnd is not counted here.
(6) And (7). Initialize the field used for integrity check in the list item, configure_ LIST_ DATA_ INTEGRITY_ CHECK_ Only valid when bytes is 1. Similarly, according to the selected MCU, the written value is also different, which can be 0x5a5a or 0x5a5a5aaul. STM32 is a 32-bit system and 0x5a5a5aaul is written.

2.2 list item initialization

Like the list, the list item needs to be initialized when it is used. The list item initialization is completed by the function vlistinitializeitem(). The functions are as follows:

void vListInitialiseItem( ListItem_t * const pxItem )
{
	pxItem->pvContainer = NULL; //Initialize pvContainer to NULL
	//Initialize the variables used for integrity check, if this function is enabled.
	listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
	listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
}

2.3 list item insertion

The function prototype is as follows:

void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )
{
	ListItem_t *pxIterator;
	const TickType_t xValueOfInsertion = pxNewListItem->xItemValue; (1)
	listTEST_LIST_INTEGRITY( pxList ); (2)
	listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );
	if( xValueOfInsertion == portMAX_DELAY ) (3) 
	{
		pxIterator = pxList->xListEnd.pxPrevious; (4) 
	}
	else
	{	
		for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd ); pxIterator->pxNext->xItemValue<=xValueOfInsertion; pxIterator = pxIterator->pxNext ) (5)
		{
			//Empty loop, do nothing!
		} 
	}
	pxNewListItem->pxNext = pxIterator->pxNext; (6)
	pxNewListItem->pxNext->pxPrevious = pxNewListItem;
	pxNewListItem->pxPrevious = pxIterator;
	pxIterator->pxNext = pxNewListItem;
	pxNewListItem->pvContainer = ( void * ) pxList; (7)
	pxList->uxNumberOfItems )++; (8) 
}

(1) . get the value of the list item to be inserted, that is, the value of the list item member variable xItemValue, because it is determined according to this value
Determines where the list item is to be inserted.
(2) , this line and the next line of code are used to check the integrity of the list and list items. In fact, it is to check whether the variable value used for integrity check in the list and list items has been changed. The values of these variables are written when the list and list items are initialized. These two lines of code need to implement the function configASSERT()!
(3) To insert a list item, the first step is to get where the list item is to be inserted! If the value of the list item to be inserted is equal to portMAX_DELAY, that is, the list item value is the maximum value. This is the best case. The position to be inserted is the end of the list.
(4) . the list value of the list item to be inserted is also portMAX_DELAY. How should I put these two in order? From this line of code, you can see that the list item to be inserted will be placed in front of xListEnd.
(5) . if the value of the list item to be inserted is not equal to portMAX_DELAY, you need to find your own position one by one in the list. This for loop is the process of finding the position. When you find the position of the appropriate list item, it will jump out. Because the for loop is used to find the insertion point of list items, there is nothing in the body of the for loop. This search process finds the insertion point of the list item in ascending order.
For ease of understanding, the insertion process is shown graphically:

• When the first node inserted is a normal node

• Insert a node again.

• The value of the inserted node is portmax_ Situation during delay

2.4 insertion at the end of a list item

The source code of the function vListInsertEnd() is as follows:

void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
{
	ListItem_t * const pxIndex = pxList->pxIndex;
	listTEST_LIST_INTEGRITY( pxList ); (1)
	listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );
	pxNewListItem->pxNext = pxIndex; (2)
	pxNewListItem->pxPrevious = pxIndex->pxPrevious;
	mtCOVERAGE_TEST_DELAY();
	pxIndex->pxPrevious->pxNext = pxNewListItem;
	pxIndex->pxPrevious = pxNewListItem;
	pxNewListItem->pvContainer = ( void * ) pxList; (3)
	pxList->uxNumberOfItems )++; (4)
}

(1) . complete the integrity check of the list and list items with the following line of code.
(2) The code from the beginning of the line to (3) is to insert the list item to be inserted to the end of the list. When using the function vListInsert() to insert a list item into the list, the position of the list item is determined by the value of the list item, that is, the list item member variable xItemValue. vListInsertEnd() adds a list item to the end of the list. We know that the xListEnd member variable in the list represents the end of the list. Does the function vListInsertEnd() insert a list item before or after xListEnd? This is not necessary. The so-called end here should be determined according to the member variable pxIndex of the list! As mentioned earlier, the pxIndex member variable in the list is used to traverse the list. The list item pointed to by pxIndex is the start list item to traverse, that is, the list item pointed to by pxIndex represents the list header! Because it is a circular list, the new list item should be inserted in front of the list item pointed to by pxIndex.
(3) . mark the new list item pxNewListItem as belonging to the list pxList.
(4) . add one to the variable of the number of list items in the record list to update the number of list items.
Insert illustration:
Before inserting list items, we prepare a default list, as shown in figure 7.4.2.1

Insert a list item with a value of 50:

The pxIndex of the List points to the List item ListItem1, so if you call the function vListInsertEnd() to insert ListItem3, it will be inserted in front of ListItem1.

2.5 deletion of list items

The function prototype is as follows:

/*
	Entry parameter: item to delete
	const Definition of pointer:
　　const Pointer is the value of pointer variable. Once initialized, the pointer cannot be changed. Initialization is necessary. Its definition form is as follows:
	type *const Pointer name;
　　When declaring a pointer, you can use the keyword const before or after the type, or both. For example, the following are legal statements, but the meanings are very different:
	const int * pOne;    //Pointer to an integer constant whose value cannot be modified
	int * const pTwo;    //Pointer to an integer constant. It cannot point to another variable, but the value pointing to (variable) can be modified. 
	const int *const pThree;  //Constant pointer to an integer constant. It can no longer point to other constants, and the value it points to cannot be modified.
	Return value:
	Returns the number of remaining list items in the list after deleting list items. Note that the deletion of a list item only deletes the specified list item from the list, and does not save the memory of the list item
	Release it! If the list item is dynamically allocated memory.
*/
UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove ) 

2.6 traversal of list items

FreeRTOS provides a function to complete the traversal of the list. This function is listGET_OWNER_OF_NEXT_ENTRY(). Every tune
Using this function once, the pxIndex variable of the list will point to the next list item and return the pxOwner of the list item
Variable value. This function is essentially a macro, which is in the file list H is defined as follows:

#define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList ) \ (1)
{ \
	List_t * const pxConstList = ( pxList ); \
	( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext; \ (2)
	if( ( void * ) ( pxConstList )->pxIndex == ( void * ) &( ( pxConstList )->xListEnd ) )\ (3)
	{ \
		( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext; \ (4)
	} \
	( pxTCB ) = ( pxConstList )->pxIndex->pvOwner; \ (5)
}

(1) . pxTCB is used to save the pvOwner variable value of the list item pointed to by pxIndex, that is, the list item belongs to
Whose? It is usually a task control block of a task. pxList represents the list to traverse.
(2) The pxIndex variable of the list points to the next list item.
(3) . if pxIndex points to the xListEnd member variable of the list, it indicates that it is at the end of the list.
(4) . if it reaches the end of the list, skip xListEnd, and pxIndex points to the list at the head of the list again
Item, which completes a traversal of the list.
(5) Assign the pvOwner of the new list item pointed to by pxIndex to pxTCB.
This function is used to find the next task to run from multiple ready tasks with the same priority.