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
57 	DIV_ROUND_UP(BITS_PER_LONG - GENRADIX_NODE_SHIFT, GENRADIX_ARY_SHIFT)
60 	((unsigned long) (roundup_pow_of_two(GENRADIX_MAX_DEPTH + 1) - 1))
122  * space at runtime - then the various accessor macros can use typeof() to get
123  * to it for casts/sizeof - we also force the alignment so that storing a type
138  * genradix_init - initialize a genradix
156 #define genradix_free(_radix)	__genradix_free(&(_radix)->tree)
175 #define __genradix_cast(_radix)		(typeof((_radix)->type[0]) *)
176 #define __genradix_obj_size(_radix)	sizeof((_radix)->type[0])
178 	(GENRADIX_NODE_SIZE / sizeof((_radix)->type[0]))
180 	(GENRADIX_NODE_SIZE % sizeof((_radix)->type[0]))
187 	struct genradix_root *r = READ_ONCE(radix->root);  in __genradix_ptr_inlined()
196 		shift -= GENRADIX_ARY_SHIFT;  in __genradix_ptr_inlined()
197 		n = n->children[offset >> shift];  in __genradix_ptr_inlined()
198 		offset &= (1UL << shift) - 1;  in __genradix_ptr_inlined()
201 	return n ? &n->data[offset] : NULL;  in __genradix_ptr_inlined()
206 	 __genradix_ptr_inlined(&(_radix)->tree,		\
212  * genradix_ptr - get a pointer to a genradix entry
220 	 __genradix_ptr(&(_radix)->tree,			\
228 	 (__genradix_ptr_inlined(&(_radix)->tree,			\
230 	  __genradix_ptr_alloc(&(_radix)->tree,				\
236 	 (__genradix_ptr_inlined(&(_radix)->tree,			\
238 	  __genradix_ptr_alloc(&(_radix)->tree,				\
243  * genradix_ptr_alloc - get a pointer to a genradix entry, allocating it
253 	 __genradix_ptr_alloc(&(_radix)->tree,			\
259 	 __genradix_ptr_alloc(&(_radix)->tree,			\
269  * genradix_iter_init - initialize a genradix_iter
270  * @_radix:	genradix that will be iterated over
282  * genradix_iter_peek - get first entry at or above iterator's current
285  * @_radix:	genradix being iterated over
287  * If no more entries exist at or above @_iter's current position, returns NULL
291 	 __genradix_iter_peek(_iter, &(_radix)->tree,		\
298  * genradix_iter_peek_prev - get first entry at or below iterator's current
301  * @_radix:	genradix being iterated over
303  * If no more entries exist at or below @_iter's current position, returns NULL
307 	 __genradix_iter_peek_prev(_iter, &(_radix)->tree,	\
315 	if (iter->offset + obj_size < iter->offset) {  in __genradix_iter_advance()
316 		iter->offset	= SIZE_MAX;  in __genradix_iter_advance()
317 		iter->pos	= SIZE_MAX;  in __genradix_iter_advance()
321 	iter->offset += obj_size;  in __genradix_iter_advance()
324 	    (iter->offset & (GENRADIX_NODE_SIZE - 1)) + obj_size > GENRADIX_NODE_SIZE)  in __genradix_iter_advance()
325 		iter->offset = round_up(iter->offset, GENRADIX_NODE_SIZE);  in __genradix_iter_advance()
327 	iter->pos++;  in __genradix_iter_advance()
336 	if (iter->offset == 0 ||  in __genradix_iter_rewind()
337 	    iter->offset == SIZE_MAX) {  in __genradix_iter_rewind()
338 		iter->offset = SIZE_MAX;  in __genradix_iter_rewind()
342 	if ((iter->offset & (GENRADIX_NODE_SIZE - 1)) == 0)  in __genradix_iter_rewind()
343 		iter->offset -= GENRADIX_NODE_SIZE % obj_size;  in __genradix_iter_rewind()
345 	iter->offset -= obj_size;  in __genradix_iter_rewind()
346 	iter->pos--;  in __genradix_iter_rewind()
358  * genradix_for_each - iterate over entry in a genradix
359  * @_radix:	genradix to iterate over
360  * @_iter:	a genradix_iter to track current position
363  * On every iteration, @_p will point to the current entry, and @_iter.pos
364  * will be the current entry's index.
370 	(SIZE_MAX / GENRADIX_NODE_SIZE * __genradix_objs_per_page(_radix) - 1)
373  * genradix_for_each_reverse - iterate over entry in a genradix, reverse order
374  * @_radix:	genradix to iterate over
375  * @_iter:	a genradix_iter to track current position
378  * On every iteration, @_p will point to the current entry, and @_iter.pos
379  * will be the current entry's index.
389  * genradix_prealloc - preallocate entries in a generic radix tree
394  * Returns 0 on success, -ENOMEM on failure
397 	 __genradix_prealloc(&(_radix)->tree,			\