培纪的博客

培纪的博客

0%

List的详细解读

发表于 更新于 分类于
OpenHarmony软总线模块的List的详细解读

在上一篇文章里面围绕了LIST_FOR_EACH_SAFE这一个宏定义进行了讲解，在这一篇文章里面主要针对其关联的List结构体进行解读。

首先回顾一下List结构体的定义：

1
2
3
4
typedef struct List {
    struct List *prev;
    struct List *next;
} List;

显而易见的，这是一个带双指针的双向链表。

在该结构的定义下面，对应的定义了几个相关联的操作函数：

1
2
3
4
5
6
7
8
void ListInitHead(List *head);
void ListInsertHead(List *head, List *node);
void ListInsertTail(List *head, List *node);
void ListRemoveNode(List *node);
int ListIsEmpty(List *head);
List *ListGetFront(List *head);
List *ListPopFront(List *head);
int ListLength(const List *head);

接下来我们一一的对这些函数进行解读。

首先是ListInitHead：

1
2
3
4
5
void ListInitHead(List *head)
{
    head->next = head;
    head->prev = head;
}

这一个函数所作的功能非常简单，就是对某一个带头节点的双向链表进行初始化。

例如在communication_softbus_lite\authmanager\source\auth_interface.c的AddSessionKey函数里面：

1
2
3
4
5
6
7
if (g_sessionKeyList == NULL) {
    g_sessionKeyList = calloc(1, sizeof(List));
    if (g_sessionKeyList == NULL) {
        return -1;
    }
    ListInitHead(g_sessionKeyList);
}

先是在内存里面申请了一块内存（内存大小与List相关），然后再使用ListInitHead函数对其进行双向链表的初始化。

接下来是ListInsertHead，同样的，先看看这个函数的内容：

1
2
3
4
5
6
7
void ListInsertHead(List *head, List *node)
{
    node->next = head->next;
    node->next->prev = node;
    node->prev = head;
    head->next = node;
}

从函数命名和具体内容可以得知该函数是在双向链表从头部插入一个节点，具体如下图所示：

插入前：

ListInsertHead1

插入后：

ListInsertHead2

与之相类似的是在链表末尾插入一个节点ListInsertTail：

1
2
3
4
5
6
7
void ListInsertTail(List *head, List *node)
{
    node->prev = head->prev;
    node->prev->next = node;
    node->next = head;
    head->prev = node;
}

其示例图如下：

插入前：

ListInsertHead1

插入后：

ListInsertHead2

在增加之后的紧接着的是删除函数ListRemoveNode：

1
2
3
4
5
6
7
8
9
10
void ListRemoveNode(List *node)
{
    if (node == NULL) {
        return;
    }
    node->next->prev = node->prev;
    node->prev->next = node->next;
    node->next = NULL;
    node->prev = NULL;
}

在对输入参数进行检查之后，删除指定的节点。

例如我们需要删除Node2：

ListRemoveNode

下面是两个功能较为简单的ListIsEmpty和ListGetFront放在一块进行讲解：

1
2
3
4
5
6
7
8
9
int ListIsEmpty(List *head)
{
    return (head == head->next);
}

List *ListGetFront(List *head)
{
    return head->next;
}

ListIsEmpty的功能是判断该双向链表是否为空，其主要是判断该链表的头节点所指向的下一个节点是否仍是头节点，据此来判断链表是否为空。因为当链表为空时，该链表只剩下一个头节点，若next指针指向头节点自身即意味着链表除了头节点外再无别的节点了，即链表为空。

ListGetFront则是返回了该链表的第一个节点，即头节点next指针所指向的节点。

接下来的ListPopFront函数是用于弹出该链表的第一个节点：

1
2
3
4
5
6
7
8
9
10
11
List *ListPopFront(List *head)
{
    List *element = NULL;
    if (head == NULL || ListIsEmpty(head)) {
        return NULL;
    }

    element = head->next;
    ListRemoveNode(element);
    return element;
}

这个“弹出”的意思是将该节点从链表中断开，取下的意思。

其首先判断链表是否有效且是否为空，紧接着通过头节点找到第一个节点。使用函数ListRemoveNode将该节点从链表上取下来，并将指向该节点的指针返回给函数调用者。

同样的在communication_softbus_lite\authmanager\source\auth_interface.c的ReplaceOldSessionNode函数里就使用到了该函数：

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @description: 从g_sessionKeyList中取出第一个SessionKeyNode，并在赋予新值后插入到尾部
 * @param {int} fd
 * @param {int} index
 * @param {const struct hc_session_key} *session
 */
static int ReplaceOldSessionNode(int fd, int index, const struct hc_session_key *session)
{
    SessionKeyNode *node = (SessionKeyNode *)ListPopFront(g_sessionKeyList);
    if (node == NULL) {
        return -1;
    }

使用该函数将第一个节点取下，赋予新的内容后再将其“挂”回到链表上。

思考：为什么是取下之后重新复制，而不是将其free后重新申请一块内存呢？或许是因为这样做开销小一点？

最后一个函数是ListLength：

1
2
3
4
5
6
7
8
9
10
11
12
int ListLength(const List *head)
{
    int len = 0;
    List *pos = NULL;
    List *tmp = NULL;

    LIST_FOR_EACH_SAFE(pos, tmp, head) {
        len++;
    }

    return len;
}

简简单单的对链表的长度进行统计，这里还用到了上一篇文章所提及的LIST_FOR_EACH_SAFE这一个宏定义，感兴趣的可以去看一看。

链接：https://blog.hpjpw.com/2021/08/14/OpenHarmony/list_for_each_safe/