jbitset: new module.
[ccan] / ccan / jbitset / jbitset.h
1 #ifndef CCAN_JBITSET_H
2 #define CCAN_JBITSET_H
3 #include <Judy.h>
4 #include <stdbool.h>
5 #include <ccan/compiler/compiler.h>
6 #include <assert.h>
7
8 /**
9  * jbit_new - create a new, empty jbitset.
10  *
11  * See Also:
12  *      JBIT_DEFINE_TYPE()
13  *
14  * Example:
15  *      struct jbitset *set = jbit_new();
16  *      if (!set)
17  *              errx(1, "Failed to allocate jbitset");
18  */
19 struct jbitset *jbit_new(void);
20
21 /**
22  * jbit_free - destroy a jbitset.
23  * @set: the set returned from jbit_new.
24  *
25  * Example:
26  *      jbit_free(set);
27  */
28 void jbit_free(const struct jbitset *set);
29
30 /* This is exposed in the header so we can inline.  Treat it as private! */
31 struct jbitset {
32         void *judy;
33         JError_t err;
34         const char *errstr;
35 };
36 const char *COLD_ATTRIBUTE jbit_error_(struct jbitset *set);
37
38 /**
39  * jbit_error - test for an error in the a previous jbit_ operation.
40  * @set: the set to test.
41  *
42  * Under normal circumstances, return NULL to indicate no error has occurred.
43  * Otherwise, it will return a string containing the error.  This string
44  * can only be freed by jbit_free() on the set.
45  *
46  * Other than out-of-memory, errors are caused by memory corruption or
47  * interface misuse.
48  *
49  * Example:
50  *      struct jbitset *set = jbit_new();
51  *      const char *errstr;
52  *
53  *      if (!set)
54  *              err(1, "allocating jbitset");
55  *      errstr = jbit_error(set);
56  *      if (errstr)
57  *              errx(1, "Woah, error on newly created set?! %s", errstr);
58  */
59 static inline const char *jbit_error(struct jbitset *set)
60 {
61         if (JU_ERRNO(&set->err) <= JU_ERRNO_NFMAX)
62                 return NULL;
63         return jbit_error_(set);
64 }
65
66 /**
67  * jbit_test - test a bit in the bitset.
68  * @set: bitset from jbit_new
69  * @index: the index to test
70  *
71  * Returns true if jbit_set() has been done on this index, false otherwise.
72  *
73  * Example:
74  *      assert(!jbit_test(set, 0));
75  */
76 static inline bool jbit_test(const struct jbitset *set, size_t index)
77 {
78         return Judy1Test(set->judy, index, (JError_t *)&set->err);
79 }
80
81 /**
82  * jbit_set - set a bit in the bitset.
83  * @set: bitset from jbit_new
84  * @index: the index to set
85  *
86  * Returns false if it was already set (ie. nothing changed)
87  *
88  * Example:
89  *      if (jbit_set(set, 0))
90  *              err(1, "Bit 0 was already set?!");
91  */
92 static inline bool jbit_set(struct jbitset *set, size_t index)
93 {
94         return Judy1Set(&set->judy, index, &set->err);
95 }
96
97 /**
98  * jbit_clear - clear a bit in the bitset.
99  * @set: bitset from jbit_new
100  * @index: the index to set
101  *
102  * Returns the old bit value (ie. false if nothing changed).
103  *
104  * Example:
105  *      if (jbit_clear(set, 0))
106  *              err(1, "Bit 0 was already clear?!");
107  */
108 static inline bool jbit_clear(struct jbitset *set, size_t index)
109 {
110         return Judy1Unset(&set->judy, index, &set->err);
111 }
112
113 /**
114  * jbit_popcount - get population of (some part of) bitset.
115  * @set: bitset from jbit_new
116  * @start: first index to count
117  * @end_incl: last index to count (use -1 for end).
118  *
119  * Example:
120  *      assert(jbit_popcount(set, 0, 1000) <= jbit_popcount(set, 0, 2000));
121  */
122 static inline size_t jbit_popcount(const struct jbitset *set,
123                                    size_t start, size_t end_incl)
124 {
125         return Judy1Count(set->judy, start, end_incl, (JError_t *)&set->err);
126 }
127
128 /**
129  * jbit_nth - return the index of the nth bit which is set.
130  * @set: bitset from jbit_new
131  * @n: which bit we are interested in (0-based)
132  * @invalid: what to return if n >= set population
133  *
134  * This normally returns the nth bit in the set, and often there is a
135  * convenient known-invalid value (ie. something which is never in the
136  * set).  Otherwise, and a wrapper function like this can be used:
137  *
138  *      static bool jbit_nth_index(struct jbitset *set, size_t n, size_t *idx)
139  *      {
140  *              // Zero might be valid, if it's first in set.
141  *              if (n == 0 && jbit_test(set, 0)) {
142  *                      *idx = 0;
143  *                      return true;
144  *              }
145  *              *idx = jbit_nth(set, n, 0);
146  *              return (*idx != 0);
147  *      }
148  *
149  * Example:
150  *      size_t i, val;
151  *
152  *      // We know 0 isn't in set.
153  *      assert(!jbit_test(set, 0));
154  *      for (i = 0; (val = jbit_nth(set, i, 0)) != 0; i++) {
155  *              assert(jbit_popcount(set, 0, val) == i);
156  *              printf("Value %zu = %zu\n", i, val);
157  *      }
158  */
159 static inline size_t jbit_nth(const struct jbitset *set,
160                               size_t n, size_t invalid)
161 {
162         Word_t index;
163         if (!Judy1ByCount(set->judy, n+1, &index, (JError_t *)&set->err))
164                 index = invalid;
165         return index;
166 }
167
168 /**
169  * jbit_first - return the first bit which is set.
170  * @set: bitset from jbit_new
171  * @invalid: return value if no bits are set at all.
172  *
173  * This is equivalent to jbit_nth(set, 0, invalid).
174  *
175  * Example:
176  *      assert(!jbit_test(set, 0));
177  *      printf("Set contents (increasing order):");
178  *      for (i = jbit_first(set, 0); i; i = jbit_next(set, i, 0))
179  *              printf(" %zu", i);
180  *      printf("\n");
181  */
182 static inline size_t jbit_first(const struct jbitset *set, size_t invalid)
183 {
184         Word_t index = 0;
185         if (!Judy1First(set->judy, &index, (JError_t *)&set->err))
186                 index = invalid;
187         else
188                 assert(index != invalid);
189         return index;
190 }
191
192 /**
193  * jbit_next - return the next bit which is set.
194  * @set: bitset from jbit_new
195  * @prev: previous index
196  * @invalid: return value if no bits are set at all.
197  *
198  * This is usually used to find an adjacent bit which is set, after
199  * jbit_first.
200  */
201 static inline size_t jbit_next(const struct jbitset *set, size_t prev,
202                                size_t invalid)
203 {
204         if (!Judy1Next(set->judy, (Word_t *)&prev, (JError_t *)&set->err))
205                 prev = invalid;
206         else
207                 assert(prev != invalid);
208         return prev;
209 }
210
211 /**
212  * jbit_last - return the last bit which is set.
213  * @set: bitset from jbit_new
214  * @invalid: return value if no bits are set at all.
215  *
216  * Example:
217  *      assert(!jbit_test(set, 0));
218  *      printf("Set contents (decreasing order):");
219  *      for (i = jbit_last(set, 0); i; i = jbit_prev(set, i, 0))
220  *              printf(" %zu", i);
221  *      printf("\n");
222  */
223 static inline size_t jbit_last(const struct jbitset *set, size_t invalid)
224 {
225         Word_t index = -1;
226         if (!Judy1Last(set->judy, &index, (JError_t *)&set->err))
227                 index = invalid;
228         else
229                 assert(index != invalid);
230         return index;
231 }
232
233 /**
234  * jbit_prev - return the previous bit which is set.
235  * @set: bitset from jbit_new
236  * @prev: previous index
237  * @invalid: return value if no bits are set at all.
238  *
239  * This is usually used to find an adjacent bit which is set, after
240  * jbit_last.
241  */
242 static inline size_t jbit_prev(const struct jbitset *set, size_t prev,
243                                size_t invalid)
244 {
245         if (!Judy1Prev(set->judy, (Word_t *)&prev, (JError_t *)&set->err))
246                 prev = invalid;
247         else
248                 assert(prev != invalid);
249         return prev;
250 }
251
252 /**
253  * jbit_first_clear - return the first bit which is unset.
254  * @set: bitset from jbit_new
255  * @invalid: return value if no bits are clear at all.
256  *
257  * This allows for iterating the inverse of the bitmap.
258  */
259 static inline size_t jbit_first_clear(const struct jbitset *set,
260                                       size_t invalid)
261 {
262         Word_t index = 0;
263         if (!Judy1FirstEmpty(set->judy, &index, (JError_t *)&set->err))
264                 index = invalid;
265         else
266                 assert(index != invalid);
267         return index;
268 }
269
270 static inline size_t jbit_next_clear(const struct jbitset *set, size_t prev,
271                                      size_t invalid)
272 {
273         if (!Judy1NextEmpty(set->judy, (Word_t *)&prev, (JError_t *)&set->err))
274                 prev = invalid;
275         else
276                 assert(prev != invalid);
277         return prev;
278 }
279
280 static inline size_t jbit_last_clear(const struct jbitset *set, size_t invalid)
281 {
282         Word_t index = -1;
283         if (!Judy1LastEmpty(set->judy, &index, (JError_t *)&set->err))
284                 index = invalid;
285         else
286                 assert(index != invalid);
287         return index;
288 }
289
290 static inline size_t jbit_prev_clear(const struct jbitset *set, size_t prev,
291                                      size_t invalid)
292 {
293         if (!Judy1PrevEmpty(set->judy, (Word_t *)&prev, (JError_t *)&set->err))
294                 prev = invalid;
295         else
296                 assert(prev != invalid);
297         return prev;
298 }
299 #endif /* CCAN_JBITSET_H */