#ifndef _LINUX_GENERIC_RADIX_TREE_H #define _LINUX_GENERIC_RADIX_TREE_H /** * DOC: Generic radix trees/sparse arrays * * Very simple and minimalistic, supporting arbitrary size entries up to * GENRADIX_NODE_SIZE. * * A genradix is defined with the type it will store, like so: * * static GENRADIX(struct foo) foo_genradix; * * The main operations are: * * - genradix_init(radix) - initialize an empty genradix * * - genradix_free(radix) - free all memory owned by the genradix and * reinitialize it * * - genradix_ptr(radix, idx) - gets a pointer to the entry at idx, returning * NULL if that entry does not exist * * - genradix_ptr_alloc(radix, idx, gfp) - gets a pointer to an entry, * allocating it if necessary * * - genradix_for_each(radix, iter, p) - iterate over each entry in a genradix * * The radix tree allocates one page of entries at a time, so entries may exist * that were never explicitly allocated - they will be initialized to all * zeroes. * * Internally, a genradix is just a radix tree of pages, and indexing works in * terms of byte offsets. The wrappers in this header file use sizeof on the * type the radix contains to calculate a byte offset from the index - see * __idx_to_offset. */ #include <asm/page.h> #include <linux/bug.h> #include <linux/limits.h> #include <linux/log2.h> #include <linux/math.h> #include <linux/slab.h> #include <linux/types.h> struct genradix_root; #define GENRADIX_NODE_SHIFT … #define GENRADIX_NODE_SIZE … #define GENRADIX_ARY … #define GENRADIX_ARY_SHIFT … /* depth that's needed for a genradix that can address up to ULONG_MAX: */ #define GENRADIX_MAX_DEPTH … #define GENRADIX_DEPTH_MASK … static inline int genradix_depth_shift(unsigned depth) { … } /* * Returns size (of data, in bytes) that a tree of a given depth holds: */ static inline size_t genradix_depth_size(unsigned depth) { … } static inline unsigned genradix_root_to_depth(struct genradix_root *r) { … } static inline struct genradix_node *genradix_root_to_node(struct genradix_root *r) { … } struct __genradix { … }; struct genradix_node { … }; static inline struct genradix_node *genradix_alloc_node(gfp_t gfp_mask) { … } static inline void genradix_free_node(struct genradix_node *node) { … } /* * NOTE: currently, sizeof(_type) must not be larger than GENRADIX_NODE_SIZE: */ #define __GENRADIX_INITIALIZER … /* * We use a 0 size array to stash the type we're storing without taking any * space at runtime - then the various accessor macros can use typeof() to get * to it for casts/sizeof - we also force the alignment so that storing a type * with a ridiculous alignment doesn't blow up the alignment or size of the * genradix. */ #define GENRADIX(_type) … #define DEFINE_GENRADIX(_name, _type) … /** * genradix_init - initialize a genradix * @_radix: genradix to initialize * * Does not fail */ #define genradix_init(_radix) … void __genradix_free(struct __genradix *); /** * genradix_free: free all memory owned by a genradix * @_radix: the genradix to free * * After freeing, @_radix will be reinitialized and empty */ #define genradix_free(_radix) … static inline size_t __idx_to_offset(size_t idx, size_t obj_size) { … } #define __genradix_cast(_radix) … #define __genradix_obj_size(_radix) … #define __genradix_objs_per_page(_radix) … #define __genradix_page_remainder(_radix) … #define __genradix_idx_to_offset(_radix, _idx) … static inline void *__genradix_ptr_inlined(struct __genradix *radix, size_t offset) { … } #define genradix_ptr_inlined(_radix, _idx) … void *__genradix_ptr(struct __genradix *, size_t); /** * genradix_ptr - get a pointer to a genradix entry * @_radix: genradix to access * @_idx: index to fetch * * Returns a pointer to entry at @_idx, or NULL if that entry does not exist. */ #define genradix_ptr(_radix, _idx) … void *__genradix_ptr_alloc(struct __genradix *, size_t, struct genradix_node **, gfp_t); #define genradix_ptr_alloc_inlined(_radix, _idx, _gfp) … #define genradix_ptr_alloc_preallocated_inlined(_radix, _idx, _new_node, _gfp) … /** * genradix_ptr_alloc - get a pointer to a genradix entry, allocating it * if necessary * @_radix: genradix to access * @_idx: index to fetch * @_gfp: gfp mask * * Returns a pointer to entry at @_idx, or NULL on allocation failure */ #define genradix_ptr_alloc(_radix, _idx, _gfp) … #define genradix_ptr_alloc_preallocated(_radix, _idx, _new_node, _gfp) … struct genradix_iter { … }; /** * genradix_iter_init - initialize a genradix_iter * @_radix: genradix that will be iterated over * @_idx: index to start iterating from */ #define genradix_iter_init(_radix, _idx) … void *__genradix_iter_peek(struct genradix_iter *, struct __genradix *, size_t); /** * genradix_iter_peek - get first entry at or above iterator's current * position * @_iter: a genradix_iter * @_radix: genradix being iterated over * * If no more entries exist at or above @_iter's current position, returns NULL */ #define genradix_iter_peek(_iter, _radix) … void *__genradix_iter_peek_prev(struct genradix_iter *, struct __genradix *, size_t, size_t); /** * genradix_iter_peek_prev - get first entry at or below iterator's current * position * @_iter: a genradix_iter * @_radix: genradix being iterated over * * If no more entries exist at or below @_iter's current position, returns NULL */ #define genradix_iter_peek_prev(_iter, _radix) … static inline void __genradix_iter_advance(struct genradix_iter *iter, size_t obj_size) { … } #define genradix_iter_advance(_iter, _radix) … static inline void __genradix_iter_rewind(struct genradix_iter *iter, size_t obj_size) { … } #define genradix_iter_rewind(_iter, _radix) … #define genradix_for_each_from(_radix, _iter, _p, _start) … /** * genradix_for_each - iterate over entry in a genradix * @_radix: genradix to iterate over * @_iter: a genradix_iter to track current position * @_p: pointer to genradix entry type * * On every iteration, @_p will point to the current entry, and @_iter.pos * will be the current entry's index. */ #define genradix_for_each(_radix, _iter, _p) … #define genradix_last_pos(_radix) … /** * genradix_for_each_reverse - iterate over entry in a genradix, reverse order * @_radix: genradix to iterate over * @_iter: a genradix_iter to track current position * @_p: pointer to genradix entry type * * On every iteration, @_p will point to the current entry, and @_iter.pos * will be the current entry's index. */ #define genradix_for_each_reverse(_radix, _iter, _p) … int __genradix_prealloc(struct __genradix *, size_t, gfp_t); /** * genradix_prealloc - preallocate entries in a generic radix tree * @_radix: genradix to preallocate * @_nr: number of entries to preallocate * @_gfp: gfp mask * * Returns 0 on success, -ENOMEM on failure */ #define genradix_prealloc(_radix, _nr, _gfp) … #endif /* _LINUX_GENERIC_RADIX_TREE_H */
Codebase Browser
linux