理key值为整形的情况，所以每个整形被转化为二进制数，并且树的最大深度是32层。根据二进制位数从左到右，如果当前位为1，就向右子树，否则向左子树插入。当然有时候我们不想构建深度为32的基数树，nginx为此提供了一个掩码mask，这个掩码中1的个数决定了基数树的深度。
代码：
ngx_int_t
ngx_radix32tree_insert(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask,
uintptr_t value)
{
uint32_t bit;
ngx_radix_node_t *node, *next;
bit = 0x80000000;//从最左位开始，判断key值
node = tree->root;
next = tree->root;
while (bit & mask) {
if (key & bit) {//等于1向右查找
next = node->right;
} else {//等于0向左查找
next = node->left;
}
if (next == NULL) {
break;
}
bit >>= 1;
node = next;
}
if (next) {//如果next不为空
if (node->value != NGX_RADIX_NO_VALUE) {//如果数据不为空
return NGX_BUSY;//返回NGX_BUSY
}
node->value = value;//直接赋值
return NGX_OK;
}
? ? //如果next为中间节点，且为空，继续查找且申请路径上为空的节点
? ? //比如找key=1000111，在找到10001时next为空，那要就要申请三个节点分别存10001,100011,1000111,
? ? //1000111最后一个节点为key要插入的节点
while (bit & mask) {//没有到达最深层，继续向下申请节点
next = ngx_radix_alloc(tree);//申请一个节点
if (next == NULL) {
return NGX_ERROR;
}
//初始化节点
next->right = NULL;
next->left = NULL;
next->parent = node;
next->value = NGX_RADIX_NO_VALUE;
if (key & bit) {
node->right = next;
} else {
node->left = next;
}
bit >>= 1;
node = next;
}
node->value = value;//指向数据区
return NGX_OK;
}
2.3ngx_radix32tree_delete删除节点
删除一个节点和插入节点的操作几乎一样，不过要注意两点：
1）如果删除的是叶子节点，直接从基数树中删除，并把这个节点放入free链表
2）如果不是叶子节点，把value值置为NGX_RADIX_NO_VALUE
代码：
ngx_int_t
ngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask)
{
uint32_t bit;
ngx_radix_node_t *node;
bit = 0x80000000;
node = tree->root;
//根据key和掩码查找
while (node && (bit & mask)) {
if (key & bit) {
node = node->right;
} else {
node = node->left;
}
bit >>= 1;
}
if (node == NULL) {//没有找到
return NGX_ERROR;
}
//node不为叶节点直接把value置为空
if (node->right || node->left) {
if (node->value != NGX_RADIX_NO_VALUE) {//value不为空
node->value = NGX_RADIX_NO_VALUE;//置空value
return NGX_OK;
}
return NGX_ERROR;//value为空，返回error
}
//node为叶子节点，直接放到free区域
for ( ;; ) {//删除叶子节点
if (node->parent->right == node) {
node->parent->right = NULL;//
} else {
node->parent->left = NULL;
}
//把node链入free链表
node->right = tree->free;//放到free区域
tree->free = node;//free指向node
//假如删除node以后，父节点是叶子节点，就继续删除父节点，
//一直到node不是叶子节点
node = node->parent;
if (node->right || node->left) {//node不为叶子节点
break;
}
if (node->value != NGX_RADIX_NO_VALUE) {//node的value不为空
break;
}
if (node->parent == NULL) {//node的parent为空
break;
}
}
return NGX_OK;
}
2.4ngx_radix32tree_find查找节点返回数据
这个函数是这四个函数中最简单的一个，就是根据key值查询，如果找到返回value值，没有找到返回NGX_RADIX_NO_VALUE。
代码：
uintptr_t
ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key)
{
uint32_t bit;
uintptr_t value;
ngx_radix_node_t *node;
bit = 0x80000000;
value = NGX_RADIX_NO_VALUE;
node = tree->root;
while (node) {
if (node->value != NGX_RADIX_NO_VALUE) {
value = node->value;
}
if (key & bit) {
node = node->right;
} else {
node = node->left;
}
bit >>= 1;//往下层查找
}
return value;
}
2.5ngx_radix_alloc申请节点函数
ngx_radix_alloc为基数树申请节点：
1）如果free链表不为空，直接从上面取下一个空闲节点
2）free链表为空，则申请一个节点
代码：
static void *
ngx_radix_alloc(ngx_radix_tree_t *tree)
{
char *p;
if (tree->free) {//如果free中有可利用的空间节点
p = (char *) tree->free;//指向第一个可利用的空间节点
tree->free = tree->free->right;//修改free
return p;
}
if (tree->size < sizeof(ngx_radix_node_t)) {//如果空闲内存大小不够分配一个节点就申请一页大小的内存
tree->start = ngx_pmemalign(tree->pool, ngx_pagesize, ngx_