嵌入式C语言(十三)

简介: 嵌入式C语言(十三)

Linux内核中常用的数据结构和算法

Linux内核代码广泛使用了数据结构和算法,其中最常用的两个是链表和红黑树

1 链表

Linux内核代码大量使用了链表这种数据结构。

链表是在解决数组不能动态扩展这个缺陷而产生的一种数据结构

链表所包含的元素可以动态创建并插入和删除

链表的每个元素都是离散存放的,因此不需要占用连续的内存。

链表通常由若干节点组成,每个节点的结构都是一样的,由有效数据区和指针区两部分组成

有效数据区用来存储有效数据信息,而指针区用来指向链表的前继节点或者后继节点。因此,链表就是利用指针将各个节点串联起来的一种存储结构。

(1)单向链表

单向链表的指针区只包含一个指向下一个节点的指针,因此会形成一个单一方向的链表,如下代码所示。

struct list {
int data;  /*有效数据*/
struct list *next; /*指向下一个元素的指针*/
};

如图2.2所示,单向链表具有单向移动性,也就是只能访问当前的节点的后继节点,而无法访问当前节点的前继节点,因此在实际项目中运用得比较少。

(2)双向链表

如图2.3所示,双向链表和单向链表的区别是指针区包含了两个指针,一个指向前继节点,另一个指向后继节点,如下代码所示。

struct list {
int data;  /*有效数据*/
struct list *next; /*指向下一个元素的指针*/
struct list *prev; /*指向上一个元素的指针*/
};

(3)Linux内核链表实现

单向链表和双向链表在实际使用中有一些局限性,如数据区必须是固定数据,而实际需求是多种多样的。

这种方法无法构建一套通用的链表,因为每个不同的数据区需要一套链表。

为此,Linux内核把所有链表操作方法的共同部分提取出来,把不同的部分留给代码编程者自己去处理

Linux内核实现了一套纯链表的封装,链表节点数据结构只有指针区而没有数据区另外还封装了各种操作函数,如创建节点函数、插入节点函数、删除节点函数、遍历节点函数等。

Linux内核链表使用struct list_head数据结构来描述。

<include/linux/types.h>
struct list_head {
struct list_head *next, *prev;
};

struct list_head数据结构不包含链表节点的数据区,通常是嵌入其他数据结构,如struct page数据结构中嵌入了一个lru链表节点,通常是把page数据结构挂入LRU链表

<include/linux/mm_types.h>
struct page {
struct list_head lru;
...
}

链表头的初始化有两种方法,一种是静态初始化,另一种动态初始化。

把 next 和 prev指针都初始化并指向自己,这样便初始化了一个带头节点的空链表。

<include/linux/list.h>
/*静态初始化*/
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
/*动态初始化*/
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}

添加节点到一个链表中,内核提供了几个接口函数,如list_add()是把一个节点添加到表头list_add_tail()是插入表尾。

<include/linux/list.h>
目录
打赏
0
0
0
0
76
分享
相关文章
C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出
本文探讨了C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出。文章还介绍了C语言在知名机器学习库中的作用,以及与Python等语言结合使用的案例,展望了其未来发展的挑战与机遇。
77 1
基于C语言的嵌入式系统开发,涵盖嵌入式系统概述、C语言的优势、开发流程、关键技术、应用实例及面临的挑战与未来趋势。
本文深入探讨了基于C语言的嵌入式系统开发,涵盖嵌入式系统概述、C语言的优势、开发流程、关键技术、应用实例及面临的挑战与未来趋势。C语言因其高效、可移植、灵活及成熟度高等特点,在嵌入式系统开发中占据重要地位。文章还介绍了从系统需求分析到部署维护的完整开发流程,以及中断处理、内存管理等关键技术,并展望了嵌入式系统在物联网和人工智能领域的未来发展。
150 1
C语言实现2048小游戏---粤嵌GE6818嵌入式系统实训
C语言实现2048小游戏---粤嵌GE6818嵌入式系统实训
|
8月前
|
嵌入式C语言(十四)
嵌入式C语言(十四)
53 0
C语言与嵌入式系统:嵌入式C编程基础。
C语言与嵌入式系统:嵌入式C编程基础。
114 0
技术心得记录:嵌入式开发中常用到的C语言库函数
技术心得记录:嵌入式开发中常用到的C语言库函数
84 1
C语言实现电子音乐相册---粤嵌GEC6818嵌入式系统实训
C语言实现电子音乐相册---粤嵌GEC6818嵌入式系统实训
嵌入式C语言(十二)
嵌入式C语言(十二)
47 1
本CSDN博主将与北京航天航空大学出版社合作出版&lt;嵌入式C语言技术实战开发&gt;一书
本书作者由以下成员合作编写:     杨源鑫,主编,毕业于广州科技贸易职业学院电子应用技术专业,在校期间一并考取了华南理工大学本科数字媒体艺术专业。2015年7月工作至今,任伟易达集团嵌入式系统工程师一职,主要从事单片机,linux,Android底层开发等相关的技术。
2997 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等