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 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, unsigned long 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, unsigned long 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, unsigned long 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 unsigned long jbit_popcount(const struct jbitset *set,
 123                                           unsigned long start,
 124                                           unsigned long end_incl)
 125 {
 126         return Judy1Count(set->judy, start, end_incl, (JError_t *)&set->err);
 127 }
 128
 129 /**
 130  * jbit_nth - return the index of the nth bit which is set.
 131  * @set: bitset from jbit_new
 132  * @n: which bit we are interested in (0-based)
 133  * @invalid: what to return if n >= set population
 134  *
 135  * This normally returns the nth bit in the set, and often there is a
 136  * convenient known-invalid value (ie. something which is never in the
 137  * set).  Otherwise, and a wrapper function like this can be used:
 138  *
 139  *      static bool jbit_nth_index(struct jbitset *set,
 140  *                                 unsigned long n, unsigned long *idx)
 141  *      {
 142  *              // Zero might be valid, if it's first in set.
 143  *              if (n == 0 && jbit_test(set, 0)) {
 144  *                      *idx = 0;
 145  *                      return true;
 146  *              }
 147  *              *idx = jbit_nth(set, n, 0);
 148  *              return (*idx != 0);
 149  *      }
 150  *
 151  * Example:
 152  *      unsigned long i, val;
 153  *
 154  *      // We know 0 isn't in set.
 155  *      assert(!jbit_test(set, 0));
 156  *      for (i = 0; (val = jbit_nth(set, i, 0)) != 0; i++) {
 157  *              assert(jbit_popcount(set, 0, val) == i);
 158  *              printf("Value %zu = %zu\n", i, val);
 159  *      }
 160  */
 161 static inline unsigned long jbit_nth(const struct jbitset *set,
 162                                      unsigned long n, unsigned long invalid)
 163 {
 164         unsigned long index;
 165         if (!Judy1ByCount(set->judy, n+1, &index, (JError_t *)&set->err))
 166                 index = invalid;
 167         return index;
 168 }
 169
 170 /**
 171  * jbit_first - return the first bit which is set.
 172  * @set: bitset from jbit_new
 173  * @invalid: return value if no bits are set at all.
 174  *
 175  * This is equivalent to jbit_nth(set, 0, invalid).
 176  *
 177  * Example:
 178  *      assert(!jbit_test(set, 0));
 179  *      printf("Set contents (increasing order):");
 180  *      for (i = jbit_first(set, 0); i; i = jbit_next(set, i, 0))
 181  *              printf(" %zu", i);
 182  *      printf("\n");
 183  */
 184 static inline unsigned long jbit_first(const struct jbitset *set,
 185                                        unsigned long invalid)
 186 {
 187         unsigned long index = 0;
 188         if (!Judy1First(set->judy, &index, (JError_t *)&set->err))
 189                 index = invalid;
 190         else
 191                 assert(index != invalid);
 192         return index;
 193 }
 194
 195 /**
 196  * jbit_next - return the next bit which is set.
 197  * @set: bitset from jbit_new
 198  * @prev: previous index
 199  * @invalid: return value if no bits are set at all.
 200  *
 201  * This is usually used to find an adjacent bit which is set, after
 202  * jbit_first.
 203  */
 204 static inline unsigned long jbit_next(const struct jbitset *set,
 205                                       unsigned long prev,
 206                                       unsigned long invalid)
 207 {
 208         if (!Judy1Next(set->judy, &prev, (JError_t *)&set->err))
 209                 prev = invalid;
 210         else
 211                 assert(prev != invalid);
 212         return prev;
 213 }
 214
 215 /**
 216  * jbit_last - return the last bit which is set.
 217  * @set: bitset from jbit_new
 218  * @invalid: return value if no bits are set at all.
 219  *
 220  * Example:
 221  *      assert(!jbit_test(set, 0));
 222  *      printf("Set contents (decreasing order):");
 223  *      for (i = jbit_last(set, 0); i; i = jbit_prev(set, i, 0))
 224  *              printf(" %zu", i);
 225  *      printf("\n");
 226  */
 227 static inline unsigned long jbit_last(const struct jbitset *set,
 228                                       unsigned long invalid)
 229 {
 230         unsigned long index = -1;
 231         if (!Judy1Last(set->judy, &index, (JError_t *)&set->err))
 232                 index = invalid;
 233         else
 234                 assert(index != invalid);
 235         return index;
 236 }
 237
 238 /**
 239  * jbit_prev - return the previous bit which is set.
 240  * @set: bitset from jbit_new
 241  * @prev: previous index
 242  * @invalid: return value if no bits are set at all.
 243  *
 244  * This is usually used to find an adjacent bit which is set, after
 245  * jbit_last.
 246  */
 247 static inline unsigned long jbit_prev(const struct jbitset *set,
 248                                       unsigned long prev,
 249                                       unsigned long invalid)
 250 {
 251         if (!Judy1Prev(set->judy, &prev, (JError_t *)&set->err))
 252                 prev = invalid;
 253         else
 254                 assert(prev != invalid);
 255         return prev;
 256 }
 257
 258 /**
 259  * jbit_first_clear - return the first bit which is unset.
 260  * @set: bitset from jbit_new
 261  * @invalid: return value if no bits are clear at all.
 262  *
 263  * This allows for iterating the inverse of the bitmap.
 264  */
 265 static inline unsigned long jbit_first_clear(const struct jbitset *set,
 266                                              unsigned long invalid)
 267 {
 268         unsigned long index = 0;
 269         if (!Judy1FirstEmpty(set->judy, &index, (JError_t *)&set->err))
 270                 index = invalid;
 271         else
 272                 assert(index != invalid);
 273         return index;
 274 }
 275
 276 static inline unsigned long jbit_next_clear(const struct jbitset *set,
 277                                             unsigned long prev,
 278                                             unsigned long invalid)
 279 {
 280         if (!Judy1NextEmpty(set->judy, &prev, (JError_t *)&set->err))
 281                 prev = invalid;
 282         else
 283                 assert(prev != invalid);
 284         return prev;
 285 }
 286
 287 static inline unsigned long jbit_last_clear(const struct jbitset *set,
 288                                             unsigned long invalid)
 289 {
 290         unsigned long index = -1;
 291         if (!Judy1LastEmpty(set->judy, &index, (JError_t *)&set->err))
 292                 index = invalid;
 293         else
 294                 assert(index != invalid);
 295         return index;
 296 }
 297
 298 static inline unsigned long jbit_prev_clear(const struct jbitset *set,
 299                                             unsigned long prev,
 300                                             unsigned long invalid)
 301 {
 302         if (!Judy1PrevEmpty(set->judy, &prev, (JError_t *)&set->err))
 303                 prev = invalid;
 304         else
 305                 assert(prev != invalid);
 306         return prev;
 307 }
 308 #endif /* CCAN_JBITSET_H */