Github: rb_next
Email: BuddyZhang1 buddy.zhang@aliyun.com
目录
源码分析
rb_next() 函数用于获得当前节点之后的下一个节点,根据树的中序定义,父节点与孩子
之间的关系是: 左孩子,父节点,右孩子。因此 rb_next() 按着中序的定义,获得下一个
rb_node。函数首先调用 RB_EMPTY_NODE() 函数判断当前节点是否是叶子节点,如果是
叶子节点,那么直接返回 NULL;如果不是叶子节点,那么如果节点的右孩子存在,那么
一直找到右孩子中最小的左孩子;如果右孩子不存在,那么此时节点可能位于父节点左孩子
中最大的右节点,那么此时从父节点的右孩子的最小左节点查找,以此获得下一个按中序排列
的节点。
RB_EMPTY_NODE
RB_EMPTY_NODE 源码解析
实践
驱动源码
驱动安装
驱动的安装很简单,首先将驱动放到 drivers/BiscuitOS/ 目录下,命名为 rbtree.c,
然后修改 Kconfig 文件,添加内容参考如下:
接着修改 Makefile,请参考如下修改:
驱动配置
驱动配置请参考下面文章中关于驱动配置一节。在配置中,勾选如下选项,如下:
具体过程请参考:
Linux 5.0 开发环境搭建 – 驱动配置
驱动编译
驱动编译也请参考下面文章关于驱动编译一节:
Linux 5.0 开发环境搭建 – 驱动编译
驱动运行
驱动的运行,请参考下面文章中关于驱动运行一节:
Linux 5.0 开发环境搭建 – 驱动运行
启动内核,并打印如下信息:
驱动分析
rb_next() 函数用于中序遍历红黑树。
附录
Data Structure Visualizations
Red Black Tress
BiscuitOS Home
BiscuitOS Driver
BiscuitOS Kernel Build
Linux Kernel
Bootlin: Elixir Cross Referencer
搭建高效的 Linux 开发环境
赞赏一下吧 🙂