container_of: don't put member_ptr in container_off.
[ccan] / ccan / jset / jset.h
1 /* Licensed under LGPLv2.1+ - see LICENSE file for details */
2 #ifndef CCAN_JSET_H
3 #define CCAN_JSET_H
4 #include "config.h"
5 #include <ccan/compiler/compiler.h>
6 #include <ccan/tcon/tcon.h>
7 #include <Judy.h>
8 #include <stdbool.h>
9 #include <assert.h>
10
11 /**
12  * struct jset - private definition of a jset.
13  *
14  * It's exposed here so you can put it in your structures and so we can
15  * supply inline functions.
16  */
17 struct jset {
18         void *judy;
19         JError_t err;
20         const char *errstr;
21 };
22
23 /**
24  * JSET_MEMBERS - declare members for a type-specific jset.
25  * @type: type for this set to contain, or void * for any pointer.
26  *
27  * Example:
28  *      struct jset_long {
29  *              JSET_MEMBERS(long);
30  *      };
31  */
32 #define JSET_MEMBERS(type)                      \
33         struct jset raw;                        \
34         TCON(type canary)
35
36 /**
37  * jset_new - create a new, empty jset.
38  * @type: the tcon-containing type to allocate.
39  *
40  * Example:
41  *      struct jset_long {
42  *              JSET_MEMBERS(long);
43  *      } *set = jset_new(struct jset_long);
44  *
45  *      if (!set)
46  *              errx(1, "Failed to allocate set");
47  */
48 #define jset_new(type) ((type *)jset_new_(sizeof(type)))
49
50 /**
51  * jset_free - destroy a jset.
52  * @set: the set returned from jset_new.
53  *
54  * Example:
55  *      jset_free(set);
56  */
57 #define jset_free(set) jset_free_(&(set)->raw)
58
59 /**
60  * jset_error - test for an error in the a previous jset_ operation.
61  * @set: the set to test.
62  *
63  * Under normal circumstances, return NULL to indicate no error has occurred.
64  * Otherwise, it will return a string containing the error.  This string
65  * can only be freed by jset_free() on the set.
66  *
67  * Other than out-of-memory, errors are caused by memory corruption or
68  * interface misuse.
69  *
70  * Example:
71  *      const char *errstr;
72  *
73  *      errstr = jset_error(set);
74  *      if (errstr)
75  *              errx(1, "Woah, error on newly created set?! %s", errstr);
76  */
77 #define jset_error(set) \
78         jset_error_(&(set)->raw)
79
80 /**
81  * jset_raw - unwrap the typed set and check the type
82  * @set: the typed jset
83  * @expr: the expression to check the type against (not evaluated)
84  *
85  * This macro usually causes the compiler to emit a warning if the
86  * variable is of an unexpected type.  It is used internally where we
87  * need to access the raw underlying jset.
88  */
89 #define jset_raw(set, expr) (&tcon_check((set), canary, (expr))->raw)
90
91 /**
92  * jset_test - test a bit in the bitset.
93  * @set: bitset from jset_new
94  * @index: the index to test
95  *
96  * Returns true if jset_set() has been done on this index, false otherwise.
97  *
98  * Example:
99  *      assert(!jset_test(set, 0));
100  */
101 #define jset_test(set, index)                                           \
102         jset_test_(jset_raw((set), (index)), (unsigned long)(index))
103
104 /**
105  * jset_set - set a bit in the bitset.
106  * @set: bitset from jset_new
107  * @index: the index to set
108  *
109  * Returns false if it was already set (ie. nothing changed)
110  *
111  * Example:
112  *      if (jset_set(set, 0))
113  *              err(1, "Bit 0 was already set?!");
114  */
115 #define jset_set(set, index)                                            \
116         jset_set_(jset_raw((set), (index)), (unsigned long)(index))
117
118 /**
119  * jset_clear - clear a bit in the bitset.
120  * @set: bitset from jset_new
121  * @index: the index to set
122  *
123  * Returns the old bit value (ie. false if nothing changed).
124  *
125  * Example:
126  *      if (jset_clear(set, 0))
127  *              err(1, "Bit 0 was already clear?!");
128  */
129 #define jset_clear(set, index)                                          \
130         jset_clear_(jset_raw((set), (index)), (unsigned long)(index))
131
132 /**
133  * jset_count - get population of bitset.
134  * @set: bitset from jset_new
135  *
136  * Example:
137  *      // We expect 1000 entries.
138  *      assert(jset_count(set) == 1000);
139  */
140 #define jset_count(set)                         \
141         jset_popcount_(&(set)->raw, 0, -1UL)
142
143 /**
144  * jset_popcount - get population of (some part of) bitset.
145  * @set: bitset from jset_new
146  * @start: first index to count
147  * @end_incl: last index to count (use -1 for end).
148  *
149  * Example:
150  *      assert(jset_popcount(set, 0, 1000) <= jset_popcount(set, 0, 2000));
151  */
152 #define jset_popcount(set, start, end_incl)                             \
153         jset_popcount_(jset_raw((set), (start) ? (start) : (end_incl)), \
154                        (unsigned long)(start), (unsigned long)(end_incl))
155
156 /**
157  * jset_nth - return the index of the nth bit which is set.
158  * @set: bitset from jset_new
159  * @n: which bit we are interested in (0-based)
160  * @invalid: what to return if n >= set population
161  *
162  * This normally returns the nth bit in the set, and often there is a
163  * convenient known-invalid value (ie. something which is never in the
164  * set).  Otherwise, and a wrapper function like this can be used:
165  *
166  *      static bool jset_nth_index(struct jset *set,
167  *                                 unsigned long n, unsigned long *idx)
168  *      {
169  *              // Zero might be valid, if it's first in set.
170  *              if (n == 0 && jset_test(set, 0)) {
171  *                      *idx = 0;
172  *                      return true;
173  *              }
174  *              *idx = jset_nth(set, n, 0);
175  *              return (*idx != 0);
176  *      }
177  *
178  * Example:
179  *      unsigned long i, val;
180  *
181  *      // We know 0 isn't in set.
182  *      assert(!jset_test(set, 0));
183  *      for (i = 0; (val = jset_nth(set, i, 0)) != 0; i++) {
184  *              assert(jset_popcount(set, 0, val) == i);
185  *              printf("Value %lu = %lu\n", i, val);
186  *      }
187  */
188 #define jset_nth(set, n, invalid)                                       \
189         tcon_cast((set), canary,                                        \
190                   jset_nth_(jset_raw((set), (invalid)),                 \
191                             (n), (unsigned long)(invalid)))
192
193 /**
194  * jset_first - return the first bit which is set (must not contain 0).
195  * @set: bitset from jset_new
196  *
197  * This is equivalent to jset_nth(set, 0, 0).  ie. useful only if 0
198  * isn't in your set.
199  *
200  * Example:
201  *      assert(!jset_test(set, 0));
202  *      printf("Set contents (increasing order):");
203  *      for (i = jset_first(set); i; i = jset_next(set, i))
204  *              printf(" %lu", i);
205  *      printf("\n");
206  */
207 #define jset_first(set)                                         \
208         tcon_cast((set), canary, jset_first_(&(set)->raw))
209
210 /**
211  * jset_next - return the next bit which is set (must not contain 0).
212  * @set: bitset from jset_new
213  * @prev: previous index
214  *
215  * This is usually used to find an adjacent index which is set, after
216  * jset_first.
217  */
218 #define jset_next(set, prev)                                            \
219         tcon_cast((set), canary, jset_next_(&(set)->raw, (unsigned long)(prev)))
220
221 /**
222  * jset_last - return the last bit which is set (must not contain 0).
223  * @set: bitset from jset_new
224  *
225  * Example:
226  *      assert(!jset_test(set, 0));
227  *      printf("Set contents (decreasing order):");
228  *      for (i = jset_last(set); i; i = jset_prev(set, i))
229  *              printf(" %lu", i);
230  *      printf("\n");
231  */
232 #define jset_last(set)                                          \
233         tcon_cast((set), canary, jset_last_(&(set)->raw))
234
235 /**
236  * jset_prev - return the previous bit which is set (must not contain 0).
237  * @set: bitset from jset_new
238  * @prev: previous index
239  *
240  * This is usually used to find an adjacent bit which is set, after
241  * jset_last.
242  */
243 #define jset_prev(set, prev)                                            \
244         tcon_cast((set), canary, jset_prev_(&(set)->raw, (unsigned long)(prev)))
245
246 /**
247  * jset_first_clear - return the first bit which is unset
248  * @set: bitset from jset_new
249  *
250  * This allows for iterating the inverse of the bitmap; only returns 0 if the
251  * set is full.
252  */
253 #define jset_first_clear(set)                                           \
254         tcon_cast((set), canary, jset_next_clear_(&(set)->raw, 0))
255
256 #define jset_next_clear(set, prev)                                      \
257         tcon_cast((set), canary, jset_next_clear_(&(set)->raw,          \
258                                                   (unsigned long)(prev)))
259
260 #define jset_last_clear(set)                                    \
261         tcon_cast((set), canary, jset_last_clear_(&(set)->raw))
262
263 #define jset_prev_clear(set, prev)                                      \
264         tcon_cast((set), canary, jset_prev_clear_(&(set)->raw,          \
265                                                   (unsigned long)(prev)))
266
267 /* Raw functions */
268 struct jset *jset_new_(size_t size);
269 void jset_free_(const struct jset *set);
270 const char *COLD jset_error_str_(struct jset *set);
271 static inline const char *jset_error_(struct jset *set)
272 {
273         if (JU_ERRNO(&set->err) <= JU_ERRNO_NFMAX)
274                 return NULL;
275         return jset_error_str_(set);
276 }
277 static inline bool jset_test_(const struct jset *set, unsigned long index)
278 {
279         return Judy1Test(set->judy, index, (JError_t *)&set->err);
280 }
281 static inline bool jset_set_(struct jset *set, unsigned long index)
282 {
283         return Judy1Set(&set->judy, index, &set->err);
284 }
285 static inline bool jset_clear_(struct jset *set, unsigned long index)
286 {
287         return Judy1Unset(&set->judy, index, &set->err);
288 }
289 static inline unsigned long jset_popcount_(const struct jset *set,
290                                            unsigned long start,
291                                            unsigned long end_incl)
292 {
293         return Judy1Count(set->judy, start, end_incl, (JError_t *)&set->err);
294 }
295 static inline unsigned long jset_nth_(const struct jset *set,
296                                       unsigned long n, unsigned long invalid)
297 {
298         unsigned long index;
299         if (!Judy1ByCount(set->judy, n+1, &index, (JError_t *)&set->err))
300                 index = invalid;
301         return index;
302 }
303 static inline unsigned long jset_first_(const struct jset *set)
304 {
305         unsigned long index = 0;
306         if (!Judy1First(set->judy, &index, (JError_t *)&set->err))
307                 index = 0;
308         else
309                 assert(index != 0);
310         return index;
311 }
312 static inline unsigned long jset_next_(const struct jset *set,
313                                        unsigned long prev)
314 {
315         if (!Judy1Next(set->judy, &prev, (JError_t *)&set->err))
316                 prev = 0;
317         else
318                 assert(prev != 0);
319         return prev;
320 }
321 static inline unsigned long jset_last_(const struct jset *set)
322 {
323         unsigned long index = -1;
324         if (!Judy1Last(set->judy, &index, (JError_t *)&set->err))
325                 index = 0;
326         else
327                 assert(index != 0);
328         return index;
329 }
330 static inline unsigned long jset_prev_(const struct jset *set,
331                                        unsigned long prev)
332 {
333         if (!Judy1Prev(set->judy, &prev, (JError_t *)&set->err))
334                 prev = 0;
335         else
336                 assert(prev != 0);
337         return prev;
338 }
339 static inline unsigned long jset_next_clear_(const struct jset *set,
340                                              unsigned long prev)
341 {
342         if (!Judy1NextEmpty(set->judy, &prev, (JError_t *)&set->err))
343                 prev = 0;
344         else
345                 assert(prev != 0);
346         return prev;
347 }
348 static inline unsigned long jset_last_clear_(const struct jset *set)
349 {
350         unsigned long index = -1;
351         if (!Judy1LastEmpty(set->judy, &index, (JError_t *)&set->err))
352                 index = 0;
353         return index;
354 }
355 static inline unsigned long jset_prev_clear_(const struct jset *set,
356                                              unsigned long prev)
357 {
358         if (!Judy1PrevEmpty(set->judy, &prev, (JError_t *)&set->err))
359                 prev = 0;
360         return prev;
361 }
362 #endif /* CCAN_JSET_H */