diff options
author | Alex Ray <aray@google.com> | 2013-01-07 16:38:49 -0800 |
---|---|---|
committer | Android (Google) Code Review <android-gerrit@google.com> | 2013-01-07 16:38:50 -0800 |
commit | b65bea46ad81a46c0c9be277474b597cc75c2737 (patch) | |
tree | 2c95560235b1fc87cff1994fd31e4fffbab6ead5 | |
parent | 273f504c14ebbcead6c4adfa630135dd77bea8d1 (diff) | |
parent | 2111bc7b28af06757fa8108bab045188d4b337fd (diff) | |
download | system_core-b65bea46ad81a46c0c9be277474b597cc75c2737.zip system_core-b65bea46ad81a46c0c9be277474b597cc75c2737.tar.gz system_core-b65bea46ad81a46c0c9be277474b597cc75c2737.tar.bz2 |
Merge "cutils: Add bitmask utilities to bitops"
-rw-r--r-- | include/cutils/bitops.h | 68 |
1 files changed, 68 insertions, 0 deletions
diff --git a/include/cutils/bitops.h b/include/cutils/bitops.h index 1b3b762..6893985 100644 --- a/include/cutils/bitops.h +++ b/include/cutils/bitops.h @@ -17,10 +17,78 @@ #ifndef __CUTILS_BITOPS_H #define __CUTILS_BITOPS_H +#include <string.h> +#include <strings.h> #include <sys/cdefs.h> __BEGIN_DECLS +/* + * Bitmask Operations + * + * Note this doesn't provide any locking/exclusion, and isn't atomic. + * Additionally no bounds checking is done on the bitmask array. + * + * Example: + * + * int num_resources; + * unsigned int resource_bits[BITS_TO_WORDS(num_resources)]; + * bitmask_init(resource_bits, num_resources); + * ... + * int bit = bitmask_ffz(resource_bits, num_resources); + * bitmask_set(resource_bits, bit); + * ... + * if (bitmask_test(resource_bits, bit)) { ... } + * ... + * bitmask_clear(resource_bits, bit); + * + */ + +#define BITS_PER_WORD (sizeof(unsigned int) * 8) +#define BITS_TO_WORDS(x) (((x) + BITS_PER_WORD - 1) / BITS_PER_WORD) +#define BIT_IN_WORD(x) ((x) % BITS_PER_WORD) +#define BIT_WORD(x) ((x) / BITS_PER_WORD) +#define BIT_MASK(x) (1 << BIT_IN_WORD(x)) + +static inline void bitmask_init(unsigned int *bitmask, int num_bits) +{ + memset(bitmask, 0, BITS_TO_WORDS(num_bits)*sizeof(unsigned int)); +} + +static inline int bitmask_ffz(unsigned int *bitmask, int num_bits) +{ + int bit, result; + unsigned int i; + + for (i = 0; i < BITS_TO_WORDS(num_bits); i++) { + bit = ffs(~bitmask[i]); + if (bit) { + // ffs is 1-indexed, return 0-indexed result + bit--; + result = BITS_PER_WORD * i + bit; + if (result >= num_bits) + return -1; + return result; + } + } + return -1; +} + +static inline void bitmask_set(unsigned int *bitmask, int bit) +{ + bitmask[BIT_WORD(bit)] |= BIT_MASK(bit); +} + +static inline void bitmask_clear(unsigned int *bitmask, int bit) +{ + bitmask[BIT_WORD(bit)] &= ~BIT_MASK(bit); +} + +static inline bool bitmask_test(unsigned int *bitmask, int bit) +{ + return bitmask[BIT_WORD(bit)] & BIT_MASK(bit); +} + static inline int popcount(unsigned int x) { return __builtin_popcount(x); |