Интерпретация исходного кода списка и элементов списка FreeRTOS
В первый раз, когда я посмотрел на список и его элементы, мне показалось, что это связанный список, хотя мой собственный связанный список не очень хорош, но он очень похож.
существуетFreeRTOS, списки и элементы списка используются часто иFreeRTOSСтуденты, изучавшие структуру данных, знают, что структура данных может сделать обработку данных более удобной и быстрой.FreeRTOSВ , этот список и элементы списка еще более важны, что может сделать нашу систему более плавной и быстрой.
Ближе к дому,FreeRTOSиспользовал много списков в（List）с элементами списка（Listitem）,существуетFreeRTOSВ планировщике они используются для отслеживания задачи и определения статуса задачи, находится ли она в приостановленном, заблокированном, готовом или выполняющемся состоянии. Эта информация будет доступна в соответствующем списке задач.
см. блок управления полетом（tskTaskControlBlock）Два элемента списка в :
ListItem_t xStateListItem; / * <任务的状态列表项目引用的列表表示该任务的状态（就绪，已阻止，暂停）。*/
ListItem_t xEventListItem; / * <用于从事件列表中引用任务。*/Один элемент списка состояния, а другой элемент списка события. Они инициализируются при создании задачи, а инициализация элементов списка инициализируется в соответствии с фактическими потребностями, как будет описано ниже.
Структура списка и элементов списка FreeRTOS
Теперь, когда мы знаем важность списков и их элементов, давайте интерпретируем исходный код list.c и list.h в FreeRTOS. Начиная с заголовочного файла lsit.h, мы видим, что некоторые структуры определены:
struct xLIST_ITEM
{
listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE / * <如果configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES设置为1，则设置为已知值。* /
configLIST_VOLATILE TickType_t xItemValue; / * <正在列出的值。在大多数情况下，这用于按降序对列表进行排序。 * /
struct xLIST_ITEM * configLIST_VOLATILE pxNext; / * <指向列表中下一个ListItem_t的指针。 * /
struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; / * <指向列表中前一个ListItem_t的指针。 * /
void * pvOwner; / * <指向包含列表项目的对象（通常是TCB）的指针。因此，包含列表项目的对象与列表项目本身之间存在双向链接。 * /
void * configLIST_VOLATILE pvContainer; / * <指向此列表项目所在列表的指针（如果有）。 * /
listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE / * <如果configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES设置为1，则设置为已知值。* /
};
typedef struct xLIST_ITEM ListItem_t; / *由于某种原因，lint希望将其作为两个单独的定义。 * /Некоторые примечания о структуре элемента списка:
xItemValueИспользуется для сортировки элементов списка, аналогично 1-2-3-4.
pxNextуказатель на следующий элемент списка
pxPreviousуказатель на предыдущий (предыдущий) элемент списка
Эти два указателя реализуют функцию, аналогичную двусвязному списку.
pvOwnerуказывает на объект, содержащий элементы списка (通常是任务控制块TCB) указатель. Следовательно, существует двусторонняя связь между объектом, содержащим элемент списка, и самим элементом списка.
pvContainerОн записывает, к какому списку относится элемент списка, грубо говоря, кто родил этого сына. . .
В то же время определена структура элемента списка MINI, а элемент списка MINI является сокращенной версией элемента списка, поскольку во многих случаях полная версия элемента списка не требуется. Нет необходимости тратить так много памяти, что может быть причиной того, что FreeRTOS является легкой операционной системой, она может немного сэкономить. Элемент списка МИНИ:
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;Структура списка снова определена. Здесь вы можете видеть, что некоторые студенты были сбиты с толку. Какова связь между списком и элементами списка? По мнению Цзецзе, это похоже на отношения родитель-потомок. Список содержит несколько элементов списка ., как отец, у которого много детей, а список — это отец, а элементы списка — это дети.
typedef struct xLIST
{
listFIRST_LIST_INTEGRITY_CHECK_VALUE / * <如果configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES设置为1，则设置为已知值。* /
configLIST_VOLATILE UBaseType_t uxNumberOfItems;
ListItem_t * configLIST_VOLATILE pxIndex; / * <用于遍历列表。 指向由listGET_OWNER_OF_NEXT_ENTRY（）调用返回的后一个列表项。*/
MiniListItem_t xListEnd; / * <List item包含最大可能的项目值，这意味着它始终在列表的末尾，因此用作标记。*/
listSECOND_LIST_INTEGRITY_CHECK_VALUE / * <如果configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES设置为1，则设置为已知值。* /
} List_t;В структуре списка примечательны:uxNumberOfItems Он используется для записи количества элементов списка в списке, то есть для записи того, сколько сыновей у отца, конечно, дочь тоже в порядке~.
pxIndexэто порядковый номер, используемый для обхода списка и вызова макросаlistGET_OWNER_OF_NEXT_ENTRY（）Затем индекс будет указывать на следующий элемент списка, который возвращает текущий элемент списка.
xListEndуказывает на последний элемент списка, и этот элемент спискаMiniListItemсвойство, является элементом мини-списка.
Инициализация списка
функция:
void vListInitialise( List_t * const pxList )
{
pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd ); /*lint The mini list structure is used as the list end to save RAM. This is checked and valid. */
pxList->xListEnd.xItemValue = portMAX_DELAY;
pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd ); /*lint 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 The mini list structure is used as the list end to save RAM. This is checked and valid. */
pxList->uxNumberOfItems = ( UBaseType_t ) 0U;
listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );
listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );
}Укажите указатель списка наxListEnd, который является элементом списка в конце（迷你列表项）
пункт спискаxItemValueЗначениеportMAX_DELAY, это,0xffffffffUL, или если в 16-битном процессоре0xffff.
Оба указателя pxNext и pxPrevious элемента списка указывают сами на себя.xListEnd.
Когда инициализация завершена, количество элементов списка0Кусок. Поскольку элемент списка еще не добавлен~.
Инициализация элементов списка
функция:
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 );
}Просто позвольте указателю pvContainer элемента списка указывать на NULL, чтобы элемент списка не принадлежал ни к какому списку, потому что инициализация элемента списка должна быть инициализирована в соответствии с реальной ситуацией.
Например, некоторые инициализации элементов списка, используемые при создании задачи:
pxNewTCB->pcTaskName[ configMAX_TASK_NAME_LEN - 1 ] = '\0';
pxNewTCB->uxPriority = uxPriority;
pxNewTCB->uxBasePriority = uxPriority;
pxNewTCB->uxMutexesHeld = 0;
vListInitialiseItem( &( pxNewTCB->xStateListItem ) );
vListInitialiseItem( &( pxNewTCB->xEventListItem ) );Или в инициализации, связанной с таймером:
pxNewTimer->pcTimerName = pcTimerName;
pxNewTimer->xTimerPeriodInTicks = xTimerPeriodInTicks;
pxNewTimer->uxAutoReload = uxAutoReload;
pxNewTimer->pvTimerID = pvTimerID;
pxNewTimer->pxCallbackFunction = pxCallbackFunction;
vListInitialiseItem( &( pxNewTimer->xTimerListItem ) );Вставить в конец элемента списка
функция:
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 );
listGET_OWNER_OF_NEXT_ENTRY(). */
pxNewListItem->pxNext = pxIndex; // 1
pxNewListItem->pxPrevious = pxIndex->pxPrevious; // 2
/* Only used during decision coverage testing. */
mtCOVERAGE_TEST_DELAY();
pxIndex->pxPrevious->pxNext = pxNewListItem; // 3
pxIndex->pxPrevious = pxNewListItem; // 4
/* Remember which list the item is in. */
pxNewListItem->pvContainer = ( void * ) pxList;
( pxList->uxNumberOfItems )++;
}Входящие параметры:
pxList: Список, в который должен быть вставлен элемент списка.
pxNewListItem: какой элемент списка нужно вставить.
Вставить с конца, тогда надо сначала узнать где голова, наши участники в спискеpxIndexОн используется для обхода элементов списка, затем место, на которое он указывает, является заголовком элемента списка, поэтому, поскольку список в FreeRTOS очень похож на двусвязный список в структуре данных, мы можем рассматривать его как кольцо, которое соединено встык, то конец функции является предыдущим из заголовка элемента списка.Очевидно, что его структурная схема должна быть как на следующем рисунке (после завершения инициализации)pxIndexуказал наxListEnd):
Почему это так, предложение кода, чтобы объяснить:
С начала:
ListItem_t * const pxIndex = pxList->pxIndex;содержит первый индексированный элемент списка (xListEnd) указывает на.
pxNewListItem->pxNext = pxIndex; // 1Следующим пунктом нового элемента списка является элемент индексного списка, обозначенный зеленой стрелкой.
pxNewListItem->pxPrevious = pxIndex->pxPrevious; // 2В начале, когда мы инициализируемpxIndex->pxPreviousуказывает на свой собственный xListEnd, затемxNewListItem->pxPreviousУказатель xListEnd. Например, 2 фиолетовые стрелки.
pxIndex->pxPrevious->pxNext = pxNewListItem; // 3Предыдущий элемент списка элемента индексного списка (xListEnd) по-прежнему принадлежит вам, тогда указывается следующий элемент вашего собственного списка.pxNewListItem.
pxIndex->pxPrevious = pxNewListItem; // 4Эту фразу легко понять. Как показано 4 оранжевыми стрелками.
Когда вставка завершена, отметьте, в какой список вставляется новый элемент списка, и добавьтеuxNumberOfItemsУвеличьте на единицу, чтобы указать еще один элемент списка.
Почему исходный код написан так? Поскольку это всего два элемента списка, а список содержит несколько элементов списка, этот код очень универсален. независимо от того, сколько элементов списка в исходном списке,pxIndexНа какой элемент списка указывает!
Посмотрите, вставлено ли оно как в исходном коде?
Вставка элементов списка
Исходный код:
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 ) /*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 )++;
}Входящие параметры:
pxList: Список, в который должен быть вставлен элемент списка.pxNewListItem: какой элемент списка нужно вставить.
pxList решает, какой список вставить,pxNewListItemсерединаxItemValueЗначение определяет, где элемент списка вставляется в список.
ListItem_t *pxIterator;
const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;Определите вспомогательный элемент списка pxIterator для итерации, чтобы узнать, куда вставить новый элемент списка, и сохраните элемент списка для вставки.pxNewListItemxItemValue.
Если включена проверка целостности элемента списка, пользователю необходимо реализоватьconfigASSERT(), в исходниках есть инструкции.
Поскольку вы хотите вставить элемент списка, вы должны знать положение элемента списка.Если новый элемент списка вставляетсяxItemValueэто самое большое слово（portMAX_DELAY）, вставляется непосредственно в конец элемента списка. В противном случае вам нужно сравнить элементы списка в спискеxItemValueразмер устроить. Затем выясните, куда вставляется новый элемент списка.
for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd ); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext )Приведенный выше исходный код представляет собой процесс реализации сравнения.
Как и исходный код, вставленный с конца пункта списка выше, код FreeRTOS очень разносторонний, а логическое мышление также сильное.
Если количество элементов списка в списке равно 0, то вставленный элемент списка находится после элемента списка инициализатора. Как показано ниже:
Анализ процесса:
новый элемент спискаpxNextнаправлениеpxIterator->pxNext, то есть указывая наxListEnd（pxIterator）.
pxNewListItem->pxNext = pxIterator->pxNext;pxPrevious для xListEnd (pxIterator) указывает на pxNewListItem.
pxNewListItem->pxNext->pxPrevious = pxNewListItem;новый элемент списка（pxPrevious）указатель наxListEnd（pxIterator）
pxIterator изpxNextуказал на新пункт списка
pxNewListItem->pxPrevious = pxIterator;
pxIterator->pxNext = pxNewListItem;Это то же самое, что и вставка элемента списка с конца, при условии, что количество элементов списка в текущем списке равно 0.
Если в элементе списка уже есть элементы, процесс будет другим. Первоначальный список выглядит так:
Предположим, что вставленный элемент спискаxItemValueда2, в то время как исходный элемент спискаxItemValueзначение3, то, согласно исходному коду, вставленный нами элемент списка находится посередине. А pxIterator — это номер элемента списка ①.
После вставки эффекта:
Проанализируйте процесс вставки:
новый элемент спискаpxNextуказывает наpxIterator->pxNext, то есть элемент списка ③. Потому что вначале pxIterator->pxNext= указывает на элемент списка ③! !
pxNewListItem->pxNext = pxIterator->pxNext;И pxNewListItem->pxNext является указателем на предыдущий элемент списка элемента списка ③ (pxPrevious) указывает на вновь вставленный элемент списка, которым является элемент списка ②.
pxNewListItem->pxNext->pxPrevious = pxNewListItem;указатель на предыдущий элемент списка для вновь вставленного элемента спискаpxNewListItem->pxPreviousуказывает на вспомогательный элемент спискаpxIterator. Очевидно, чтобы подключиться!
pxNewListItem->pxPrevious = pxIterator; Так же,pxIteratorУказатель элемента списка на следующий элемент списка теперь указывает на вновь вставленный элемент списка.pxNewListItem.
pxIterator->pxNext = pxNewListItem;А другие места, в которых не менялась наводка, менять не надо. (Соединительную линию, образованную двумя прямыми линиями на рисунке, менять не нужно)
Когда вставка будет завершена, запишите, к какому списку принадлежит вновь вставленный элемент списка. И увеличьте количество элементов списка в списке на один.
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;
}На самом деле удаление очень простое, вам не нужно думать об этом, если вы хотите удалить элемент списка, вы должны знать, к какому списку принадлежит этот элемент списка.
Удалить - удалить элементы списка в списке из списка.Суть его в том, чтобы удалить их отношения связи, а затем соединить два списка до и после удаляемого элемента списка.Если есть только один элемент списка, то удалить После этого, список возвращается в исходное состояние.
pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;Эти две строки кода реализуют связь между двумя элементами списка до и после удаленного элемента списка.
Согласно приведенному выше объяснению, вы можете понять эти два простых кода.
Если удаленный элемент списка является элементом списка текущего индекса, то после удаления pxIndex в списке будет указывать на предыдущий элемент списка удаленного элемента списка.
if( pxList->pxIndex == pxItemToRemove )
{
pxList->pxIndex = pxItemToRemove->pxPrevious;
}Конечно, текущий удаленный элемент списка должен бытьpvContainerнаправлениеNULL, чтобы он не принадлежал ни одному списку, потому что суть удаления заключается в удалении только отношения связи элементов списка, а его память не освобождается, если это динамическое выделение памяти.
И вернуть количество элементов списка в текущем списке.
Пока исходный код списка в основном объяснен.
Наконец
Вы также можете узнать о макросе, который проходит по списку, который находится в файле list.h:
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; \
}Это макрос для обхода списка, возвращающий элементы списка в списке.pxOwnerУчастник, каждый раз, когда вызывается этот макрос (функция), его индекс pxIndex будет указывать на следующий элемент списка текущего возвращенного элемента списка.
Добро пожаловать в публичный аккаунт «Развития Интернета вещей IoT»