1 /* Public domain. */
2
3 #ifndef _LINUX_XARRAY_H
4 #define _LINUX_XARRAY_H
5
6 #include <linux/gfp.h>
7
8 #include <sys/tree.h>
9
10 #define XA_FLAGS_ALLOC (1 << 0)
11 #define XA_FLAGS_ALLOC1 (1 << 1)
12 #define XA_FLAGS_LOCK_IRQ (1 << 2)
13
14 /*
15 * lower bits of pointer are tagged:
16 * 00: pointer
17 * 01: value
18 * 10: internal
19 */
20 struct xarray_entry {
21 SPLAY_ENTRY(xarray_entry) entry;
22 int id;
23 void *ptr;
24 };
25
26 struct xarray {
27 gfp_t xa_flags;
28 struct mutex xa_lock;
29 SPLAY_HEAD(xarray_tree, xarray_entry) xa_tree;
30 };
31
32 #define DEFINE_XARRAY_ALLOC(name) \
33 struct xarray name = { \
34 .xa_flags = XA_FLAGS_ALLOC, \
35 .xa_lock = MUTEX_INITIALIZER(IPL_NONE), \
36 .xa_tree = SPLAY_INITIALIZER(&name.xa_tree) \
37 }
38
39 struct xarray_range {
40 uint32_t start;
41 uint32_t end;
42 };
43
44 #define XA_LIMIT(_start, _end) (struct xarray_range){ _start, _end }
45 #define xa_limit_32b XA_LIMIT(0, UINT_MAX)
46
47 void xa_init_flags(struct xarray *, gfp_t);
48 void xa_destroy(struct xarray *);
49 int __xa_alloc(struct xarray *, u32 *, void *, struct xarray_range, gfp_t);
50 int __xa_alloc_cyclic(struct xarray *, u32 *, void *, struct xarray_range,
51 u32 *, gfp_t);
52 void *__xa_load(struct xarray *, unsigned long);
53 void *__xa_store(struct xarray *, unsigned long, void *, gfp_t);
54 void *__xa_erase(struct xarray *, unsigned long);
55 void *xa_get_next(struct xarray *, unsigned long *);
56
57 #define xa_for_each(xa, index, entry) \
58 for (index = 0; ((entry) = xa_get_next(xa, &(index))) != NULL; index++)
59
60 #define xa_lock(_xa) do { \
61 mtx_enter(&(_xa)->xa_lock); \
62 } while (0)
63
64 #define xa_unlock(_xa) do { \
65 mtx_leave(&(_xa)->xa_lock); \
66 } while (0)
67
68 #define xa_lock_irq(_xa) do { \
69 mtx_enter(&(_xa)->xa_lock); \
70 } while (0)
71
72 #define xa_unlock_irq(_xa) do { \
73 mtx_leave(&(_xa)->xa_lock); \
74 } while (0)
75
76 #define xa_lock_irqsave(_xa, _flags) do { \
77 _flags = 0; \
78 mtx_enter(&(_xa)->xa_lock); \
79 } while (0)
80
81 #define xa_unlock_irqrestore(_xa, _flags) do { \
82 (void)(_flags); \
83 mtx_leave(&(_xa)->xa_lock); \
84 } while (0)
85
86 static inline void *
xa_mk_value(unsigned long v)87 xa_mk_value(unsigned long v)
88 {
89 unsigned long r = (v << 1) | 1;
90 return (void *)r;
91 }
92
93 static inline bool
xa_is_value(const void * e)94 xa_is_value(const void *e)
95 {
96 unsigned long v = (unsigned long)e;
97 return v & 1;
98 }
99
100 static inline unsigned long
xa_to_value(const void * e)101 xa_to_value(const void *e)
102 {
103 unsigned long v = (unsigned long)e;
104 return v >> 1;
105 }
106
107 #define XA_ERROR(x) ((struct xa_node *)(((unsigned long)x << 2) | 2))
108
109 static inline int
xa_err(const void * e)110 xa_err(const void *e)
111 {
112 long v = (long)e;
113 /* not tagged internal, not an errno */
114 if ((v & 3) != 2)
115 return 0;
116 v >>= 2;
117 if (v >= -ELAST)
118 return v;
119 return 0;
120 }
121
122 static inline bool
xa_is_err(const void * e)123 xa_is_err(const void *e)
124 {
125 return xa_err(e) != 0;
126 }
127
128 static inline int
xa_alloc(struct xarray * xa,u32 * id,void * entry,struct xarray_range xr,gfp_t gfp)129 xa_alloc(struct xarray *xa, u32 *id, void *entry, struct xarray_range xr,
130 gfp_t gfp)
131 {
132 int r;
133 mtx_enter(&xa->xa_lock);
134 r = __xa_alloc(xa, id, entry, xr, gfp);
135 mtx_leave(&xa->xa_lock);
136 return r;
137 }
138
139 static inline void *
xa_load(struct xarray * xa,unsigned long index)140 xa_load(struct xarray *xa, unsigned long index)
141 {
142 void *r;
143 r = __xa_load(xa, index);
144 return r;
145 }
146
147
148 static inline void *
xa_store(struct xarray * xa,unsigned long index,void * entry,gfp_t gfp)149 xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)
150 {
151 void *r;
152 mtx_enter(&xa->xa_lock);
153 r = __xa_store(xa, index, entry, gfp);
154 mtx_leave(&xa->xa_lock);
155 return r;
156 }
157
158 static inline void *
xa_erase(struct xarray * xa,unsigned long index)159 xa_erase(struct xarray *xa, unsigned long index)
160 {
161 void *r;
162 mtx_enter(&xa->xa_lock);
163 r = __xa_erase(xa, index);
164 mtx_leave(&xa->xa_lock);
165 return r;
166 }
167
168 static inline void *
xa_store_irq(struct xarray * xa,unsigned long index,void * entry,gfp_t gfp)169 xa_store_irq(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)
170 {
171 void *r;
172 mtx_enter(&xa->xa_lock);
173 r = __xa_store(xa, index, entry, gfp);
174 mtx_leave(&xa->xa_lock);
175 return r;
176 }
177
178 static inline void *
xa_erase_irq(struct xarray * xa,unsigned long index)179 xa_erase_irq(struct xarray *xa, unsigned long index)
180 {
181 void *r;
182 mtx_enter(&xa->xa_lock);
183 r = __xa_erase(xa, index);
184 mtx_leave(&xa->xa_lock);
185 return r;
186 }
187
188 static inline bool
xa_empty(const struct xarray * xa)189 xa_empty(const struct xarray *xa)
190 {
191 return SPLAY_EMPTY(&xa->xa_tree);
192 }
193
194 static inline void
xa_init(struct xarray * xa)195 xa_init(struct xarray *xa)
196 {
197 xa_init_flags(xa, 0);
198 }
199
200 #endif
201