一、侵入式鏈表

侵入式鏈表讓結(jié)構(gòu)體包含一個(gè)成員變量，該成員變量是一個(gè)通用的鏈表結(jié)點(diǎn)。普通的單鏈表的結(jié)點(diǎn)鏈接域存的是下一個(gè)結(jié)點(diǎn)的內(nèi)存首地址，而侵入式單鏈表的結(jié)點(diǎn)鏈接域存的是下一個(gè)結(jié)點(diǎn)的鏈接域成員變量的內(nèi)存首地址。

typedef struct list_s {

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

} list_t;

typedef struct foo_s {

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

??????? list_t? link;

} foo_t;

下面給出一個(gè)最簡單的侵入式單鏈表實(shí)現(xiàn)。

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 “l(fā)ist.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 }

延伸閱讀：

二、侵入式的好處

一般來說，大家都會優(yōu)先選擇使用非侵入式的實(shí)現(xiàn)。因?yàn)榍秩胧綄?shí)現(xiàn)需要將一些邏輯耦合到業(yè)務(wù)代碼中，因此為人所不喜。但是在背景介紹中提到的場景下，侵入式實(shí)現(xiàn)有顯著的好處，從而使得侵入式實(shí)現(xiàn)被廣泛的使用。我們在此不再強(qiáng)調(diào)侵入式與非侵入式的區(qū)別，主要考慮一下侵入式鏈表的優(yōu)勢有哪些。

更好的 Data Locality

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

更友好的 API

對于侵入式鏈表，我們拿到數(shù)據(jù)就可以將這個(gè)節(jié)點(diǎn)從鏈表中摘除，而無需再去定位其 iterator，然后再去找到對應(yīng)的容器 erase 這個(gè) iterator。

脫離容器進(jìn)行生命周期管理

最主要的應(yīng)用場景是同一份對象需要在多個(gè)容器中共享，例如在背景介紹中提到的實(shí)現(xiàn) LRU 的場景，又例如需要將同一份數(shù)據(jù)加入多個(gè)鏈表中。因此侵入式鏈表需要用戶自己管理數(shù)據(jù)節(jié)點(diǎn)生命周期的特性在這里就成為了一個(gè)優(yōu)點(diǎn)。