1 /* Licensed under LGPLv2.1+ - see LICENSE file for details */
5 #include <ccan/compiler/compiler.h>
6 #include <ccan/tcon/tcon.h>
12 * struct jset - private definition of a jset.
14 * It's exposed here so you can put it in your structures and so we can
15 * supply inline functions.
24 * JSET_MEMBERS - declare members for a type-specific jset.
25 * @type: type for this set to contain, or void * for any pointer.
32 #define JSET_MEMBERS(type) \
33 TCON_WRAP(struct jset, type canary) jset_
36 * jset_new - create a new, empty jset.
37 * @type: the tcon-containing type to allocate.
42 * } *set = jset_new(struct jset_long);
45 * errx(1, "Failed to allocate set");
47 #define jset_new(type) ((type *)jset_new_(sizeof(type)))
51 * jset_raw_ - unwrap the typed set (without type checking)
52 * @set: the typed jset
54 #define jset_raw_(set) (tcon_unwrap(&(set)->jset_))
58 * jset_free - destroy a jset.
59 * @set: the set returned from jset_new.
64 #define jset_free(set) jset_free_(jset_raw_(set))
67 * jset_error - test for an error in the a previous jset_ operation.
68 * @set: the set to test.
70 * Under normal circumstances, return NULL to indicate no error has occurred.
71 * Otherwise, it will return a string containing the error. This string
72 * can only be freed by jset_free() on the set.
74 * Other than out-of-memory, errors are caused by memory corruption or
80 * errstr = jset_error(set);
82 * errx(1, "Woah, error on newly created set?! %s", errstr);
84 #define jset_error(set) jset_error_(jset_raw_(set))
88 * jset_raw - unwrap the typed set and check the type
89 * @set: the typed jset
90 * @expr: the expression to check the type against (not evaluated)
92 * This macro usually causes the compiler to emit a warning if the
93 * variable is of an unexpected type. It is used internally where we
94 * need to access the raw underlying jset.
96 #define jset_raw(set, expr) \
97 (tcon_unwrap(tcon_check(&(set)->jset_, canary, (expr))))
101 * jset_test - test a bit in the bitset.
102 * @set: bitset from jset_new
103 * @index: the index to test
105 * Returns true if jset_set() has been done on this index, false otherwise.
108 * assert(!jset_test(set, 0));
110 #define jset_test(set, index) \
111 jset_test_(jset_raw((set), (index)), (unsigned long)(index))
114 * jset_set - set a bit in the bitset.
115 * @set: bitset from jset_new
116 * @index: the index to set
118 * Returns false if it was already set (ie. nothing changed)
121 * if (jset_set(set, 0))
122 * err(1, "Bit 0 was already set?!");
124 #define jset_set(set, index) \
125 jset_set_(jset_raw((set), (index)), (unsigned long)(index))
128 * jset_clear - clear a bit in the bitset.
129 * @set: bitset from jset_new
130 * @index: the index to set
132 * Returns the old bit value (ie. false if nothing changed).
135 * if (jset_clear(set, 0))
136 * err(1, "Bit 0 was already clear?!");
138 #define jset_clear(set, index) \
139 jset_clear_(jset_raw((set), (index)), (unsigned long)(index))
142 * jset_count - get population of bitset.
143 * @set: bitset from jset_new
146 * // We expect 1000 entries.
147 * assert(jset_count(set) == 1000);
149 #define jset_count(set) \
150 jset_popcount_(jset_raw_(set), 0, -1UL)
153 * jset_popcount - get population of (some part of) bitset.
154 * @set: bitset from jset_new
155 * @start: first index to count
156 * @end_incl: last index to count (use -1 for end).
159 * assert(jset_popcount(set, 0, 1000) <= jset_popcount(set, 0, 2000));
161 #define jset_popcount(set, start, end_incl) \
162 jset_popcount_(jset_raw((set), (start) ? (start) : (end_incl)), \
163 (unsigned long)(start), (unsigned long)(end_incl))
166 * jset_nth - return the index of the nth bit which is set.
167 * @set: bitset from jset_new
168 * @n: which bit we are interested in (0-based)
169 * @invalid: what to return if n >= set population
171 * This normally returns the nth bit in the set, and often there is a
172 * convenient known-invalid value (ie. something which is never in the
173 * set). Otherwise, and a wrapper function like this can be used:
175 * static bool jset_nth_index(struct jset *set,
176 * unsigned long n, unsigned long *idx)
178 * // Zero might be valid, if it's first in set.
179 * if (n == 0 && jset_test(set, 0)) {
183 * *idx = jset_nth(set, n, 0);
184 * return (*idx != 0);
188 * unsigned long i, val;
190 * // We know 0 isn't in set.
191 * assert(!jset_test(set, 0));
192 * for (i = 0; (val = jset_nth(set, i, 0)) != 0; i++) {
193 * assert(jset_popcount(set, 0, val) == i);
194 * printf("Value %lu = %lu\n", i, val);
197 #define jset_nth(set, n, invalid) \
198 tcon_cast(&(set)->jset_, canary, \
199 jset_nth_(jset_raw((set), (invalid)), \
200 (n), (unsigned long)(invalid)))
203 * jset_first - return the first bit which is set (must not contain 0).
204 * @set: bitset from jset_new
206 * This is equivalent to jset_nth(set, 0, 0). ie. useful only if 0
210 * assert(!jset_test(set, 0));
211 * printf("Set contents (increasing order):");
212 * for (i = jset_first(set); i; i = jset_next(set, i))
216 #define jset_first(set) \
217 tcon_cast(&(set)->jset_, canary, jset_first_(jset_raw_(set)))
220 * jset_next - return the next bit which is set (must not contain 0).
221 * @set: bitset from jset_new
222 * @prev: previous index
224 * This is usually used to find an adjacent index which is set, after
227 #define jset_next(set, prev) \
228 tcon_cast(&(set)->jset_, canary, \
229 jset_next_(jset_raw_(set), (unsigned long)(prev)))
232 * jset_last - return the last bit which is set (must not contain 0).
233 * @set: bitset from jset_new
236 * assert(!jset_test(set, 0));
237 * printf("Set contents (decreasing order):");
238 * for (i = jset_last(set); i; i = jset_prev(set, i))
242 #define jset_last(set) \
243 tcon_cast(&(set)->jset_, canary, jset_last_(jset_raw_(set)))
246 * jset_prev - return the previous bit which is set (must not contain 0).
247 * @set: bitset from jset_new
248 * @prev: previous index
250 * This is usually used to find an adjacent bit which is set, after
253 #define jset_prev(set, prev) \
254 tcon_cast(&(set)->jset_, canary, \
255 jset_prev_(jset_raw_(set), (unsigned long)(prev)))
258 * jset_first_clear - return the first bit which is unset
259 * @set: bitset from jset_new
261 * This allows for iterating the inverse of the bitmap; only returns 0 if the
264 #define jset_first_clear(set) \
265 tcon_cast(&(set)->jset_, canary, jset_next_clear_(jset_raw_(set), 0))
267 #define jset_next_clear(set, prev) \
268 tcon_cast(&(set)->jset_, canary, jset_next_clear_(jset_raw_(set), \
269 (unsigned long)(prev)))
271 #define jset_last_clear(set) \
272 tcon_cast(&(set)->jset_, canary, jset_last_clear_(jset_raw_(set)))
274 #define jset_prev_clear(set, prev) \
275 tcon_cast(&(set)->jset_, canary, jset_prev_clear_(jset_raw_(set), \
276 (unsigned long)(prev)))
279 struct jset *jset_new_(size_t size);
280 void jset_free_(const struct jset *set);
281 const char *COLD jset_error_str_(struct jset *set);
282 static inline const char *jset_error_(struct jset *set)
284 if (JU_ERRNO(&set->err) <= JU_ERRNO_NFMAX)
286 return jset_error_str_(set);
288 static inline bool jset_test_(const struct jset *set, unsigned long index)
290 return Judy1Test(set->judy, index, (JError_t *)&set->err);
292 static inline bool jset_set_(struct jset *set, unsigned long index)
294 return Judy1Set(&set->judy, index, &set->err);
296 static inline bool jset_clear_(struct jset *set, unsigned long index)
298 return Judy1Unset(&set->judy, index, &set->err);
300 static inline unsigned long jset_popcount_(const struct jset *set,
302 unsigned long end_incl)
304 return Judy1Count(set->judy, start, end_incl, (JError_t *)&set->err);
306 static inline unsigned long jset_nth_(const struct jset *set,
307 unsigned long n, unsigned long invalid)
310 if (!Judy1ByCount(set->judy, n+1, &index, (JError_t *)&set->err))
314 static inline unsigned long jset_first_(const struct jset *set)
316 unsigned long index = 0;
317 if (!Judy1First(set->judy, &index, (JError_t *)&set->err))
323 static inline unsigned long jset_next_(const struct jset *set,
326 if (!Judy1Next(set->judy, &prev, (JError_t *)&set->err))
332 static inline unsigned long jset_last_(const struct jset *set)
334 unsigned long index = -1;
335 if (!Judy1Last(set->judy, &index, (JError_t *)&set->err))
341 static inline unsigned long jset_prev_(const struct jset *set,
344 if (!Judy1Prev(set->judy, &prev, (JError_t *)&set->err))
350 static inline unsigned long jset_next_clear_(const struct jset *set,
353 if (!Judy1NextEmpty(set->judy, &prev, (JError_t *)&set->err))
359 static inline unsigned long jset_last_clear_(const struct jset *set)
361 unsigned long index = -1;
362 if (!Judy1LastEmpty(set->judy, &index, (JError_t *)&set->err))
366 static inline unsigned long jset_prev_clear_(const struct jset *set,
369 if (!Judy1PrevEmpty(set->judy, &prev, (JError_t *)&set->err))
373 #endif /* CCAN_JSET_H */