嵌入式C语言学习记录之-14~17day
嵌入式C语言学习打卡记录第14~17天 2025.02.28~03.03
一、链表
应用场景：比如在一个智能网关的场景中，需要具备动态管理子设备的功能，注册、添加、删除、获取数据等等。首先可能会想到使用数组来管理所有的子设备，但是数组方案存在一个问题，元素数量如何定义，不同环境部署的子设备数量是有差异的，太大会浪费内存，太小会导致子设备数量受限制。这时就需要一种按需分配的方案，首先就会想到指针和动态内存，当网关每检测到一个新的子设备时，就为这个子设备申请动态内存。但是又会出现一个新的问题，程序中如何遍历这些子设备对应的动态内存数据？各子设备对应的动态内存不像数组，内存布局是不连续的，所以需要找到一种方案能将这些动态内存串联起来，这就要用到链表数据结构了。链表原理：简单来说就是使用头一个内存块保存下一个内存块的首地址。
基于图中，设计数据结构：
struct TempHumiListNode_t
{
uint8_t id;
uint8_t humi;
float temp;
struct TempHumiListNode_t *next;
};
typedef struct TempHumiListNode_t TempHumiListNode;
为什么结构体能嵌套自己，编译不会报错吗？
如果成员是struct TempHumiListNode_t next;就会报错，因为编译器在解析这个成员时，结构体还没结束，不知道该为它分配多大内存空间；如果是*next，因为是指针类型，对于ARM32平台，编译器会固定分配4个字节内存空间，用于保存下个子设备对应的动态内存首地址。
如果要将动态内存的数据串联起来，还需要设计一个头部，这个头部不需要对应实际的子设备，只需要保存第一个设备的地址。
对于链表如何管理这些动态内存块，需要实现下面几个功能：
- 链表初始化（创建头结点）；
- 添加节点，当检测到新的子设备时，添加到链表尾部；
- 遍历链表节点；
- 删除节点，当检测到子设备下线时没从链表中删除。
1.1 链表初始化（创建头结点）；
TempHumiListNode *InitSensorList(void)
{
TempHumiListNode *header = (TempHumiListNode *)malloc(sizeof(TempHumiListNode));
if(header == NULL)
{
return NULL;
}
header->id = 0;
header->next = NULL;
return header;
}
static TempHumiListNode *g_header;
int main()
{
g_header = InitSensorList();
}
1.2添加节点，当检测到新的子设备时，添加到链表尾部；
static TempHumiListNode *g_header;
TempHumiListNode *FindTempHumiSensor(void)
{
TemHumiListNode *node = (TempHumiListNode *)malloc(sizeof(TempHumiListNode));
if(node == NULL)
{
return NULL;
}
static uint32_t id = 100;
node->id = id;
id--;
node->temp = 20.5f;
node->humi = 40;
return node;
}
int main()
{
g_header = InitSensorList();
while(1)
{
TempHumiListNode *node = FindTempHumiSensor();
AddSensorNode(g_header,node);
}
}
void AddSensorNode(TempHumiListNode *header,TempHumiListNode *node)
{
TempHumiListNode *current = header;
while(current->next != NULL)
{
current = current->next;
}
current->next = node;
node->next = NULL;
}
添加节点的另外一种方案（更好，在后续删除节点或双向循环链表中更实用）：
void AddSensorNode(TempHumiListNode *header,TempHumiListNode *node)
{
TempHumiListNode *prev = header;
TempHumiListNode *current = header->next;
while(current != NULL)
{
pre = current;
current = current->next;
}
current->next = node;
node->next = NULL;
}
1.3遍历链表节点。
void PrintTempHumiData(TempHumiListNode *header)
{
TempHumiListNode *current;
current = header->next;
if(current == NULL)
{
printf("List has no node\n");
}
while(current != NULL)
{
printf("\nSensor id:%d,temp=%.1f,humi=%d",
current->id,current->temp.current->humi);
current = current->next;
}
}
1.4删除节点
void DelSensorNode(TempHumiListNode *header,uint32_t id)
{
TempHumiListNode *prev = header;
TempHumiListNode *current = header->next;
while(current != NULL)
{
if(current->id == id)
{
break;
}
prev = current;
current = current->next;
}
if (current == NULL)
{
printf("Del Sensor %d failed,can not find it",id)
return;
}
prev->next = current->next;
free(current);
current = NULL;
}
二、双向循环链表
定义以下结构体：
typedef struct TempHumiListNode
{
uint8_t id;
uint8_t humi;
float temp;
struct TempHumiListNode *next;
struct TempHumiListNode *prev;
}TempHumiListNode;
双向循环链表，通过一个指针变量，就可以找到前向和后向节点，方便写程序；而且可以从任意节点开始遍历整个链表。
添加节点：其中oldNode表示添加在哪一个节点后面，newNode表示待添加节点
void AddNode(TempHumiListNode *oldNode,TempHumiListNode *newNode)
{
newNode->next = oldNode->next;
newNode->prev = oldNode;
oldNode->next->prev = newNode;
oldNode->next = newNode;
}
删除节点：
void DelNode(TempHumiListNode *node)
{
node->prev->next = node->next;
node->next->prev = node->prev;
}
void DelSensorNode(TempHumiListNode *header,uint32_t id)
{
TempHumiListNode *current = header->next;
while(current != header)
{
if(current->id == id)
{
break;
}
current = current->next;
}
if (current == header)
{
printf("Del Sensor %d failed,can not find it",id)
return;
}
DelNode(current);
free(current);
current = NULL;
}
三、通用链表
通用链表：如果有新的业务数据，需要有新的链表，就必须要定义新的接口函数，这样会使得代码冗余且易出错。
将通用链表嵌入到业务数据结构体中，作为一个成员使用：
typedef struct List
{
struct List *prev;
struct List *next;
}
typedef struct TempHumiSensor
{
uint8_t id;
uint8_t humi;
float temp;
List list;
}TempHumiSensor;
在常规双向循环链表中，next和prev指向的都是业务数据结构体的首地址。而通用链表，也是双向循环链表，next和prev指向的是业务数据结构体中list的首地址。
3.1通用链表初始化：
static List *g_tempHumiHeader;
void InitList (List *header)
{
header->next = header;
header->prev = header;
}
bool InitTempHumiSensor(void)
{
g_tempHumiHeader = (List *)malloc(sizeof(struct List));
if (g_tempHumiHeader == NULL)
{
return false;
}
InitList(g_tempHumiHeader);
return true;
}
3.2通用链表添加节点：
void AddNode(TempHumiListNode *oldNode,TempHumiListNode *newNode)
{
newNode->next = oldNode->next;
newNode->prev = oldNode;
oldNode->next->prev = newNode;
oldNode->next = newNode;
}
void AddNodeToTail(List *header,List *node)
{
AddNode(header->prev,node);
}
void AddTempHumiSensor(TempHumiSensor)
{
AddNodeToTail(g_tempHumiHeader,&sensor->list);
}
int main(void)
{
InitTempHumiSensor();
InitTempHumiSensor *sensor;
sensor = FindTempHumiSensor();
AddTempHumiSensor(sensor);
}
3.3通用链表遍历：
通用链表的数据块是由list成员串联起来的，它的next和prev指向的是业务数据结构体中list成员的首地址，所以需要根据list成员的首地址得到业务数据结构体的首地址，才能进一步访问其他成员打印数据。
已知结构体内某个成员的地址，如何计算得到该结构体变量的首地址？
typedef struct TempHumiSensor
{
uint8_t id;
uint8_t humi;
float temp;
}TempHumiSensor;
Linux中的container_of宏
#define offsetof(TYPE,MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
#define container_of(ptr,type,member) ({
const typeof(((type *)0)->member)*_mptr = (ptr);
(type *)((char *)_mptr - offsetof(type,member));
})
Linux中的container_of宏的作用是通过结构体内某个成员的地址和该成员的名字，以及结构体类型，找到该结构体变量的首地址。
思路：
1.可以先计算成员在结构体中的偏移量：
(uint32_t)&((TempHumiSensor *)0)->temp
(uint32_t)&((TempHumiSensor *)0)->temp将0转换为结构体类型指针，告诉编译器可以使用结构体类型去解释从0开始的地址空间了。&((TempHumiSensor *)0)->temp，访问结构体的成员，并获取成员的地址，最后(uint32_t)&((TempHumiSensor *)0)->temp将获得的地址转为数值，即是该成员的基于结构体首地址的偏移量。
2.根据已知的成员地址，再计算结构体变量的首地址：
(TempHumiSensor *)((uint8_t *)(&temp)-(uint32_t)&((TempHumiSensor *)0)->temp)
typedef struct List
{
struct List *prev;
struct List *next;
}List;
typedef struct
{
uint8_t id;
uint8_t humi;
float temp;
List list;
}TempHumiSensor;
int main(void)
{
TempHumiSensor sensor = {1,40,20.05f};
List *li = &sensor.list;
TempHumiSensor *p = (TempHumiSensor *)((uint8_t *)(li)-(uint32_t)&((TempHumiSensor *)0)->list);
printf("id = %d, humi = %d, temp = &.1f",p->id,p->humi,p->temp);
}
此时就可以为了代码简略，进行宏定义：
#define OFFSET_OF(typeName,memberName) ((uint32_t)&((typeName *)0)->memberName)
#define CONTAINER_OF(pMember,typeName,memberName)\
((typeName *)((uint8_t *)pMember - OFFSET_OF(typeName,memberName)))
有了上述得到数据块的首地址之后，则通用链表的遍历为：
void PrintTmepHumiSensor(void)
{
TmepHumiSensor *sensor = NULL;
for (sensor = CONTAINER_OF(g_tempHumiHeader->next,TmepHumiSensor，list);
&sensor->list != g_tempHumiHeader；
sensor = CONTAINER_OF(sensor->list.next,TempHumiSensor,list))
{
printf("");
}
}
3.4链表的删除：
void DelTmepHumiSensor(uint32_t id)
{
TmepHumiSensor *sensor = NULL;
for (sensor = CONTAINER_OF(g_tempHumiHeader->next,TmepHumiSensor，list);
&sensor->list != g_tempHumiHeader；
sensor = CONTAINER_OF(sensor->list.next,TempHumiSensor,list))
{
if(sensor->id == id)
{
DelNode(&sensor->list);
free(sensor);
sensor = NULL;
return;
}
}
printf("Can not find sensor %d",id);
}