Изучайте FreeRTOS с 0-(список и элемент списка)-6

Интернет вещей

Интерпретация исходного кода списка и элементов списка 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Номер индекса, используемый для обхода списка, вызова макроса listGETOWNEROFNEXTПосле 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 или 0xffff на 16-разрядном процессоре.

Оба указателя 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 определяет, какой список нужно вставить, а значение xItemValue в pxNewListItem определяет, куда элемент списка вставляется в список.

ListItem_t *pxIterator;  
const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;

Определите вспомогательный элемент списка pxIterator для итерации, чтобы выяснить, куда вставить новый элемент списка, и сохраните xItemValue элемента списка pxNewListItem для вставки.

Если проверка целостности элемента списка включена, пользователь должен реализовать 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)

pxNext of pxIterator указывает на новый элемент списка

pxNewListItem->pxPrevious = pxIterator;
pxIterator->pxNext = pxNewListItem;

Это то же самое, что и вставка элемента списка с конца, при условии, что количество элементов списка в текущем списке равно 0.

Если в элементе списка уже есть элементы, процесс будет другим. Первоначальный список выглядит так:

Если предположить, что xItemValue вставленного элемента списка равно 2, а значение xItemValue исходного элемента списка равно 3, то, согласно исходному коду, вставленный нами элемент списка находится в середине. А pxIterator — это номер элемента списка ①.

После вставки эффекта:Проанализируйте процесс вставки:

pxNext нового элемента списка указывает на pxIterator->pxNext, который является элементом списка ③. Потому что вначале pxIterator->pxNext= указывает на элемент списка ③! !

pxNewListItem->pxNext = pxIterator->pxNext;

И pxNewListItem->pxNext, то есть указатель на предыдущий элемент списка (pxPrevious) элемента списка ③ указывает на вновь вставленный элемент списка, то есть элемент списка номер 2.

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;
}

На самом деле удаление очень простое, вам не нужно думать об этом, чтобы удалить элемент списка, вы должны знать, к какому списку принадлежит этот элемент списка, pvContainer — это список, которому принадлежит элемент списка.

Удалить - удалить элементы списка в списке из списка.Суть его в том, чтобы удалить их отношения связи, а затем соединить два списка до и после удаляемого элемента списка.Если есть только один элемент списка, то удалить После этого, список возвращается в исходное состояние.

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»

Категории