#pragma once
#ifndef __AUTO_BITMAP__
#define __AUTO_BITMAP__
#include "AutoDefs.h"
#include "AutoRange.h"
namespace Auto {
class Bitmap : public Range {
private:
static inline const usword_t index(const usword_t bp) { return bp >> bits_per_word_log2; }
static inline const usword_t shift(const usword_t bp) { return bp & bits_mask; }
inline usword_t cursor_bp(const usword_t *cursor) const { return ((uintptr_t)cursor - (uintptr_t)address()) << bits_per_byte_log2; }
inline usword_t *end_cursor() const { return (usword_t *)Range::end(); }
public:
Bitmap() {}
Bitmap(usword_t n, void *bits) {
ASSERTION(!((uintptr_t)bits & mask(bytes_per_quad_log2)) && !(bytes_needed(n) & mask(bytes_per_quad_log2)));
set_range(bits, bytes_needed(n));
}
inline usword_t *bp_cursor(const usword_t bp) const {
return (usword_t *)displace(address(), (bp >> (bits_per_word_log2 - bytes_per_word_log2)) & ~mask(bytes_per_word_log2));
}
inline usword_t size_in_bits() const { return size() << bits_per_byte_log2; }
inline void initialize(usword_t n, void *bits) { set_range(bits, bytes_needed(n)); }
static inline const usword_t bytes_needed(usword_t n) { return partition2(n, bits_per_word_log2) << bytes_per_word_log2; }
inline usword_t bit(const usword_t bp) const { return (*bp_cursor(bp) >> shift(bp)) & 1; }
inline void set_bit(const usword_t bp) const {
usword_t *cursor = bp_cursor(bp);
*cursor |= 1L << shift(bp);
}
inline void set_bit_atomic(const usword_t bp) const {
usword_t *cursor = bp_cursor(bp);
__sync_or_and_fetch(cursor, 1L << shift(bp));
}
void set_bits_large(const usword_t bp, const usword_t n) const;
inline void set_bits(const usword_t bp, const usword_t n) const {
const usword_t sh = shift(bp);
if ((sh + n) > bits_per_word) {
set_bits_large(bp, n);
} else {
usword_t m = mask(n); *bp_cursor(bp) |= (m << sh); }
}
inline void clear_bit(const usword_t bp) const {
usword_t *cursor = bp_cursor(bp);
*cursor &= ~(1L << shift(bp));
}
void clear_bits_large(const usword_t bp, const usword_t n) const;
inline void clear_bits(const usword_t bp, const usword_t n) const {
const usword_t sh = shift(bp);
if ((sh + n) > bits_per_word) {
clear_bits_large(bp, n);
} else {
usword_t m = mask(n); *bp_cursor(bp) &= ~(m << sh); }
}
bool bits_are_clear_large(const usword_t bp, const usword_t n) const;
inline bool bits_are_clear(const usword_t bp, const usword_t n) const {
const usword_t sh = shift(bp);
if ((sh + n) > bits_per_word) {
return bits_are_clear_large(bp, n);
} else {
usword_t m = mask(n); return (*bp_cursor(bp) & (m << sh)) == 0; }
}
static inline usword_t *skip_all_zeros(usword_t *cursor, usword_t *end) {
usword_t *near_end = end - 4;
while (cursor < near_end) {
usword_t word0 = cursor[0];
usword_t word1 = cursor[1];
usword_t word2 = cursor[2];
usword_t word3 = cursor[3];
cursor += 4;
if (!is_all_zeros(word0)) { cursor -= 4; break; }
if (!is_all_zeros(word1)) { cursor -= 3; break; }
if (!is_all_zeros(word2)) { cursor -= 2; break; }
if (!is_all_zeros(word3)) { cursor -= 1; break; }
}
while (cursor < end) {
usword_t word = *cursor++;
if (!is_all_zeros(word)) { cursor--; break; }
}
return cursor;
}
static inline usword_t *skip_backward_all_zeros(usword_t *cursor, usword_t *first) {
usword_t *near_first = first + 3;
while (near_first <= cursor) {
usword_t word0 = cursor[0];
usword_t word1 = cursor[-1];
usword_t word2 = cursor[-2];
usword_t word3 = cursor[-3];
cursor -= 4;
if (!is_all_zeros(word0)) { cursor += 4; break; }
if (!is_all_zeros(word1)) { cursor += 3; break; }
if (!is_all_zeros(word2)) { cursor += 2; break; }
if (!is_all_zeros(word3)) { cursor += 1; break; }
}
while (first <= cursor) {
usword_t word = *cursor--;
if (!is_all_zeros(word)) { cursor++; break; }
}
return cursor;
}
usword_t count_set() const ;
usword_t previous_set(const usword_t bp) const ;
usword_t next_set(const usword_t bp) const;
};
};
#endif // __AUTO_BITMAP__