本节研究基数树相关的机制和实现；
基数树
说明几点
（1）基数树，是一种基于二进制表示键值的二叉查找树，类似字典树；其典型应用为IP地址的查找；
（2）如果使用IPv4时，基数树只需要支持到最大深度为32就可以了，key值从最高位向最低位开始匹配，比如key为0xC0000000，将会从key的最高位1向0开始匹配；
代码分析
（本节代码选自Nginx中关于基数树的代码）
基数树声明
//基数树节点struct ngx_radix_node_s {ngx_radix_node_t *right;//右孩子ngx_radix_node_t *left;//左孩子ngx_radix_node_t *parent; //父亲uintptr_tvalue;//指向用户实际的数据，若还没有使用为NGX_RADIX_NO_VALUE};//基数树管理结构typedef struct {ngx_radix_node_t *root;//指向根结点ngx_pool_t*pool;//内存池ngx_radix_node_t *free;//管理已经分配但暂时未使用（不在树中）的节点，实际上所有不在树中节点的单链表，使用right组成一个单链表char*start;//管理已经分配但暂时未使用内存的首地址size_tsize;//已经分配内存中还未使用的内存大小} ngx_radix_tree_t;
基数树节点分配（内存分配）
//基数树节点分配（申请一个节点内存）static ngx_radix_node_t *ngx_radix_alloc(ngx_radix_tree_t *tree){ngx_radix_node_t *p;if (tree->free) { //管理已经分配但暂时未使用（不在树中）的节点有节点p = tree->free; //直接找到tree->free = tree->free->right; //指向下一个节点return p;}if (tree->size < sizeof(ngx_radix_node_t)) { //已有内存不够分配一个节点tree->start = ngx_pmemalign(tree->pool, ngx_pagesize, ngx_pagesize); //分配一页内存if (tree->start == NULL) {return NULL;}tree->size = ngx_pagesize; //一页大小}p = (ngx_radix_node_t *) tree->start;//分配的节点内存地址tree->start += sizeof(ngx_radix_node_t); //更新已分配内存还未使用内存的地址tree->size -= sizeof(ngx_radix_node_t); //剩余的内存大小return p;}
基数树创建
//基数树创建ngx_radix_tree_t *ngx_radix_tree_create(ngx_pool_t *pool, ngx_int_t preallocate) {//preallocate表示建树的深度；当preallocate为1时，一共有3个节点；当preallocate为2，一共有7个节点；当为n时有2^(n+1)-1个节点；默认为-1;uint32_tkey, mask, inc;ngx_radix_tree_t *tree;tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t)); //申请基数树管理结构内存if (tree == NULL) {return NULL;}tree->pool = pool;tree->free = NULL; //管理已经分配但暂时未使用（不在树中）的节点，初始化为NULLtree->start = NULL; //管理已经分配但暂时未使用内存的首地址，初始化为NULLtree->size = 0;//已经分配内存中还未使用的内存大小，初始化为0tree->root = ngx_radix_alloc(tree);//创建根节点if (tree->root == NULL) {return NULL;}tree->root->right = NULL;tree->root->left = NULL;tree->root->parent = NULL;tree->root->value = NGX_RADIX_NO_VALUE; //初始值if (preallocate == 0) {return tree;}/** Preallocation of first nodes : 0, 1, 00, 01, 10, 11, 000, 001, etc.* increases TLB hits even if for first lookup iterations.* On 32-bit platforms the 7 preallocated bits takes continuous 4K,* 8 – 8K, 9 – 16K, etc. On 64-bit platforms the 6 preallocated bits* takes continuous 4K, 7 – 8K, 8 – 16K, etc. There is no sense to* to preallocate more than one page, because further preallocation* distributes the only bit per page. Instead, a random insertion* may distribute several bits per page.** Thus, by default we preallocate maximum*6 bits on amd64 (64-bit platform and 4K pages)*7 bits on i386 (32-bit platform and 4K pages)*7 bits on sparc64 in 64-bit mode (8K pages)*8 bits on sparc64 in 32-bit mode (8K pages)*/if (preallocate == -1) {switch (ngx_pagesize / sizeof(ngx_radix_node_t)) { //可以有多少个树节点/* amd64 */case 128:preallocate = 6; // 2^7-1为127个节点break;/* i386, sparc64 */case 256:preallocate = 7; // 2^8-1为255个节点break;/* sparc64 in 32-bit mode */default:preallocate = 8;}}mask = 0;inc = 0x80000000;//增加的幅度//预创建树while (preallocate–) {key = 0;mask >>= 1;mask |= 0x80000000; //初始时为0x80000000，表示第一层；然后依次右移和或，变为0xC0000000，表示第二层；其实mask表示对应的层次do {if (ngx_radix32tree_insert(tree, key, mask, NGX_RADIX_NO_VALUE)!= NGX_OK){return NULL;}key += inc;//inc为0x80000000时，mask为0x80000000（表示第一层），key表示创建的节点值，根节点为0，然后变为0x80000000这样就创建了根结点的左右孩子；//退出循环后，inc为0x40000000时，mask为0xC0000000（表示第2层）key为依次又变为0，，然后到0x40000000，然后到0x80000000，//然后到0xC0000000，然后到0x00000000，这样又对应创建了4个孩子；} while (key);inc >>= 1;}return tree;}
插入基数树节点
//插入基数树节点，使用mask来控制层次，避免建立额外的层次//预创建，将会建立一颗满二叉树；如果不用预创建，只会创建对应路径的树节点，其他分支则不会创建；ngx_int_tngx_radix32tree_insert(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask,uintptr_t value){uint32_tbit;ngx_radix_node_t *node, *next;bit = 0x80000000;node = tree->root; //头节点next = tree->root;while (bit & mask) { //一位位判断，从高到低，mask控制移动的层次if (key & bit) { //对应的位为1，向有查找，初始时，key为0直接break;next = node->right;} else {next = node->left; //为0向左找}if (next == NULL) { //跳出，已经找到break;}bit >>= 1;//向低位移动node = next; //指向父节点}if (next) { //找到指定层的节点时，若不为空时if (node->value != NGX_RADIX_NO_VALUE) {return NGX_BUSY;}node->value = value; //可以赋值return NGX_OK;}while (bit & mask) {//一位位判断，从高到低，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; //bit继续右移node = next;}node->value = value; //对应的叶子节点，指向对应的值valuereturn NGX_OK;}
删除基数树节点怕仍是不能。于是他们比任何人都看的清楚，又比任何人都看的不确切。
