企业官网建设流程全解析

链表知识点总结

1. 什么是链表

链表是一种线性数据结构，元素通过指针串联，不像数组那样在内存里连续排列。

数组（连续内存）： [0] [1] [2] [3] [4] 链表（离散内存）： node_A ─→ node_B ─→ node_C ─→ NULL (有指针) (有指针) (有指针)

2. Linux 内核链表——双向环形链表

结构体定义

structlist_head{structlist_head*next;// 指向下一个节点structlist_head*prev;// 指向上一个节点};

环形结构

┌──────────────────────────────────┐ ↓ │ head ─→ node1 ─→ node2 ─→ node3 ─→ head head ←─ node1 ←─ node2 ←─ node3 ←─ head ↑ │ └──────────────────────────────────┘

头节点的prev指向最后一个节点，最后一个节点的next指向头节点——环形。遍历时从头走到尾再回到头。

空链表

INIT_LIST_HEAD(head);

head.next = &head head.prev = &head

自己指向自己，表示空链表。

3. 链表节点 vs 链表头

链表头是一个特殊的 list_head，用来标识链表从哪里开始。

链表节点是嵌入在数据结构体中的 list_head 字段。

在 SPI 中有两种用法：

用法一：链表节点嵌入在 message 里，作为 master->queue 的一个元素

structspi_message{structlist_headqueue;// ← 这是"节点"，不是链表头// ...};structspi_master{structlist_headqueue;// ← 这是"链表头"// ...};

master->queue（链表头） ├── msgA.queue ← 节点 ├── msgB.queue ← 节点 └── msgC.queue ← 节点

用法二：链表头嵌入在 message 里，用来串 transfer

structspi_message{structlist_headtransfers;// ← 这是"链表头"，下面挂 transfer// ...};structspi_transfer{structlist_headtransfer_list;// ← 节点// ...};

msgA.transfers（链表头，跟 master->queue 无关） ├── t1.transfer_list ← 节点 ├── t2.transfer_list ← 节点 └── t3.transfer_list ← 节点

4. 常用操作

初始化链表头

INIT_LIST_HEAD(&master->queue);

判断链表是否为空

list_empty(&master->queue);

返回非零表示空链表（head->next == head）。

加入到尾部

list_add_tail(&msg->queue,&master->queue);

把 msgA 的 queue 节点加入到 master->queue 链表尾部。

执行前：head ─→ msgB 执行后：head ─→ msgB ─→ msgA

取第一个节点

list_first_entry(&master->queue,structspi_message,queue);

取链表头下一个节点，然后用container_of反推出外层结构体。

从链表中删除

list_del_init(&msg->queue);

修改前后节点的指针，把自己从链表中摘除，然后把自己初始化成空链表状态。

staticinlinevoidlist_del_init(structlist_head*entry){__list_del(entry->prev,entry->next);// 摘除INIT_LIST_HEAD(entry);// 自己指向自己}

摘除前： head ─→ msgA ─→ msgB ─→ msgC ─→ head 摘除 msgA 后： head ─────────→ msgB ─→ msgC ─→ head msgA.next = msgA.prev = &msgA (安全状态)

遍历链表

structspi_message*msg;list_for_each_entry(msg,&master->queue,queue){// 遍历 master->queue 链表上的所有 message}

宏展开后等价于：

for(pos=list_first_entry(head,type,member);&pos->member!=(head);pos=list_next_entry(pos,member))

从头开始，走到回到头为止。

5. container_of——从节点反推结构体

这是内核链表的精髓。链表节点list_head本身不存数据，它只是嵌入在数据结构里的一个字段。要拿到数据，必须从节点地址反推出整个结构体的地址。

#definecontainer_of(ptr,type,member)({\consttypeof(((type*)0)->member)*__mptr=(ptr);\(type*)((char*)__mptr-offsetof(type,member));})

原理：用member在结构体中的偏移量，减去这个偏移量，得到结构体的起始地址。

内存布局： |←────── struct spi_message ────────────────────────────→| msgA 起始地址 msgA 结束 │ │ ├─────────────────────────┬──────────────────────────────┤ │ 其他字段 │ queue 字段 │ │ │ next / prev │ └─────────────────────────┴──────────────────────────────┘ │ ↑ │ │ list_first_entry 拿到的地址（&msgA.queue） │ │ │←── offsetof(queue) ───→│ │ │ │←── container_of 返回 ──→│（&msgA.queue 地址减去 offset）

所以在 SPI 里：

// master->queue.next 是一个 struct list_head 地址// 它实际上是某个 message 里 queue 字段的地址// container_of 减去 queue 在 spi_message 中的偏移// 得到这个 message 的起始地址master->cur_msg=container_of(master->queue.next,structspi_message,queue);

6. 野指针

什么是野指针

野指针是指向已释放或无效内存的指针。访问野指针会导致不可预测的后果——可能读/写到了别人的内存。

链表中的野指针

list_del（不带_init）只是修改前后节点的指针把自己摘除，但不修改自己：

staticinlinevoid__list_del(structlist_head*prev,structlist_head*next){next->prev=prev;prev->next=next;}

摘除后，entry->next和entry->prev仍然指向之前的前后节点。此时如果误操作再次list_del这个节点：

list_del(&msg->queue);//第一次：摘除成功，但 msg->queue.next 和 prev 还是野指针list_del(&msg->queue);//第二次：__list_del 用野指针修改别人的内存 → 内存损坏

第一次 list_del 后： msgA.queue.next = &msgB.queue (指向链表中的一个有效节点——但其实 msgA 已经不在链表里了) msgA.queue.prev = &head (同上) 如果再 list_del： __list_del(msgA.queue.prev, msgA.queue.next) → 修改 head.next = msgB.queue (没问题) → 修改 msgB.queue.prev = &head (没问题) 但是，如果第二次 del 时的 prev/next 已经指向了已释放的内存？ 或者某个中间状态，prev/next 指向的节点已经不在链表里了？ 继续操作那些节点就会导致内存损坏。

list_del_init 解决了这个问题

staticinlinevoidlist_del_init(structlist_head*entry){__list_del(entry->prev,entry->next);INIT_LIST_HEAD(entry);// entry->next = entry->prev = &entry}

摘除后把自己设成"空"状态，再误操作list_del也只是对自己操作，不影响别人。

7. 链表在 SPI 中的两级嵌套

SPI 消息泵用链表实现了一个"二级队列"结构：

master->queue（链表头——存放所有待处理的 message） │ ├── msgA.queue（节点） │ └── msgA.transfers（链表头——存放这个 message 的所有 transfer） │ ├── t1.transfer_list（节点） │ ├── t2.transfer_list（节点） │ └── t3.transfer_list（节点） │ ├── msgB.queue（节点） │ └── msgB.transfers（链表头） │ ├── t1.transfer_list（节点） │ └── t2.transfer_list（节点） │ ├── msgC.queue（节点） │ ...

代码上的操作路径：

// 从 master->queue 链表取 messagemaster->cur_msg=list_first_entry(&master->queue,structspi_message,queue);// cur_msg 指向整个 spi_message 结构体// 访问它的 transfers 链表头，遍历 transferlist_for_each_entry(xfer,&master->cur_msg->transfers,transfer_list){master->transfer_one(master,master->cur_msg->spi,xfer);}

第一级通过queue节点找到 message，第二级通过transfers链表头找到每个 transfer。container_of是两级之间的桥梁——从queue节点的地址，反推出包含它的spi_message结构体，然后就可以访问transfers这个链表头了。