【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 内核实现与应用开发实战指南》