diff options
| -rw-r--r-- | src/common/container.h | 44 | ||||
| -rw-r--r-- | src/or/test.c | 39 |
2 files changed, 83 insertions, 0 deletions
diff --git a/src/common/container.h b/src/common/container.h index db5967208..a342b2667 100644 --- a/src/common/container.h +++ b/src/common/container.h @@ -267,5 +267,49 @@ void* strmap_remove_lc(strmap_t *map, const char *key); return digestmap_iter_done((digestmap_iter_t*)iter); \ } +#if SIZEOF_INT == 4 +#define BITARRAY_SHIFT 5 +#define BITARRAY_MASK 31 +#elif SIZEOF_INT == 8 +#define BITARRAY_SHIFT 6 +#define BITARRAY_MASK 63 +#else +#error "int is neither 4 nor 8 bites. I can't deal with that." +#endif + +typedef unsigned int bitarray_t; +/** Create a new bit array that can hold <b>n_bits</b> bits. */ +static INLINE bitarray_t * +bitarray_init_zero(int n_bits) +{ + size_t sz = (n_bits+BITARRAY_MASK) & BITARRAY_MASK; + return tor_malloc_zero(sz*sizeof(unsigned int)); +} +/** Free the bit array <b>ba</b>. */ +static INLINE void +bitarray_free(bitarray_t *ba) +{ + tor_free(ba); +} +/** Set the <b>bit</b>th bit in <b>b</b> to 1. */ +static INLINE void +bitarray_set(bitarray_t *b, int bit) +{ + b[bit >> BITARRAY_SHIFT] |= (1u << (bit & BITARRAY_MASK)); +} +/** Set the <b>bit</b>th bit in <b>b</b> to 0. */ +static INLINE void +bitarray_clear(bitarray_t *b, int bit) +{ + b[bit >> BITARRAY_SHIFT] &= ~ (1u << (bit & BITARRAY_MASK)); +} +/** Return true iff <b>bit</b>th bit in <b>b</b> is nonzero. NOTE: does + * not necessarily return 1 on true. */ +static INLINE unsigned int +bitarray_is_set(bitarray_t *b, int bit) +{ + return b[bit >> BITARRAY_SHIFT] & (1u << (bit & BITARRAY_MASK)); +} + #endif diff --git a/src/or/test.c b/src/or/test.c index 2776fcbfc..147023a8d 100644 --- a/src/or/test.c +++ b/src/or/test.c @@ -1544,6 +1544,43 @@ test_smartlist(void) smartlist_free(sl); } +static void +test_bitarray(void) +{ + bitarray_t *ba; + int i, j, ok=1; + + ba = bitarray_init_zero(1); + test_assert(! bitarray_is_set(ba, 0)); + bitarray_set(ba, 0); + test_assert(bitarray_is_set(ba, 0)); + bitarray_clear(ba, 0); + test_assert(! bitarray_is_set(ba, 0)); + bitarray_free(ba); + + ba = bitarray_init_zero(1023); + for (i = 1; i < 64; ) { + for (j = 0; j < 1023; ++j) { + if (j % i) + bitarray_set(ba, j); + else + bitarray_clear(ba, j); + } + for (j = 0; j < 1023; ++j) { + if (!bool_eq(bitarray_is_set(ba, j), j%i)) + ok = 0; + } + test_assert(ok); + if (i < 7) + ++i; + else if (i == 28) + i = 32; + else + i += 7; + } + bitarray_free(ba); +} + /* stop threads running at once. */ static tor_mutex_t *_thread_test_mutex = NULL; /* make sure that threads have to run at the same time. */ @@ -2990,6 +3027,8 @@ main(int c, char**v) test_util(); puts("\n--smartlist"); test_smartlist(); + puts("\n--bitarray"); + test_bitarray(); puts("\n--mempool"); test_mempool(); puts("\n--strmap"); |