7.5.5　如何自定义添加成员方法

由于节点的key关键字必须是整型，这导致很多情况下不同的节点会具有相同的key关键字。如果不希望出现具有相同key关键字的不同节点在向红黑树添加时出现覆盖原节点的情况，就需要实现自有的ngx_rbtree_insert_pt方法。

许多Nginx模块在使用红黑树时都自定义了ngx_rbtree_insert_pt方法（如geo、filecache模块等），本节以7.5.3节中介绍过的ngx_str_rbtree_insert_value为例，来说明如何定义这样的方法。先看一下ngx_str_rbtree_insert_value的实现。代码如下。

void

ngx_str_rbtree_insert_value（ngx_rbtree_node_t*temp，

ngx_rbtree_node_tnode,ngx_rbtree_node_tsentinel）

{

ngx_str_node_t

n，t；

ngx_rbtree_node_t**p；

for（；）{

n=（ngx_str_node_t*）node；

t=（ngx_str_node_t*）temp；

//首先比较key关键字，红黑树中以key作为第一索引关键字

if（node-＞key！=temp-＞key）{

//左子树节点的关键节小于右子树

p=（node-＞key＜temp-＞key）?＆temp-＞left：＆temp-＞right；

}

//当key关键字相同时，以字符串长度为第二索引关键字

else if（n-＞str.len！=t-＞str.len）{

//左子树节点字符串的长度小于右子树

p=（n-＞str.len＜t-＞str.len）?＆temp-＞left：＆temp-＞right；

}else{

//key关键字相同且字符串长度相同时，再继续比较字符串内容

p=（ngx_memcmp（n-＞str.data,t-＞str.data,n-＞str.len）＜0）?＆temp-＞left：＆temp-＞right；

}

//如果当前节点p是哨兵节点，那么跳出循环准备插入节点

if（*p==sentinel）{

break；

}

//p节点与要插入的节点具有相同的标识符时，必须覆盖内容

temp=*p；

}

*p=node；

//置插入节点的父节点

node-＞parent=temp；

//左右子节点都是哨兵节点

node-＞left=sentinel；

node-＞right=sentinel；

/将节点颜色置为红色。注意，红黑树的ngx_rbtree_insert方法会在可能的旋转操作后重置该节点的颜色/

ngx_rbt_red（node）；

}

可以看到，该代码与7.5.4节中介绍过的检索节点代码很相似。它所要处理的主要问题就是当key关键字相同时，继续以何种数据结构作为标准来确定红黑树节点的唯一性。Nginx中已经实现的诸多ngx_rbtree_insert_pt方法都是非常相似的，读者完全可以参照ngx_str_rbtree_insert_value方法来自定义红黑树节点添加方法。