git.ozlabs.org Git - ccan/blob - ccan/jbitset/jbitset.h

   1 /* Licensed under LGPLv2.1+ - see LICENSE file for details */
   2 #ifndef CCAN_JBITSET_H
   3 #define CCAN_JBITSET_H
   4 #include <Judy.h>
   5 #include <stdbool.h>
   6 #include <ccan/compiler/compiler.h>
   7 #include <assert.h>
   8
   9 /**
  10  * jbit_new - create a new, empty jbitset.
  11  *
  12  * See Also:
  13  *      JBIT_DEFINE_TYPE()
  14  *
  15  * Example:
  16  *      struct jbitset *set = jbit_new();
  17  *      if (!set)
  18  *              errx(1, "Failed to allocate jbitset");
  19  */
  20 struct jbitset *jbit_new(void);
  21
  22 /**
  23  * jbit_free - destroy a jbitset.
  24  * @set: the set returned from jbit_new.
  25  *
  26  * Example:
  27  *      jbit_free(set);
  28  */
  29 void jbit_free(const struct jbitset *set);
  30
  31 /* This is exposed in the header so we can inline.  Treat it as private! */
  32 struct jbitset {
  33         void *judy;
  34         JError_t err;
  35         const char *errstr;
  36 };
  37 const char *COLD jbit_error_(struct jbitset *set);
  38
  39 /**
  40  * jbit_error - test for an error in the a previous jbit_ operation.
  41  * @set: the set to test.
  42  *
  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.
  46  *
  47  * Other than out-of-memory, errors are caused by memory corruption or
  48  * interface misuse.
  49  *
  50  * Example:
  51  *      struct jbitset *set = jbit_new();
  52  *      const char *errstr;
  53  *
  54  *      if (!set)
  55  *              err(1, "allocating jbitset");
  56  *      errstr = jbit_error(set);
  57  *      if (errstr)
  58  *              errx(1, "Woah, error on newly created set?! %s", errstr);
  59  */
  60 static inline const char *jbit_error(struct jbitset *set)
  61 {
  62         if (JU_ERRNO(&set->err) <= JU_ERRNO_NFMAX)
  63                 return NULL;
  64         return jbit_error_(set);
  65 }
  66
  67 /**
  68  * jbit_test - test a bit in the bitset.
  69  * @set: bitset from jbit_new
  70  * @index: the index to test
  71  *
  72  * Returns true if jbit_set() has been done on this index, false otherwise.
  73  *
  74  * Example:
  75  *      assert(!jbit_test(set, 0));
  76  */
  77 static inline bool jbit_test(const struct jbitset *set, unsigned long index)
  78 {
  79         return Judy1Test(set->judy, index, (JError_t *)&set->err);
  80 }
  81
  82 /**
  83  * jbit_set - set a bit in the bitset.
  84  * @set: bitset from jbit_new
  85  * @index: the index to set
  86  *
  87  * Returns false if it was already set (ie. nothing changed)
  88  *
  89  * Example:
  90  *      if (jbit_set(set, 0))
  91  *              err(1, "Bit 0 was already set?!");
  92  */
  93 static inline bool jbit_set(struct jbitset *set, unsigned long index)
  94 {
  95         return Judy1Set(&set->judy, index, &set->err);
  96 }
  97
  98 /**
  99  * jbit_clear - clear a bit in the bitset.
 100  * @set: bitset from jbit_new
 101  * @index: the index to set
 102  *
 103  * Returns the old bit value (ie. false if nothing changed).
 104  *
 105  * Example:
 106  *      if (jbit_clear(set, 0))
 107  *              err(1, "Bit 0 was already clear?!");
 108  */
 109 static inline bool jbit_clear(struct jbitset *set, unsigned long index)
 110 {
 111         return Judy1Unset(&set->judy, index, &set->err);
 112 }
 113
 114 /**
 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).
 119  *
 120  * Example:
 121  *      assert(jbit_popcount(set, 0, 1000) <= jbit_popcount(set, 0, 2000));
 122  */
 123 static inline unsigned long jbit_popcount(const struct jbitset *set,
 124                                           unsigned long start,
 125                                           unsigned long end_incl)
 126 {
 127         return Judy1Count(set->judy, start, end_incl, (JError_t *)&set->err);
 128 }
 129
 130 /**
 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
 135  *
 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:
 139  *
 140  *      static bool jbit_nth_index(struct jbitset *set,
 141  *                                 unsigned long n, unsigned long *idx)
 142  *      {
 143  *              // Zero might be valid, if it's first in set.
 144  *              if (n == 0 && jbit_test(set, 0)) {
 145  *                      *idx = 0;
 146  *                      return true;
 147  *              }
 148  *              *idx = jbit_nth(set, n, 0);
 149  *              return (*idx != 0);
 150  *      }
 151  *
 152  * Example:
 153  *      unsigned long i, val;
 154  *
 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 %lu = %lu\n", i, val);
 160  *      }
 161  */
 162 static inline unsigned long jbit_nth(const struct jbitset *set,
 163                                      unsigned long n, unsigned long invalid)
 164 {
 165         unsigned long index;
 166         if (!Judy1ByCount(set->judy, n+1, &index, (JError_t *)&set->err))
 167                 index = invalid;
 168         return index;
 169 }
 170
 171 /**
 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.
 175  *
 176  * This is equivalent to jbit_nth(set, 0, invalid).
 177  *
 178  * Example:
 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))
 182  *              printf(" %lu", i);
 183  *      printf("\n");
 184  */
 185 static inline unsigned long jbit_first(const struct jbitset *set,
 186                                        unsigned long invalid)
 187 {
 188         unsigned long index = 0;
 189         if (!Judy1First(set->judy, &index, (JError_t *)&set->err))
 190                 index = invalid;
 191         else
 192                 assert(index != invalid);
 193         return index;
 194 }
 195
 196 /**
 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.
 201  *
 202  * This is usually used to find an adjacent bit which is set, after
 203  * jbit_first.
 204  */
 205 static inline unsigned long jbit_next(const struct jbitset *set,
 206                                       unsigned long prev,
 207                                       unsigned long invalid)
 208 {
 209         if (!Judy1Next(set->judy, &prev, (JError_t *)&set->err))
 210                 prev = invalid;
 211         else
 212                 assert(prev != invalid);
 213         return prev;
 214 }
 215
 216 /**
 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.
 220  *
 221  * Example:
 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))
 225  *              printf(" %lu", i);
 226  *      printf("\n");
 227  */
 228 static inline unsigned long jbit_last(const struct jbitset *set,
 229                                       unsigned long invalid)
 230 {
 231         unsigned long index = -1;
 232         if (!Judy1Last(set->judy, &index, (JError_t *)&set->err))
 233                 index = invalid;
 234         else
 235                 assert(index != invalid);
 236         return index;
 237 }
 238
 239 /**
 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.
 244  *
 245  * This is usually used to find an adjacent bit which is set, after
 246  * jbit_last.
 247  */
 248 static inline unsigned long jbit_prev(const struct jbitset *set,
 249                                       unsigned long prev,
 250                                       unsigned long invalid)
 251 {
 252         if (!Judy1Prev(set->judy, &prev, (JError_t *)&set->err))
 253                 prev = invalid;
 254         else
 255                 assert(prev != invalid);
 256         return prev;
 257 }
 258
 259 /**
 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.
 263  *
 264  * This allows for iterating the inverse of the bitmap.
 265  */
 266 static inline unsigned long jbit_first_clear(const struct jbitset *set,
 267                                              unsigned long invalid)
 268 {
 269         unsigned long index = 0;
 270         if (!Judy1FirstEmpty(set->judy, &index, (JError_t *)&set->err))
 271                 index = invalid;
 272         else
 273                 assert(index != invalid);
 274         return index;
 275 }
 276
 277 static inline unsigned long jbit_next_clear(const struct jbitset *set,
 278                                             unsigned long prev,
 279                                             unsigned long invalid)
 280 {
 281         if (!Judy1NextEmpty(set->judy, &prev, (JError_t *)&set->err))
 282                 prev = invalid;
 283         else
 284                 assert(prev != invalid);
 285         return prev;
 286 }
 287
 288 static inline unsigned long jbit_last_clear(const struct jbitset *set,
 289                                             unsigned long invalid)
 290 {
 291         unsigned long index = -1;
 292         if (!Judy1LastEmpty(set->judy, &index, (JError_t *)&set->err))
 293                 index = invalid;
 294         else
 295                 assert(index != invalid);
 296         return index;
 297 }
 298
 299 static inline unsigned long jbit_prev_clear(const struct jbitset *set,
 300                                             unsigned long prev,
 301                                             unsigned long invalid)
 302 {
 303         if (!Judy1PrevEmpty(set->judy, &prev, (JError_t *)&set->err))
 304                 prev = invalid;
 305         else
 306                 assert(prev != invalid);
 307         return prev;
 308 }
 309 #endif /* CCAN_JBITSET_H */