本文共 4747 字，大约阅读时间需要 15 分钟。

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

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

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

 

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

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

 

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

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

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

 

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

elist 的代码实现，如下：

// elist.h#ifndef ELIST_H#define ELIST_Htypedef 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 
   
    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 
   
    #include 
    
     #include 
     
      #include 
      
       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

 

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

转载地址：http://ktlsi.baihongyu.com/