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