【RT-Thread笔记】对象容器与双链表

前言

在我们嵌入式中,可能会有些人认为数据结构与算法相关知识没什么用,很少用得上。

以前,我也是这么认为的,那东西那么难学,好像又用不上,学了有什么用,干脆就不学了。

直到后面深入学习一些东西之后发现,原来那些知识并不是没有用,只是当时我们的认知还不足。废话不多说,下面进入正题:

对象容器与双链表

1、RT-Thread中的对象容器

RT-Thread 内核对象包括:线程,信号量,互斥量,事件,邮箱,消息队列和定时器,内存池,设备驱动等。

对象容器中包含了每类内核对象的信息,包括对象类型,大小等。

对象容器给每类内核对象分配了一个链表,所有的内核对象都被链接到该链表上, RT-Thread 的内核对象容器及链表如下图所示:

这个对象容器对应到代码上是一个结构体数组,这个结构体数组在object.c里定义,其内容如下(已做删减):

static struct rt_object_information
rt_object_container[RT_Object_Info_Unknown] =
{
/* 初始化对象容器 - 线程 */
{
RT_Object_Class_Thread,
_OBJ_CONTAINER_LIST_INIT(RT_Object_Info_Thread),
sizeof(struct rt_thread)
},

#ifdef RT_USING_SEMAPHORE
/* 初始化对象容器 - 信号量 */
{
RT_Object_Class_Semaphore,
_OBJ_CONTAINER_LIST_INIT(RT_Object_Info_Semaphore),
sizeof(struct rt_semaphore)
},
#endif

/* 省略部分代码。。。。。。。。。。。。。。。。。*/

/* 初始化对象容器 - 定时器 */
{
RT_Object_Class_Timer,
_OBJ_CONTAINER_LIST_INIT(RT_Object_Info_Timer),
sizeof(struct rt_timer)
},

/* 省略部分代码。。。。。。。。。。。。。。。。。*/
};

其中,内核对象信息结构体  struct rt_object_information 的定义如下:

struct rt_object_information
{
enum rt_object_class_type type; /**< 对象类型 */
rt_list_t object_list; /**< 对象链表节点头 */
rt_size_t object_size; /**< 对象大小 */
};

RT-Thread 的内核对象的继承关系如:

在代码阅读器Source Insight中(相关笔记:《Source Insight的使用》)也可以看出这样的关系:

每个内核对象的初始化函数里都有调用对象初始化函数rt_object_init

而对象初始化函数里做了什么呢?看其内部实现(已做删减):

void rt_object_init(struct rt_object *object,
enum rt_object_class_type type,
const char *name)
{
register rt_base_t temp;
struct rt_object_information *information;

/* 获取对象信息,即从容器里拿到对应对象列表头指针 */
information = rt_object_get_information(type);
RT_ASSERT(information != RT_NULL);

/* 设置对象类型为静态 */
object->type = type | RT_Object_Class_Static;

/* 拷贝名字 */
rt_strncpy(object->name, name, RT_NAME_MAX);

/* 关中断 */
temp = rt_hw_interrupt_disable();

/* 把对象信息插入到对象链表中 */
rt_list_insert_after(&(information->object_list), &(object->list));

/* 开中断 */
rt_hw_interrupt_enable(temp);
}

这里用到的rt_list_insert_after函数就是双链表插入函数。

2、RT-Thread中双链表的操作

RT-Thread的对象容器是依赖于双链表(双向循环链表)的,其双链表的相关操作在文件rtservice.h中:

其节点结构体为:

struct rt_list_node
{
struct rt_list_node *next; /**< 指向后一个节点 */
struct rt_list_node *prev; /**< 指向后一个节点 */
};
typedef struct rt_list_node rt_list_t;

下面介绍几个基本的操作接口(截图来自野火的RT-Thread书籍):

(1)初始化链表节点:

rt_inline void rt_list_init(rt_list_t *l)
{
l->next = l->prev = l;/* 节点的next指针与prev指针都指向其本身 */
}

(2)  在双向链表表头后面插入一个节点:

rt_inline void rt_list_insert_after(rt_list_t *l, rt_list_t *n)
{
l->next->prev = n; /* 第(1)步 */
n->next = l->next; /* 第(2)步 */

l->next = n; /* 第(3)步 */
n->prev = l; /* 第(4)步 */
}

(3)在双向链表表头前面(表尾后面)插入一个节点:

rt_inline void rt_list_insert_before(rt_list_t *l, rt_list_t *n)
{
l->prev->next = n; /* 第(1)步 */
n->prev = l->prev; /* 第(2)步 */

l->prev = n; /* 第(3)步 */
n->next = l; /* 第(4)步 */
}

(4)从双向链表删除一个节点:

rt_inline void rt_list_remove(rt_list_t *n)
{
n->next->prev = n->prev; /* 第(1)步 */
n->prev->next = n->next; /* 第(2)步 */

n->next = n->prev = n; /* 第(3)步 */
}

初始化对象列表节点头里面的 next 和 prev 两个节点指针分别指向自身,如:

若创建两个led线程对象,则对象容器里变为:

顺便提一个关于链表的一个名词上的疑惑,是节点还是结点?我之前也看过一些书,有的书写为节点,有的书写为结点,我也不知道哪个更准确。不纠结了,知道这么一回事就可以了,不影响我们学习。

最后

看到了吧,数据结构在嵌入式中还是很有用的吧,更多的细节可以阅读其源码。

以上就是本次的笔记分享,如有错误,欢迎指出!如果觉得文章不错,转发、在看,也是我们继续更新得动力。

参考资料:

1、官方的《RT-THREAD 编程指南》

2、野火的《RT-Thread 内核实现与应用开发实战指南》

(0)

相关推荐

  • 干货 | 扒一扒RT-Thread内核对象管理器设计思路

    RT-Tread内核架构 RT-Thread,全称是 Real Time-Thread,顾名思义,它是一个嵌入式实时多线程操作系统,基本属性之一是支持多任务,允许多个任务同时运行并不意味着处理器在同一 ...

  • Java之ThreadLocal

    Java之ThreadLocal

  • C语言—双链表操作

    双链表操作 /*双链表的操作:查询.删除.显示.插入. *双向链表克服单向链表向前查找结点需要执行时间O(n)的缺点 *2008.1.17 */ #include <stdio.h> #i ...

  • 双链表,这回彻底搞dong了

    前言 前面有很详细的讲过线性表(顺序表和链表),当时讲的链表以单链表为主,但实际上在实际应用中双链表的应用多一些就比如LinkedList. 双链表与单链表区别 逻辑上它们均是线性表的链式实现,主要的 ...

  • C/C++编程笔记:链接列表(链表)及其遍历,今天就教你

    像数组一样,链表是线性数据结构.与数组不同,链接列表元素不存储在连续的位置:元素使用指针链接. 为什么要链接列表? 数组可用于存储相似类型的线性数据,但是数组具有以下限制. 1)数组的大小是固定的:因 ...

  • 双链表的操作示例(附代码)

    什么是双链表? 双链表是在操作系统中常用的数据结构,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱,其结点组成如下: 其示意图举例如下: 双链表的操作示例 1.双链表结点定义: /* 数据 ...

  • 换对象了,“双风暴”奥尔加和巴勃罗生成,一个或影响美国8大州

    换对象了,"双风暴"奥尔加和巴勃罗生成,一个或影响美国8大州 太快了!又有两个新风暴诞生了,奥尔加即将登陆或影响美国8大州 不是不明白,而是气象变化太快.也确实是这样,都到10月底 ...

  • 父母催婚,却始终遇不到一个让自己满意的对象。李双林

    作者:李双林 案例: 李老师您好!一直以来都关注您的命理文章,每天一早看您更新的文章已成为我的习惯,每一篇的博文都是在品别人的故事受李老师的教诲.老师,谢谢您!一直坚持给李老师写信,写信的同时,也总是 ...

  • 九、Swift对象存储服务(双节点搭建)

    要求:Controoler节点需要2块空盘 Compute节点需要再加2块空盘 本次搭建采用Controller 和 Compute双节点节点做swift组件 1.Controller安装并配置控制节 ...

  • 《C++ Primer》笔记 第9章 顺序容器

    顺序容器类型 类型 解释 vector 可变大小数组.支持快速随机访问.在尾部之外的位置插入或删除元素可能很慢 deque 双端队列.支持快速随机访问.在头尾位置插入.删除速度很快 list 双向链表 ...

  • 略读《灌木集》笔记 | 姚双梧

    作者 略读<灌木集>笔记 姚双梧 <灌木集>是著名教育家.诗人.文学评论家李广田于一九四三年出版的散文选集.之所以命之为<灌木集>,是先生的自谦说法,因为集子中几乎 ...