21 void idr_init(struct idr *idp)  in idr_init()  argument
23     memset(idp, 0, sizeof(struct idr));  in idr_init()
24     spin_init(&idp->lock);  in idr_init()
33 static void __move_to_free_list(struct idr *idp, struct idr_layer *p)  in __move_to_free_list()  argument
36     spin_lock_irqsave(&idp->lock, flags);  in __move_to_free_list()
39     p->ary[0] = idp->free_list;  in __move_to_free_list()
41     idp->free_list = p;  in __move_to_free_list()
43     ++(idp->id_free_cnt);  in __move_to_free_list()
45     spin_unlock_irqrestore(&idp->lock, flags);  in __move_to_free_list()
54 static void *__get_from_free_list(struct idr *idp)  in __get_from_free_list()  argument
56     if (idp->id_free_cnt == 0)  in __get_from_free_list()
58         if (idr_preload(idp, 0) != 0)  in __get_from_free_list()
66     spin_lock_irqsave(&idp->lock, flags);  in __get_from_free_list()
69     struct idr_layer *item = idp->free_list;  in __get_from_free_list()
77     idp->free_list = idp->free_list->ary[0];  in __get_from_free_list()
81     --(idp->id_free_cnt);  in __get_from_free_list()
83     spin_unlock_irqrestore(&idp->lock, flags);  in __get_from_free_list()
95 int idr_preload(struct idr *idp, gfp_t gfp_mask)  in idr_preload()  argument
98     while (idp->id_free_cnt < IDR_FREE_MAX)  in idr_preload()
105         __move_to_free_list(idp, new_one);  in idr_preload()
127 static int __idr_grow(struct idr *idp)  in __idr_grow()  argument
129     struct idr_layer *new_node = __get_from_free_list(idp);  in __idr_grow()
133     __swap(&new_node, &idp->top);  in __idr_grow()
135     idp->top->ary[0] = new_node;  in __idr_grow()
136     idp->top->layer = new_node ? (new_node->layer + 1) : 0; // 注意特判空指针  in __idr_grow()
137     idp->top->bitmap = 0;  in __idr_grow()
138     idp->top->full = 0; // clear  in __idr_grow()
142         idp->top->bitmap = 1;  in __idr_grow()
146         idp->top->full = 1; // 别忘了初始化 full  in __idr_grow()
159 static int __idr_get_empty_slot(struct idr *idp, struct idr_layer **stk)  in __idr_get_empty_slot()  argument
162     while (NULL == idp->top || idp->top->full == IDR_FULL)  in __idr_get_empty_slot()
163         if (__idr_grow(idp) != 0)  in __idr_get_empty_slot()
167     int layer = idp->top->layer;  in __idr_get_empty_slot()
171     struct idr_layer *cur_layer = idp->top;  in __idr_get_empty_slot()
189             cur_layer = __get_from_free_list(idp);  in __idr_get_empty_slot()
213 static __always_inline void __idr_mark_full(struct idr *idp, int id, struct idr_layer **stk, int ma…  in __idr_mark_full()  argument
216     if (unlikely(NULL == stk[0] || NULL == idp->top))  in __idr_mark_full()
248 static __always_inline int __idr_get_path(struct idr *idp, int id, struct idr_layer **stk)  in __idr_get_path()  argument
251     if (unlikely(idp->top == NULL || __id < 0))  in __idr_get_path()
257     struct idr_layer *cur_layer = idp->top;  in __idr_get_path()
294 static __always_inline void __idr_erase_full(struct idr *idp, int id, struct idr_layer **stk, int m…  in __idr_erase_full()  argument
297     if (unlikely(NULL == stk[0] || NULL == idp->top))  in __idr_erase_full()
340     while (idp->top != NULL && ((idp->top->bitmap <= 1 && idp->top->layer > 0) || // 一条链的情况  in __idr_erase_full()
341                                 (idp->top->layer == 0 && idp->top->bitmap == 0))) // 最后一个点的情况  in __idr_erase_full()
343         struct idr_layer *t = idp->top->layer ? idp->top->ary[0] : NULL;  in __idr_erase_full()
344         __idr_layer_free(idp->top);  in __idr_erase_full()
345         idp->top = t;  in __idr_erase_full()
357 static int __idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id)  in __idr_get_new_above_int()  argument
364     int64_t id = __idr_get_empty_slot(idp, stk);  in __idr_get_new_above_int()
369         __idr_mark_full(idp, id, stk, 2);  in __idr_get_new_above_int()
383 int idr_alloc(struct idr *idp, void *ptr, int *id)  in idr_alloc()  argument
385     int rv = __idr_get_new_above_int(idp, ptr, 0);  in idr_alloc()
400 void *idr_remove(struct idr *idp, int id)  in idr_remove()  argument
403     if (unlikely(idp->top == NULL || __id < 0))  in idr_remove()
408     if (0 == __idr_get_path(idp, __id, stk))  in idr_remove()
412     __idr_erase_full(idp, __id, stk, 0);  in idr_remove()
423 static void __idr_remove_all_with_free(struct idr *idp, bool free)  in __idr_remove_all_with_free()  argument
425     if (unlikely(NULL == idp->top))  in __idr_remove_all_with_free()
434     struct idr_layer *cur_layer = idp->top;  in __idr_remove_all_with_free()
468     idp->top = NULL;  in __idr_remove_all_with_free()
475 static void __idr_destroy_with_free(struct idr *idp)  in __idr_destroy_with_free()  argument
477     if (likely(idp->top))  in __idr_destroy_with_free()
478         __idr_remove_all_with_free(idp, 1);  in __idr_destroy_with_free()
479     idp->top = NULL;  in __idr_destroy_with_free()
480     while (idp->id_free_cnt)  in __idr_destroy_with_free()
481         __idr_layer_free(__get_from_free_list(idp));  in __idr_destroy_with_free()
482     idp->free_list = NULL;  in __idr_destroy_with_free()
490 void idr_remove_all(struct idr *idp)  in idr_remove_all()  argument
492     if (unlikely(NULL == idp->top))  in idr_remove_all()
495     __idr_remove_all_with_free(idp, 0);  in idr_remove_all()
503 void idr_destroy(struct idr *idp)  in idr_destroy()  argument
505     idr_remove_all(idp);  in idr_destroy()
506     idp->top = NULL;  in idr_destroy()
507     while (idp->id_free_cnt)  in idr_destroy()
508         __idr_layer_free(__get_from_free_list(idp));  in idr_destroy()
509     idp->free_list = NULL;  in idr_destroy()
519 void *idr_find(struct idr *idp, int id)  in idr_find()  argument
522     if (unlikely(idp->top == NULL || __id < 0))  in idr_find()
528     struct idr_layer *cur_layer = idp->top;  in idr_find()
558 void *idr_find_next_getid(struct idr *idp, int64_t start_id, int *nextid)  in idr_find_next_getid()  argument
561     if (unlikely(idp->top == NULL))  in idr_find_next_getid()
580     struct idr_layer *cur_layer = idp->top;  in idr_find_next_getid()
654 void *idr_find_next(struct idr *idp, int start_id)  in idr_find_next()  argument
657     void *ptr = idr_find_next_getid(idp, start_id, &nextid);  in idr_find_next()
671 int idr_replace_get_old(struct idr *idp, void *ptr, int id, void **old_ptr)  in idr_replace_get_old()  argument
681     if (unlikely(idp->top == NULL || __id < 0))  in idr_replace_get_old()
684     struct idr_layer *cur_layer = idp->top;  in idr_replace_get_old()
716 int idr_replace(struct idr *idp, void *ptr, int id)  in idr_replace()  argument
723     int flags = idr_replace_get_old(idp, ptr, __id, &old_ptr);  in idr_replace()
735 bool idr_empty(struct idr *idp)  in idr_empty()  argument
737     if (idp == NULL || idp->top == NULL || !idp->top->bitmap)  in idr_empty()
788 bool idr_count(struct idr *idp, int id)  in idr_count()  argument
792     if (unlikely(idp == NULL || idp->top == NULL || __id < 0))  in idr_count()
796     struct idr_layer *cur_layer = idp->top;  in idr_count()