红黑树（三） - Linux内核实现

概要

前面分别介绍了红黑树的理论知识 以及 通过C语言实现了红黑树。本章继续会红黑树进行介绍，下面将Linux 内核中的红黑树单独移植出来进行测试验证。若读者对红黑树的理论知识不熟悉，建立先学习红黑树的理论知识，再来学习本章。

转载请注明出处：红黑树(三)之 Linux内核中红黑树的经典实现 - 如果天空不死 - 博客园

---

更多内容：数据结构与算法系列 目录

(01) 红黑树(一)之 原理和算法详细介绍
(02) 红黑树(二)之 C语言的实现
(03) 红黑树(三)之 Linux内核中红黑树的经典实现
(04) 红黑树(四)之 C++的实现 
(05) 红黑树(五)之 Java的实现
(06) 红黑树(六)之 参考资料

Linux内核中红黑树(完整源码)

红黑树的实现文件(rbtree.h)

 View Code

红黑树的实现文件(rbtree.c)

 View Code

红黑树的测试文件(test.c)

 View Code

rbtree.h和rbtree.c基本上是从Linux 3.0的Kernel中移植出来的。仅仅只添加了offestof和container_of两个宏，这两个宏在文章"Linux内核中双向链表的经典实现"中已经介绍过了，这里就不再重复说明了。
test.c中包含了两部分内容：一是，基于内核红黑树接口，自定义的一个结构体，并提供了相应的接口(添加、删除、搜索、打印)。二是，包含了相应的测试程序。