1 #ifndef _LINUX_GENERIC_RADIX_TREE_H
2 #define _LINUX_GENERIC_RADIX_TREE_H
5 * Generic radix trees/sparse arrays:
7 * A generic radix tree has all nodes of size PAGE_SIZE - both leaves and
11 #include <linux/bug.h>
12 #include <linux/kernel.h>
13 #include <linux/log2.h>
18 struct genradix_node *root;
23 * NOTE: currently, sizeof(_type) must be a power of two and not larger than
27 #define __GENRADIX_INITIALIZER \
36 * We use a 0 size array to stash the type we're storing without taking any
37 * space at runtime - then the various accessor macros can use typeof() to get
38 * to it for casts/sizeof - we also force the alignment so that storing a type
39 * with a ridiculous alignment doesn't blow up the alignment or size of the
43 #define GENRADIX(_type) \
45 struct __genradix tree; \
46 _type type[0] __aligned(1); \
49 #define DEFINE_GENRADIX(_name, _type) \
50 GENRADIX(_type) _name = __GENRADIX_INITIALIZER
52 #define genradix_init(_radix) \
54 *(_radix) = (typeof(*_radix)) __GENRADIX_INITIALIZER; \
57 void __genradix_free(struct __genradix *);
59 #define genradix_free(_radix) __genradix_free(&(_radix)->tree)
61 static inline size_t __idx_to_offset(size_t idx, size_t obj_size)
63 BUILD_BUG_ON(obj_size > PAGE_SIZE);
65 if (!is_power_of_2(obj_size)) {
66 size_t objs_per_page = PAGE_SIZE / obj_size;
68 return (idx / objs_per_page) * PAGE_SIZE +
69 (idx % objs_per_page) * obj_size;
71 return idx * obj_size;
75 #define __genradix_cast(_radix) (typeof((_radix)->type[0]) *)
76 #define __genradix_obj_size(_radix) sizeof((_radix)->type[0])
77 #define __genradix_idx_to_offset(_radix, _idx) \
78 __idx_to_offset(_idx, __genradix_obj_size(_radix))
80 void *__genradix_ptr(struct __genradix *, size_t);
82 /* Returns a pointer to element at @_idx */
83 #define genradix_ptr(_radix, _idx) \
84 (__genradix_cast(_radix) \
85 __genradix_ptr(&(_radix)->tree, \
86 __genradix_idx_to_offset(_radix, _idx)))
88 void *__genradix_ptr_alloc(struct __genradix *, size_t, gfp_t);
90 /* Returns a pointer to element at @_idx, allocating it if necessary */
91 #define genradix_ptr_alloc(_radix, _idx, _gfp) \
92 (__genradix_cast(_radix) \
93 __genradix_ptr_alloc(&(_radix)->tree, \
94 __genradix_idx_to_offset(_radix, _idx), \
97 struct genradix_iter {
102 #define genradix_iter_init(_radix, _idx) \
103 ((struct genradix_iter) { \
105 .offset = __genradix_idx_to_offset((_radix), (_idx)),\
108 void *__genradix_iter_peek(struct genradix_iter *, struct __genradix *, size_t);
110 #define genradix_iter_peek(_iter, _radix) \
111 (__genradix_cast(_radix) \
112 __genradix_iter_peek(_iter, &(_radix)->tree, \
113 PAGE_SIZE / __genradix_obj_size(_radix)))
115 static inline void __genradix_iter_advance(struct genradix_iter *iter,
118 iter->offset += obj_size;
120 if (!is_power_of_2(obj_size) &&
121 (iter->offset & (PAGE_SIZE - 1)) + obj_size > PAGE_SIZE)
122 iter->offset = round_up(iter->offset, PAGE_SIZE);
127 #define genradix_iter_advance(_iter, _radix) \
128 __genradix_iter_advance(_iter, __genradix_obj_size(_radix))
130 #endif /* _LINUX_GENERIC_RADIX_TREE_H */