LIST_ENTRY

链表的定义：

typedef struct _LIST_ENTRY
{
    struct _LIST_ENTRY *Flink;
    struct _LIST_ENTRY *Blink;
}LIST_ENTRY, *PLIST_ENTRY;

LIST_ENTRY表示一个链表的节点，其中Flink成员指向当前节点的后一个节点，Blink成员指向当前节点的前一个节点。

链表的使用：

typedef struct _TestListEntry
{
    ULONG m_ulDataA;
    ULONG m_ulDataB;
    LIST_ENTRY m_ListEntry;
    /*双向链表节点的结构，m_ListEntry可以放在结构体的任意位置*/
    ULONG m_ulDataC;
    ULONG m_ulDataD;
}TestListEntry, *PTestListEntry;

m_ulDataA成员处于最低地址，m_ulDataD处于最高地址，而链表节点LIST_ENTRY的两个成员展开后在结构体中分别为Flink与Blink，其中Flink处于低地址，Blink处于高地址。

内存布局

节点的关系

包含头结点

头结点初始化

头结点的定义和初始化

LIST_ENTRAY ListHeader = {0};
InitializeListHeader(&ListHeader);

InitializeListHead函数，函数只有一个参数ListHead，表示需要被初始化的头节点

VOID InitializeListHead(_Out_PLIST_ENTRAY ListHead)
{
    ListHeader->Flink = ListHeader->Blink = listHead;
    return;
}

当只存在头结点的时候，没有其他节点时，这个链表就是一个空链表，用 IsListEmpty 可以判断一个链表是否为空，IsListEmpty返回TRUE表示链表为空链表，返回FALSE表示链表非空。

BOOLEAN　IslistEmpty(const_LIST_ENTRY *ListHead )；

节点插入

InsertHeadList函数的作用是把一个节点插入到链表的第一个位置

InsertTailList函数的作用是把一个节点插入到链表的最后一个位置

VOID InsertHeadList(PLIST_ENTRY ListHead, PLSIT_ENTRY Entry);
VOID InsertTailList(PLIST_ENTRY ListHead, PLSIT_ENTRY Entry);

链表的遍历

链表遍历可以通过Flink指针从前往后遍历，也可以通过Blink从后往前遍历。

PLIST_ENTRY pListEntry = NULL;
plistEntry = ListHeader.Flink;
while(pListEntry!=&ListHeader)
{
    PTestListEntray pTestEntry = CONTINING_RECORD (pListEntry,TestListEntry,m_ListEntry );
    Dbgprint("ListPtr = %p，Entry = %p,Tag = %c\n",pListEntry,pTestEntry,(CHAR)pTestEntry->m_ulDataA);
    PListEntry=pTestEntry->Flink;
}

pTestEntry指针的获取:

在while循环块中，是通过pListEntry指针进行遍历的，而pListEntry指向的地址是TestListEntry结构体中的m_ListEntry地址，而m_ListEntry成员的地址并不是这个结构体的首地址，所以这里需要通过一个宏CONTAINING_RECORD把m_ListEntry的地址转换成结构体TestListEntry的首地址.

CONTAINING_RECORD宏的用法:

PCHAR CONTAINING_RECORD(PCHAR Address,TYPE Type,PCHAR Field);

Address表示LIST_ENTRY的地址，在本例中，就是pListEntry指向的地址

Type表示类型，在本例中为TestListEntry

Field表示结构体中LIST_ENTRY成员的名字，在本例中为m_ListEntry。

CONTAINING_RECORD宏通过Type与Field这两个成员，计算出Field成员距离结构体顶部的内存距离，然后结合具体的Address成员，算出最终的结构体首地址。

节点移除

  1. 移除链表中第一个节点与最后一个节点分别使用RemoveHeadList以及RemoveTailList函数。

    PLIST_ENTRY RemoveHeadList(PLIST_ENTRY ListHead);
    PLIST_ENTRY RemoveTailList(PLIST_ENTRY ListHead);

    函数仅有一个参数，表示所需要移除的链表头节点指针，这两个函数的返回值均为PLIST_ENTRY，成功移除则返回从链表移除的节点指针，如果无节点可以移除（如链表为空）则返回NULL。

  2. 移除某个特定节点，即可使用RemoveEntryList函数。

    BOOLEAN RemoveEntryList(PLSIT_ENTRY Entry);

    Entry表示需要移除的链表节点指针，RemoveEntryList函数的返回值类型为BOOLEAN，节点被移除后，若链表变为空链表，RemoveEntryList返回TRUE，否则返回FALSE。

本博客采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议(CC BY-NC-SA 4.0) 发布.
Page View
⬆︎TOP