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

   1 /* Licensed under LGPLv2.1+ - see LICENSE file for details */
   2 #ifndef CCAN_JSET_H
   3 #define CCAN_JSET_H
   4 #include "config.h"
   5 #include <ccan/compiler/compiler.h>
   6 #include <ccan/tcon/tcon.h>
   7 #include <Judy.h>
   8 #include <stdbool.h>
   9 #include <assert.h>
  10
  11 /**
  12  * struct jset - private definition of a jset.
  13  *
  14  * It's exposed here so you can put it in your structures and so we can
  15  * supply inline functions.
  16  */
  17 struct jset {
  18         void *judy;
  19         JError_t err;
  20         const char *errstr;
  21 };
  22
  23 /**
  24  * JSET_MEMBERS - declare members for a type-specific jset.
  25  * @type: type for this set to contain, or void * for any pointer.
  26  *
  27  * Example:
  28  *      struct jset_long {
  29  *              JSET_MEMBERS(long);
  30  *      };
  31  */
  32 #define JSET_MEMBERS(type)                      \
  33         struct jset raw;                        \
  34         TCON(type canary)
  35
  36 /**
  37  * jset_new - create a new, empty jset.
  38  * @type: the tcon-containing type to allocate.
  39  *
  40  * Example:
  41  *      struct jset_long {
  42  *              JSET_MEMBERS(long);
  43  *      } *set = jset_new(struct jset_long);
  44  *
  45  *      if (!set)
  46  *              errx(1, "Failed to allocate set");
  47  */
  48 #define jset_new(type) ((type *)jset_new_(sizeof(type)))
  49
  50 /**
  51  * jset_free - destroy a jset.
  52  * @set: the set returned from jset_new.
  53  *
  54  * Example:
  55  *      jset_free(set);
  56  */
  57 #define jset_free(set) jset_free_(&(set)->raw)
  58
  59 /**
  60  * jset_error - test for an error in the a previous jset_ operation.
  61  * @set: the set to test.
  62  *
  63  * Under normal circumstances, return NULL to indicate no error has occurred.
  64  * Otherwise, it will return a string containing the error.  This string
  65  * can only be freed by jset_free() on the set.
  66  *
  67  * Other than out-of-memory, errors are caused by memory corruption or
  68  * interface misuse.
  69  *
  70  * Example:
  71  *      const char *errstr;
  72  *
  73  *      errstr = jset_error(set);
  74  *      if (errstr)
  75  *              errx(1, "Woah, error on newly created set?! %s", errstr);
  76  */
  77 #define jset_error(set) \
  78         jset_error_(&(set)->raw)
  79
  80 /**
  81  * jset_raw - unwrap the typed set and check the type
  82  * @set: the typed jset
  83  * @expr: the expression to check the type against (not evaluated)
  84  *
  85  * This macro usually causes the compiler to emit a warning if the
  86  * variable is of an unexpected type.  It is used internally where we
  87  * need to access the raw underlying jset.
  88  */
  89 #define jset_raw(set, expr) (&tcon_check((set), canary, (expr))->raw)
  90
  91 /**
  92  * jset_test - test a bit in the bitset.
  93  * @set: bitset from jset_new
  94  * @index: the index to test
  95  *
  96  * Returns true if jset_set() has been done on this index, false otherwise.
  97  *
  98  * Example:
  99  *      assert(!jset_test(set, 0));
 100  */
 101 #define jset_test(set, index)                                           \
 102         jset_test_(jset_raw((set), (index)), (unsigned long)(index))
 103
 104 /**
 105  * jset_set - set a bit in the bitset.
 106  * @set: bitset from jset_new
 107  * @index: the index to set
 108  *
 109  * Returns false if it was already set (ie. nothing changed)
 110  *
 111  * Example:
 112  *      if (jset_set(set, 0))
 113  *              err(1, "Bit 0 was already set?!");
 114  */
 115 #define jset_set(set, index)                                            \
 116         jset_set_(jset_raw((set), (index)), (unsigned long)(index))
 117
 118 /**
 119  * jset_clear - clear a bit in the bitset.
 120  * @set: bitset from jset_new
 121  * @index: the index to set
 122  *
 123  * Returns the old bit value (ie. false if nothing changed).
 124  *
 125  * Example:
 126  *      if (jset_clear(set, 0))
 127  *              err(1, "Bit 0 was already clear?!");
 128  */
 129 #define jset_clear(set, index)                                          \
 130         jset_clear_(jset_raw((set), (index)), (unsigned long)(index))
 131
 132 /**
 133  * jset_count - get population of bitset.
 134  * @set: bitset from jset_new
 135  *
 136  * Example:
 137  *      // We expect 1000 entries.
 138  *      assert(jset_count(set) == 1000);
 139  */
 140 #define jset_count(set)                         \
 141         jset_popcount_(&(set)->raw, 0, -1UL)
 142
 143 /**
 144  * jset_popcount - get population of (some part of) bitset.
 145  * @set: bitset from jset_new
 146  * @start: first index to count
 147  * @end_incl: last index to count (use -1 for end).
 148  *
 149  * Example:
 150  *      assert(jset_popcount(set, 0, 1000) <= jset_popcount(set, 0, 2000));
 151  */
 152 #define jset_popcount(set, start, end_incl)                             \
 153         jset_popcount_(jset_raw((set), (start) ? (start) : (end_incl)), \
 154                        (unsigned long)(start), (unsigned long)(end_incl))
 155
 156 /**
 157  * jset_nth - return the index of the nth bit which is set.
 158  * @set: bitset from jset_new
 159  * @n: which bit we are interested in (0-based)
 160  * @invalid: what to return if n >= set population
 161  *
 162  * This normally returns the nth bit in the set, and often there is a
 163  * convenient known-invalid value (ie. something which is never in the
 164  * set).  Otherwise, and a wrapper function like this can be used:
 165  *
 166  *      static bool jset_nth_index(struct jset *set,
 167  *                                 unsigned long n, unsigned long *idx)
 168  *      {
 169  *              // Zero might be valid, if it's first in set.
 170  *              if (n == 0 && jset_test(set, 0)) {
 171  *                      *idx = 0;
 172  *                      return true;
 173  *              }
 174  *              *idx = jset_nth(set, n, 0);
 175  *              return (*idx != 0);
 176  *      }
 177  *
 178  * Example:
 179  *      unsigned long i, val;
 180  *
 181  *      // We know 0 isn't in set.
 182  *      assert(!jset_test(set, 0));
 183  *      for (i = 0; (val = jset_nth(set, i, 0)) != 0; i++) {
 184  *              assert(jset_popcount(set, 0, val) == i);
 185  *              printf("Value %lu = %lu\n", i, val);
 186  *      }
 187  */
 188 #define jset_nth(set, n, invalid)                                       \
 189         tcon_cast((set), canary,                                        \
 190                   jset_nth_(jset_raw((set), (invalid)),                 \
 191                             (n), (unsigned long)(invalid)))
 192
 193 /**
 194  * jset_first - return the first bit which is set (must not contain 0).
 195  * @set: bitset from jset_new
 196  *
 197  * This is equivalent to jset_nth(set, 0, 0).  ie. useful only if 0
 198  * isn't in your set.
 199  *
 200  * Example:
 201  *      assert(!jset_test(set, 0));
 202  *      printf("Set contents (increasing order):");
 203  *      for (i = jset_first(set); i; i = jset_next(set, i))
 204  *              printf(" %lu", i);
 205  *      printf("\n");
 206  */
 207 #define jset_first(set)                                         \
 208         tcon_cast((set), canary, jset_first_(&(set)->raw))
 209
 210 /**
 211  * jset_next - return the next bit which is set (must not contain 0).
 212  * @set: bitset from jset_new
 213  * @prev: previous index
 214  *
 215  * This is usually used to find an adjacent index which is set, after
 216  * jset_first.
 217  */
 218 #define jset_next(set, prev)                                            \
 219         tcon_cast((set), canary, jset_next_(&(set)->raw, (unsigned long)(prev)))
 220
 221 /**
 222  * jset_last - return the last bit which is set (must not contain 0).
 223  * @set: bitset from jset_new
 224  *
 225  * Example:
 226  *      assert(!jset_test(set, 0));
 227  *      printf("Set contents (decreasing order):");
 228  *      for (i = jset_last(set); i; i = jset_prev(set, i))
 229  *              printf(" %lu", i);
 230  *      printf("\n");
 231  */
 232 #define jset_last(set)                                          \
 233         tcon_cast((set), canary, jset_last_(&(set)->raw))
 234
 235 /**
 236  * jset_prev - return the previous bit which is set (must not contain 0).
 237  * @set: bitset from jset_new
 238  * @prev: previous index
 239  *
 240  * This is usually used to find an adjacent bit which is set, after
 241  * jset_last.
 242  */
 243 #define jset_prev(set, prev)                                            \
 244         tcon_cast((set), canary, jset_prev_(&(set)->raw, (unsigned long)(prev)))
 245
 246 /**
 247  * jset_first_clear - return the first bit which is unset
 248  * @set: bitset from jset_new
 249  *
 250  * This allows for iterating the inverse of the bitmap; only returns 0 if the
 251  * set is full.
 252  */
 253 #define jset_first_clear(set)                                           \
 254         tcon_cast((set), canary, jset_next_clear_(&(set)->raw, 0))
 255
 256 #define jset_next_clear(set, prev)                                      \
 257         tcon_cast((set), canary, jset_next_clear_(&(set)->raw,          \
 258                                                   (unsigned long)(prev)))
 259
 260 #define jset_last_clear(set)                                    \
 261         tcon_cast((set), canary, jset_last_clear_(&(set)->raw))
 262
 263 #define jset_prev_clear(set, prev)                                      \
 264         tcon_cast((set), canary, jset_prev_clear_(&(set)->raw,          \
 265                                                   (unsigned long)(prev)))
 266
 267 /* Raw functions */
 268 struct jset *jset_new_(size_t size);
 269 void jset_free_(const struct jset *set);
 270 const char *COLD jset_error_str_(struct jset *set);
 271 static inline const char *jset_error_(struct jset *set)
 272 {
 273         if (JU_ERRNO(&set->err) <= JU_ERRNO_NFMAX)
 274                 return NULL;
 275         return jset_error_str_(set);
 276 }
 277 static inline bool jset_test_(const struct jset *set, unsigned long index)
 278 {
 279         return Judy1Test(set->judy, index, (JError_t *)&set->err);
 280 }
 281 static inline bool jset_set_(struct jset *set, unsigned long index)
 282 {
 283         return Judy1Set(&set->judy, index, &set->err);
 284 }
 285 static inline bool jset_clear_(struct jset *set, unsigned long index)
 286 {
 287         return Judy1Unset(&set->judy, index, &set->err);
 288 }
 289 static inline unsigned long jset_popcount_(const struct jset *set,
 290                                            unsigned long start,
 291                                            unsigned long end_incl)
 292 {
 293         return Judy1Count(set->judy, start, end_incl, (JError_t *)&set->err);
 294 }
 295 static inline unsigned long jset_nth_(const struct jset *set,
 296                                       unsigned long n, unsigned long invalid)
 297 {
 298         unsigned long index;
 299         if (!Judy1ByCount(set->judy, n+1, &index, (JError_t *)&set->err))
 300                 index = invalid;
 301         return index;
 302 }
 303 static inline unsigned long jset_first_(const struct jset *set)
 304 {
 305         unsigned long index = 0;
 306         if (!Judy1First(set->judy, &index, (JError_t *)&set->err))
 307                 index = 0;
 308         else
 309                 assert(index != 0);
 310         return index;
 311 }
 312 static inline unsigned long jset_next_(const struct jset *set,
 313                                        unsigned long prev)
 314 {
 315         if (!Judy1Next(set->judy, &prev, (JError_t *)&set->err))
 316                 prev = 0;
 317         else
 318                 assert(prev != 0);
 319         return prev;
 320 }
 321 static inline unsigned long jset_last_(const struct jset *set)
 322 {
 323         unsigned long index = -1;
 324         if (!Judy1Last(set->judy, &index, (JError_t *)&set->err))
 325                 index = 0;
 326         else
 327                 assert(index != 0);
 328         return index;
 329 }
 330 static inline unsigned long jset_prev_(const struct jset *set,
 331                                        unsigned long prev)
 332 {
 333         if (!Judy1Prev(set->judy, &prev, (JError_t *)&set->err))
 334                 prev = 0;
 335         else
 336                 assert(prev != 0);
 337         return prev;
 338 }
 339 static inline unsigned long jset_next_clear_(const struct jset *set,
 340                                              unsigned long prev)
 341 {
 342         if (!Judy1NextEmpty(set->judy, &prev, (JError_t *)&set->err))
 343                 prev = 0;
 344         else
 345                 assert(prev != 0);
 346         return prev;
 347 }
 348 static inline unsigned long jset_last_clear_(const struct jset *set)
 349 {
 350         unsigned long index = -1;
 351         if (!Judy1LastEmpty(set->judy, &index, (JError_t *)&set->err))
 352                 index = 0;
 353         return index;
 354 }
 355 static inline unsigned long jset_prev_clear_(const struct jset *set,
 356                                              unsigned long prev)
 357 {
 358         if (!Judy1PrevEmpty(set->judy, &prev, (JError_t *)&set->err))
 359                 prev = 0;
 360         return prev;
 361 }
 362 #endif /* CCAN_JSET_H */