#include "common/Formatter.h"
#include "include/assert.h"
#include "include/encoding.h"
+#include <utility>
namespace ceph {
// must be power of 2
BOOST_STATIC_ASSERT((_bit_count != 0) && !(_bit_count & (_bit_count - 1)));
BOOST_STATIC_ASSERT(_bit_count <= BITS_PER_BYTE);
-public:
- static const uint32_t BLOCK_SIZE;
- class ConstReference {
+ template <typename DataIterator>
+ class ReferenceImpl {
+ protected:
+ DataIterator m_data_iterator;
+ uint64_t m_shift;
+
+ ReferenceImpl(const DataIterator& data_iterator, uint64_t shift)
+ : m_data_iterator(data_iterator), m_shift(shift) {
+ }
+ ReferenceImpl(DataIterator&& data_iterator, uint64_t shift)
+ : m_data_iterator(std::move(data_iterator)), m_shift(shift) {
+ }
+
public:
- operator uint8_t() const;
+ inline operator uint8_t() const {
+ return (*m_data_iterator >> m_shift) & MASK;
+ }
+ };
+
+public:
+
+ class ConstReference : public ReferenceImpl<bufferlist::const_iterator> {
private:
friend class BitVector;
- const BitVector &m_bit_vector;
- uint64_t m_offset;
- ConstReference(const BitVector &bit_vector, uint64_t offset);
+ ConstReference(const bufferlist::const_iterator& data_iterator,
+ uint64_t shift)
+ : ReferenceImpl<bufferlist::const_iterator>(data_iterator, shift) {
+ }
+ ConstReference(bufferlist::const_iterator&& data_iterator, uint64_t shift)
+ : ReferenceImpl<bufferlist::const_iterator>(std::move(data_iterator),
+ shift) {
+ }
};
- class Reference {
+ class Reference : public ReferenceImpl<bufferlist::iterator> {
public:
- operator uint8_t() const;
Reference& operator=(uint8_t v);
+
+ private:
+ friend class BitVector;
+
+ Reference(const bufferlist::iterator& data_iterator, uint64_t shift)
+ : ReferenceImpl<bufferlist::iterator>(data_iterator, shift) {
+ }
+ Reference(bufferlist::iterator&& data_iterator, uint64_t shift)
+ : ReferenceImpl<bufferlist::iterator>(std::move(data_iterator), shift) {
+ }
+ };
+
+public:
+ template <typename BitVectorT, typename DataIterator>
+ class IteratorImpl {
private:
friend class BitVector;
- BitVector &m_bit_vector;
- uint64_t m_offset;
- Reference(BitVector &bit_vector, uint64_t offset);
+ uint64_t m_offset = 0;
+ BitVectorT *m_bit_vector;
+
+ // cached derived values
+ uint64_t m_index = 0;
+ uint64_t m_shift = 0;
+ DataIterator m_data_iterator;
+
+ IteratorImpl(BitVectorT *bit_vector, uint64_t offset)
+ : m_bit_vector(bit_vector),
+ m_data_iterator(bit_vector->m_data.begin()) {
+ *this += offset;
+ }
+
+ public:
+ inline IteratorImpl& operator++() {
+ ++m_offset;
+
+ uint64_t index;
+ compute_index(m_offset, &index, &m_shift);
+
+ assert(index == m_index || index == m_index + 1);
+ if (index > m_index) {
+ m_index = index;
+ ++m_data_iterator;
+ }
+ return *this;
+ }
+ inline IteratorImpl& operator+=(uint64_t offset) {
+ m_offset += offset;
+ compute_index(m_offset, &m_index, &m_shift);
+ if (m_offset < m_bit_vector->size()) {
+ m_data_iterator.seek(m_index);
+ } else {
+ m_data_iterator = m_bit_vector->m_data.end();
+ }
+ return *this;
+ }
+
+ inline IteratorImpl operator++(int) {
+ IteratorImpl iterator_impl(*this);
+ ++iterator_impl;
+ return iterator_impl;
+ }
+ inline IteratorImpl operator+(uint64_t offset) {
+ IteratorImpl iterator_impl(*this);
+ iterator_impl += offset;
+ return iterator_impl;
+ }
+
+ inline bool operator==(const IteratorImpl& rhs) const {
+ return (m_offset == rhs.m_offset && m_bit_vector == rhs.m_bit_vector);
+ }
+ inline bool operator!=(const IteratorImpl& rhs) const {
+ return (m_offset != rhs.m_offset || m_bit_vector != rhs.m_bit_vector);
+ }
+
+ inline ConstReference operator*() const {
+ return ConstReference(m_data_iterator, m_shift);
+ }
+ inline Reference operator*() {
+ return Reference(m_data_iterator, m_shift);
+ }
};
+ typedef IteratorImpl<const BitVector,
+ bufferlist::const_iterator> ConstIterator;
+ typedef IteratorImpl<BitVector, bufferlist::iterator> Iterator;
+
+ static const uint32_t BLOCK_SIZE;
static const uint8_t BIT_COUNT = _bit_count;
BitVector();
+ inline ConstIterator begin() const {
+ return ConstIterator(this, 0);
+ }
+ inline ConstIterator end() const {
+ return ConstIterator(this, m_size);
+ }
+ inline Iterator begin() {
+ return Iterator(this, 0);
+ }
+ inline Iterator end() {
+ return Iterator(this, m_size);
+ }
+
void set_crc_enabled(bool enabled) {
m_crc_enabled = enabled;
}
template <uint8_t _b>
typename BitVector<_b>::Reference BitVector<_b>::operator[](uint64_t offset) {
- return Reference(*this, offset);
-}
-
-template <uint8_t _b>
-typename BitVector<_b>::ConstReference BitVector<_b>::operator[](uint64_t offset) const {
- return ConstReference(*this, offset);
-}
-
-template <uint8_t _b>
-BitVector<_b>::ConstReference::ConstReference(const BitVector<_b> &bit_vector,
- uint64_t offset)
- : m_bit_vector(bit_vector), m_offset(offset)
-{
-}
-
-template <uint8_t _b>
-BitVector<_b>::ConstReference::operator uint8_t() const {
uint64_t index;
uint64_t shift;
- this->m_bit_vector.compute_index(this->m_offset, &index, &shift);
+ compute_index(offset, &index, &shift);
- return (this->m_bit_vector.m_data[index] >> shift) & MASK;
+ bufferlist::iterator data_iterator(m_data.begin());
+ data_iterator.seek(index);
+ return Reference(std::move(data_iterator), shift);
}
template <uint8_t _b>
-BitVector<_b>::Reference::Reference(BitVector<_b> &bit_vector, uint64_t offset)
- : m_bit_vector(bit_vector), m_offset(offset)
-{
-}
-
-template <uint8_t _b>
-BitVector<_b>::Reference::operator uint8_t() const {
+typename BitVector<_b>::ConstReference BitVector<_b>::operator[](uint64_t offset) const {
uint64_t index;
uint64_t shift;
- this->m_bit_vector.compute_index(this->m_offset, &index, &shift);
+ compute_index(offset, &index, &shift);
- return (this->m_bit_vector.m_data[index] >> shift) & MASK;
+ bufferlist::const_iterator data_iterator(m_data.begin());
+ data_iterator.seek(index);
+ return ConstReference(std::move(data_iterator), shift);
}
template <uint8_t _b>
typename BitVector<_b>::Reference& BitVector<_b>::Reference::operator=(uint8_t v) {
- uint64_t index;
- uint64_t shift;
- this->m_bit_vector.compute_index(this->m_offset, &index, &shift);
-
- uint8_t mask = MASK << shift;
- char packed_value = (this->m_bit_vector.m_data[index] & ~mask) |
- ((v << shift) & mask);
- this->m_bit_vector.m_data.copy_in(index, 1, &packed_value);
+ uint8_t mask = MASK << this->m_shift;
+ char packed_value = (*this->m_data_iterator & ~mask) |
+ ((v << this->m_shift) & mask);
+ bufferlist::iterator it(this->m_data_iterator);
+ it.copy_in(1, &packed_value, true);
return *this;
}