一、簡介概述

1、普通鏈表數(shù)據(jù)結(jié)構(gòu)

每個節(jié)點的next指針指向下一個節(jié)點的首地址。這樣會有如下的限制：

• 一條鏈表上的所有節(jié)點的數(shù)據(jù)類型需要完全一致。
• 對某條鏈表的操作如插入，刪除等只能對這種類型的鏈表進(jìn)行操作，如果鏈表的類型換了，就要重新再封裝出一套一樣的操作，泛化能力差

2、侵入式鏈表數(shù)據(jù)結(jié)構(gòu)

?節(jié)點的鏈接成員指向的是下一個節(jié)點的鏈接成員。使用侵入式鏈表的好處是：

• 節(jié)點類型無需一致，只需要成員節(jié)點（element_t）包含list_node_t成員即可
• 泛化能力強，所有鏈表的操作方式均可統(tǒng)一；

typedef struct list_node list_node_t;//鏈表節(jié)點結(jié)構(gòu)體定義
typedef struct list_node {list_node_t* prev;list_node_t* next;
} list_node_t;//鏈表結(jié)構(gòu)體定義
typedef struct list {int list_size;list_node_t head;
} list_t;//鏈表成員結(jié)構(gòu)體定義，重點需要包含list_node_t定義
typedef struct element {list_node_t list_node;int  element_type;int  element_size;char element_data[1];
} element_t;

二、詳細(xì)介紹

侵入式鏈表中的節(jié)點只有地址信息，能夠訪問節(jié)點上的數(shù)據(jù)成員變量，主要靠兩個核心函數(shù)：?

• offsetof
• container_of

1、offsetof

1）宏原型

#if defined _MSC_VER && !defined _CRT_USE_BUILTIN_OFFSETOF#ifdef __cplusplus#define offsetof(s,m)  \((::size_t)&reinterpret_cast<char const volatile&>((((s*)0)->m)))#else#define offsetof(s,m) ((size_t)&(((s*)0)->m))#endif
#else#define offsetof(s,m) __builtin_offsetof(s,m)
#endif

2）宏作用

計算結(jié)構(gòu)體成員相對于結(jié)構(gòu)體的偏移

3）參數(shù)說明

• type：? ? ? 結(jié)構(gòu)體類型
• member：結(jié)構(gòu)體成員

4）原理分析

偏移 = 成員地址 - 結(jié)構(gòu)體地址，若結(jié)構(gòu)體地址為0，則偏移 = 成員地址；

5）應(yīng)用示例

typedef struct element {list_node_t list_node;int  element_type;int  element_size;char element_data[1];
} element_t;printf("offset: %zd %zd %zd\r\n", offsetof(element_t, list_node), offsetof(element_t, element_type), offsetof(element_t, element_size));//打印結(jié)果
offset: 0 16 20

2、container_of

1）宏原型

#define container_of(ptr, type, member) \((type*)(((char*)((type*)(ptr))) - offsetof(type, member)))

2）宏作用

? ? ?通過結(jié)構(gòu)體的成員，結(jié)構(gòu)體成員的地址以及結(jié)構(gòu)體的類型來獲取結(jié)構(gòu)體的首地址。

3）參數(shù)說明

• ? ??ptr：? ? ? ? ?結(jié)構(gòu)體成員的地址
• ? ? type：? ? ? 結(jié)構(gòu)體類型
• ? ? member：結(jié)構(gòu)體成員

4）原理分析

? ? ??結(jié)構(gòu)體首地址 = 成員地址 - 成員偏移，成員偏移通過offsetof宏求出；

5）應(yīng)用示例

int main()
{element_t element, *p_element;element.element_type = 1234;element.element_size = 5678;p_element = container_of(&element.list_node, element_t, list_node);printf("p_element->element_type :%d p_element->element_size :%d\n", p_element->element_type, p_element->element_size);
}p_element->element_type :1234 p_element->element_size :5678

3、侵入式鏈表?

介紹到這里，就可以理解面前第一章第2小節(jié)，介紹的節(jié)點類型無需一致，只需要成員節(jié)點（element_t）包含list_node_t成員即可。我們只要知道list_node_t成員地址，就可以通過offsetof=>container_of獲取整個element_t的成員變量。

示例代碼如下：

#include "list.h"
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>void ListInit(list_t* list) {list->list_size = 0;ListNodeInit(&list->head);
}void ListAppend(list_t* list, list_node_t* node) {node->next = &list->head;node->prev = list->head.prev;node->prev->next = node;list->head.prev = node;list->list_size++;
}void ListRemove(list_t* list, list_node_t* node) {ListNodeDetach(node);ListNodeInit(node);list->list_size--;
}list_node_t* ListFirstGet(const list_t* list) {return !ListEmpty(list) ? list->head.next : NULL;
}list_node_t* ListLastGet(const list_t* list) {return !ListEmpty(list) ? list->head.prev : NULL;
}bool ListEmpty(const list_t* list) {return !ListEnlisted(&list->head);
}void ListNodeInit(list_node_t* node) {node->prev = node;node->next = node;
}void ListNodeDetach(list_node_t* node) {node->prev->next = node->next;node->next->prev = node->prev;
}bool ListEnlisted(const list_node_t* node) {return node->prev != node;
}list_t list_;int main()
{list_node_t* list_node = NULL;ListInit(&list_);for (int i = 0; i < 15; i++) {element_t* element = (element_t*)malloc(sizeof(element_t) + sizeof(AI_UPLOAD_ALL_INFO_T));element->element_type = i;element->element_size = sizeof(AI_UPLOAD_ALL_INFO_T);ListAppend(&list_, &element->list_node);printf("push element :%d queue_size :%d\n", element->element_type, list_.list_size);list_node = ListLastGet(&list_);element_t* element1 = GetListNode(list_node, element_t);printf("QueueLastGet element :%d queue_size :%d\n", element1->element_type, list_.list_size);}printf("list_size :%d\n", list_.list_size);while ((list_node = ListFirstGet(&list_)) != NULL) {element_t* element = GetListNode(list_node, element_t);printf("pop element :%d queue_size :%d\n", element->element_type, list_.list_size);ListRemove(&list_, list_node);}return 0;
}