链表LIST_ENTRY

Windows的内核开发者们自己开发了部分数据结构，比如说LIST_ENTRY。

LIST_ENTRY是一个双向链表结构。它总是在使用的时候，被插入到已有的数据结构中。下面举一个例子。我构筑一个链表，这个链表的每个节点，是一个文件名和一个文件大小两个数据成员组成的结构。此外有一个FILE_OBJECT的指针对象。在驱动中，这代表一个文件对象。本书后面的章节会详细解释。这个链表的作用是：保存了文件的文件名和长度。只要传入FILE_OBJECT的指针，使用者就可以遍历链表找到文件名和文件长度。

typedef struct {
    PFILE_OBJECT file_object;
    UNICODE_STRING file_name;
    LARGE_INTEGER file_length;
} MY_FILE_INFOR, *PMY_FILE_INFOR;

一些读者会马上注意到文件的长度用LARGE_INTEGER表示。这是一个代表长长整型的数据结构。这个结构我们在下一小小节“使用长长整型数据”中介绍。

为了让上面的结构成为链表节点，我必须在里面插入一个LIST_ENTRY结构。至于插入的位置并无所谓。可以放在最前，也可以放中间，或者最后面。但是实际上读者很快会发现把LIST_ENTRY放在开头是最简单的做法：

typedef struct {
    LIST_ENTRY list_entry;
    PFILE_OBJECT file_object;
    UNICODE_STRING file_name;
    LARGE_INTEGER file_length;
} MY_FILE_INFOR, *PMY_FILE_INFOR;

list_entry如果是作为链表的头，在使用之前，必须调用InitializeListHead来初始化。下面是示例的代码：

// 我们的链表头
LIST_ENTRY        my_list_head;

// 链表头初始化。一般的说在应该在程序入口处调用一下
void MyFileInforInilt()
{
    InitializeListHead(&my_list_head);
}

// 我们的链表节点。里面保存一个文件名和一个文件长度信息。
typedef struct {
    LIST_ENTRY list_entry;
    PFILE_OBJECT file_object;
    PUNICODE_STRING file_name;
    LARGE_INTEGER file_length;
} MY_FILE_INFOR, *PMY_FILE_INFOR;

// 追加一条信息。也就是增加一个链表节点。请注意file_name是外面分配的。
// 内存由使用者管理。本链表并不管理它。
NTSTATUS MyFileInforAppendNode(
    PFILE_OBJECT file_object, 
    PUNICODE_STRING file_name,
    PLARGE_INTEGER file_length)
{
    PMY_FILE_INFOR my_file_infor = 
        (PMY_FILE_INFOR)ExAllocatePoolWithTag(
            PagedPool,sizeof(MY_FILE_INFOR),MEM_TAG);
    if(my_file_infor == NULL)
        return STATUS_INSUFFICIENT_RESOURES;

    // 填写数据成员。
    my_file_infor->file_object = file_object;
    my_file_infor->file_name = file_name;
    my_file_infor->file_length = file_length;

    // 插入到链表末尾。请注意这里没有使用任何锁。所以，这个函数不是多
    // 多线程安全的。在下面自旋锁的使用中讲解如何保证多线程安全性。
    InsertHeadList(&my_list_head, (PLIST_ENTRY)& my_file_infor);
    return STATUS_SUCCESS;    
    }

以上的代码实现了插入。可以看到LIST_ENTRY插入到MY_FILE_INFOR结构的头部的好处。这样一来一个MY_FILE_INFOR看起来就像一个LIST_ENTRY。不过糟糕的是并非所有的情况都可以这样。比如MS的许多结构喜欢一开头是结构的长度。因此在通过LIST_ENTRY结构的地址获取所在的节点的地址的时候，有个地址偏移计算的过程。可以通过下面的一个典型的遍历链表的示例中看到：

for(p = my_list_head.Flink; p != &my_list_head.Flink; p = p->Flink)
{
    PMY_FILE_INFOR elem = CONTAINING_RECORD(p,MY_FILE_INFOR, list_entry);
    {
        // 在这里做需要做的事…
    }
}

其中的CONTAINING_RECORD是一个WDK中已经定义的宏，作用是通过一个LIST_ENTRY结构的指针，找到这个结构所在的节点的指针。定义如下：

#define CONTAINING_RECORD(address, type, field) ((type *)( \
        (PCHAR)(address) - \
        (ULONG_PTR)(&((type *)0)->field)))

从上面的代码中可以总结如下的信息：

• LIST_ENTRY中的数据成员Flink指向下一个LIST_ENTRY。
• 整个链表中的最后一个LIST_ENTRY的Flink不是空。而是指向头节点。
• 得到LIST_ENTRY之后，要用CONTAINING_RECORD来得到链表节点中的数据。