列表和列表项是直接从 FreeRTOS 源码的注释中的list和list item翻译过来的，对应 C 语言中的链表和节点，在后续的讲解中，我们说的链表就是列表，节点就是列表项。

List→ 链表
List Item→ 节点

链表分为单向链表和双向链表，单向链表很少使用，用得最多的还是双向链表。

定义 List Item

struct xLIST_ITEM
{
    TickType_t xItemValue;             /* auxiliary value,  Help nodes to arrange in order */
    struct xLIST_ITEM * pxNext;
    struct xLIST_ITEM * pxPrevious;
    void * pvOwner;                    /* point to the kernel object that owns the node, usually TCB */
    void * pvContainer;                /* point to linklist where the node is located */ 
};
typedef struct xLIST_ITEM ListItem_t;  /* redefinition of node data type */

Pasted image 20251124160028.png

初始化 List Item

void vListInitializeItem(ListItem_t * const pxItem)
{
    /* Initializing the node is empty, which means that the node has not inserted any linked list. */
    pxItem->pvContainer = NULL;
}

初始化 List Item 时只需要将pvContainer初始化为空即可，表示该 Item 还没有插入任何链表。

定义 List

typedef struct xLIST
{
    UBaseType_t uxNumberOfItems;
    ListItem_t * pxIndex;
    MiniListItem_t xListEnd;
} List_t;

Pasted image 20251124160309.png

哨兵节点

struct xMINI_LIST_ITEM
{
    TickType_t xItemValue;                      
    struct xLIST_ITEM * pxNext;                 
    struct xLIST_ITEM * pxPrevious;             
};
typedef struct xMINI_LIST_ITEM MiniListItem_t;

List 初始化

void vListInitialize(List_t * const pxList)
{
    /* Point the linked list index pointer to the last node. */
    pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );

    /* Set the auxiliary sorting value of the last node of the linked list to the maximum to ensure that this node is the last node of the linked list. */
    pxList->xListEnd.xItemValue = portMAX_DELAY;

    /* Pointing the pxNext and pxPrevious pointers of the last node to the node itself indicates that the linked list is empty. */
    pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );
    pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );

    /* The value of the initialization linked list node counter is 0, indicating that the linked list is empty. */
    pxList->uxNumberOfItems = ( UBaseType_t ) 0U;
}

Pasted image 20251124160435.png

  1. List 初始化时，将 pxIndex 指向最后一个元素，即第1个，或者第0个，因为这个元素不会计入计数器。
  2. 将哨兵元素的辅助排序值xItemValue设置为最大，确保该元素就是最后一个(也可以理解为第一个)。
  3. 将最后一个(第一个)的pxNext和pxPrevious均指向自身，表示 List 为空。
  4. 初始化uxNumberOfItems为0，表示 List 为空。

将 Item 插入 List 尾部

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;

    /* Remember the linked list where the node is located. */
    pxNewListItem->pvContainer = (void *) pxList;

    /* Linked list node counter */
    (pxList->uxNumberOfItems)++;
}

Pasted image 20251125090052.png

这里有两个地方，我之前没弄明白。

第一个是ListItem_t * const pxIndex = pxList->pxIndex;，图中给了误导，让我以为这里的 pxIndex是图片中所标识的pxIndex，但不是同一个，代码中的 pxIndex是在这个函数内部新定义的一个局部指针变量，不是从外面传进来的，也不是“新建一块内存”。它只是“新建了一个指针变量”，然后把 pxList->pxIndex 里的地址拷贝了一份给它。

ListItem_t * const pxIndex = pxList->pxIndex;

可以分成两部分理解：

  • ListItem_t * const pxIndex; 在栈上定义了一个名叫 pxIndex 的局部变量，类型是 “指向 ListItem_t 的常量指针”。

    • “常量指针（* const）” 的意思是：指针本身的值（指向哪个地址）不能再改，但它指向的那个对象的内容是可以改的。
  • = pxList->pxIndex; 把 pxList 这个 List_t 结构体中的成员 pxIndex（也是一个指针）的值，拷贝给 这个局部变量 pxIndex。
    所以：
  • pxIndex 不是 一个新的节点，也没有 申请新的内存。
  • 它只是一个新的“别名指针”，指向和 pxList->pxIndex 同一个节点。

第二个是

pxIndex->pxPrevious->pxNext = pxNewListItem;
pxIndex->pxPrevious = pxNewListItem;

也是被图片误导了，其实是理解偏差，图片表示的是 List 中只有一个哨兵节点，在这种情况下，pxNext和pxPrevious都指向自己，所以我单纯的以为pxIndex->pxPrevious就是pxIndex，那么pxIndex->pxPrevious->pxNext就是pxIndex->pxNext。

但是，当 List 非空，pxIndex->pxNext 和 pxIndex->pxPrevious->pxNext 不是同一个指针成员，也不一定指向同一个节点。

将 Item 按照升序插入 List

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 )
        {
            /* Do nothing, and keep iterating to find the position where the node is to be inserted. */
        }        
    }

    /* Insert nodes according to ascending order. */
    pxNewListItem->pxNext = pxIterator->pxNext;
    pxNewListItem->pxNext->pxPrevious = pxNewListItem;
    pxNewListItem->pxPrevious = pxIterator;
    pxIterator->pxNext = pxNewListItem;

    /* Remember the linked list where the node is located. */
    pxNewListItem->pvContainer = (void * )pxList;

    (pxList->uxNumberOfItems)++;
}

Pasted image 20251125125431.png

这里的重点是理解for循环

for( pxIterator = (ListItem_t *) & (pxList->xListEnd);
                pxIterator->pxNext->xItemValue <= xValueOfInsertion;
                pxIterator = pxIterator->pxNext )
        {
            /* Do nothing, and keep iterating to find the position where the node is to be inserted. */
        }

通过循环找到要插入的位置，后面就是各个Item指针指向的更新。

将 Item 从 List 中删除

UBaseType_t uxListRemove(ListItem_t * const pxItemToRemove)
{
    /* Get the linked list where the node is located. */
    List_t * const pxList = (List_t *) pxItemToRemove->pvContainer;

    /* Delete the specified node from the linked list.  */
    pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
    pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;

    /* Adjust the node index pointer of the linked list */
    if(pxList->pxIndex == pxItemToRemove)
    {
        pxList->pxIndex = pxItemToRemove->pxPrevious;
    }

    /* The linked list where the node is initialized is empty, which means that the node has not inserted any linked list. */
    pxItemToRemove->pvContainer = NULL;

    (pxList->uxNumberOfItems)--;

    /* Returns the number of remaining nodes in the linked list. */
    return pxList->uxNumberOfItems;
}

Pasted image 20251125141112.png

下面我把 FreeRTOS 链表的三个核心操作，从头到尾给你做一个 “总复盘”。你已经自己做过实验和画图了，这里主要是把关键概念 + 指针套路系统整理一下，方便你以后一眼就能看懂源码。

0. 基本结构与整体设计

0.1 结构体

typedef struct xLIST_ITEM
{
    TickType_t xItemValue;
    struct xLIST_ITEM * pxNext;
    struct xLIST_ITEM * pxPrevious;
    void * pvOwner;
    void * pvContainer;   /* 指向所属 List_t */
} ListItem_t;

typedef struct xMINI_LIST_ITEM
{
    TickType_t xItemValue;
    struct xLIST_ITEM * pxNext;
    struct xLIST_ITEM * pxPrevious;
} MiniListItem_t;

typedef struct xLIST
{
    UBaseType_t uxNumberOfItems;
    ListItem_t * pxIndex;     /* 遍历用的当前指针 */
    MiniListItem_t xListEnd;  /* 哨兵结点 */
} List_t;

0.2 关键设计点

  1. 双向循环链表

    • 每个节点有 pxNext / pxPrevious。
    • 最后一个节点的 pxNext 指向 xListEnd；
    • 第一个节点的 pxPrevious 指向 xListEnd；
    • xListEnd 的 pxNext 是“第一个节点”，pxPrevious 是“最后一个节点”。

  2. 哨兵节点 xListEnd（MiniListItem_t）

    • 永远在链里，不计入 uxNumberOfItems。
    • xListEnd.xItemValue = portMAX_DELAY（最大值），保证排序逻辑简单。

  3. 每个 ListItem 记录所属链表

    listItem->pvContainer = pxList;  // 插入时设置
listItem->pvContainer = NULL;    // 删除/初始化时清空

    这样 uxListRemove() 不需要搜索，就能直接拿到 List_t。

  4. pxIndex 只是“遍历游标”

    • 有些 API（如获取下一个就绪任务）会用 pxList->pxIndex 在环里绕圈。
    • 删除时如果删到它，就把它挪到前一个节点，保持遍历安全。

1. 初始化：vListInitialise() & vListInitialiseItem()

1.1 初始化 List_t

核心逻辑（省略无关代码）：

void vListInitialise( List_t * const pxList )
{
    pxList->uxNumberOfItems = 0U;

    pxList->xListEnd.xItemValue = portMAX_DELAY;

    pxList->xListEnd.pxNext     = ( ListItem_t * ) &( pxList->xListEnd );
    pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );

    pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );
}

结果：只有一个哨兵节点自环：

xListEnd.pxNext     -> xListEnd
xListEnd.pxPrevious -> xListEnd
uxNumberOfItems     = 0
pxIndex             = &xListEnd

1.2 初始化 ListItem_t

void vListInitialiseItem( ListItem_t * const pxItem )
{
    pxItem->pvContainer = NULL;
}
  • 表示：这个节点当前不在任何链表中。

2. 无序尾插：vListInsertEnd()

语义：把新节点插到“末尾”——也就是 xListEnd 的前面。

本质上插入到：

oldLast  <->  xListEnd

之间，成为新的 oldLast；xListEnd 永远在最后。

关键代码：

void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
{
    ListItem_t * const pxIndex = pxList->pxIndex;  // 通常是 &xListEnd

    pxNewListItem->pxNext     = pxIndex;
    pxNewListItem->pxPrevious = pxIndex->pxPrevious;

    pxIndex->pxPrevious->pxNext = pxNewListItem;
    pxIndex->pxPrevious         = pxNewListItem;

    pxNewListItem->pvContainer  = ( void * ) pxList;
    ( pxList->uxNumberOfItems )++;
}

理解方式（假设 pxIndex == &xListEnd）：

  1. pxNewListItem->pxNext = pxIndex;
    → 新节点的 next 指向 xListEnd。
  2. pxNewListItem->pxPrevious = pxIndex->pxPrevious;
    → 新节点的 previous 指向“旧的最后一个节点”（oldLast）。
  3. pxIndex->pxPrevious->pxNext = pxNewListItem;
    → oldLast->next = new，让旧尾的 next 指向新节点。
  4. pxIndex->pxPrevious = pxNewListItem;
    → xListEnd->previous = new，更新“谁是新的最后一个”。

你之前已经弄明白的关键点：

pxIndex->pxNext 和 pxIndex->pxPrevious->pxNext 不是一回事。
这里要改的是旧尾结点的 next，所以必须用 pxIndex->pxPrevious->pxNext。

3. 有序插入：vListInsert()

目标：按 xItemValue 升序，把新节点插入到合适位置，保持链表一直有序。

3.1 先确定插入位置 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 )
    {
        /* 空循环，只是往前走 */
    }
}
  • 从 xListEnd 开始，每次看 pxIterator->pxNext->xItemValue。
  • 只要“下一个节点的值 <= 新节点的值”，就继续往前走。

  • 循环结束时，满足：

    pxIterator->pxNext->xItemValue > xValueOfInsertion;

    此时：

    • 左边节点 = pxIterator
    • 右边节点 = pxIterator->pxNext

    → 新节点应该插在这两个之间。

3.2 再做和插入尾部几乎一样的 4 步

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

pxNewListItem->pvContainer           = ( void * ) pxList;
( pxList->uxNumberOfItems )++;

对应关系：

... <-> pxIterator <-> oldNext <-> ...
变成
... <-> pxIterator <-> newItem <-> oldNext <-> ...

和 vListInsertEnd() 的指针套路是同一个模板，只是“基准节点”从 pxIndex 换成了搜索出来的 pxIterator。

4. 删除：uxListRemove()

语义：从所在链表中摘掉这个节点，保持链表结构仍然是一个完整的双向循环环。

4.1 找到所属链表

List_t * const pxList = ( List_t * ) pxItemToRemove->pvContainer;
  • 插入时我们设置过 pvContainer。
  • 这里直接拿到对应的 List_t，不需要搜索。

4.2 双向断开中间节点

pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;

设：

prev = pxItemToRemove->pxPrevious;
next = pxItemToRemove->pxNext;

则这两行就是：

next->pxPrevious = prev;  // 右 ↤ 左
prev->pxNext     = next;  // 左 ↦ 右

前后连起来：

... <-> prev <-> itemToRemove <-> next <-> ...
变成
... <-> prev <-> next <-> ...
这正好是插入时那 4 步的“反向操作”。

无论中间节点是第一个、最后一个，还是唯一一个，这两行都正确成立，因为：

  • 如果删的是第一个真实节点，prev 就是 xListEnd；
  • 如果删的是最后一个真实节点，next 就是 xListEnd；
  • 如果删的是唯一一个真实节点，prev == next == xListEnd，
    最终恢复到只有一个自环哨兵的状态。

4.3 调整 pxIndex（遍历安全）

if( pxList->pxIndex == pxItemToRemove )
{
    pxList->pxIndex = pxItemToRemove->pxPrevious;
}

  • 如果当前遍历指针正好指向被删的节点，就把它退回到 prev：

    • 这个 prev 一定还在链里（可能是 xListEnd）；
    • 下一次从它继续往前遍历，不会漏、不访问野指针。

4.4 解除节点与链表的关系 & 更新计数

pxItemToRemove->pvContainer = NULL;
( pxList->uxNumberOfItems )--;

return pxList->uxNumberOfItems;
  • pvContainer = NULL：标记“这个节点现在不在任何链表中”。
  • uxNumberOfItems——只统计真实节点数，不包含哨兵。

5. 一个完整的例子串起来看

假设：

  1. 初始化一个空链表 list；
  2. 初始化 3 个节点 i1, i2, i3，值分别为 2、1、3；
  3. 用 vListInsert(&list, &i1/i2/i3) 依次插入；
  4. 用 uxListRemove(&i2) 删除值为 1 的节点。

5.1 插入之后（有序）

插入顺序：2 → 1 → 3
最终链表（从 xListEnd.pxNext 向前）：

xListEnd -> (1) -> (2) -> (3) -> xListEnd
uxNumberOfItems = 3

5.2 删除节点 (1)

pxItemToRemove = &i2 (xItemValue = 1)：

  • prev = xListEnd
  • next = 节点 (2)

两句删除指针：

next->pxPrevious = prev;   // (2).prev = xListEnd
prev->pxNext     = next;   // xListEnd.next = (2)

结果：

xListEnd -> (2) -> (3) -> xListEnd
uxNumberOfItems = 2
i2.pvContainer = NULL

如果此时 pxIndex 本来正好指向 i2，就被调整为 xListEnd。

标签: none

评论已关闭