1 /* Licensed under LGPLv2.1+ - see LICENSE file for details */
6 #include <ccan/compiler/compiler.h>
10 * jbit_new - create a new, empty jbitset.
16 * struct jbitset *set = jbit_new();
18 * errx(1, "Failed to allocate jbitset");
20 struct jbitset *jbit_new(void);
23 * jbit_free - destroy a jbitset.
24 * @set: the set returned from jbit_new.
29 void jbit_free(const struct jbitset *set);
31 /* This is exposed in the header so we can inline. Treat it as private! */
37 const char *COLD jbit_error_(struct jbitset *set);
40 * jbit_error - test for an error in the a previous jbit_ operation.
41 * @set: the set to test.
43 * Under normal circumstances, return NULL to indicate no error has occurred.
44 * Otherwise, it will return a string containing the error. This string
45 * can only be freed by jbit_free() on the set.
47 * Other than out-of-memory, errors are caused by memory corruption or
51 * struct jbitset *set = jbit_new();
55 * err(1, "allocating jbitset");
56 * errstr = jbit_error(set);
58 * errx(1, "Woah, error on newly created set?! %s", errstr);
60 static inline const char *jbit_error(struct jbitset *set)
62 if (JU_ERRNO(&set->err) <= JU_ERRNO_NFMAX)
64 return jbit_error_(set);
68 * jbit_test - test a bit in the bitset.
69 * @set: bitset from jbit_new
70 * @index: the index to test
72 * Returns true if jbit_set() has been done on this index, false otherwise.
75 * assert(!jbit_test(set, 0));
77 static inline bool jbit_test(const struct jbitset *set, unsigned long index)
79 return Judy1Test(set->judy, index, (JError_t *)&set->err);
83 * jbit_set - set a bit in the bitset.
84 * @set: bitset from jbit_new
85 * @index: the index to set
87 * Returns false if it was already set (ie. nothing changed)
90 * if (jbit_set(set, 0))
91 * err(1, "Bit 0 was already set?!");
93 static inline bool jbit_set(struct jbitset *set, unsigned long index)
95 return Judy1Set(&set->judy, index, &set->err);
99 * jbit_clear - clear a bit in the bitset.
100 * @set: bitset from jbit_new
101 * @index: the index to set
103 * Returns the old bit value (ie. false if nothing changed).
106 * if (jbit_clear(set, 0))
107 * err(1, "Bit 0 was already clear?!");
109 static inline bool jbit_clear(struct jbitset *set, unsigned long index)
111 return Judy1Unset(&set->judy, index, &set->err);
115 * jbit_popcount - get population of (some part of) bitset.
116 * @set: bitset from jbit_new
117 * @start: first index to count
118 * @end_incl: last index to count (use -1 for end).
121 * assert(jbit_popcount(set, 0, 1000) <= jbit_popcount(set, 0, 2000));
123 static inline unsigned long jbit_popcount(const struct jbitset *set,
125 unsigned long end_incl)
127 return Judy1Count(set->judy, start, end_incl, (JError_t *)&set->err);
131 * jbit_nth - return the index of the nth bit which is set.
132 * @set: bitset from jbit_new
133 * @n: which bit we are interested in (0-based)
134 * @invalid: what to return if n >= set population
136 * This normally returns the nth bit in the set, and often there is a
137 * convenient known-invalid value (ie. something which is never in the
138 * set). Otherwise, and a wrapper function like this can be used:
140 * static bool jbit_nth_index(struct jbitset *set,
141 * unsigned long n, unsigned long *idx)
143 * // Zero might be valid, if it's first in set.
144 * if (n == 0 && jbit_test(set, 0)) {
148 * *idx = jbit_nth(set, n, 0);
149 * return (*idx != 0);
153 * unsigned long i, val;
155 * // We know 0 isn't in set.
156 * assert(!jbit_test(set, 0));
157 * for (i = 0; (val = jbit_nth(set, i, 0)) != 0; i++) {
158 * assert(jbit_popcount(set, 0, val) == i);
159 * printf("Value %zu = %zu\n", i, val);
162 static inline unsigned long jbit_nth(const struct jbitset *set,
163 unsigned long n, unsigned long invalid)
166 if (!Judy1ByCount(set->judy, n+1, &index, (JError_t *)&set->err))
172 * jbit_first - return the first bit which is set.
173 * @set: bitset from jbit_new
174 * @invalid: return value if no bits are set at all.
176 * This is equivalent to jbit_nth(set, 0, invalid).
179 * assert(!jbit_test(set, 0));
180 * printf("Set contents (increasing order):");
181 * for (i = jbit_first(set, 0); i; i = jbit_next(set, i, 0))
185 static inline unsigned long jbit_first(const struct jbitset *set,
186 unsigned long invalid)
188 unsigned long index = 0;
189 if (!Judy1First(set->judy, &index, (JError_t *)&set->err))
192 assert(index != invalid);
197 * jbit_next - return the next bit which is set.
198 * @set: bitset from jbit_new
199 * @prev: previous index
200 * @invalid: return value if no bits are set at all.
202 * This is usually used to find an adjacent bit which is set, after
205 static inline unsigned long jbit_next(const struct jbitset *set,
207 unsigned long invalid)
209 if (!Judy1Next(set->judy, &prev, (JError_t *)&set->err))
212 assert(prev != invalid);
217 * jbit_last - return the last bit which is set.
218 * @set: bitset from jbit_new
219 * @invalid: return value if no bits are set at all.
222 * assert(!jbit_test(set, 0));
223 * printf("Set contents (decreasing order):");
224 * for (i = jbit_last(set, 0); i; i = jbit_prev(set, i, 0))
228 static inline unsigned long jbit_last(const struct jbitset *set,
229 unsigned long invalid)
231 unsigned long index = -1;
232 if (!Judy1Last(set->judy, &index, (JError_t *)&set->err))
235 assert(index != invalid);
240 * jbit_prev - return the previous bit which is set.
241 * @set: bitset from jbit_new
242 * @prev: previous index
243 * @invalid: return value if no bits are set at all.
245 * This is usually used to find an adjacent bit which is set, after
248 static inline unsigned long jbit_prev(const struct jbitset *set,
250 unsigned long invalid)
252 if (!Judy1Prev(set->judy, &prev, (JError_t *)&set->err))
255 assert(prev != invalid);
260 * jbit_first_clear - return the first bit which is unset.
261 * @set: bitset from jbit_new
262 * @invalid: return value if no bits are clear at all.
264 * This allows for iterating the inverse of the bitmap.
266 static inline unsigned long jbit_first_clear(const struct jbitset *set,
267 unsigned long invalid)
269 unsigned long index = 0;
270 if (!Judy1FirstEmpty(set->judy, &index, (JError_t *)&set->err))
273 assert(index != invalid);
277 static inline unsigned long jbit_next_clear(const struct jbitset *set,
279 unsigned long invalid)
281 if (!Judy1NextEmpty(set->judy, &prev, (JError_t *)&set->err))
284 assert(prev != invalid);
288 static inline unsigned long jbit_last_clear(const struct jbitset *set,
289 unsigned long invalid)
291 unsigned long index = -1;
292 if (!Judy1LastEmpty(set->judy, &index, (JError_t *)&set->err))
295 assert(index != invalid);
299 static inline unsigned long jbit_prev_clear(const struct jbitset *set,
301 unsigned long invalid)
303 if (!Judy1PrevEmpty(set->judy, &prev, (JError_t *)&set->err))
306 assert(prev != invalid);
309 #endif /* CCAN_JBITSET_H */