linux内核hlist详解

时间: 2024-09-06 07:03:27 浏览: 42

Linux内核list&hlist;解读

3星 · 编辑精心推荐

目录 1. 前言 2 2. 通用宏 2 2.1. typeof 2 2.1.1. 定义 3 2.1.2. 用途 3 2.1.3. 示例 3 2.2. offset_of 3 2.2.1. 定义 3 2.2.2. 作用 3 2.2.3. 原理 3 2.2.4. 示例 3 2.3. container_of 4 2.3.1. 定义 4 2.3.2. 作用 4 2.3.3. 示例 4 2.4. prefetch 4 2.4.1. 定义 4 2.4.2. 作用 4 3. list 5 3.1. list结构 5 3.1.1. 定义 5 3.1.2. 作用 5 3.1.3. 解读 5 3.1.4. 示例 5 3.2. 遍历方向 6 3.3. list_entry 6 3.3.1. 定义 6 3.3.2. 作用 7 3.4. list_for_each 7 3.4.1. 定义 7 3.4.2. 作用 7 3.4.3. 示例 7 3.5. __list_for_each 8 3.5.1. 定义 8 3.5.2. 作用 8 3.6. list_for_each_prev 8 3.6.1. 定义 8 3.6.2. 作用 8 3.7. list_for_each_safe 8 3.7.1. 定义 8 3.7.2. 作用 9 3.7.3. 区别 9 3.7.4. 示例 9 3.8. list_for_each_entry 9 3.8.1. 定义 9 3.8.2. 作用 10 3.8.3. 区别 10 3.8.4. 完整示例 10 3.9. list_for_each_entry_safe 12 3.9.1. 定义 12 3.9.2. 作用 13 3.10. list_for_each_entry_reverse 13 3.10.1. 定义 13 3.10.2. 作用 13 3.11. list_for_each_entry_continue 13 3.11.1. 定义 13 3.11.2. 作用 13 3.11.3. 区别 13 3.12. list_for_each_safe_rcu 14 4. hlist（hash list） 14 4.1. hlist（hash list）结构 14 4.1.1. 简述 14 4.1.2. 定义 14 ### Linux内核list&hlist解读 #### 1. 前言 Linux 内核中广泛使用了链表作为数据结构，为了更好地管理和操作这些链表，内核提供了一系列宏来帮助开发者进行高效的数据处理。本文将详细介绍 Linux 内核中的两种主要链表结构：list 和 hlist，并解释与之相关的宏及其用法。 #### 2. 通用宏 ##### 2.1. typeof **2.1.1. 定义** `typeof` 并不是一个宏，而是 GCC 的一个内建操作符，用于获取变量的类型。 **2.1.2. 用途** 通过 `typeof` 可以获取某个变量的类型，进而定义其他具有相同类型的变量。 **2.1.3. 示例** ```c int m = 1; typeof(m) n = m; // 等同于 int n = m; ``` ##### 2.2. offset_of **2.2.1. 定义** `offset_of` 用于计算结构体中某成员相对于结构体起始位置的偏移量。 ```c #define offsetof(type, member) \ ((size_t)&((type*)0)->member) ``` **2.2.2. 作用** 计算结构体 `type` 中指定成员 `member` 在该结构体中的偏移量。 **2.2.3. 原理** `(type*)0` 创建了一个类型为 `type` 的指针，其地址值为 `0x0`。`&((type*)0)->member` 获取到成员 `member` 的地址，再减去结构体的起始地址，即得到了成员 `member` 的偏移量。 **2.2.4. 示例** 假设有一个结构体 `struct node`，其中包含一个成员 `int value`。 ```c struct node { int value; }; ``` 可以通过 `offsetof(struct node, value)` 来计算 `value` 成员的偏移量。 ##### 2.3. container_of **2.3.1. 定义** `container_of` 用于从指向结构体成员的指针反向找到指向整个结构体的指针。 ```c #define container_of(ptr, type, member) \ ((type *)((char *)(ptr) - offsetof(type, member))) ``` **2.3.2. 作用** 通过已知的结构体成员指针 `ptr`、结构体类型 `type` 和成员名 `member`，可以反向获取指向整个结构体的指针。 **2.3.3. 示例** 假设有一个结构体 `struct node`，包含一个链表节点 `struct list_head node_list`。 ```c struct node { struct list_head node_list; int data; }; struct node *node_ptr = container_of(list_head_ptr, struct node, node_list); ``` 这里 `list_head_ptr` 是指向 `struct node` 中 `node_list` 成员的指针，`node_ptr` 即是指向整个 `struct node` 结构体的指针。 ##### 2.4. prefetch **2.4.1. 定义** `prefetch` 用于对内存访问进行预取操作。 ```c __builtin_prefetch(const void *addr, int rw, int locality); ``` **2.4.2. 作用** 通过预测后续内存访问，提前加载数据到缓存中，以减少延迟。 #### 3. list ##### 3.1. list结构 **3.1.1. 定义** `list` 是一种双向循环链表，每个节点包含两个指针，分别指向其前驱和后继节点。 ```c struct list_head { struct list_head *next, *prev; }; ``` **3.1.2. 作用** `list` 结构提供了灵活的插入和删除操作，且不需要额外的内存分配。 **3.1.3. 解读** 每个 `list_head` 结构都包含了两个指针，通过这些指针可以快速地在链表中遍历。 **3.1.4. 示例** 创建一个简单的 `list_head` 实例： ```c struct list_head my_list; INIT_LIST_HEAD(&my_list); ``` ##### 3.2. 遍历方向在遍历链表时，可以从前向后或者从后向前遍历。 ##### 3.3. list_entry **3.3.1. 定义** `list_entry` 用于从指向链表节点的指针转换为指向包含该节点的结构体的指针。 ```c #define list_entry(ptr, type, member) \ container_of(ptr, type, member) ``` **3.3.2. 作用** 结合 `container_of` 使用，使得从指向链表节点的指针转换为指向包含该节点的结构体指针变得简单。 #### 3.4. list_for_each **3.4.1. 定义** `list_for_each` 用于遍历整个链表。 ```c #define list_for_each(pos, head) \ for (pos = (head)->next; pos != (head); pos = pos->next) ``` **3.4.2. 作用** 遍历整个链表，`pos` 指向当前节点。 **3.4.3. 示例** 遍历一个链表并打印每个节点的数据： ```c struct list_head *pos, *head; // 初始化链表... for (pos = head->next; pos != head; pos = pos->next) { printf("Node data: %d\n", pos->data); } ``` ##### 3.5. __list_for_each **3.5.1. 定义** `__list_for_each` 是 `list_for_each` 的内部实现。 ```c #define __list_for_each(pos, head) \ for (pos = (head)->next; pos && (pos != (head)); pos = pos->next) ``` **3.5.2. 作用** 用于内部遍历链表，与 `list_for_each` 功能相似但更底层。 ##### 3.6. list_for_each_prev **3.6.1. 定义** `list_for_each_prev` 用于反向遍历链表。 ```c #define list_for_each_prev(pos, head) \ for (pos = (head)->prev; pos != (head); pos = pos->prev) ``` **3.6.2. 作用** 从链表尾部开始，向前遍历整个链表。 #### 3.7. list_for_each_safe **3.7.1. 定义** `list_for_each_safe` 提供了一种安全的遍历链表的方法，即使在遍历过程中删除了节点也不会出现问题。 ```c #define list_for_each_safe(pos, n, head) \ for (pos = (head)->next, n = pos->next; pos != (head); \ pos = n, n = pos->next) ``` **3.7.2. 作用** 安全地遍历整个链表，即使在遍历过程中删除了节点也不会导致链表破坏。 **3.7.3. 区别** 相比于 `list_for_each`，`list_for_each_safe` 多了一个额外的指针 `n` 来保存下一个节点，以防止在删除当前节点时丢失对下一个节点的引用。 **3.7.4. 示例** 遍历一个链表并删除某些节点： ```c struct list_head *pos, *n, *head; // 初始化链表... for (pos = head->next, n = pos->next; pos != head; pos = n, n = pos->next) { if (pos->data == some_condition) { list_del(pos); } } ``` #### 3.8. list_for_each_entry **3.8.1. 定义** `list_for_each_entry` 用于遍历链表，并自动转换为指向包含该节点的结构体的指针。 ```c #define list_for_each_entry(pos, head, member) \ for (pos = list_entry((head)->next, typeof(*pos), member); \ &pos->member != (head); \ pos = list_entry(pos->member.next, typeof(*pos), member)) ``` **3.8.2. 作用** 在遍历链表的同时，通过 `list_entry` 自动将链表节点指针转换为指向包含该节点的结构体的指针。 **3.8.3. 区别** 相比于 `list_for_each`，`list_for_each_entry` 直接提供了指向结构体的指针，简化了代码。 **3.8.4. 完整示例** 遍历一个链表并打印每个节点的数据： ```c struct node { struct list_head node_list; int data; }; struct node *pos, *head; // 初始化链表... for (pos = list_entry(head->next, struct node, node_list); &pos->node_list != head; pos = list_entry(pos->node_list.next, struct node, node_list)) { printf("Node data: %d\n", pos->data); } ``` #### 3.9. list_for_each_entry_safe **3.9.1. 定义** `list_for_each_entry_safe` 提供了安全的遍历链表的方式，并能同时转换为指向结构体的指针。 ```c #define list_for_each_entry_safe(pos, n, head, member) \ for (pos = list_entry((head)->next, typeof(*pos), member); \ &pos->member != (head); \ pos = n, n = list_entry(pos->member.next, typeof(*pos), member)) ``` **3.9.2. 作用** 类似于 `list_for_each_safe`，但在遍历的同时还提供了指向结构体的指针。 #### 3.10. list_for_each_entry_reverse **3.10.1. 定义** `list_for_each_entry_reverse` 用于反向遍历链表，并转换为指向结构体的指针。 ```c #define list_for_each_entry_reverse(pos, head, member) \ for (pos = list_entry((head)->prev, typeof(*pos), member); \ &pos->member != (head); \ pos = list_entry(pos->member.prev, typeof(*pos), member)) ``` **3.10.2. 作用** 从链表尾部开始，向前遍历整个链表，同时提供了指向结构体的指针。 #### 3.11. list_for_each_entry_continue **3.11.1. 定义** `list_for_each_entry_continue` 用于继续遍历链表。 ```c #define list_for_each_entry_continue(pos, head, member) \ for (pos = list_entry(pos->member.next, typeof(*pos), member); \ &pos->member != (head); \ pos = list_entry(pos->member.next, typeof(*pos), member)) ``` **3.11.2. 作用** 从当前位置开始继续遍历链表，通常用于链表中已经有一个起点的情况。 **3.11.3. 区别** 与 `list_for_each_entry` 类似，但允许从链表中的任意位置开始遍历。 #### 3.12. list_for_each_safe_rcu **3.12.1. 定义** `list_for_each_safe_rcu` 是 `list_for_each_safe` 的 RCU 版本。 ```c #define list_for_each_safe_rcu(pos, n, head, lock) \ for (pos = (head)->next, n = pos->next; pos != (head); \ pos = n, n = pos->next) \ rcu_read_lock(); ``` **3.12.2. 作用** 安全地遍历链表，支持 RCU 读取锁，适用于并发环境下的链表遍历。 #### 4. hlist（hash list） ##### 4.1. hlist（hash list）结构 **4.1.1. 简述** `hlist` 是一种基于哈希表的链表结构，用于高效地存储和查找数据。 **4.1.2. 定义** `hlist` 结构通常由哈希表和链表节点组成，哈希表负责根据键值快速定位到链表，链表则用于存储具体的数据。 ```c struct hlist_head { struct hlist_node **first; }; struct hlist_node { struct hlist_node *next, **pprev; struct hlist_node *next_this_hash; }; ``` **总结** 本文详细介绍了 Linux 内核中的 `list` 和 `hlist` 数据结构以及相关的宏函数，这些宏函数提供了方便快捷的方式来管理链表，极大地提高了开发效率。理解这些宏的含义及使用方法对于深入学习 Linux 内核源码至关重要。

在Linux内核中，hlist（Hashed List）是一种用于快速查找的数据结构，它是链表的一种变体，特别适合于哈希表的实现。hlist通过减少链表中的节点数来优化性能，特别是在处理大量元素时，能够减少遍历的开销。 hlist的主要特点包括： 1. 节省空间：传统的链表每个节点都包含指向下一个节点的指针，而hlist节点利用存储空间允许的情况下，可以将多个hlist节点放入一个存储块中。这样，当链表中没有很多元素时，可以只用一个存储块，从而减少内存分配的数量。 2. 双向链接：hlist节点包括两个指针，一个指向前一个节点，一个指向后一个节点，但不同于传统的双向链表，hlist的“前一个节点”指针在某些情况下可以不用，以节省空间。 3. 哈希表适配：hlist特别设计用来与哈希表一起使用。在哈希表的每个桶（bucket）中，可以通过hlist高效地存储和检索多个相同哈希值的元素。 hlist的节点定义如下： ```c struct hlist_head { struct hlist_node *first; }; struct hlist_node { struct hlist_node *next, **pprev; }; ``` 在使用hlist时，一个hlist_head结构作为链表的头部，hlist_node作为链表的节点。与普通链表不同的是，hlist_node中的`pprev`是一个指向next指针的指针，这样可以实现对链表中间节点的快速删除。 hlist的常见操作包括插入、删除、遍历等，这些操作都经过优化以适应哈希表的快速查找和更新需求。

阅读全文

linux内核hlist详解

相关推荐

kernel_list_and_hash_table.tar.gz_Table_linux内核 list

Linux内核链表详解：数据组织与操作接口

Linux内核详解：list_head与链表结构

Linux内核双向链表操作详解

Linux内核链表数据结构详解

Linux内核之list_head

linux链表详解

linux加密设计框架

Linux桥接功能的分析

Linux内核中的list_head链表详解

开题报告SpringBoot家具商城系统.docx

Flask-2.2.3-py3-none-any.zip

编译器前端与后端设计.docx

google-2.0.1.tar.gz

1Python 3 介绍（十五）-- Python函数.docx

天气图绘制的相关nc数据与shp

Django-3.2.7-py3-none-any.whl

开题报告SpringBoot剧本杀管理系统.docx

开题报告SpringBoot高校汉服租赁平台.docx

最新推荐

Linux代码分析 本文详细分析了 2.6.x 内核中链表结构的实现，并通过实例对每个链表操作接口进行了详尽的讲解。

开题报告SpringBoot家具商城系统.docx

Flask-2.2.3-py3-none-any.zip

编译器前端与后端设计.docx

google-2.0.1.tar.gz

Haskell编写的C-Minus编译器针对TM架构实现

管理建模和仿真的文件

【数据整理秘籍】：R语言与tidyr包的高效数据处理流程

在使用STEP7编程环境为S7-300 PLC进行编程时，如何正确分配I/O接口地址并利用SM信号模板进行编址？

水电模拟工具HydroElectric开发使用Matlab

Linux代码分析本文详细分析了 2.6.x 内核中链表结构的实现，并通过实例对每个链表操作接口进行了详尽的讲解。