首页 > 代码库 > LIST_ENTRY链表学习

LIST_ENTRY链表学习

2024-07-18 21:08:45   217人阅读


链表是驱动开发中经常遇到的一个数据结构，主要是双向循环链表；要使用链表，需要用到一个LIST_ENTRY的结构，其定义如下：

typedef struct _LIST_ENTRY {
    struct _LIST_ENTRY  *Flink;    // 指向下一个节点
    struct _LIST_ENTRY  *Blink;    // 指向前一个节点
} LIST_ENTRY, *PLIST_ENTRY;


每个双向链表都是一个以链表头作为链表第一个元素，初次使用时需要进行初始化，主要讲链表头的Flink，Blink指向自己，连表头所代表的是空链。初始化时用InitializeListHead宏实现。


常用操作：

InitializeListHead，初始化链表头 
IsListEmpty，判断链表是否为空 
InsertHeadList，从链表头部插入节点 
InsertTailList，从链表尾部插入节点 
RemoveHeadList，从链表头部删除节点 
RemoveTailList，从链表尾部删除节点 
CONTAINING_RECORD，从RemoveHeadList或者RemoveTailList返回的数据获取一个指向删除节点的指针
实例代码（from windows 驱动开发技术详解）

#include <ntddk.h>

typedef struct _MYDATASTRUCT 
{
	ULONG number;
	LIST_ENTRY ListEntry;
}MYDATASTRUCT, *PMYDATASTRUCT;

VOID LinkListTest()
{
	LIST_ENTRY linkListHead;
	//初始化链表
	InitializeListHead(&linkListHead);
	PMYDATASTRUCT pData;
	ULONG i = 0;
	//在链表中插入10个元素
	KdPrint(("Begin insert to link list\n"));
	for(i=0; i<10; i++)
	{
		//分配页内存
		pData = http://www.mamicode.com/(PMYDATASTRUCT)ExAllocatePool(PagedPool, sizeof(MYDATASTRUCT));>
下面用windbg跟了下看看：
在InitializeListHead函数之前，查看 linkListHead
kd> dt linkListHead
Local var @ 0xf78eec78 Type _LIST_ENTRY
 [ 0x8 - 0x386 ]
   +0x000 Flink            : 0x00000008 _LIST_ENTRY
   +0x004 Blink            : 0x00000386 _LIST_ENTRY

可知Flink、Blink随机给了两个值
InitializeListHead函数执行后
kd> dt linkListHead
Local var @ 0xf78eec78 Type _LIST_ENTRY
 [ 0xf78eec78 - 0xf78eec78 ]
   +0x000 Flink            : 0xf78eec78 _LIST_ENTRY [ 0xf78eec78 - 0xf78eec78 ]
   +0x004 Blink            : 0xf78eec78 _LIST_ENTRY [ 0xf78eec78 - 0xf78eec78 ]

可知结构中两个成员都指向自己。
跟踪程序，当程序中链表有两个元素后（除了表头），查看下链表情况
链头：
kd> dt linkListHead
Local var @ 0xf78eec78 Type _LIST_ENTRY
 [ 0xe139a29c - 0xe12a9ba4 ]
   +0x000 Flink            : 0xe139a29c _LIST_ENTRY [ 0xe12a9ba4 - 0xf78eec78 ]
   +0x004 Blink            : 0xe12a9ba4 _LIST_ENTRY [ 0xf78eec78 - 0xe139a29c ]

第一个元素：
前三个值分别对应结构
typedef struct _MYDATASTRUCT 
{
	ULONG number;
	LIST_ENTRY ListEntry;
}MYDATASTRUCT, *PMYDATASTRUCT;

的
{
 ULONG number;
 _LIST_ENTRY *Flink;
 _LIST_ENTRY *Blink;
}

值
kd> dd 0xe139a29c -4
e139a298  00000001 e12a9ba4 f78eec78 87357020
e139a2a8  0c090203 76666647 e139a2b8 00000000
e139a2b8  647ce000 01c2f458 00000000 007d0000
e139a2c8  00001630 e1d1c308 00000001 00000000


第二个元素：
kd> dd 0xe12a9ba4-4
e12a9ba0  00000000 f78eec78 e139a29c 87c816f0
e12a9bb0  0c060403 f7564d43 e115c740 e12aac40
e12a9bc0  e12a9bc0 e12a9bc0 0009c000 00004000
e12a9bd0  dea5c000 884d1831 00000000 05000072


因为是从头部插入链表，所以先插入的元素在链表后面。


联系
我们