11  * idr_alloc_u32() - Allocate an ID.
13  * @ptr: Pointer to be associated with the new ID.
14  * @nextid: Pointer to an ID.
15  * @max: The maximum ID to allocate (inclusive).
18  * Allocates an unused ID in the range specified by @nextid and @max.
20  * is exclusive.  The new ID is assigned to @nextid before the pointer
22  * to by @ptr, a concurrent lookup will not find an uninitialised ID.
29  * Return: 0 if an ID was allocated, -ENOMEM if memory allocation failed,
39 	unsigned int id = *nextid;  in idr_alloc_u32()  local
44 	id = (id < base) ? 0 : id - base;  in idr_alloc_u32()
45 	radix_tree_iter_init(&iter, id);  in idr_alloc_u32()
60  * idr_alloc() - Allocate an ID.
62  * @ptr: Pointer to be associated with the new ID.
63  * @start: The minimum ID (inclusive).
64  * @end: The maximum ID (exclusive).
67  * Allocates an unused ID in the range specified by @start and @end.  If
76  * Return: The newly allocated ID, -ENOMEM if memory allocation failed,
81 	u32 id = start;  in idr_alloc()  local
87 	ret = idr_alloc_u32(idr, ptr, &id, end > 0 ? end - 1 : INT_MAX, gfp);  in idr_alloc()
91 	return id;  in idr_alloc()
96  * idr_alloc_cyclic() - Allocate an ID cyclically.
98  * @ptr: Pointer to be associated with the new ID.
99  * @start: The minimum ID (inclusive).
100  * @end: The maximum ID (exclusive).
103  * Allocates an unused ID in the range specified by @nextid and @end.  If
106  * The search for an unused ID will start at the last ID allocated and will
114  * Return: The newly allocated ID, -ENOMEM if memory allocation failed,
119 	u32 id = idr->idr_next;  in idr_alloc_cyclic()  local
122 	if ((int)id < start)  in idr_alloc_cyclic()
123 		id = start;  in idr_alloc_cyclic()
125 	err = idr_alloc_u32(idr, ptr, &id, max, gfp);  in idr_alloc_cyclic()
126 	if ((err == -ENOSPC) && (id > start)) {  in idr_alloc_cyclic()
127 		id = start;  in idr_alloc_cyclic()
128 		err = idr_alloc_u32(idr, ptr, &id, max, gfp);  in idr_alloc_cyclic()
133 	idr->idr_next = id + 1;  in idr_alloc_cyclic()
134 	return id;  in idr_alloc_cyclic()
139  * idr_remove() - Remove an ID from the IDR.
141  * @id: Pointer ID.
143  * Removes this ID from the IDR.  If the ID was not previously in the IDR,
150  * Return: The pointer formerly associated with this ID.
152 void *idr_remove(struct idr *idr, unsigned long id)  in idr_remove()  argument
154 	return radix_tree_delete_item(&idr->idr_rt, id - idr->idr_base, NULL);  in idr_remove()
159  * idr_find() - Return pointer for given ID.
161  * @id: Pointer ID.
163  * Looks up the pointer associated with this ID.  A %NULL pointer may
164  * indicate that @id is not allocated or that the %NULL pointer was
165  * associated with this ID.
170  * Return: The pointer associated with this ID.
172 void *idr_find(const struct idr *idr, unsigned long id)  in idr_find()  argument
174 	return radix_tree_lookup(&idr->idr_rt, id - idr->idr_base);  in idr_find()
185  * the ID, the entry and @data.
196 		int (*fn)(int id, void *p, void *data), void *data)  in idr_for_each()  argument
204 		unsigned long id = iter.index + base;  in idr_for_each()  local
206 		if (WARN_ON_ONCE(id > INT_MAX))  in idr_for_each()
208 		ret = fn(id, rcu_dereference_raw(*slot), data);  in idr_for_each()
220  * @nextid: Pointer to an ID.
222  * Returns the next populated entry in the tree with an ID greater than
224  * to the ID of the found value.  To use in a loop, the value pointed to by
233 	unsigned long id = *nextid;  in idr_get_next_ul()  local
235 	id = (id < base) ? 0 : id - base;  in idr_get_next_ul()
236 	radix_tree_for_each_slot(slot, &idr->idr_rt, &iter, id) {  in idr_get_next_ul()
257  * @nextid: Pointer to an ID.
259  * Returns the next populated entry in the tree with an ID greater than
261  * to the ID of the found value.  To use in a loop, the value pointed to by
266 	unsigned long id = *nextid;  in idr_get_next()  local
267 	void *entry = idr_get_next_ul(idr, &id);  in idr_get_next()
269 	if (WARN_ON_ONCE(id > INT_MAX))  in idr_get_next()
271 	*nextid = id;  in idr_get_next()
277  * idr_replace() - replace pointer for given ID.
279  * @ptr: New pointer to associate with the ID.
280  * @id: ID to change.
282  * Replace the pointer registered with an ID and return the old value.
284  * idr_alloc() and idr_remove() (as long as the ID being removed is not
287  * Returns: the old value on success.  %-ENOENT indicates that @id was not
290 void *idr_replace(struct idr *idr, void *ptr, unsigned long id)  in idr_replace()  argument
296 	id -= idr->idr_base;  in idr_replace()
298 	entry = __radix_tree_lookup(&idr->idr_rt, id, &node, &slot);  in idr_replace()
299 	if (!slot || radix_tree_tag_get(&idr->idr_rt, id, IDR_FREE))  in idr_replace()
311  * The IDA is an ID allocator which does not provide the ability to
312  * associate an ID with a pointer.  As such, it only needs to store one
313  * bit per ID, and so is more space efficient than an IDR.  To use an IDA,
315  * then initialise it using ida_init()).  To allocate a new ID, call
317  * To free an ID, call ida_free().
366  * ida_alloc_range() - Allocate an unused ID.
368  * @min: Lowest ID to allocate.
369  * @max: Highest ID to allocate.
372  * Allocate an ID between @min and @max, inclusive.  The allocated ID will
376  * Return: The allocated ID, or %-ENOMEM if memory could not be allocated,
478  * ida_free() - Release an allocated ID.
480  * @id: Previously allocated ID.
484 void ida_free(struct ida *ida, unsigned int id)  in ida_free()  argument
486 	XA_STATE(xas, &ida->xa, id / IDA_BITMAP_BITS);  in ida_free()
487 	unsigned bit = id % IDA_BITMAP_BITS;  in ida_free()
491 	BUG_ON((int)id < 0);  in ida_free()
521 	WARN(1, "ida_free called for id=%d which is not allocated.\n", id);  in ida_free()