include/linux/generic-radix-tree.h

16  * - genradix_init(radix) - initialize an empty genradix
18  * - genradix_free(radix) - free all memory owned by the genradix and
21  * - genradix_ptr(radix, idx) - gets a pointer to the entry at idx, returning
24  * - genradix_ptr_alloc(radix, idx, gfp) - gets a pointer to an entry,
27  * - genradix_for_each(radix, iter, p) - iterate over each entry in a genradix
30  * that were never explicitly allocated - they will be initialized to all
35  * type the radix contains to calculate a byte offset from the index - see
65  * space at runtime - then the various accessor macros can use typeof() to get
66  * to it for casts/sizeof - we also force the alignment so that storing a type
81  * genradix_init - initialize a genradix
99 #define genradix_free(_radix)	__genradix_free(&(_radix)->tree)
118 #define __genradix_cast(_radix)		(typeof((_radix)->type[0]) *)
119 #define __genradix_obj_size(_radix)	sizeof((_radix)->type[0])
121 	(PAGE_SIZE / sizeof((_radix)->type[0]))
123 	(PAGE_SIZE % sizeof((_radix)->type[0]))
131  * genradix_ptr - get a pointer to a genradix entry
139 	 __genradix_ptr(&(_radix)->tree,			\
145  * genradix_ptr_alloc - get a pointer to a genradix entry, allocating it
155 	 __genradix_ptr_alloc(&(_radix)->tree,			\
165  * genradix_iter_init - initialize a genradix_iter
166  * @_radix:	genradix that will be iterated over
178  * genradix_iter_peek - get first entry at or above iterator's current
181  * @_radix:	genradix being iterated over
183  * If no more entries exist at or above @_iter's current position, returns NULL
187 	 __genradix_iter_peek(_iter, &(_radix)->tree,		\
194  * genradix_iter_peek_prev - get first entry at or below iterator's current
197  * @_radix:	genradix being iterated over
199  * If no more entries exist at or below @_iter's current position, returns NULL
203 	 __genradix_iter_peek_prev(_iter, &(_radix)->tree,	\
211 	if (iter->offset + obj_size < iter->offset) {  in __genradix_iter_advance()
212 		iter->offset	= SIZE_MAX;  in __genradix_iter_advance()
213 		iter->pos	= SIZE_MAX;  in __genradix_iter_advance()
217 	iter->offset += obj_size;  in __genradix_iter_advance()
220 	    (iter->offset & (PAGE_SIZE - 1)) + obj_size > PAGE_SIZE)  in __genradix_iter_advance()
221 		iter->offset = round_up(iter->offset, PAGE_SIZE);  in __genradix_iter_advance()
223 	iter->pos++;  in __genradix_iter_advance()
232 	if (iter->offset == 0 ||  in __genradix_iter_rewind()
233 	    iter->offset == SIZE_MAX) {  in __genradix_iter_rewind()
234 		iter->offset = SIZE_MAX;  in __genradix_iter_rewind()
238 	if ((iter->offset & (PAGE_SIZE - 1)) == 0)  in __genradix_iter_rewind()
239 		iter->offset -= PAGE_SIZE % obj_size;  in __genradix_iter_rewind()
241 	iter->offset -= obj_size;  in __genradix_iter_rewind()
242 	iter->pos--;  in __genradix_iter_rewind()
254  * genradix_for_each - iterate over entry in a genradix
255  * @_radix:	genradix to iterate over
256  * @_iter:	a genradix_iter to track current position
259  * On every iteration, @_p will point to the current entry, and @_iter.pos
260  * will be the current entry's index.
266 	(SIZE_MAX / PAGE_SIZE * __genradix_objs_per_page(_radix) - 1)
269  * genradix_for_each_reverse - iterate over entry in a genradix, reverse order
270  * @_radix:	genradix to iterate over
271  * @_iter:	a genradix_iter to track current position
274  * On every iteration, @_p will point to the current entry, and @_iter.pos
275  * will be the current entry's index.
285  * genradix_prealloc - preallocate entries in a generic radix tree
290  * Returns 0 on success, -ENOMEM on failure
293 	 __genradix_prealloc(&(_radix)->tree,			\