From daa29f7d2b50bc4b44a108a0f91d45ce90fc16e5 Mon Sep 17 00:00:00 2001 From: Jason Dillaman Date: Fri, 13 Oct 2017 11:05:48 -0400 Subject: [PATCH] common/bit_vector: provide constant time iteration of underlying bufferlist Signed-off-by: Jason Dillaman --- src/common/bit_vector.hpp | 189 +++++++++++++++++++++-------- src/test/common/test_bit_vector.cc | 28 +++++ 2 files changed, 169 insertions(+), 48 deletions(-) diff --git a/src/common/bit_vector.hpp b/src/common/bit_vector.hpp index 6a6e6b7d03e7c..b010970b3213d 100644 --- a/src/common/bit_vector.hpp +++ b/src/common/bit_vector.hpp @@ -14,6 +14,7 @@ #include "common/Formatter.h" #include "include/assert.h" #include "include/encoding.h" +#include namespace ceph { @@ -28,36 +29,150 @@ private: // 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 + 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 { 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(data_iterator, shift) { + } + ConstReference(bufferlist::const_iterator&& data_iterator, uint64_t shift) + : ReferenceImpl(std::move(data_iterator), + shift) { + } }; - class Reference { + class Reference : public ReferenceImpl { public: - operator uint8_t() const; Reference& operator=(uint8_t v); + + private: + friend class BitVector; + + Reference(const bufferlist::iterator& data_iterator, uint64_t shift) + : ReferenceImpl(data_iterator, shift) { + } + Reference(bufferlist::iterator&& data_iterator, uint64_t shift) + : ReferenceImpl(std::move(data_iterator), shift) { + } + }; + +public: + template + 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 ConstIterator; + typedef IteratorImpl 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; } @@ -345,55 +460,33 @@ bool BitVector<_b>::operator==(const BitVector &b) const { template typename BitVector<_b>::Reference BitVector<_b>::operator[](uint64_t offset) { - return Reference(*this, offset); -} - -template -typename BitVector<_b>::ConstReference BitVector<_b>::operator[](uint64_t offset) const { - return ConstReference(*this, offset); -} - -template -BitVector<_b>::ConstReference::ConstReference(const BitVector<_b> &bit_vector, - uint64_t offset) - : m_bit_vector(bit_vector), m_offset(offset) -{ -} - -template -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 -BitVector<_b>::Reference::Reference(BitVector<_b> &bit_vector, uint64_t offset) - : m_bit_vector(bit_vector), m_offset(offset) -{ -} - -template -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 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; } diff --git a/src/test/common/test_bit_vector.cc b/src/test/common/test_bit_vector.cc index f5b0b26dc2530..a486bf46d07b2 100644 --- a/src/test/common/test_bit_vector.cc +++ b/src/test/common/test_bit_vector.cc @@ -248,3 +248,31 @@ TYPED_TEST(BitVectorTest, data_crc) { ASSERT_THROW(bit_vector2.decode_data(data_it, byte_offset), buffer::malformed_input); } + +TYPED_TEST(BitVectorTest, iterator) { + typename TestFixture::bit_vector_t bit_vector; + + uint64_t radix = 1 << bit_vector.BIT_COUNT; + uint64_t size = 25 * (1ULL << 20); + uint64_t offset = 0; + + // create fragmented in-memory bufferlist layout + uint64_t resize = 0; + while (resize < size) { + resize += 4096; + if (resize > size) { + resize = size; + } + bit_vector.resize(resize); + } + + for (auto it = bit_vector.begin(); it != bit_vector.end(); ++it, ++offset) { + *it = offset % radix; + } + + offset = 123; + auto end_it = bit_vector.begin() + (size - 1024); + for (auto it = bit_vector.begin() + offset; it != end_it; ++it, ++offset) { + ASSERT_EQ(offset % radix, *it); + } +} -- 2.39.5