Loading...
--- libmalloc/libmalloc-409.60.6/src/bitarray.c
+++ libmalloc/libmalloc-53.1.1/src/bitarray.c
@@ -28,15 +28,15 @@
// Copyright (c) 2010 Apple. All rights reserved.
//
-#include "internal.h"
+#include "bitarray.h"
+#define NDEBUG 1
+#include <assert.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,232 +44,171 @@
#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)
-{
- // returns 1 iff word changed
- uint64_t old = *word;
- uint64_t new = BIT_ZAP(old, bit);
- if (old == new) {
- return 0;
- }
+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;
*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
@@ -277,325 +216,231 @@
/******************************** 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)) {
+ 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);
return 1;
- }
- /* no break */
- case 2:
- bit = index & MASKNB;
- index >>= NB;
- if (!SET_GO_DOWN(bits + LEVEL1 + index * NUM_64b, bit)) {
+ default: abort();
+ }
+}
+
+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;
+ 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);
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;
- }
- 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);
- return 1;
- default:
- MALLOC_FATAL_ERROR(level, "invalid bitarray level");
+ default: abort();
}
}
// 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: \
- MALLOC_FATAL_ERROR(level, "invalid bitarray level"); \
- } \
- }
+#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(); \
+} \
+}
// 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: \
- MALLOC_FATAL_ERROR(level, "invalid bitarray level"); \
- } \
- }
-
-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: abort(); \
+} \
+}
+
+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;
@@ -605,14 +450,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;
@@ -622,18 +467,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");
@@ -648,14 +493,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;
@@ -666,7 +511,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;
}
@@ -674,7 +519,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");
}