Linux的idr机制(32叉树)(4)

四.查找id
1.idr_find

void *idr_find(struct idr *idp, int id) { int n; struct idr_layer *p; p = rcu_dereference_raw(idp->top); //获取根top if (!p) return NULL; n = (p->layer+1) * IDR_BITS; //计算最外层的n值 id &= MAX_ID_MASK; if (id >= (1 << n)) return NULL; BUG_ON(n == 0); while (n > 0 && p) { //循环一层层查找 n -= IDR_BITS; BUG_ON(n != p->layer*IDR_BITS); p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]); //一次获取an ... a0 } return((void *)p); } EXPORT_SYMBOL(idr_find);

前面讲过32进制的id值算法

当构建完idr机制之后

id=top->ary[an]->ary[a(n-1)]->....->ary[a0]来获得

借助图片分析下(idr_layer13的位图标记有错)

五idr操作

1. idr_remove  idr_remove_all 移除

void idr_remove(struct idr *idp, int id) { struct idr_layer *p; struct idr_layer *to_free; id &= MAX_ID_MASK; sub_remove(idp, (idp->layers - 1) * IDR_BITS, id); if (idp->top && idp->top->count == 1 && (idp->layers > 1) && idp->top->ary[0]) { to_free = idp->top; p = idp->top->ary[0]; rcu_assign_pointer(idp->top, p); --idp->layers; to_free->bitmap = to_free->count = 0; free_layer(to_free); } while (idp->id_free_cnt >= IDR_FREE_MAX) { p = get_from_free_list(idp); kmem_cache_free(idr_layer_cache, p); } return; } EXPORT_SYMBOL(idr_remove);

移除全部

void idr_remove_all(struct idr *idp) { int n, id, max; int bt_mask; struct idr_layer *p; struct idr_layer *pa[MAX_LEVEL]; struct idr_layer **paa = &pa[0]; n = idp->layers * IDR_BITS; p = idp->top; rcu_assign_pointer(idp->top, NULL); max = 1 << n; id = 0; while (id < max) { while (n > IDR_BITS && p) { n -= IDR_BITS; *paa++ = p; p = p->ary[(id >> n) & IDR_MASK]; } bt_mask = id; id += 1 << n; /* Get the highest bit that the above add changed from 0->1. */ while (n < fls(id ^ bt_mask)) { if (p) free_layer(p); n += IDR_BITS; p = *--paa; } } idp->layers = 0; } EXPORT_SYMBOL(idr_remove_all);

 

2.idr_replace 替换

void *idr_replace(struct idr *idp, void *ptr, int id) { int n; struct idr_layer *p, *old_p; p = idp->top; if (!p) return ERR_PTR(-EINVAL); n = (p->layer+1) * IDR_BITS; id &= MAX_ID_MASK; if (id >= (1 << n)) return ERR_PTR(-EINVAL); n -= IDR_BITS; while ((n > 0) && p) { p = p->ary[(id >> n) & IDR_MASK]; n -= IDR_BITS; } n = id & IDR_MASK; if (unlikely(p == NULL || !test_bit(n, &p->bitmap))) return ERR_PTR(-ENOENT); old_p = p->ary[n]; rcu_assign_pointer(p->ary[n], ptr); return old_p; } EXPORT_SYMBOL(idr_replace);

六.idr空闲链表的销毁