Linux的idr机制(32叉树)
一.结构体
1.idr结构体
2.idr_layer结构体
在32位系统中IDR_BITS的取值为5
二.idr的初始化
定义一个idr结构体并赋值
三.分配id
1.idr_pre_get
move_to_free_list
__move_to_free_list
第一次循环结果
接着循环
再接着
一直这样下去直到循环结束(14次)
2.idr_get_new和idr_get_new_above
idr_get_new
idr_get_new_above
两个函数都会调用idr_get_new_above_int函数,差别在于starting_id不同
下面分情况讨论,先以id为0走个过场
idr的top简称为根top,free简称为根free均为idr_layer指针类型,分别指向使用中和空闲idr_layer链表头
idr_get_empty_slot
图A：
图B
>>>get_from_free_list 从idr空闲idr_layer链表中获取第一个idr_layer
这里先穿插一下32进制的计算,上面图B中2^0,2^5,2^10,2^15,2^20,2^25可以(32=2^5)理解成32^0,32^1,32^2,32^3,32^3,32^4,32^5
那么用32进制表达一个十进制数id可以套用一下公式
a的值属于[0,31]
an的值如何获得id/(32^n)即可,等同于id/(2^5^n)等同于id/((1<<5)^n)
an-1的值如何获得id>>(5*(n-1))即可
>>>sub_alloc
>>>find_next_bit
该宏的意思是在p指向的(大小为sz的)位图表中的第off个位置开始找寻可用(为"1")的格子,找到返回该位
_find_next_bit_le是汇编代码实现的定义在/arch/arm/lib/findbit.S
.L_found找到合适的跳转
>>>id值的计算的补充说明
首先前面n的取值n = (id >> (IDR_BITS*l)) & IDR_MASK;
IDR_MASK的定义#define IDR_MASK ((1 << IDR_BITS)-1)也就是说IDR_MASK=31等于2进制的1,1111b
所以&IDR_MASK只是框定n值落在0~31之间,掩码作用
那么不出意外的话n = (id >> (IDR_BITS*l))
接着
sh = IDR_BITS*l;
id = ((id >> sh) ^ n ^ m) << sh;
带入表达式中
id=((id >> IDR_BITS*l) ^ (id >> (IDR_BITS*l)) ^ m) << IDR_BITS*l;
异或的操作是相同为1,不同为0,结合起来化简得
id = ((1 ^ m) << sh=m<
图C
^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_
已经借用id0走了过场,下面分析下其他情况
来个效果图id=4吧
id=32情况(idr_layer13的位图1标记错了)
1024情况
四.查找id
1.idr_find
前面讲过32进制的id值算法
当构建完idr机制之后
id=top->ary[an]->ary[a(n-1)]->....->ary[a0]来获得
借助图片分析下(idr_layer13的位图标记有错)
五idr操作
1.idr_remove idr_remove_all 移除
移除全部
2.idr_replace 替换
六.idr空闲链表的销毁
idr_destroy
七.用法
1.api函数
2.大致用法
1.idr_init声明设置idr
2.idr_pre_get分配空闲idr_layer链表
3.id_get_new/idr_get_new_above分配id并将id与指针ptr捆绑
4.利用idr_find根据id获取指针ptr
5.idr_remove/idr_remove_all移除分配的id
6.idr_destroy销毁空闲idr_layer链表
7.idr_replace替换id