idr机制(32叉树)(四)
{
struct idr_layer *p, *new;
int layers, v, id;
unsigned long flags;
id = starting_id;
build_up:
p = idp->top; //获取根top
layers = idp->layers; //获取层数量 layers=1
if (unlikely(!p)) { //FALSE
if (!(p = get_from_free_list(idp)))
return -1;
p->layer = 0;
layers = 1;
}
while ((layers < 6) && (id >= (1 << (layers*5)))) { //参考图B,如果id值超过或等于对应层所能容纳的最大数,则进入循环
layers++; //增加层数量
if (!p->count) { //0~31没使用,直接使用32就属于这种情况
p->layer++; //由于32需要添加1层的,所以之前的层的层号需要+1
continue; //层数量也需要加1
}
if (!(new = get_from_free_list(idp))) { //空闲链表中获取新的idr_layer
spin_lock_irqsave(&idp->lock, flags); //分配失败,--空闲idr_layer链表缺货
for (new = p; p && p != idp->top; new = p) { //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; //新的idr_layer->ary[0]指向旧的idr_layer
new->count = 1; //新的idr_layer计数加1
new->layer = layers-1; //设置新的idr_layer的层号
if (p->bitmap == IDR_FULL) //若旧的(叶子)idr_layer的id全用过了
__set_bit(0, &new->bitmap); //那么标记下新(父)idr_layer位图的第0位
p = new; //根top指向新的idr_layer
}
rcu_assign_pointer(idp->top, p); //设置根top
idp->layers = layers; //更新层数量
v = sub_alloc(idp, &id, pa); //获取id
if (v == IDR_NEED_TO_GROW) //该层id号全用完了,必须扩大idr_layer层数量
goto build_up;
return(v);
}
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; //pa[1]=NULL,l=0
while (1) {
n = (id >> (5*l)) & IDR_MASK; //n做处理 属于[0,31]
bm = ~p->bitmap; //位图取反
m = find_next_bit(&bm, IDR_SIZE, n); //查找n开始能用的位
if (m == IDR_SIZE) { //id表满了
l++; 层数+1
oid = id;
id = (id | ((1 << (5 * l)) - 1)) + 1; //id或上掩码再+1
if (id >= 1 << (idp->layers * 5)) { //需要添加层
*starting_id = id;
return IDR_NEED_TO_GROW;
}
p = pa[l];
BUG_ON(!p);
sh = 5 * (l + 1);
if (oid >> sh == id >> sh)
continue;
else
goto restart;
}
if (m != n) { //期望id给用但有可用id
sh = 5*l;
id = ((id >> sh) ^ n ^ m) << sh; //id设置为可用id
}
if ((id >= MAX_ID_BIT) || (id < 0))
return IDR_NOMORE_SPACE;
if (l == 0) //一层层循环计算直到到达叶子处l才为0
break;
if (!p->ary[m]) { //叶子m为空
new = get_from_free_list(idp); //从空闲链表拿一个idr_layer
if (!new)
return -1;
new->layer = l-1; //设置新链表层数
rcu_assign_pointer(p->ary[m], new); //叶子m指向新链表
p->count++; //使用计数加1
}
pa[l--] = p; //pa[大]=节点
p = p->ary[m]; //p=节点->叶子m
}
pa[l] = p; //pa[小]=叶子
return id;
}
来个效果图id=4吧
id=32情况(idr_layer13的位图1标记错了)
1024情况
四.查找id
1.idr_find
[cpp]
void *idr_find(struct idr *idp, int id)
{
int n;
struct idr_layer *p;