【Radix Tree】
Radix Tree 是一种数据结构，又称为 PAT Tree（Patricia Tire or crit bit Tree），源自于 Patricia Tree（Practical Algorithm To Retrieve Information Coded In Alphanumeric Tree）。这是一种基于二进制表示键值的查找树，树的叶子节点数是实际的数据条目。Radix 树与二叉树的不同在于，二叉树的每个节点最多有 2 个子节点（0或者1，即每个子节点只使用 1 个 bit 表示），而 Radix 树可以根据实际要表示的数据的长度将每个节点分出 2^n 个子节点（n 是用于表示子节点的 bit 位数）。比如我们为一堆物品编上 8-bit 长度的 ID 号，使用 Radix 树来存储/查找这些物品，每个子节点使用 2-bit 进行表示时，树的结构类似下图：
图1、Radix树
按顺序每次比较 ID 值中的 2 bit，最终将在叶子节点找到编号为 00000010 和 11111010 所对应的物品。
使用 n-bit 来表示子节点时，n 越大树的高度越低，但宽度越宽；n 越小树的高度越高但宽度越窄。若每个 ID 的长度为 N-bit，则一个完全的 Radix 树的高度为 N/n，宽度为 (2^n)^(N/n)。
【Linux IDR】
IDR 的全称是 ID Radix，顾名思义是一种采用 Radix 树来存储/查找 ID 的方法。在 Linux 中使用 IDR 机制将长整型的 ID 与指针进行关联，实现 2 者间的相互转化。更常用的情况是传入 1 个 ID，查找该 ID 所对应的指针。
举个例子，在 Linux I2C 框架中，一般通过传入 i2c_busnum 的方式来获取 i2c_adapter。代码如下：
static int __init rt5677_i2c_dev_init(void)
{
int i2c_busnum = 0;
...
struct i2c_adapter *adapter;
...
adapter = i2c_get_adapter(i2c_busnum); // 获取 adapter
if(adapter) {
…
}
…
}
这里的 i2c_busnum 实际上就是 ID。查看 i2c_get_adapter() 函数原型就可以看到：
struct i2c_adapter *i2c_get_adapter(int nr)
{
struct i2c_adapter *adapter;
mutex_lock(&core_lock);
adapter = idr_find(&i2c_adapter_idr, nr); // 传入 ID 值，获得对应的 adapter 指针
if(adapter && !try_module_get(adapter->owner))
adapter = NULL;
mutex_unlock(&core_lock);
return adapter;
}
进入到 idr_find() 函数，闻到的就是彻头彻尾的 idr 气息了。如下：
/**
*idr_find - return pointer for given id
*@idr: idr handle
*@id: lookup key
*
*Return the pointer given the id it has been registered with. A %NULL
*return indicates that @id is not valid or you passed %NULL in
*idr_get_new().
*
*This function can be called under rcu_read_lock(), given that the leaf
*pointers lifetimes are correctly managed.
*/
static inline void *idr_find(struct idr *idr, int id)
{
struct idr_layer *hint = rcu_dereference_raw(idr->hint);
if(hint && (id & ~IDR_MASK) == hint->prefix)
returnrcu_dereference_raw(hint->ary[id & IDR_MASK]);
returnidr_find_slowpath(idr, id);
}
关于 Linux IDR 的框架，这里不做介绍。