内嵌双向链表的设计与实现

实力程序员

关注

发布于: 2021 年 06 月 09 日

前一篇文章《双向链表，还能这么实现》，介绍了双向链表如何彻底消除内部的 NULL 指针，从而代码实现更加简洁，并且不增加任何额外的内存。

实际项目中，对双向链表的需求场景非常多，并且有很多变体的实现。今天介绍内嵌双向链表。先说说场景的需求：

双向链表的经典实现结构，如下图所示：

链表本身维护各个节点，业务使用者需要将自己的数据结构以指针的方式放入链接节点中。

这意味着，向链表增加一个数据，需要做两次内存分配：一次是链表节点自身的内存分配，另一次是业务数据结构的内存分配。

在一些对性能要求严苛的场景中，希望尽可能减少内存分配的次数。因此，我们希望将链表节点直接嵌入至业务的数据结构中，通过内嵌的链表节点，实现将多个业务数据结构链接成一个链表。

用下图展示一下这个需求：

上图用 elist 代表 embed list(内嵌链表)。链表的每个节点，都内嵌在业务的数据结构中，通过链表节点形成一个首尾相连的链表环。

链表中的业务数据结构，通常为同一类型，并且大小都是相同的。更严格的说，是链表节点相对业务数据结构开始地址的偏移是相同的。因此，elist 初始化时需要提供链表节点相对业务数据结构的偏移量，这样就能在业务数据结构和链表节点之间进行互相转换。

elist 的代码实现，如下：

// elist.h#ifndef ELIST_H#define ELIST_H
typedef struct elist_node_t {        struct elist_node_t* pprev;        struct elist_node_t* pnext;} elist_node_t;
typedef struct elist_t {        elist_node_t* ptail;        elist_node_t* phead;        int node_offset;} elist_t;
int elist_init(elist_t* plist, int node_offset);
int elist_push_tail(elist_t* plist, void* pdata);int elist_push_head(elist_t* plist, void* pdata);
void* elist_pop_tail(elist_t* plist);void* elist_pop_head(elist_t* plist);
#endif

复制代码

elist.c 的代码，如下：

// elist.c#include "elist.h"#include <stdlib.h>
int elist_init(elist_t* plist, int node_offset) {        plist->phead = (elist_node_t*)plist;        plist->ptail = (elist_node_t*)plist;        plist->node_offset = node_offset;        return 0;}
int elist_push_tail(elist_t* plist, void* pdata) {        // locate node        elist_node_t* pnode = (elist_node_t*)((char*)pdata + plist->node_offset);
        // tail node        elist_node_t* ptail = plist->ptail;
        // ring : insert as next node of the tail node        pnode->pnext = ptail->pnext;        ptail->pnext->pprev = pnode;        pnode->pprev = ptail;        ptail->pnext = pnode;
        return 0;}
int elist_push_head(elist_t* plist, void* pdata) {        // locate node        elist_node_t* pnode = (elist_node_t*)((char*)pdata + plist->node_offset);
        // head node        elist_node_t* phead = plist->phead;
        // ring : insert as prev node of the head node        pnode->pprev = phead->pprev;        phead->pprev->pnext = pnode;        pnode->pnext = phead;        phead->pprev = pnode;
        return 0;}
void* elist_pop_tail(elist_t* plist) {        if (plist->ptail == (elist_node_t*)plist) {     // empty                return NULL;        }
        // remove tail node from elist        elist_node_t* pnode = plist->ptail;        pnode->pprev->pnext = pnode->pnext;        pnode->pnext->pprev = pnode->pprev;
        // break links        pnode->pprev = pnode->pnext = pnode;
        return (char*)pnode - plist->node_offset;}
void* elist_pop_head(elist_t* plist) {        if (plist->phead == (elist_node_t*)plist) {     // empty                return NULL;        }
        // remove head node from elist        elist_node_t* pnode = plist->phead;        pnode->pprev->pnext = pnode->pnext;        pnode->pnext->pprev = pnode->pprev;
        // break links        pnode->pprev = pnode->pnext = pnode;
        return (char*)pnode - plist->node_offset;}

复制代码

测试程序 test_elist.c, 代码如下：

#include "elist.h"
#include <stdlib.h>#include <stdio.h>#include <stdint.h>#include <stddef.h>
typedef struct msg_t {        elist_node_t enode;        uint64_t msg_id;        // msg_content ...} msg_t;
int push_msg_to_tail(elist_t* plist, uint64_t msg_id);int push_msg_to_head(elist_t* plist, uint64_t msg_id);int pop_msg_from_tail(elist_t* plist);int pop_msg_from_head(elist_t* plist);
int main() {        elist_t list, *plist = &list;        int iret = elist_init(plist, offsetof(msg_t, enode));
        push_msg_to_tail(plist, 1);        push_msg_to_tail(plist, 2);        push_msg_to_tail(plist, 3);        push_msg_to_head(plist, 4);        push_msg_to_head(plist, 5);
        pop_msg_from_head(plist);        pop_msg_from_head(plist);        pop_msg_from_head(plist);        pop_msg_from_head(plist);        pop_msg_from_head(plist);        return 0;}
int push_msg_to_tail(elist_t* plist, uint64_t msg_id) {        msg_t* pmsg = (msg_t*)malloc(sizeof(*pmsg));        pmsg->msg_id = msg_id;        return elist_push_tail(plist, pmsg);}
int push_msg_to_head(elist_t* plist, uint64_t msg_id) {        msg_t* pmsg = (msg_t*)malloc(sizeof(*pmsg));        pmsg->msg_id = msg_id;        return elist_push_head(plist, pmsg);}
int pop_msg_from_tail(elist_t* plist) {        msg_t* pmsg = (msg_t*)elist_pop_tail(plist);        if (NULL == pmsg) {                return -1;        }
        printf("%lu\n", pmsg->msg_id);        free(pmsg);        return 0;}
int pop_msg_from_head(elist_t* plist) {        msg_t* pmsg = (msg_t*)elist_pop_head(plist);        if (NULL == pmsg) {                return -1;        }
        printf("%lu\n", pmsg->msg_id);        free(pmsg);		return 0;}

复制代码

运行 ./test_elist, 输出结果如下：

$ ./test_elist54123

复制代码

我的微信号 "实力程序员"，欢迎大家关注我。

发布于: 2021 年 06 月 09 日阅读数: 8

原文链接:【http://xie.infoq.cn/article/d16b67c8ee49498c3c19d1df2】。文章转载请联系作者。

实力程序员

关注

实力程序员，用实力说话！ 2021.05.24 加入

超过20年一线产品研发和技术管理的实力程序员

发布

暂无评论

创作场景

内嵌双向链表的设计与实现

实力程序员

评论