idr机制(32叉树)(二)
0]->ary[0]=ptr 也就是idr_layer14->ary[0]=ptr
pa[0]->count++; //idr_layer14->count++
idr_mark_full(pa, id); //设置其位图-->走完0过场的效果见图c
}
return id;
}
idr_get_empty_slot
[cpp]
static int idr_get_empty_slot(struct idr *idp, int starting_id,struct idr_layer **pa)
{
struct idr_layer *p, *new;
int layers, v, id;
unsigned long flags;
id = starting_id; //按常规出牌吧,假设这个为0
build_up:
p = idp->top; //根top指向的idr_layer NULL
layers = idp->layers; //获取layers层数量(0)
if (unlikely(!p)) { //第一次运行idp->top=NULL,所以if条件为真,执行if分支的结果参考 图A
if (!(p = get_from_free_list(idp))) //>>>1-->get_from_free_list 从根free中获取一个idr_layer14
return -1;
p->layer = 0; //指定idr_layer14的层号为0
layers = 1; //layers层数量设为1
}
//layers<6 && id>=2^(layers*5) 看需不需要增加层数 见图B
while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) {
layers++;
if (!p->count) {
p->layer++;
continue;
}
if (!(new = get_from_free_list(idp))) {
spin_lock_irqsave(&idp->lock, flags);
for (new = p; p && p != idp->top; new = p) {
p = p->ary[0];
new->ary[0] = NULL;
new->bitmap = new->count = 0;
__move_to_free_list(idp, new);
}
spin_unlock_irqrestore(&idp->lock, flags);
return -1;
}
new->ary[0] = p;
new->count = 1;
new->layer = layers-1;
if (p->bitmap == IDR_FULL)
__set_bit(0, &new->bitmap);
p = new;
}
rcu_assign_pointer(idp->top, p); //根top指向idr_layer14
idp->layers = layers; //设置更新idr->layers层数量
//----------------------------------------------分割线----------------------------------------------
//以上部分主要处理layer相关,以下部分主要处理id相关
v = sub_alloc(idp, &id, pa); //>>>2-->sub_alloc
if (v == IDR_NEED_TO_GROW) //IDR_NEED_TO_GROW=-2需要扩大
goto build_up;
return(v);
}
图A：
图B
>>>get_from_free_list 从idr空闲idr_layer链表中获取第一个idr_layer
[cpp]
static struct idr_layer *get_from_free_list(struct idr *idp)
{
struct idr_layer *p; //定义一个idr_layer指针
unsigned long flags;
spin_lock_irqsave(&idp->lock, flags);
if ((p = idp->id_free)) { //根free获取一个空闲idr_layer
idp->id_free = p->ary[0]; //idr空闲链表指针指向第二个idr_layer
idp->id_free_cnt--; //idr的空闲idr_layer个数减1(14-1)
p->ary[0] = NULL; //断开第一个idr_layer和第二个idr_layer的联系
}
spin_unlock_irqrestore(&idp->lock, flags);
return(p);
}
这里先穿插一下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
[cpp]
static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa)
{
int n, m, sh;
struct idr_layer *p, *new;
int l, id, oid;
unsigned long bm;
id = *starting_id;
restart:
p = idp->top; //根top
l = idp->layers; //l=1
pa[l--] = NULL; //p[1]=NULL;l=0
while (1) {
n = (id >> (IDR_BITS*l)) & IDR_MASK; //计算对应的n值,属于[0,31]
bm = ~p->bitmap; //取反位图
m = find_next_bit(&bm, IDR_SI