Threaded Red-Black Tree 线索红黑树
项目地址:http://code.google.com/p/febird
使用 libavl 中的 trb ,经过修改,实现了一个更高效更友好易用的版本,并且也支持范围查询,提供完备的std::map/set接口。
- 对基本类型的key,实现高效search
- 支持 lower_bound/upper_bound/equal_range
- 结点采用压缩方式,将colorbit(1bit)和tagbit(2bit)压缩到指针中
- 从而每个结点的overhead是2ptr(32位环境下8byte,64位环境下16bits)
- stl::map/stl::set 的节点overhead 一般是 4ptr
- 遍历tree的速度比stl::map/set快一倍
- 线索树的线索(thread)可以直接访问next/prev,而不需要回溯到祖先结点再访问其最左/右叶子
- 通过线索(thread)直接访问到next/prev的概率大约有50%
- key的访问使用fieldoffset,C标准中有 offsetof(T,f) 宏来计算字段偏移
- 因为使用C模拟template,从而没有C++的代码膨胀问题
- C接口需要手工打造vtable
- vtable指针通过参数传递,而不是将它作为trb_tree的一部分,更节约内存
- 也许仅仅一个vtable指针用不了多少内存
- 但是当有若干个【在我的应用中,大约2M个】trb_tree时,节省的内存相当可观
- 使用C实现核心功能,同时提供更易用的C++接口(trbset/trbmap/trbtab)
- 类似stl中的相应东西
- trbset相当于stl::set
- trbmap相当于stl::map
- trbtab提供更多的控制
- C++接口只是一个语法糖wrapper,将调用转发到C,但是使用C++可以避免几乎一切误用
- C++将vtable作为模板的static成员,非常合理,非常恰到好处
以前我写过两篇文章:
对基本类型的key,实现高效search,其核心思想就来源于这两篇文章,但是有许多精化。其间使用了更之前的一些东西:
- 基本类型enum
- 类型迭代(使用preprocessor)
基本类型enum,使用enum的目的在于:使用这个enum,查找到相应的处理函数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
enum field_type_t { tev_char, tev_byte, tev_int16, tev_uint16, tev_int32, tev_uint32, tev_int64, tev_uint64, tev_float, tev_double, tev_int, tev_uint, tev_long, tev_ulong, tev_ptr, tev_blob, ///< blob tev_cstr, tev_std_string, ///< for c++ std::string, only used in c++ tev_std_wstring, ///< for c++ std::wstring, only used in c++ tev_app ///< application defined type #define tev_type_count__ tev_int }; |
类型迭代:p_field_type_loop.h
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// field type loop without judge VALUE_SIZE // input macro: // FIELD_TYPE_FILE # define FIELD_TYPE_TYPE signed char # define FIELD_TYPE_PROMOTED int # define FIELD_TYPE_NAME tev_char # include FIELD_TYPE_FILE # undef FIELD_TYPE_PROMOTED # define FIELD_TYPE_TYPE unsigned char # define FIELD_TYPE_PROMOTED unsigned # define FIELD_TYPE_NAME tev_byte # include FIELD_TYPE_FILE # undef FIELD_TYPE_PROMOTED // and so on .... // more types |
在包含该文件之前,需要定义 FIELD_TYPE_FILE ,从而p_field_type_loop.h可以作为一个通用的代码生成器。在FIELD_TYPE_FILE中,实现具体的代码,在需要参数化类型的地方,使用FIELD_TYPE_TYPE来代替。FIELD_TYPE_PROMOTED用来提升相应的FIELD_TYPE_TYPE,例如 signed char 被提升到 int,float 被提升到double,这一点,在使用C的vararg时是绝对必要的。
另外,在包含该文件之前,还要将FIELD_TYPE_FILE中实现的函数名定义成宏,如:
1 2 3 4 5 6 7 8 9 10 |
#define trb_compare_kd CAT_TOKEN2(trb_compare_, FIELD_TYPE_NAME) #define trb_find_xx CAT_TOKEN2(trb_find_, FIELD_TYPE_NAME) #define trb_lower_bound_xx CAT_TOKEN2(trb_lower_bound_, FIELD_TYPE_NAME) #define trb_upper_bound_xx CAT_TOKEN2(trb_upper_bound_, FIELD_TYPE_NAME) #define trb_equal_range_xx CAT_TOKEN2(trb_equal_range_, FIELD_TYPE_NAME) #define trb_find_path_xx CAT_TOKEN2(trb_find_path_, FIELD_TYPE_NAME) #define FIELD_TYPE_FILE "trb_fun_field_type.h" #include "p_field_type_loop.h" #undef FIELD_TYPE_FILE |
以trb_find_xx为例,当trb_find_xx被展开后,变成trb_find_tev_double等等。
为什么要搞这么多呢?因为在这些函数中,对key值的大小比较实际上是个trivial操作,而一般传统的方法是传递一个compare函数指针,通过该指针调用compare函数,来实现灵活性(对任意类型的key)。
但是,通过函数指针调用一个非常trivial的操作,有很多不必要的性能损失(经过测试,对int的key,trb_find_xx会慢约20%~80%,服务器GCC+至强2.29G中慢20%,台式机VC+奔腾2.49G中慢80%)。
使用这种编程范式,可以在不必造成冗余代码的情况下,大幅提升性能。
全部的代码在这里