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

前一篇文章《双向链表，还能这么实现》，介绍了双向链表如何彻底消除内部的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_elist
5
4
1
2
3

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