Linux 内核链表头数据结构
链表头必须在使用前用 INIT_LIST_HEAD 宏来初始化. 一个"要做的事情"的链表头可能声 明并且初始化用:
struct list_head todo_list; INIT_LIST_HEAD(&todo_list);
<para>可选地, 链表可在编译时初始化:</para>
LIST_HEAD(todo_list); 几个使用链表的函数定义在 <linux/list.h>:
list_add(struct list_head *new, struct list_head *head);
在紧接着链表 head 后面增加新入口项 -- 正常地在链表的开头. 因此, 它可用来 构建堆栈. 但是, 注意, head 不需要是链表名义上的头; 如果你传递一个 list_head 结构, 它在链表某处的中间, 新的项紧靠在它后面. 因为 Linux 链表 是环形的, 链表的头通常和任何其他的项没有区别.
list_add_tail(struct list_head *new, struct list_head *head);
刚好在给定链表头前面增加一个新入口项 -- 在链表的尾部, 换句话说. list_add_tail 能够, 因此, 用来构建先入先出队列.
list_del(struct list_head *entry); list_del_init(struct list_head *entry);
给定的项从队列中去除. 如果入口项可能注册在另外的链表中, 你应当使用 list_del_init, 它重新初始化这个链表指针.
list_move(struct list_head *entry, struct list_head *head); list_move_tail(struct list_head *entry, struct list_head *head);
给定的入口项从它当前的链表里去除并且增加到 head 的开始. 为安放入口项在新 链表的末尾, 使用 list_move_tail 代替.
list_empty(struct list_head *head); 如果给定链表是空, 返回一个非零值.
list_splice(struct list_head *list, struct list_head *head); 将 list 紧接在 head 之后来连接 2 个链表.
list_head 结构对于实现一个相似结构的链表是好的, 但是调用程序常常感兴趣更大的结 构, 它组成链表作为一个整体. 一个宏定义, list_entry, 映射一个 list_head 结构指 针到一个指向包含它的结构的指针. 它如下被调用:
list_entry(struct list_head *ptr, type_of_struct, field_name);
这里 ptr 是一个指向使用的 struct list_head 的指针, type_of_struct 是包含 ptr 的结构的类型, field_name 是结构中列表成员的名子. 在我们之前的 todo_struct 结构 中, 链表成员称为简单列表. 因此, 我们应当转变一个列表入口项为它的包含结构, 使用 这样一行:
struct todo_struct *todo_ptr = list_entry(listptr, struct todo_struct, list); list_entry 宏定义使用了一些习惯的东西但是不难用.
链表的遍历是容易的: 只要跟随 prev 和 next 指针. 作为一个例子, 假设我们想保持 todo_struct 项的列表已降序的优先级顺序排列. 一个函数来添加新项应当看来如此:
void todo_add_entry(struct todo_struct *new)
{
struct list_head *ptr; struct todo_struct *entry;
for (ptr = todo_list.next; ptr != &todo_list; ptr = ptr->next)
{
entry = list_entry(ptr, struct todo_struct, list); if (entry->priority < new->priority) {
list_add_tail(&new->list, ptr); return;
}
}
list_add_tail(&new->list, &todo_struct)
}
但是, 作为一个通用的规则, 最好使用一个预定义的宏来创建循环, 它遍历链表. 前一个 循环, 例如, 可这样编码:
void todo_add_entry(struct todo_struct *new)
{
struct list_head *ptr; struct todo_struct *entry;
list_for_each(ptr, &todo_list)
{
entry = list_entry(ptr, struct todo_struct, list); if (entry->priority < new->priority) {
list_add_tail(&new->list, ptr); return;
}
}
list_add_tail(&new->list, &todo_struct)
}
使用提供的宏帮助避免简单的编程错误; 宏的开发者也已做了些努力来保证它们进行正常. 存在几个变体:
list_for_each(struct list_head *cursor, struct list_head *list)
这个宏创建一个 for 循环, 执行一次, cursor 指向链表中的每个连续的入口项. 小心改变列表在遍历它时.
list_for_each_prev(struct list_head *cursor, struct list_head *list) 这个版本后向遍历链表.
list_for_each_safe(struct list_head *cursor, struct list_head *next, struct list_head *list)
如果你的循环可能删除列表中的项, 使用这个版本. 它简单的存储列表 next 中下 一个项, 在循环的开始, 因此如果 cursor 指向的入口项被删除, 它不会被搞乱.
list_for_each_entry(type *cursor, struct list_head *list, member) list_for_each_entry_safe(type *cursor, type *next, struct list_head *list, member)
这些宏定义减轻了对一个包含给定结构类型的列表的处理. 这里, cursor 是一个 指向包含数据类型的指针, member 是包含结构中 list_head 结构的名子. 有了这 些宏, 没有必要安放 list_entry 调用在循环里了.
如果你查看 <linux/list.h> 里面, 你看到有一些附加的声明. hlist 类型是一个有一个 单独的, 单指针列表头类型的双向链表; 它常用作创建哈希表和类型结构. 还有宏用来遍 历 2 种列表类型, 打算作使用 读取-拷贝-更新 机制(在第 5 章的"读取-拷贝-更新"一 节中描述 ). 这些原语在设备驱动中不可能有用; 看头文件如果你愿意知道更多信息关于 它们是如何工作的.
相关文章
- [Linux] Linux smaps接口文件结构
- linux驱动开发--内核链表
- [driver]linux内核动态加载模块
- 时间同步:Linux同步国家授时中心的时间
- linux内核数据结构之链表
- linux下发布war包
- linux内核数据结构之链表
- linux内核数据结构之链表
- 如何获取Linux中某个命令的源代码
- linux socket编程详解大全
- Linux复习资料——CentOS7下安装MySQL5.7.22(完整版本)
- 【Linux】《Linux 内核设计与实现》笔记
- 【Linux 内核 内存管理】memblock 分配器 ② ( memblock_type 内存块类型 | memblock_type 结构体成员分析 )
- 【Linux 内核 内存管理】RCU 机制 ③ ( RCU 模式下添加链表项 list_add_rcu 函数 | RCU 模式下删除链表项 list_del_rcu 函数 )
- 【Linux 内核 内存管理】RCU 机制 ① ( RCU 机制简介 | RCU 机制的优势与弊端 | RCU 机制的链表应用场景 )
- 【Linux 内核】线程调度示例一 ③ ( 获取线程优先级 | 设置线程调度策略 | 代码示例 )
- 【Linux 内核】实时调度类 ④ ( 实时运行队列 rt_rq 源码分析 | 实时运行队列 rt_rq 结构体字段分析 | active、rt_nr_running、curr、next 字段 )
- 【Linux 内核】实时调度类 ② ( 实时调度实体 sched_rt_entity 源码分析 | run_list、timeout、watchdog_stamp、time_slice 字段 )
- 【错误记录】编译 Linux 内核报错 ( /bin/sh: 1: bison: not found )
- L72.linux命令每日一练 -- 第十章 Linux网络管理命令 -- mail和nslookup
- xshell连接Linux服务器快捷键(非常实用)
- 嵌入式Linux开发,Ubuntu下交叉编译内核报错:error while loading shared libraries: /lib/x86_64-linux-gnu/libc++.so:
- 02 从头开始atac项目 ubuntu20 install r4.2 Linux系统环境配置 服务器版本的rstudio r install in linux /ubuntu/centos
- linux strace调试用法
- 内核中do while(0)的巧用 避免goto的方法 linux内核中代码有这样的代码
- Linux 探秘之用户态与内核态
- Linux基础笔记4 | 必备基础命令
- linux内核radeon gpu源码解析5 —— drm_get_pci_dev函数详解2
- [ Linux ] 如何查看内核 Kernel 版本(查多个Kernel的方法)