git.ozlabs.org Git - ccan/blob - 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 */