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
11 #define XA_FLAGS_ALLOC1 2
12 #define XA_FLAGS_LOCK_IRQ 4
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 void xa_init_flags(struct xarray *, gfp_t);
33 void xa_destroy(struct xarray *);
34 int __xa_alloc(struct xarray *, u32 *, void *, int, gfp_t);
35 int __xa_alloc_cyclic(struct xarray *, u32 *, void *, int, u32 *, gfp_t);
36 void *__xa_load(struct xarray *, unsigned long);
37 void *__xa_store(struct xarray *, unsigned long, void *, gfp_t);
38 void *__xa_erase(struct xarray *, unsigned long);
39 void *xa_get_next(struct xarray *, unsigned long *);
40
41 #define xa_for_each(xa, index, entry) \
42 for (index = 0; ((entry) = xa_get_next(xa, &(index))) != NULL; index++)
43
44 #define xa_limit_32b 0
45
46 #define xa_lock(_xa) do { \
47 mtx_enter(&(_xa)->xa_lock); \
48 } while (0)
49
50 #define xa_unlock(_xa) do { \
51 mtx_leave(&(_xa)->xa_lock); \
52 } while (0)
53
54 #define xa_lock_irq(_xa) do { \
55 mtx_enter(&(_xa)->xa_lock); \
56 } while (0)
57
58 #define xa_unlock_irq(_xa) do { \
59 mtx_leave(&(_xa)->xa_lock); \
60 } while (0)
61
62 #define xa_lock_irqsave(_xa, _flags) do { \
63 _flags = 0; \
64 mtx_enter(&(_xa)->xa_lock); \
65 } while (0)
66
67 #define xa_unlock_irqrestore(_xa, _flags) do { \
68 (void)(_flags); \
69 mtx_leave(&(_xa)->xa_lock); \
70 } while (0)
71
72 static inline void *
xa_mk_value(unsigned long v)73 xa_mk_value(unsigned long v)
74 {
75 unsigned long r = (v << 1) | 1;
76 return (void *)r;
77 }
78
79 static inline bool
xa_is_value(const void * e)80 xa_is_value(const void *e)
81 {
82 unsigned long v = (unsigned long)e;
83 return v & 1;
84 }
85
86 static inline unsigned long
xa_to_value(const void * e)87 xa_to_value(const void *e)
88 {
89 unsigned long v = (unsigned long)e;
90 return v >> 1;
91 }
92
93 #define XA_ERROR(x) ((struct xa_node *)(((unsigned long)x << 2) | 2))
94
95 static inline int
xa_err(const void * e)96 xa_err(const void *e)
97 {
98 long v = (long)e;
99 /* not tagged internal, not an errno */
100 if ((v & 3) != 2)
101 return 0;
102 v >>= 2;
103 if (v >= -ELAST)
104 return v;
105 return 0;
106 }
107
108 static inline bool
xa_is_err(const void * e)109 xa_is_err(const void *e)
110 {
111 return xa_err(e) != 0;
112 }
113
114 static inline int
xa_alloc(struct xarray * xa,u32 * id,void * entry,int limit,gfp_t gfp)115 xa_alloc(struct xarray *xa, u32 *id, void *entry, int limit, gfp_t gfp)
116 {
117 int r;
118 mtx_enter(&xa->xa_lock);
119 r = __xa_alloc(xa, id, entry, limit, gfp);
120 mtx_leave(&xa->xa_lock);
121 return r;
122 }
123
124 static inline void *
xa_load(struct xarray * xa,unsigned long index)125 xa_load(struct xarray *xa, unsigned long index)
126 {
127 void *r;
128 r = __xa_load(xa, index);
129 return r;
130 }
131
132
133 static inline void *
xa_store(struct xarray * xa,unsigned long index,void * entry,gfp_t gfp)134 xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)
135 {
136 void *r;
137 mtx_enter(&xa->xa_lock);
138 r = __xa_store(xa, index, entry, gfp);
139 mtx_leave(&xa->xa_lock);
140 return r;
141 }
142
143 static inline void *
xa_erase(struct xarray * xa,unsigned long index)144 xa_erase(struct xarray *xa, unsigned long index)
145 {
146 void *r;
147 mtx_enter(&xa->xa_lock);
148 r = __xa_erase(xa, index);
149 mtx_leave(&xa->xa_lock);
150 return r;
151 }
152
153 static inline void *
xa_store_irq(struct xarray * xa,unsigned long index,void * entry,gfp_t gfp)154 xa_store_irq(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)
155 {
156 void *r;
157 mtx_enter(&xa->xa_lock);
158 r = __xa_store(xa, index, entry, gfp);
159 mtx_leave(&xa->xa_lock);
160 return r;
161 }
162
163 static inline void *
xa_erase_irq(struct xarray * xa,unsigned long index)164 xa_erase_irq(struct xarray *xa, unsigned long index)
165 {
166 void *r;
167 mtx_enter(&xa->xa_lock);
168 r = __xa_erase(xa, index);
169 mtx_leave(&xa->xa_lock);
170 return r;
171 }
172
173 static inline bool
xa_empty(const struct xarray * xa)174 xa_empty(const struct xarray *xa)
175 {
176 return SPLAY_EMPTY(&xa->xa_tree);
177 }
178
179 static inline void
xa_init(struct xarray * xa)180 xa_init(struct xarray *xa)
181 {
182 xa_init_flags(xa, 0);
183 }
184
185 #endif
186