一、侵入式鏈表

侵入式鏈表讓結構體包含一個成員變量，該成員變量是一個通用的鏈表結點。普通的單鏈表的結點鏈接域存的是下一個結點的內存首地址，而侵入式單鏈表的結點鏈接域存的是下一個結點的鏈接域成員變量的內存首地址。

typedef struct list_s {

??????? struct list_s *next;

} list_t;

typedef struct foo_s {

??????? int???? data;

??????? list_t? link;

} foo_t;

下面給出一個最簡單的侵入式單鏈表實現。

1. list.h

?1 #ifndef _LIST_H

?2 #define _LIST_H

?3

?4 #ifdef? __cplusplus

?5 extern “C” {

?6 #endif

?7

?8 /**

?9 ?* offsetof – offset of a structure member

10 ?* @TYPE:?????? the type of the struct.

11 ?* @MEMBER:???? the name of the member within the struct.

12? */

13 #define offsetof(TYPE, MEMBER) ((size_t)(&(((TYPE *)0)->MEMBER)))

14

15 /**

16 ?* container_of – cast a member of a structure out to the containing structure

17 ?* @ptr:??????? the pointer to the member.

18 ?* @type:?????? the type of the container struct this is embedded in.

19 ?* @member:???? the name of the member within the struct.

20 ?*

21? */

22 #define container_of(ptr, type, member) ({????????????????????? \

23???????? const typeof( ((type *)0)->member ) *__mptr = (ptr);??? \

24???????? (type *)( (char *)__mptr – offsetof(type, member) );})

25

26 typedef struct list_s {

27???????? struct list_s *next;

28 } list_t;

29

30 typedef void (*list_handler_t)(void *arg);

31

32 extern void list_init(list_t **head, list_t *node);

33 extern void list_fini(list_t *head, list_handler_t fini);

34 extern void list_show(list_t *head, list_handler_t show);

35

36 #ifdef? __cplusplus

37 }

38 #endif

39

40 #endif /* _LIST_H */

2. list.c

?1 /*

?2 ?* Generic single linked list implementation

?3? */

?4 #include

?5 #include “list.h”

?6

?7 void

?8 list_init(list_t **head, list_t *node)

?9 {

10???????? static list_t *tail = NULL;

11

12???????? if (*head == NULL) {

13???????????????? *head = tail = node;

14???????????????? return;

15???????? }

16

17???????? tail->next = node;

18???????? tail = node;

19???????? node->next = NULL;

20 }

21

22 void

23 list_show(list_t *head, list_handler_t show)

24 {

25???????? for (list_t *p = head; p != NULL; p = p->next)

26???????????????? show(p);

27 }

28

29 void

30 list_fini(list_t *head, list_handler_t fini)

31 {

32???????? list_t *p = head;

33???????? while (p != NULL) {

34???????????????? list_t *q = p;

35???????????????? p = p->next;

36???????????????? fini(q);

37???????? }

38 }

延伸閱讀：

二、侵入式的好處

一般來說，大家都會優先選擇使用非侵入式的實現。因為侵入式實現需要將一些邏輯耦合到業務代碼中，因此為人所不喜。但是在背景介紹中提到的場景下，侵入式實現有顯著的好處，從而使得侵入式實現被廣泛的使用。我們在此不再強調侵入式與非侵入式的區別，主要考慮一下侵入式鏈表的優勢有哪些。

更好的 Data Locality

std::list?在遍歷的過程中還需要對?T*?進行解引用才能訪問?T?內部的數據。但是侵入式鏈表的?next?和?T?內部的數據是放在一起的，因此無需額外的解引用。而且由于內存 layout 就是在一起的，所以也會獲得更好的 Data Locality。

更友好的 API

對于侵入式鏈表，我們拿到數據就可以將這個節點從鏈表中摘除，而無需再去定位其 iterator，然后再去找到對應的容器 erase 這個 iterator。

脫離容器進行生命周期管理

最主要的應用場景是同一份對象需要在多個容器中共享，例如在背景介紹中提到的實現 LRU 的場景，又例如需要將同一份數據加入多個鏈表中。因此侵入式鏈表需要用戶自己管理數據節點生命周期的特性在這里就成為了一個優點。