UEFI开发学习11 – 使用双向链表

前言

双向链表在UEFI的代码中是很常见的，如在BdsBoot.c中用于存储引导菜单选项。如果只是作存储，那为什么不用数组而用双向链表呢？

我们知道，数组在定义的时候必须给定一个长度，定义完后便是一个固定的大小了，假如我还需要往其中再添加数据怎么办呢？或者定义的数组太大了，实际上并没有使用完，那岂不是造成资源浪费？C语言中是没有可变大小数组的，这时候链表的作用便显现出来了，因为链表的长度是可变的，存储多大的数据都可以，也可以很方便的进行增删改查。

什么是双向链表？

首先要从单向链表说起，学过C语言的应该都不陌生了,简单说一下，单向链表是一串带有指针成员的结构体序列，每个结构体中的地址指针用于指向结构体的首地址，这样就可通过当前结构体中的指针访问另一个结构体的数据了，示意图如下：

单向链表的缺点就是只能从当前节点访问下一个节点，是无法访问上一个节点的。双向链表便可以做到这一点，它在结构体增加了一个指针，用与存储上一个节点的地址，如下图：

使用双向链表

EDKII的代码中，已经定义好双向链表这个结构体了，在自己定义的结构体中加入这个数据类型即可：

///
/// LIST_ENTRY structure definition.
///
typedef struct _LIST_ENTRY LIST_ENTRY;

///
/// _LIST_ENTRY structure definition.
///
struct _LIST_ENTRY {
  LIST_ENTRY  *ForwardLink;
  LIST_ENTRY  *BackLink;
};

1.定义结构体

typedef struct {
    LIST_ENTRY Link;
    UINTN Data;
} TESTLIST;

2.初始化链表头，使其前后指针都指向自己的首地址，这里直接调用库函数即可：

InitializeListHead(&ListHead.Link);

示意图可表示为：

3.插入新节点，可选择从头插入或从尾部插入，以从尾部插入为例：

InsertTailList(&ListHead.Link, &Node1.Link);  // 从尾部插入

示意图可表示为：

这里可看到，头节点的back指针总是指向尾节点的地址；尾节点的forward指针总是指向头节点的地址。

4.获取节点信息

1) . 先获取第一个节点：

Node = (TESTLIST*)GetFirstNode(&ListHead.Link);

2).遍历所有节点：

while (!IsNull(&ListHead.Link, &Node->Link))
{
    Print(L"LIST DATA: %d\n\r", Node->Data);
    Node = (TESTLIST*)GetNextNode(&ListHead.Link, &Node->Link);
}

Note：获取上一个节点可使用GetPrevious()函数。

5.完整代码:

/** @file
    A simple, basic, EDK II native, "hello" application to verify that
    we can build applications without LibC.

    Copyright (c) 2010 - 2011, Intel Corporation. All rights reserved.<BR>
    This program and the accompanying materials
    are licensed and made available under the terms and conditions of the BSD License
    which accompanies this distribution. The full text of the license may be found at
    http://opensource.org/licenses/bsd-license.

    THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
    WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
**/
#include  <Uefi.h>
#include  <Library/UefiLib.h>
#include  <Library/ShellCEntryLib.h>

typedef struct {
    LIST_ENTRY Link;
    UINTN Data;
} TESTLIST;

int main(
  IN int Argc,
  IN char **Argv
)
{
    TESTLIST ListHead, Node1, Node2, Node3, * Node;

    Node1.Data = 13;
    Node2.Data = 14;
    Node3.Data = 15;

    InitializeListHead(&ListHead.Link);

    InsertTailList(&ListHead.Link, &Node1.Link);
    InsertTailList(&ListHead.Link, &Node2.Link);
    InsertTailList(&ListHead.Link, &Node3.Link);

    Node = (TESTLIST *) GetFirstNode (&ListHead.Link);

    while (!IsNull(&ListHead.Link, &Node->Link))
    {
        Print(L"LIST DATA: %d\n\r", Node->Data);
        Node = (TESTLIST*)GetNextNode(&ListHead.Link, &Node->Link);
    }
    
    return 0;
}

代码

https://gitee.com/ay123net/uefistudy