Loading...
--- libmalloc/libmalloc-53.30.1/src/bitarray.c
+++ libmalloc/libmalloc-317.100.9/src/bitarray.c
@@ -28,15 +28,15 @@
// Copyright (c) 2010 Apple. All rights reserved.
//
-#include "bitarray.h"
-#define NDEBUG 1
-#include <assert.h>
+#include "internal.h"
/******************************** Utilities ***************************/
#define STATIC_INLINE static __inline
-STATIC_INLINE unsigned __ffsll(uint64_t xx) {
+STATIC_INLINE unsigned
+__ffsll(uint64_t xx)
+{
#if defined(__LP64__)
return __builtin_ffsl(xx);
#else
@@ -44,171 +44,232 @@
#endif
}
-#define BIT_SET(old,bit) ((old) | (1ULL << (bit)))
-#define BIT_GET(old,bit) ((old) & (1ULL << (bit)))
-#define BIT_ZAP(old,bit) ((old) & ~ (1ULL << (bit)))
+#define BIT_SET(old, bit) ((old) | (1ULL << (bit)))
+#define BIT_GET(old, bit) ((old) & (1ULL << (bit)))
+#define BIT_ZAP(old, bit) ((old) & ~(1ULL << (bit)))
// several variants below of bit setting or zapping to generate minimal code
// All these do 1 memory read and (maybe) 1 memory write
-STATIC_INLINE bool word_get_bit_simple(uint64_t *word, unsigned bit) {
- uint64_t old = *word;
+STATIC_INLINE bool
+word_get_bit_simple(uint64_t *word, unsigned bit)
+{
+ uint64_t old = *word;
return BIT_GET(old, bit) != 0;
}
-STATIC_INLINE void word_set_bit_simple(uint64_t *word, unsigned bit) {
- uint64_t old = *word;
+STATIC_INLINE void
+word_set_bit_simple(uint64_t *word, unsigned bit)
+{
+ uint64_t old = *word;
*word = BIT_SET(old, bit);
}
-STATIC_INLINE bool word_set_bit_changed(uint64_t *word, unsigned bit) {
+STATIC_INLINE bool
+word_set_bit_changed(uint64_t *word, unsigned bit)
+{
// returns 1 iff word has changed
- uint64_t old = *word;
- uint64_t new = BIT_SET(old, bit);
- if (old == new) return 0;
+ uint64_t old = *word;
+ uint64_t new = BIT_SET(old, bit);
+ if (old == new) {
+ return 0;
+ }
*word = new;
return 1;
}
-STATIC_INLINE bool word_set_bit_changed_go_down(uint64_t *word, unsigned bit, bool *was_non_zero) {
+STATIC_INLINE bool
+word_set_bit_changed_go_down(uint64_t *word, unsigned bit, bool *was_non_zero)
+{
// returns 1 iff word changed
// sets was_non_zero (when something changed)
- uint64_t old = *word;
- uint64_t new = BIT_SET(old, bit);
- if (old == new) return 0;
+ uint64_t old = *word;
+ uint64_t new = BIT_SET(old, bit);
+ if (old == new) {
+ return 0;
+ }
*word = new;
*was_non_zero = old != 0;
return 1;
}
-STATIC_INLINE bool word_set_bit_go_down(uint64_t *word, unsigned bit) {
+STATIC_INLINE bool
+word_set_bit_go_down(uint64_t *word, unsigned bit)
+{
// returns 1 iff level below should be set too
- uint64_t old = *word;
- uint64_t new = BIT_SET(old, bit);
- if (old == new) return 0;
+ uint64_t old = *word;
+ uint64_t new = BIT_SET(old, bit);
+ if (old == new) {
+ return 0;
+ }
*word = new;
return !old;
}
-STATIC_INLINE void word_zap_bit_simple(uint64_t *word, unsigned bit) {
- uint64_t old = *word;
+STATIC_INLINE void
+word_zap_bit_simple(uint64_t *word, unsigned bit)
+{
+ uint64_t old = *word;
*word = BIT_ZAP(old, bit);
}
-STATIC_INLINE bool word_zap_bit_changed(uint64_t *word, unsigned bit) {
+STATIC_INLINE bool
+word_zap_bit_changed(uint64_t *word, unsigned bit)
+{
// returns 1 iff word changed
- uint64_t old = *word;
- uint64_t new = BIT_ZAP(old, bit);
- if (old == new) return 0;
+ uint64_t old = *word;
+ uint64_t new = BIT_ZAP(old, bit);
+ if (old == new) {
+ return 0;
+ }
*word = new;
return 1;
}
-STATIC_INLINE bool word_zap_bit_changed_go_down(uint64_t *word, unsigned bit, bool *is_now_zero) {
+STATIC_INLINE bool
+word_zap_bit_changed_go_down(uint64_t *word, unsigned bit, bool *is_now_zero)
+{
// returns 1 iff word changed
// sets is_now_zero (when something changed)
- uint64_t old = *word;
- uint64_t new = BIT_ZAP(old, bit);
- if (old == new) return 0;
+ uint64_t old = *word;
+ uint64_t new = BIT_ZAP(old, bit);
+ if (old == new) {
+ return 0;
+ }
*word = new;
- *is_now_zero = ! new;
+ *is_now_zero = !new;
return 1;
}
-STATIC_INLINE bool word_zap_bit_go_down(uint64_t *word, unsigned bit) {
+STATIC_INLINE bool
+word_zap_bit_go_down(uint64_t *word, unsigned bit)
+{
// returns 1 iff level below might require a bit-zeroing
- uint64_t old = *word;
- uint64_t new = BIT_ZAP(old, bit);
- if (old == new) return 0;
+ uint64_t old = *word;
+ uint64_t new = BIT_ZAP(old, bit);
+ if (old == new) {
+ return 0;
+ }
*word = new;
return !new;
}
/******************************** Helpers ***************************/
-#define NB 9 // number of bits we process at once
+#define NB 9 // number of bits we process at once
// must be at least 6 (64-bit) and 9 seems the best on x86
-#define MASKNB ((1 << NB) - 1) // to just keep these bits
+#define MASKNB ((1 << NB) - 1) // to just keep these bits
#define NUM_64b (1 << (NB - 6)) // number of 64-bit words we process at once
// number of uint64_t of summaries
-#define LEVEL0 (NUM_64b)
-#define LEVEL1 (LEVEL0 + (1 << NB)*NUM_64b)
-#define LEVEL2 (LEVEL1 + (1 << (NB+NB))*NUM_64b)
-#define LEVEL3 (LEVEL2 + (1 << (NB+NB+NB))*NUM_64b)
-
-#define MAX_LEVEL 5
-
-static const unsigned levels_num_words[] = {LEVEL0, LEVEL1, LEVEL2, LEVEL3}; // this encodes the number of words reserved for the bitmap summaries at various levels
-
-STATIC_INLINE bool GET_SIMPLE(uint64_t *word, unsigned bit) {
+#define LEVEL0 (NUM_64b)
+#define LEVEL1 (LEVEL0 + (1 << NB) * NUM_64b)
+#define LEVEL2 (LEVEL1 + (1 << (NB + NB)) * NUM_64b)
+#define LEVEL3 (LEVEL2 + (1 << (NB + NB + NB)) * NUM_64b)
+
+#define MAX_LEVEL 5
+
+static const unsigned levels_num_words[] = {
+ LEVEL0, LEVEL1, LEVEL2, LEVEL3}; // this encodes the number of words reserved for the bitmap summaries at various levels
+
+STATIC_INLINE bool
+GET_SIMPLE(uint64_t *word, unsigned bit)
+{
return word_get_bit_simple(word + (bit >> 6), bit & 63);
}
-STATIC_INLINE void SET_SIMPLE(uint64_t *word, unsigned bit) {
+STATIC_INLINE void
+SET_SIMPLE(uint64_t *word, unsigned bit)
+{
word_set_bit_simple(word + (bit >> 6), bit & 63);
}
-STATIC_INLINE bool SET_CHANGED(uint64_t *word, unsigned bit) {
+STATIC_INLINE bool
+SET_CHANGED(uint64_t *word, unsigned bit)
+{
// returns 1 iff word changed
return word_set_bit_changed(word + (bit >> 6), bit & 63);
}
-STATIC_INLINE bool SET_CHANGED_GO_DOWN(uint64_t *word, unsigned bit, bool *was_non_zero) {
+STATIC_INLINE bool
+SET_CHANGED_GO_DOWN(uint64_t *word, unsigned bit, bool *was_non_zero)
+{
// returns 1 iff word changed
// sets was_non_zero (when something changed)
return word_set_bit_changed_go_down(word + (bit >> 6), bit & 63, was_non_zero);
}
-STATIC_INLINE bool SET_GO_DOWN(uint64_t *word, unsigned bit) {
+STATIC_INLINE bool
+SET_GO_DOWN(uint64_t *word, unsigned bit)
+{
// returns 1 iff level below should be set too
return word_set_bit_go_down(word + (bit >> 6), bit & 63);
}
-STATIC_INLINE void ZAP_SIMPLE(uint64_t *word, unsigned bit) {
+STATIC_INLINE void
+ZAP_SIMPLE(uint64_t *word, unsigned bit)
+{
return word_zap_bit_simple(word + (bit >> 6), bit & 63);
}
-STATIC_INLINE bool ZAP_CHANGED(uint64_t *word, unsigned bit) {
+STATIC_INLINE bool
+ZAP_CHANGED(uint64_t *word, unsigned bit)
+{
// returns 1 iff word changed
return word_zap_bit_changed(word + (bit >> 6), bit & 63);
}
-STATIC_INLINE bool all_zeros(uint64_t *words) {
+STATIC_INLINE bool
+all_zeros(uint64_t *words)
+{
for (unsigned w = 0; w < NUM_64b; w++) {
- if (words[w]) return 0;
+ if (words[w]) {
+ return 0;
+ }
}
return 1;
}
-STATIC_INLINE bool ZAP_CHANGED_GO_DOWN(uint64_t *word, unsigned bit, bool *is_now_zero) {
+STATIC_INLINE bool
+ZAP_CHANGED_GO_DOWN(uint64_t *word, unsigned bit, bool *is_now_zero)
+{
// returns 1 iff word changed
// sets is_now_zero (when something changed)
bool changed = word_zap_bit_changed_go_down(word + (bit >> 6), bit & 63, is_now_zero);
if (changed && (NUM_64b != 1)) {
// One component went entirely zero, now examine all components in the level
- if (!all_zeros(word)) *is_now_zero = 0;
+ if (!all_zeros(word)) {
+ *is_now_zero = 0;
+ }
}
return changed;
}
-STATIC_INLINE bool ZAP_GO_DOWN(uint64_t *word, unsigned bit) {
+STATIC_INLINE bool
+ZAP_GO_DOWN(uint64_t *word, unsigned bit)
+{
// returns 1 iff level below should be changed too
bool changed = word_zap_bit_go_down(word + (bit >> 6), bit & 63);
if (changed && (NUM_64b != 1)) {
// One component went entirely zero, now examine all components in the level
- if (!all_zeros(word)) return 0;
+ if (!all_zeros(word)) {
+ return 0;
+ }
}
return changed;
}
-STATIC_INLINE unsigned FFS(uint64_t *word) {
- // does NUM_64b memory reads, at most
-#if NB==6
+STATIC_INLINE unsigned
+FFS(uint64_t *word)
+{
+// does NUM_64b memory reads, at most
+#if NB == 6
return __ffsll(*word);
#else
for (unsigned w = 0; w < NUM_64b; w++) {
- unsigned f = __ffsll(word[w]);
- if (f) return f + (w << 6);
+ unsigned f = __ffsll(word[w]);
+ if (f) {
+ return f + (w << 6);
+ }
}
return 0;
#endif
@@ -216,231 +277,325 @@
/******************************** Entry Points ***************************/
-size_t bitarray_size(unsigned log_size) {
- assert(log_size <= MAX_LEVEL * NB);
- unsigned num = NUM_64b;
+size_t
+bitarray_size(unsigned log_size)
+{
+ assert(log_size <= MAX_LEVEL * NB);
+ unsigned num = NUM_64b;
if (log_size > NB) {
- unsigned level = (log_size - NB - 1) / NB;
+ unsigned level = (log_size - NB - 1) / NB;
num = levels_num_words[level] + (1 << (log_size - 6));
}
return num * sizeof(uint64_t);
}
-bitarray_t bitarray_create(unsigned log_size) {
+bitarray_t
+bitarray_create(unsigned log_size)
+{
return calloc(1, bitarray_size(log_size));
}
-bool bitarray_get(bitarray_t bits, unsigned log_size, index_t index) {
+bool
+bitarray_get(bitarray_t bits, unsigned log_size, index_t index)
+{
assert(log_size <= MAX_LEVEL * NB);
assert(index < (1 << log_size));
- if (log_size <= NB) return GET_SIMPLE(bits, index);
- unsigned level = (log_size - NB - 1) / NB;
- unsigned bit;
- bit = index & MASKNB; index >>= NB;
- return GET_SIMPLE(bits + levels_num_words[level] + index*NUM_64b, bit);
-}
-
-bool bitarray_set(bitarray_t bits, unsigned log_size, index_t index) {
+ if (log_size <= NB) {
+ return GET_SIMPLE(bits, index);
+ }
+ unsigned level = (log_size - NB - 1) / NB;
+ unsigned bit;
+ bit = index & MASKNB;
+ index >>= NB;
+ return GET_SIMPLE(bits + levels_num_words[level] + index * NUM_64b, bit);
+}
+
+bool
+bitarray_set(bitarray_t bits, unsigned log_size, index_t index)
+{
// returns whether changed
assert(log_size <= MAX_LEVEL * NB);
assert(index < (1 << log_size));
- if (log_size <= NB) return SET_CHANGED(bits, index);
- unsigned level = (log_size - NB - 1) / NB;
- bool was_non_zero;
- unsigned bit;
- bit = index & MASKNB; index >>= NB;
+ if (log_size <= NB) {
+ return SET_CHANGED(bits, index);
+ }
+ unsigned level = (log_size - NB - 1) / NB;
+ bool was_non_zero;
+ unsigned bit;
+ bit = index & MASKNB;
+ index >>= NB;
// printf("SET_CHANGED_GO_DOWN(bits + %d, %d,…)\n", levels_num_words[level] + index, bit);
- if (!SET_CHANGED_GO_DOWN(bits + levels_num_words[level] + index*NUM_64b, bit, &was_non_zero)) return 0;
- if (was_non_zero) return 1;
+ if (!SET_CHANGED_GO_DOWN(bits + levels_num_words[level] + index * NUM_64b, bit, &was_non_zero)) {
+ return 0;
+ }
+ if (was_non_zero) {
+ return 1;
+ }
switch (level) {
- case 3:
- bit = index & MASKNB; index >>= NB;
- if (!SET_GO_DOWN(bits + LEVEL2 + index*NUM_64b, bit)) return 1;
- /* no break */
- case 2:
- bit = index & MASKNB; index >>= NB;
- if (!SET_GO_DOWN(bits + LEVEL1 + index*NUM_64b, bit)) return 1;
- /* no break */
- case 1:
- bit = index & MASKNB; index >>= NB;
- if (!SET_GO_DOWN(bits + LEVEL0 + index*NUM_64b, bit)) return 1;
- /* no break */
- case 0:
- SET_SIMPLE(bits, index & MASKNB);
+ case 3:
+ bit = index & MASKNB;
+ index >>= NB;
+ if (!SET_GO_DOWN(bits + LEVEL2 + index * NUM_64b, bit)) {
return 1;
- default: abort();
- }
-}
-
-bool bitarray_zap(bitarray_t bits, unsigned log_size, index_t index) {
+ }
+ /* no break */
+ case 2:
+ bit = index & MASKNB;
+ index >>= NB;
+ if (!SET_GO_DOWN(bits + LEVEL1 + index * NUM_64b, bit)) {
+ return 1;
+ }
+ /* no break */
+ case 1:
+ bit = index & MASKNB;
+ index >>= NB;
+ if (!SET_GO_DOWN(bits + LEVEL0 + index * NUM_64b, bit)) {
+ return 1;
+ }
+ /* no break */
+ case 0:
+ SET_SIMPLE(bits, index & MASKNB);
+ return 1;
+ default:
+ MALLOC_FATAL_ERROR(level, "invalid bitarray level");
+ }
+}
+
+bool
+bitarray_zap(bitarray_t bits, unsigned log_size, index_t index)
+{
assert(log_size <= MAX_LEVEL * NB);
assert(index < (1 << log_size));
- if (log_size <= NB) return ZAP_CHANGED(bits, index);
- unsigned level = (log_size - NB - 1) / NB;
- bool is_now_zero;
- unsigned bit;
- bit = index & MASKNB; index >>= NB;
- if (!ZAP_CHANGED_GO_DOWN(bits + levels_num_words[level] + index*NUM_64b, bit, &is_now_zero)) return 0;
- if (!is_now_zero) return 1;
+ if (log_size <= NB) {
+ return ZAP_CHANGED(bits, index);
+ }
+ unsigned level = (log_size - NB - 1) / NB;
+ bool is_now_zero;
+ unsigned bit;
+ bit = index & MASKNB;
+ index >>= NB;
+ if (!ZAP_CHANGED_GO_DOWN(bits + levels_num_words[level] + index * NUM_64b, bit, &is_now_zero)) {
+ return 0;
+ }
+ if (!is_now_zero) {
+ return 1;
+ }
switch (level) {
- case 3:
- bit = index & MASKNB; index >>= NB;
- if (!ZAP_GO_DOWN(bits + LEVEL2 + index*NUM_64b, bit)) return 1;
- /* no break */
- case 2:
- bit = index & MASKNB; index >>= NB;
- if (!ZAP_GO_DOWN(bits + LEVEL1 + index*NUM_64b, bit)) return 1;
- /* no break */
- case 1:
- bit = index & MASKNB; index >>= NB;
- if (!ZAP_GO_DOWN(bits + LEVEL0 + index*NUM_64b, bit)) return 1;
- /* no break */
- case 0:
- ZAP_SIMPLE(bits, index & MASKNB);
+ case 3:
+ bit = index & MASKNB;
+ index >>= NB;
+ if (!ZAP_GO_DOWN(bits + LEVEL2 + index * NUM_64b, bit)) {
return 1;
- default: abort();
+ }
+ /* no break */
+ case 2:
+ bit = index & MASKNB;
+ index >>= NB;
+ if (!ZAP_GO_DOWN(bits + LEVEL1 + index * NUM_64b, bit)) {
+ return 1;
+ }
+ /* no break */
+ case 1:
+ bit = index & MASKNB;
+ index >>= NB;
+ if (!ZAP_GO_DOWN(bits + LEVEL0 + index * NUM_64b, bit)) {
+ return 1;
+ }
+ /* no break */
+ case 0:
+ ZAP_SIMPLE(bits, index & MASKNB);
+ return 1;
+ default:
+ MALLOC_FATAL_ERROR(level, "invalid bitarray level");
}
}
// Note in the following macro that "words" and "base" are variables being written
-#define ADJUST_OFFSET_FOR_FFS(words, base, current_level) { \
-words += (1 << (NB * current_level)) * NUM_64b; \
-base = (base << NB) + FFS(words + base*NUM_64b) - 1; \
-}
+#define ADJUST_OFFSET_FOR_FFS(words, base, current_level) \
+ { \
+ words += (1 << (NB * current_level)) * NUM_64b; \
+ base = (base << NB) + FFS(words + base * NUM_64b) - 1; \
+ }
// Note in the following macro that "words" and "base" are variables being written
-#define ADJUST_OFFSET_FOR_FFS_ACROSS_SUMMARIES(words, base, level) {\
-switch (level) { \
-case 4: \
-ADJUST_OFFSET_FOR_FFS(words, base, 0); \
-ADJUST_OFFSET_FOR_FFS(words, base, 1); \
-ADJUST_OFFSET_FOR_FFS(words, base, 2); \
-break; \
-case 3: \
-ADJUST_OFFSET_FOR_FFS(words, base, 0); \
-ADJUST_OFFSET_FOR_FFS(words, base, 1); \
-break; \
-case 2: \
-ADJUST_OFFSET_FOR_FFS(words, base, 0); \
-break; \
-case 1: \
-break; \
-default: abort(); \
-} \
-}
+#define ADJUST_OFFSET_FOR_FFS_ACROSS_SUMMARIES(words, base, level) \
+ { \
+ switch (level) { \
+ case 4: \
+ ADJUST_OFFSET_FOR_FFS(words, base, 0); \
+ ADJUST_OFFSET_FOR_FFS(words, base, 1); \
+ ADJUST_OFFSET_FOR_FFS(words, base, 2); \
+ break; \
+ case 3: \
+ ADJUST_OFFSET_FOR_FFS(words, base, 0); \
+ ADJUST_OFFSET_FOR_FFS(words, base, 1); \
+ break; \
+ case 2: \
+ ADJUST_OFFSET_FOR_FFS(words, base, 0); \
+ break; \
+ case 1: \
+ break; \
+ default: \
+ MALLOC_FATAL_ERROR(level, "invalid bitarray level"); \
+ } \
+ }
// Note in the following macro that "ix" and "bit" are variables being written
-#define ZAP_SUMMARIES(bits, ix, level) {\
-unsigned bit; \
-switch (level) { \
-case 3: \
-bit = ix & MASKNB; ix >>= NB; \
-if (!ZAP_GO_DOWN(bits + LEVEL2 + ix*NUM_64b, bit)) break; \
-case 2: \
-bit = ix & MASKNB; ix >>= NB; \
-if (!ZAP_GO_DOWN(bits + LEVEL1 + ix*NUM_64b, bit)) break; \
-case 1: \
-bit = ix & MASKNB; ix >>= NB; \
-if (!ZAP_GO_DOWN(bits + LEVEL0 + ix*NUM_64b, bit)) break; \
-case 0: \
-ZAP_SIMPLE(bits, ix & MASKNB); \
-break; \
-default: abort(); \
-} \
-}
-
-index_t bitarray_first_set(const bitarray_t bits, unsigned log_size) {
+#define ZAP_SUMMARIES(bits, ix, level) \
+ { \
+ unsigned bit; \
+ switch (level) { \
+ case 3: \
+ bit = ix & MASKNB; \
+ ix >>= NB; \
+ if (!ZAP_GO_DOWN(bits + LEVEL2 + ix * NUM_64b, bit)) { \
+ break; \
+ } \
+ case 2: \
+ bit = ix & MASKNB; \
+ ix >>= NB; \
+ if (!ZAP_GO_DOWN(bits + LEVEL1 + ix * NUM_64b, bit)) { \
+ break; \
+ } \
+ case 1: \
+ bit = ix & MASKNB; \
+ ix >>= NB; \
+ if (!ZAP_GO_DOWN(bits + LEVEL0 + ix * NUM_64b, bit)) { \
+ break; \
+ } \
+ case 0: \
+ ZAP_SIMPLE(bits, ix &MASKNB); \
+ break; \
+ default: \
+ MALLOC_FATAL_ERROR(level, "invalid bitarray level"); \
+ } \
+ }
+
+index_t
+bitarray_first_set(const bitarray_t bits, unsigned log_size)
+{
// return 0 if none set
assert(log_size <= MAX_LEVEL * NB);
- uint64_t *words = bits;
- unsigned bit = FFS(words);
- if (log_size <= NB) return bit;
- if (!bit) return 0;
- unsigned level = (log_size - 1) / NB;
- index_t base = bit - 1; // offset, in number of uin64_t words
+ uint64_t *words = bits;
+ unsigned bit = FFS(words);
+ if (log_size <= NB) {
+ return bit;
+ }
+ if (!bit) {
+ return 0;
+ }
+ unsigned level = (log_size - 1) / NB;
+ index_t base = bit - 1; // offset, in number of uin64_t words
ADJUST_OFFSET_FOR_FFS_ACROSS_SUMMARIES(words, base, level);
- words += (1 << (NB * (level-1))) * NUM_64b;
- base = (base << NB) + FFS(words + base*NUM_64b) - 1;
- return base+1; //+1 because bit N is encoded as N+1
-}
-
-bool bitarray_zap_first_set(bitarray_t bits, unsigned log_size, index_t *index) {
- assert(log_size <= MAX_LEVEL * NB);
- uint64_t *words = bits;
- index_t ix = FFS(words);
- if (!ix) return 0;
- unsigned level = (log_size - 1) / NB;
- if (! level) {
+ words += (1 << (NB * (level - 1))) * NUM_64b;
+ base = (base << NB) + FFS(words + base * NUM_64b) - 1;
+ return base + 1; //+1 because bit N is encoded as N+1
+}
+
+bool
+bitarray_zap_first_set(bitarray_t bits, unsigned log_size, index_t *index)
+{
+ assert(log_size <= MAX_LEVEL * NB);
+ uint64_t *words = bits;
+ index_t ix = FFS(words);
+ if (!ix) {
+ return 0;
+ }
+ unsigned level = (log_size - 1) / NB;
+ if (!level) {
ix--;
*index = ix;
ZAP_SIMPLE(bits, ix);
return 1;
}
- index_t base = ix - 1; // offset, in number of uin64_t words
+ index_t base = ix - 1; // offset, in number of uin64_t words
ADJUST_OFFSET_FOR_FFS_ACROSS_SUMMARIES(words, base, level);
- words += (1 << (NB * (level-1))) * NUM_64b;
- base = (base << NB) + FFS(words + base*NUM_64b) - 1;
+ words += (1 << (NB * (level - 1))) * NUM_64b;
+ base = (base << NB) + FFS(words + base * NUM_64b) - 1;
ix = base;
*index = ix;
assert(ix < (1 << log_size));
level--;
- bool is_now_zero;
- unsigned bit;
- bit = ix & MASKNB; ix >>= NB;
- if (!ZAP_CHANGED_GO_DOWN(bits + levels_num_words[level] + ix*NUM_64b, bit, &is_now_zero)) return 1;
- if (!is_now_zero) return 1;
+ bool is_now_zero;
+ unsigned bit;
+ bit = ix & MASKNB;
+ ix >>= NB;
+ if (!ZAP_CHANGED_GO_DOWN(bits + levels_num_words[level] + ix * NUM_64b, bit, &is_now_zero)) {
+ return 1;
+ }
+ if (!is_now_zero) {
+ return 1;
+ }
ZAP_SUMMARIES(bits, ix, level);
return 1;
}
-static unsigned FFS_and_zap_word(uint64_t *words, unsigned max, index_t *indices, index_t to_be_added) {
+static unsigned
+FFS_and_zap_word(uint64_t *words, unsigned max, index_t *indices, index_t to_be_added)
+{
// returns the number of bits zapped
- unsigned zapped = 0;
+ unsigned zapped = 0;
for (unsigned w = 0; w < NUM_64b; w++) {
- uint64_t word = words[w];
- if (!word) continue;
+ uint64_t word = words[w];
+ if (!word) {
+ continue;
+ }
while (1) {
- unsigned f = __ffsll(word);
+ unsigned f = __ffsll(word);
assert(f);
f--;
// printf("%d ", f);
indices[zapped++] = f + (w << 6) + to_be_added;
word = BIT_ZAP(word, f);
- if (!word) break;
- if (zapped >= max) break;
+ if (!word) {
+ break;
+ }
+ if (zapped >= max) {
+ break;
+ }
}
words[w] = word;
// printf("word=%lld \n", word);
- if (zapped >= max) break;
+ if (zapped >= max) {
+ break;
+ }
}
return zapped;
}
-unsigned bitarray_zap_first_set_multiple(bitarray_t bits, unsigned log_size, unsigned max, index_t *indices) {
- assert(log_size <= MAX_LEVEL * NB);
- if (log_size <= NB) return FFS_and_zap_word(bits, max, indices, 0);
- unsigned zapped = 0;
- unsigned level = (log_size - 1) / NB;
+unsigned
+bitarray_zap_first_set_multiple(bitarray_t bits, unsigned log_size, unsigned max, index_t *indices)
+{
+ assert(log_size <= MAX_LEVEL * NB);
+ if (log_size <= NB) {
+ return FFS_and_zap_word(bits, max, indices, 0);
+ }
+ unsigned zapped = 0;
+ unsigned level = (log_size - 1) / NB;
while (zapped < max) {
- /* the lines in loop could be written just as:
- // if (! bitarray_zap_first_set(bits, log_size, indices + zapped)) break;
- // zapped++;
- but the code is faster because it wont go up and down in the summaries */
- uint64_t *words = bits;
- index_t ix = FFS(words);
- if (!ix) return zapped; // if the top level summary is 0, no bit is set
- index_t base = ix - 1; // offset, in number of uin64_t words
+ /*
+ * the lines in loop could be written just as:
+ * if (! bitarray_zap_first_set(bits, log_size, indices + zapped)) break;
+ * zapped++;
+ * but the code is faster because it wont go up and down in the summaries
+ */
+ uint64_t *words = bits;
+ index_t ix = FFS(words);
+ if (!ix) {
+ return zapped; // if the top level summary is 0, no bit is set
+ }
+ index_t base = ix - 1; // offset, in number of uin64_t words
ADJUST_OFFSET_FOR_FFS_ACROSS_SUMMARIES(words, base, level);
- words += (1 << (NB * (level-1))) * NUM_64b; // the beginning of the non-summarized bitarray
- uint64_t *word = words + base*NUM_64b; // the first non-zero word
+ words += (1 << (NB * (level - 1))) * NUM_64b; // the beginning of the non-summarized bitarray
+ uint64_t *word = words + base * NUM_64b; // the first non-zero word
ix = base;
// the idea here is that we zap a whole bunch of bits at once
- unsigned z = FFS_and_zap_word(word, max - zapped, indices + zapped, base << NB);
+ unsigned z = FFS_and_zap_word(word, max - zapped, indices + zapped, base << NB);
assert(z);
zapped += z;
if ((zapped < max) /* entire word was zapped */ || all_zeros(word) /* partial zap, a priori */) {
// adjust summaries to reflect all zeros in the bitarray
- ZAP_SUMMARIES(bits, ix, level-1);
+ ZAP_SUMMARIES(bits, ix, level - 1);
}
}
return zapped;
@@ -450,14 +605,14 @@
/******************************** Test and debug utilities ***************************/
static void print_ones(const uint64_t *bits, unsigned num_big_words) {
- unsigned base = 0;
- unsigned num = num_big_words * NUM_64b;
+ unsigned base = 0;
+ unsigned num = num_big_words * NUM_64b;
// printf("In print_ones; num=%d, num_big=%d \n", num, num_big_words);
while (num--) {
- uint64_t word = *(bits++);
+ uint64_t word = *(bits++);
if (word) {
for (unsigned bit = 0; bit < 64; bit++) {
- if (word & (1ULL << bit)) printf("%d ", base + bit);
+ if (word & (1ULL << bit)) { printf("%d ", base + bit); }
}
}
base += 64;
@@ -467,18 +622,18 @@
void bitarray_print(bitarray_t bits, unsigned log_size) {
assert(log_size <= MAX_LEVEL * NB);
printf("bitarray %p log_size=%d\n", bits, log_size);
- if (log_size > 4*NB) {
+ if (log_size > 4 * NB) {
printf("Level 4: "); print_ones(bits, 1); printf("\n");
printf("Level 3: "); print_ones(bits + LEVEL0, 1 << NB); printf("\n");
printf("Level 2: "); print_ones(bits + LEVEL1, 1 << NB); printf("\n");
printf("Level 1: "); print_ones(bits + LEVEL2, 1 << NB); printf("\n");
printf("Level 0: "); print_ones(bits + LEVEL3, 1 << (log_size - NB)); printf("\n");
- } else if (log_size > 3*NB) {
+ } else if (log_size > 3 * NB) {
printf("Level 3: "); print_ones(bits, 1); printf("\n");
printf("Level 2: "); print_ones(bits + LEVEL0, 1 << NB); printf("\n");
printf("Level 1: "); print_ones(bits + LEVEL1, 1 << NB); printf("\n");
printf("Level 0: "); print_ones(bits + LEVEL2, 1 << (log_size - NB)); printf("\n");
- } else if (log_size > 2*NB) {
+ } else if (log_size > 2 * NB) {
printf("Level 2: "); print_ones(bits, 1); printf("\n");
printf("Level 1: "); print_ones(bits + LEVEL0, 1 << NB); printf("\n");
printf("Level 0: "); print_ones(bits + LEVEL1, 1 << (log_size - NB)); printf("\n");
@@ -493,14 +648,14 @@
bool compare_to_truth(bitarray_t bits, unsigned nbits, const bool *truth) {
uint64_t *start = bits;
if (nbits > NB) {
- unsigned level = (nbits - NB - 1) / NB;
+ unsigned level = (nbits - NB - 1) / NB;
start += levels_num_words[level];
}
- bool ok = 1;
+ bool ok = 1;
for (unsigned bit = 0; bit < (1 << nbits); bit++) {
- bool expected = truth[bit];
- uint64_t word = start[bit >> 6];
- bool actual = (word >> (bit & 63)) & 1;
+ bool expected = truth[bit];
+ uint64_t word = start[bit >> 6];
+ bool actual = (word >> (bit & 63)) & 1;
if (actual != expected) {
printf("*** # for bit %d, expected=%d actual=%d\n", bit, expected, actual);
ok = 0;
@@ -511,7 +666,7 @@
unsigned first_set_in_truth(const bool *truth, unsigned log_size) {
for (unsigned bit = 0; bit < (1 << log_size); bit++) {
- if (truth[bit]) return bit+1;
+ if (truth[bit]) { return bit + 1; }
}
return 0;
}
@@ -519,7 +674,7 @@
void truth_print(const bool *truth, unsigned log_size) {
printf("Truth: ");
for (unsigned bit = 0; bit < (1 << log_size); bit++) {
- if (truth[bit]) printf("%d ", bit);
+ if (truth[bit]) { printf("%d ", bit); }
}
printf("\n");
}