编码基础一：侵入式链表

一、简介概述

1、普通链表数据结构

每个节点的next指针指向下一个节点的首地址。这样会有如下的限制：

• 一条链表上的所有节点的数据类型需要完全一致。
• 对某条链表的操作如插入，删除等只能对这种类型的链表进行操作，如果链表的类型换了，就要重新再封装出一套一样的操作，泛化能力差

2、侵入式链表数据结构

 节点的链接成员指向的是下一个节点的链接成员。使用侵入式链表的好处是：

• 节点类型无需一致，只需要成员节点（element_t）包含list_node_t成员即可
• 泛化能力强，所有链表的操作方式均可统一；

typedef struct list_node list_node_t;//链表节点结构体定义
typedef struct list_node {list_node_t* prev;list_node_t* next;
} list_node_t;//链表结构体定义
typedef struct list {int list_size;list_node_t head;
} list_t;//链表成员结构体定义，重点需要包含list_node_t定义
typedef struct element {list_node_t list_node;int  element_type;int  element_size;char element_data[1];
} element_t;

二、详细介绍

侵入式链表中的节点只有地址信息，能够访问节点上的数据成员变量，主要靠两个核心函数： 

• 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）宏作用

计算结构体成员相对于结构体的偏移

3）参数说明

• type：      结构体类型
• member：结构体成员

4）原理分析

偏移 = 成员地址 - 结构体地址，若结构体地址为0，则偏移 = 成员地址；

5）应用示例

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));//打印结果
offset: 0 16 20

2、container_of

1）宏原型

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

2）宏作用

     通过结构体的成员，结构体成员的地址以及结构体的类型来获取结构体的首地址。

3）参数说明

•     ptr：         结构体成员的地址
•     type：      结构体类型
•     member：结构体成员

4）原理分析

      结构体首地址 = 成员地址 - 成员偏移，成员偏移通过offsetof宏求出；

5）应用示例

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小节，介绍的节点类型无需一致，只需要成员节点（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;
}