这是 Linux 内核中使用的一种链表. 通过将链表节点插入到结构体当中, 来让结构体获得链表的能力

比如下面这个结构体:

struct ipaddr {
    char address[45];
}

假设有一个链表节点:

struct list {
    struct list *next;
 };

将其插入到结构体:

struct ipaddr {
    char address[45];
    struct list blacklist;
}

在插入元素时, 只需要将 blacklist 成员的地址加入链表即可

将 struct list *blacklist 放在末尾, 这样在获取某个节点的时候, 可以通过减去 blacklist 的地址偏移量来获得原本的结构体指针

这样的实现就完全脱离了数据本身, 并不依赖外层结构体中存储的业务数据

可以嵌入多个链表节点成员让一个对象可以同时属于多个链表, 并且可通过变量名来标识:

struct ipaddr {
    char address[45];
    struct list *blacklist;
    struct list *vistorlist
}

实现

在这个设计中, 链表不获取所有权, 所有权和生命周期相关问题交给使用者管理

首先实现一个基本的结构体:

struct list_head {
    struct list_head *prev;
    struct list_head *next;
 };

以此来构建一个双向链表

然后实现添加的函数:

static inline void list_add(struct list_head *prev, struct list_head *next,
                             struct list_head *_new) {
     prev->next = _new;
     _new->prev = prev;
     _new->next = next;
     next->prev = _new;
 }
 
static inline void list_add_tail(struct list_head *head,
                                  struct list_head *_new) {
     list_add(head->prev, head, _new); // 这里 head->prev 指向的就是末尾节点
}

接下来实现获取节点的函数, 这是这个实现的重点:

/**
  * 获取 MEMBER 在 TYPE 这个结构体中的地址偏移量. 
  * ((size_t)&((TYPE *)0)->MEMBER 会由编译器以 0 为基址推导出 MEMBER 的地址偏移量, 不会发生实际的内存访问
  */
 #define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
 
 /**
  * ptr 是要传入的 node 指针, 将 node 的地址 减去 member 在 type 结构体中的偏移量之后,
  * 即可算出原本结构体的地址
  * 
  * 这里将指针转换为 (char *) 再进行计算的原因是:
  * offsetof() 返回的是以字节为单位的偏移量, 而 C 语言中的指针算术
  * 是以指针所指向类型的大小为步长进行的. 由于 sizeof(char) == 1,
  * 使用 char * 可以保证按字节进行地址计算, 从而得到正确的结果
  */
 #define container_of(ptr, type, member)                    \
     ({                                                     \
         const typeof(((type *)0)->member) *__mptr = (ptr); \
         (type *)((char *)__mptr - offsetof(type, member)); \
     })
 
 #define list_entry(ptr, type, member) container_of(ptr, type, member)
 
 #define list_for_each_entry(pos, head, member)                 \
     for (pos = list_entry((head)->next, typeof(*pos), member); \
          &pos->member != (head);                               \
          pos = list_entry(pos->member.next, typeof(*pos), member))
 
 /**
  * Linux 中没有这个实现
  */
 #define list_get(head, type, member, index)       \
     ({                                            \
         type *_pos = NULL;                        \
         type *_result = NULL;                     \
         int _i = 0;                               \
         list_for_each_entry(_pos, head, member) { \
             if (_i++ >= (index)) {                \
                 _result = _pos;                   \
                 break;                            \
             }                                     \
         }                                         \
         _result;                                  \
     })

使用示例

#define MAX_IP_LENGTH 45

enum VERSION {
    IPV4 = 0x00,
    IPV6 = 0x01,
};
 
struct ipaddr {
    char address[MAX_IP_LENGTH];
    enum VERSION version;
};
 
struct ipaddr_node {
    struct ipaddr ipaddr;
    struct list_head blacklist;
};
 
int main() {
    struct list_head blacklist = { &blacklist, &blacklist };
 
    struct ipaddr_node black1 = { { "10.168.12.10", IPV4 } };
    struct ipaddr_node black2 = { { "101.162.12.35", IPV4 } };
    struct ipaddr_node black3 = { "35.13.52.15", IPV4 };
 
    list_add_tail(&blacklist, &black1.blacklist);
    list_add_tail(&blacklist, &black2.blacklist);
    list_add_tail(&blacklist, &black3.blacklist);
 
    struct ipaddr_node *node1 = list_get(&blacklist, struct ipaddr_node, blacklist, 0);
    struct ipaddr_node *node2 = list_get(&blacklist, struct ipaddr_node, blacklist, 1);
    struct ipaddr_node *node3 = list_get(&blacklist, struct ipaddr_node, blacklist, 2);
    
    printf("%s\n", node1->ipaddr.address);
    printf("%s\n", node2->ipaddr.address);
    printf("%s\n", node3->ipaddr.address);
    
    return 0;
}