1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
#ifndef _LINUX_GENERIC_RADIX_TREE_H
#define _LINUX_GENERIC_RADIX_TREE_H
/*
* Generic radix trees/sparse arrays:
*
* A generic radix tree has all nodes of size PAGE_SIZE - both leaves and
* interior nodes.
*/
#include <linux/page.h>
#include <linux/bug.h>
#include <linux/kernel.h>
#include <linux/log2.h>
struct genradix_node;
struct __genradix {
struct genradix_node *root;
size_t depth;
};
/*
* NOTE: currently, sizeof(_type) must be a power of two and not larger than
* PAGE_SIZE:
*/
#define __GENRADIX_INITIALIZER \
{ \
.tree = { \
.root = NULL, \
.depth = 0, \
} \
}
/*
* 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 DECLARE_GENRADIX_TYPE(_name, _type) \
struct _name { \
struct __genradix tree; \
_type type[0] __aligned(1); \
}
#define DECLARE_GENRADIX(_name, _type) \
struct { \
struct __genradix tree; \
_type type[0] __aligned(1); \
} _name
#define DEFINE_GENRADIX(_name, _type) \
DECLARE_GENRADIX(_name, _type) = __GENRADIX_INITIALIZER
#define genradix_init(_radix) \
do { \
*(_radix) = (typeof(*_radix)) __GENRADIX_INITIALIZER; \
} while (0)
void __genradix_free(struct __genradix *);
#define genradix_free(_radix) __genradix_free(&(_radix)->tree)
static inline size_t __idx_to_offset(size_t idx, size_t obj_size)
{
BUILD_BUG_ON(obj_size > PAGE_SIZE);
if (!is_power_of_2(obj_size)) {
size_t objs_per_page = PAGE_SIZE / obj_size;
return (idx / objs_per_page) * PAGE_SIZE +
(idx % objs_per_page) * obj_size;
} else {
return idx * obj_size;
}
}
#define __genradix_cast(_radix) (typeof((_radix)->type[0]) *)
#define __genradix_obj_size(_radix) sizeof((_radix)->type[0])
#define __genradix_idx_to_offset(_radix, _idx) \
__idx_to_offset(_idx, __genradix_obj_size(_radix))
void *__genradix_ptr(struct __genradix *, size_t);
/* Returns a pointer to element at @_idx */
#define genradix_ptr(_radix, _idx) \
(__genradix_cast(_radix) \
__genradix_ptr(&(_radix)->tree, \
__genradix_idx_to_offset(_radix, _idx)))
void *__genradix_ptr_alloc(struct __genradix *, size_t, gfp_t);
/* Returns a pointer to element at @_idx, allocating it if necessary */
#define genradix_ptr_alloc(_radix, _idx, _gfp) \
(__genradix_cast(_radix) \
__genradix_ptr_alloc(&(_radix)->tree, \
__genradix_idx_to_offset(_radix, _idx), \
_gfp))
struct genradix_iter {
size_t offset;
size_t pos;
};
static inline void genradix_iter_init(struct genradix_iter *iter)
{
iter->offset = 0;
iter->pos = 0;
}
void *__genradix_iter_peek(struct genradix_iter *, struct __genradix *, size_t);
#define genradix_iter_peek(_iter, _radix) \
(__genradix_cast(_radix) \
__genradix_iter_peek(_iter, &(_radix)->tree, \
PAGE_SIZE / __genradix_obj_size(_radix)))
static inline void __genradix_iter_advance(struct genradix_iter *iter,
size_t obj_size)
{
iter->offset += obj_size;
if (!is_power_of_2(obj_size) &&
(iter->offset & (PAGE_SIZE - 1)) + obj_size > PAGE_SIZE)
iter->offset = round_up(iter->offset, PAGE_SIZE);
iter->pos++;
}
#define genradix_iter_advance(_iter, _radix) \
__genradix_iter_advance(_iter, __genradix_obj_size(_radix))
#endif /* _LINUX_GENERIC_RADIX_TREE_H */
|
