刘火良 FreeRTOS内核实现与应用之1——列表学习

重要数据

节点的命名都以_ITEM后缀进行，链表取消了后缀，直接LIST

普通的节点数据类型

/* 节点结构体定义 */

struct xLIST_ITEM

{

    TickType_t xItemValue;             /* 辅助值，用于帮助节点做顺序排列 */            

    struct xLIST_ITEM *  pxNext;       /* 指向链表下一个节点 */      

    struct xLIST_ITEM *  pxPrevious;   /* 指向链表前一个节点 */  

    void * pvOwner;                    /* 指向拥有该节点的内核对象，通常是TCB */

    void *  pvContainer;               /* 指向该节点所在的链表 */

};

typedef struct xLIST_ITEM ListItem_t;  /* 节点数据类型重定义 */

迷你节点数据类型

/* mini节点结构体定义，作为双向链表的结尾

   因为双向链表是首尾相连的，头即是尾，尾即是头 */

struct xMINI_LIST_ITEM

{

    TickType_t xItemValue;                      /* 辅助值，用于帮助节点做升序排列 */

    struct xLIST_ITEM *  pxNext;                /* 指向链表下一个节点 */

    struct xLIST_ITEM *  pxPrevious;            /* 指向链表前一个节点 */

};

typedef struct xMINI_LIST_ITEM MiniListItem_t;  /* 最小节点数据类型重定义 */

链表数据类型

/* 链表结构体定义 */

typedef struct xLIST

{

    UBaseType_t uxNumberOfItems;    /* 链表节点计数器 */

    ListItem_t *  pxIndex;          /* 链表节点索引指针 */

    MiniListItem_t xListEnd;        /* 链表最后一个节点 */

} List_t;

函数

1. 链表插入函数  vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )

升序插入函数

新的节点项插入后，需要解开原来的链接，建立新的链接：

语句1：向后看：新的节点项指向插入出（后面的）

pxNewListItem->pxNext = pxIterator->pxNext; // 插入，建立新的链接；

语句2：向前看：插入出（后面的）指向新的节点项

pxNewListItem->pxNext->pxPrevious = pxNewListItem; // 插入，建立新的链接；

语句3：向前看：新的节点项的前面为插入出（前面的）

pxNewListItem->pxPrevious = pxIterator; // 插入，建立新的链接；

语句4：向后看：插入出（前面的）指向新的节点项

pxIterator->pxNext = pxNewListItem;// 插入，建立新的链接；

/* 将节点按照升序排列插入到链表 */
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 )
        {
            /* 没有事情可做，不断迭代只为了找到节点要插入的位置 */            
        }
    }

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

    /* 记住该节点所在的链表 */
    pxNewListItem->pvContainer = ( void * ) pxList;

    /* 链表节点计数器++ */
    ( pxList->uxNumberOfItems )++;
}

2. 链表尾部插入函数  void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )

根节点既是头部也是尾部，当Item4插入，调用vListInsertEnd，插入如图所示位置，尾部插入

/* 将节点插入到链表的尾部 */

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;

    /* 记住该节点所在的链表 */

    pxNewListItem->pvContainer = ( void * ) pxList;

    /* 链表节点计数器++ */

    ( pxList->uxNumberOfItems )++;

}

3. 链表删除节点函数 

删除节点，解开原来的链接，建立新的链接：

函数中为何会修改：pxList->pxIndex = pxItemToRemove->pxPrevious，

上面的建立函数一直没有修改链表中根节点的索引值的，索引值一直是指向根节点内部的xListEnd（根节点初始化的时候设置的。），既然建立的时候没有改变，为何删除的时候改变？

《我的理解是保护用的，其实用处不大》

/* 将节点从链表中删除 */

UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )

{

    /* 获取节点所在的链表 */

    List_t * const pxList = ( List_t * ) pxItemToRemove->pvContainer;

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

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

    /* Make sure the index is left pointing to a valid item. */

    if( pxList->pxIndex == pxItemToRemove )

    {

        pxList->pxIndex = pxItemToRemove->pxPrevious;

    }

    /* 初始化该节点所在的链表为空，表示节点还没有插入任何链表 */

    pxItemToRemove->pvContainer = NULL;

   

    /* 链表节点计数器-- */

    ( pxList->uxNumberOfItems )--;

    /* 返回链表中剩余节点的个数 */

    return pxList->uxNumberOfItems;

}