国产一区二区精品-国产一区二区精品久-国产一区二区精品久久-国产一区二区精品久久91-免费毛片播放-免费毛片基地

千鋒教育-做有情懷、有良心、有品質的職業教育機構

手機站
千鋒教育

千鋒學習站 | 隨時隨地免費學

千鋒教育

掃一掃進入千鋒手機站

領取全套視頻
千鋒教育

關注千鋒學習站小程序
隨時隨地免費學習課程

當前位置:首頁  >  技術干貨  > 侵入式鏈表什么意思?

侵入式鏈表什么意思?

來源:千鋒教育
發布人:xqq
時間: 2023-10-11 08:51:06 1696985466

一、侵入式鏈表

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

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 的場景,又例如需要將同一份數據加入多個鏈表中。因此侵入式鏈表需要用戶自己管理數據節點生命周期的特性在這里就成為了一個優點。

聲明:本站稿件版權均屬千鋒教育所有,未經許可不得擅自轉載。
10年以上業內強師集結,手把手帶你蛻變精英
請您保持通訊暢通,專屬學習老師24小時內將與您1V1溝通
免費領取
今日已有369人領取成功
劉同學 138****2860 剛剛成功領取
王同學 131****2015 剛剛成功領取
張同學 133****4652 剛剛成功領取
李同學 135****8607 剛剛成功領取
楊同學 132****5667 剛剛成功領取
岳同學 134****6652 剛剛成功領取
梁同學 157****2950 剛剛成功領取
劉同學 189****1015 剛剛成功領取
張同學 155****4678 剛剛成功領取
鄒同學 139****2907 剛剛成功領取
董同學 138****2867 剛剛成功領取
周同學 136****3602 剛剛成功領取
相關推薦HOT