+++ /dev/null
-/* Licensed under LGPLv2.1+ - see LICENSE file for details */
-#ifndef CCAN_JBITSET_H
-#define CCAN_JBITSET_H
-#include <Judy.h>
-#include <stdbool.h>
-#include <ccan/compiler/compiler.h>
-#include <assert.h>
-
-/**
- * jbit_new - create a new, empty jbitset.
- *
- * See Also:
- * JBIT_DEFINE_TYPE()
- *
- * Example:
- * struct jbitset *set = jbit_new();
- * if (!set)
- * errx(1, "Failed to allocate jbitset");
- */
-struct jbitset *jbit_new(void);
-
-/**
- * jbit_free - destroy a jbitset.
- * @set: the set returned from jbit_new.
- *
- * Example:
- * jbit_free(set);
- */
-void jbit_free(const struct jbitset *set);
-
-/* This is exposed in the header so we can inline. Treat it as private! */
-struct jbitset {
- void *judy;
- JError_t err;
- const char *errstr;
-};
-const char *COLD jbit_error_(struct jbitset *set);
-
-/**
- * jbit_error - test for an error in the a previous jbit_ operation.
- * @set: the set to test.
- *
- * Under normal circumstances, return NULL to indicate no error has occurred.
- * Otherwise, it will return a string containing the error. This string
- * can only be freed by jbit_free() on the set.
- *
- * Other than out-of-memory, errors are caused by memory corruption or
- * interface misuse.
- *
- * Example:
- * struct jbitset *set = jbit_new();
- * const char *errstr;
- *
- * if (!set)
- * err(1, "allocating jbitset");
- * errstr = jbit_error(set);
- * if (errstr)
- * errx(1, "Woah, error on newly created set?! %s", errstr);
- */
-static inline const char *jbit_error(struct jbitset *set)
-{
- if (JU_ERRNO(&set->err) <= JU_ERRNO_NFMAX)
- return NULL;
- return jbit_error_(set);
-}
-
-/**
- * jbit_test - test a bit in the bitset.
- * @set: bitset from jbit_new
- * @index: the index to test
- *
- * Returns true if jbit_set() has been done on this index, false otherwise.
- *
- * Example:
- * assert(!jbit_test(set, 0));
- */
-static inline bool jbit_test(const struct jbitset *set, unsigned long index)
-{
- return Judy1Test(set->judy, index, (JError_t *)&set->err);
-}
-
-/**
- * jbit_set - set a bit in the bitset.
- * @set: bitset from jbit_new
- * @index: the index to set
- *
- * Returns false if it was already set (ie. nothing changed)
- *
- * Example:
- * if (jbit_set(set, 0))
- * err(1, "Bit 0 was already set?!");
- */
-static inline bool jbit_set(struct jbitset *set, unsigned long index)
-{
- return Judy1Set(&set->judy, index, &set->err);
-}
-
-/**
- * jbit_clear - clear a bit in the bitset.
- * @set: bitset from jbit_new
- * @index: the index to set
- *
- * Returns the old bit value (ie. false if nothing changed).
- *
- * Example:
- * if (jbit_clear(set, 0))
- * err(1, "Bit 0 was already clear?!");
- */
-static inline bool jbit_clear(struct jbitset *set, unsigned long index)
-{
- return Judy1Unset(&set->judy, index, &set->err);
-}
-
-/**
- * jbit_popcount - get population of (some part of) bitset.
- * @set: bitset from jbit_new
- * @start: first index to count
- * @end_incl: last index to count (use -1 for end).
- *
- * Example:
- * assert(jbit_popcount(set, 0, 1000) <= jbit_popcount(set, 0, 2000));
- */
-static inline unsigned long jbit_popcount(const struct jbitset *set,
- unsigned long start,
- unsigned long end_incl)
-{
- return Judy1Count(set->judy, start, end_incl, (JError_t *)&set->err);
-}
-
-/**
- * jbit_nth - return the index of the nth bit which is set.
- * @set: bitset from jbit_new
- * @n: which bit we are interested in (0-based)
- * @invalid: what to return if n >= set population
- *
- * This normally returns the nth bit in the set, and often there is a
- * convenient known-invalid value (ie. something which is never in the
- * set). Otherwise, and a wrapper function like this can be used:
- *
- * static bool jbit_nth_index(struct jbitset *set,
- * unsigned long n, unsigned long *idx)
- * {
- * // Zero might be valid, if it's first in set.
- * if (n == 0 && jbit_test(set, 0)) {
- * *idx = 0;
- * return true;
- * }
- * *idx = jbit_nth(set, n, 0);
- * return (*idx != 0);
- * }
- *
- * Example:
- * unsigned long i, val;
- *
- * // We know 0 isn't in set.
- * assert(!jbit_test(set, 0));
- * for (i = 0; (val = jbit_nth(set, i, 0)) != 0; i++) {
- * assert(jbit_popcount(set, 0, val) == i);
- * printf("Value %lu = %lu\n", i, val);
- * }
- */
-static inline unsigned long jbit_nth(const struct jbitset *set,
- unsigned long n, unsigned long invalid)
-{
- unsigned long index;
- if (!Judy1ByCount(set->judy, n+1, &index, (JError_t *)&set->err))
- index = invalid;
- return index;
-}
-
-/**
- * jbit_first - return the first bit which is set.
- * @set: bitset from jbit_new
- * @invalid: return value if no bits are set at all.
- *
- * This is equivalent to jbit_nth(set, 0, invalid).
- *
- * Example:
- * assert(!jbit_test(set, 0));
- * printf("Set contents (increasing order):");
- * for (i = jbit_first(set, 0); i; i = jbit_next(set, i, 0))
- * printf(" %lu", i);
- * printf("\n");
- */
-static inline unsigned long jbit_first(const struct jbitset *set,
- unsigned long invalid)
-{
- unsigned long index = 0;
- if (!Judy1First(set->judy, &index, (JError_t *)&set->err))
- index = invalid;
- else
- assert(index != invalid);
- return index;
-}
-
-/**
- * jbit_next - return the next bit which is set.
- * @set: bitset from jbit_new
- * @prev: previous index
- * @invalid: return value if no bits are set at all.
- *
- * This is usually used to find an adjacent bit which is set, after
- * jbit_first.
- */
-static inline unsigned long jbit_next(const struct jbitset *set,
- unsigned long prev,
- unsigned long invalid)
-{
- if (!Judy1Next(set->judy, &prev, (JError_t *)&set->err))
- prev = invalid;
- else
- assert(prev != invalid);
- return prev;
-}
-
-/**
- * jbit_last - return the last bit which is set.
- * @set: bitset from jbit_new
- * @invalid: return value if no bits are set at all.
- *
- * Example:
- * assert(!jbit_test(set, 0));
- * printf("Set contents (decreasing order):");
- * for (i = jbit_last(set, 0); i; i = jbit_prev(set, i, 0))
- * printf(" %lu", i);
- * printf("\n");
- */
-static inline unsigned long jbit_last(const struct jbitset *set,
- unsigned long invalid)
-{
- unsigned long index = -1;
- if (!Judy1Last(set->judy, &index, (JError_t *)&set->err))
- index = invalid;
- else
- assert(index != invalid);
- return index;
-}
-
-/**
- * jbit_prev - return the previous bit which is set.
- * @set: bitset from jbit_new
- * @prev: previous index
- * @invalid: return value if no bits are set at all.
- *
- * This is usually used to find an adjacent bit which is set, after
- * jbit_last.
- */
-static inline unsigned long jbit_prev(const struct jbitset *set,
- unsigned long prev,
- unsigned long invalid)
-{
- if (!Judy1Prev(set->judy, &prev, (JError_t *)&set->err))
- prev = invalid;
- else
- assert(prev != invalid);
- return prev;
-}
-
-/**
- * jbit_first_clear - return the first bit which is unset.
- * @set: bitset from jbit_new
- * @invalid: return value if no bits are clear at all.
- *
- * This allows for iterating the inverse of the bitmap.
- */
-static inline unsigned long jbit_first_clear(const struct jbitset *set,
- unsigned long invalid)
-{
- unsigned long index = 0;
- if (!Judy1FirstEmpty(set->judy, &index, (JError_t *)&set->err))
- index = invalid;
- else
- assert(index != invalid);
- return index;
-}
-
-static inline unsigned long jbit_next_clear(const struct jbitset *set,
- unsigned long prev,
- unsigned long invalid)
-{
- if (!Judy1NextEmpty(set->judy, &prev, (JError_t *)&set->err))
- prev = invalid;
- else
- assert(prev != invalid);
- return prev;
-}
-
-static inline unsigned long jbit_last_clear(const struct jbitset *set,
- unsigned long invalid)
-{
- unsigned long index = -1;
- if (!Judy1LastEmpty(set->judy, &index, (JError_t *)&set->err))
- index = invalid;
- else
- assert(index != invalid);
- return index;
-}
-
-static inline unsigned long jbit_prev_clear(const struct jbitset *set,
- unsigned long prev,
- unsigned long invalid)
-{
- if (!Judy1PrevEmpty(set->judy, &prev, (JError_t *)&set->err))
- prev = invalid;
- else
- assert(prev != invalid);
- return prev;
-}
-#endif /* CCAN_JBITSET_H */
projects / ccan / blobdiff