在驱动开发中,经常使用链表这种数据结构。
DDK为用户提供了两种链表的数据结构,简化了对链表的操作
链表中可以记录整形、浮点、字符型或程序员自定义的数据结构
链表通过指针将这些数据结构组成一条“链”,链中每个元素对应着记录的数据
对于单向链表,每个元素中有一个Next指向下一个元素。
对于双向链表,每个元素有两个指针:BLINK指向下一个前一个元素,FLINK指向后一个元素
DDK提供了标准的双向链表。
以下是DDK提供的双向链表的数据结构。
typedef struct _LIST_ENTRY{
struct _LIST_ENTRY* Flink;
struct _LIST_ENTRY* Blink;
}LIST_ENTRY, *PLIST_ENTRY;
链表初始化
每个双向链表都是以一个链表头作为链表的第一个元素。
初次使用链表头需要进行初始化,主要将链表头的Flink和Blink两个指针都指向自己。
这意味着链表头所代表的链是空链。
初始化链表头用InitializeListHead宏实现。
如何判断链表是否为空,可以判断链表头的Flink和Blink是否指向自己。
DDK为程序员提供了一个宏简化这种检查。这就是IsListEmpty
IsListEmpty( &head )
程序员需要自己定义链表中每个元素的数据类型,并将LIST_ENTRY结构作为自定义结构的一个子域。
LIST_ENTRY的作用是将自定义的数据结构串成一个链表
typedef struct _MYDATASTRUCT{
//List Entry需要作为_MYDATASTRUCT结构体的一部分
LIST_ENTRY ListEntry;
//下面是自定义的数据
ULONG X;
ULONG Y;
}MYDATASTRUCT, *PMYDATASTRUCT;
从首部插入链表
对链表的插入有两种方式,一种是在链表的头部插入,一种在链表的尾部插入
在头部插入链表使用语句InsertHeadList,用法如下
InsertHeadList( &head, &mydata->ListEntry );
其中head是LIST_ENTRY结构的链表头,mydata是用户定义的数据结构
它的子域ListEntry是包含其中的LIST_ENTRY数据结构
从尾部插入链表
另外一种方法是在链表的尾部插入。InsertTailList
InsertTailList( &head, &mydata->ListEntry )
其中head是LIST_ENTRY结构的链表头,mydata是用户定义的数据结构
它的子域ListEntry是包含其中的LIST_ENTRY数据结构
从链表中删除
和插入链表一样,删除也有两种对应的方法。
一种是从链表头删除,一种是从链表尾删除
RemoveHeadList RemoveTailList
PLIST_ENTRY pEntry = RemoveHeadList( &head );
PLIST_ENTRY pEntry = RemoveTailList( &head );
其中,head是链表头,pEntry是从链表中删除下来的元素中的ListEntry。
这里有一个问题,就是如何从pEntry得到用户自定义数据结构的指针。这里有以下两种情况。
1)当自定义的数据结构的第一个字段是LIST_ENTRY时,此时RemoveHeadList返回的指针可以
当做用户自定义结构的指针,也就是:
PLIST_ENTRY pEntry = RemoveHeadList( &head );
PMYDATASTRUCT pMyData = (PMYDATASTRUCT)pEntry;
2)当用户自定义的数据结构体的第一个字段不是LIST_ENTRY时,
此时RemoveHeadList返回的指针不可以当做用户自定结构的指针,
需要通过pEntry的地址逆向算出自定义数据的指针。一般通过pEntry在自动以结构中的偏移量,
用pEntry减去这个偏移量,就会得到用户自定义结构的指针的地址。
为了简化这个操作,DDK为程序员提供了宏CONTAINING_RECORD,用法:
PLIST_ENTRY pEntry = RemoveHeadList( &head );
PIRP pIrp = CONTAINING_RECORD( pEntry, MYDATASRUCT, ListEntry );
第二个参数是数据结构的名字,第三个参数是数据结构中的字段
DDK建议无论自定义数据结构的第一个字段是否为ListEntry,最好都使用CONTAINING_RECORD宏得到数据结构指针。