diff options
author | Yuri Gorshenin <y@maps.me> | 2016-01-19 13:19:45 +0300 |
---|---|---|
committer | Sergey Yershov <yershov@corp.mail.ru> | 2016-03-23 16:03:44 +0300 |
commit | d9da3fe5185038949225bf520eb1c47176486d79 (patch) | |
tree | ede2481f6a0a51bdd7c513cf08aecb1a0e44d2fe /coding | |
parent | 1ee6af51dfa7334e729f4d42b503513ab0715fc9 (diff) |
[search] [coding] Added undefined state to a FixedBitsDDVector.
Diffstat (limited to 'coding')
-rw-r--r-- | coding/coding_tests/fixed_bits_ddvector_test.cpp | 11 | ||||
-rw-r--r-- | coding/fixed_bits_ddvector.hpp | 26 |
2 files changed, 29 insertions, 8 deletions
diff --git a/coding/coding_tests/fixed_bits_ddvector_test.cpp b/coding/coding_tests/fixed_bits_ddvector_test.cpp index 4919bf82ad..f50e11a06f 100644 --- a/coding/coding_tests/fixed_bits_ddvector_test.cpp +++ b/coding/coding_tests/fixed_bits_ddvector_test.cpp @@ -22,7 +22,7 @@ template <size_t Bits> void TestWithData(vector<uint32_t> const & lst) typename TVector::template Builder<TWriter> builder(writer); uint32_t optCount = 0; - uint32_t const optBound = (1 << Bits) - 1; + uint32_t const optBound = (1 << Bits) - 2; for (uint32_t v : lst) { @@ -40,8 +40,13 @@ template <size_t Bits> void TestWithData(vector<uint32_t> const & lst) auto const vec = TVector::Create(reader); size_t i = 0; - for (uint32_t v : lst) - TEST_EQUAL(vec->Get(i++), v, ()); + for (uint32_t actual : lst) + { + uint32_t expected; + TEST(vec->Get(i, expected), ()); + TEST_EQUAL(expected, actual, ()); + ++i; + } } } // namespace diff --git a/coding/fixed_bits_ddvector.hpp b/coding/fixed_bits_ddvector.hpp index f0a65b197a..c87a416335 100644 --- a/coding/fixed_bits_ddvector.hpp +++ b/coding/fixed_bits_ddvector.hpp @@ -16,7 +16,8 @@ /// 4 bytes to store vector's size /// Buffer of ceil(Size * Bits / 8) bytes, e.g. vector of Bits-sized elements. /// - values in range [0, (1 << Bits) - 2] stored as is -/// - value (1 << Bits) - 1 tells that actual value is stored in the exceptions table below. +/// - value (1 << Bits) - 2 tells that actual value is stored in the exceptions table below. +/// - value (1 << Bits) - 1 tells that the value is undefined. /// Buffer with exceptions table, e.g. vector of (index, value) pairs till the end of the reader, /// sorted by index parameter. /// Component is stored and used in host's endianness, without any conversions. @@ -33,6 +34,7 @@ class FixedBitsDDVector static_assert(is_unsigned<TSize>::value, ""); static_assert(is_unsigned<TValue>::value, ""); // 16 - is the maximum bits count to get all needed bits in random access within uint32_t. + static_assert(Bits > 0, ""); static_assert(Bits <= 16, ""); using TSelf = FixedBitsDDVector<Bits, TReader, TSize, TValue>; @@ -59,6 +61,8 @@ class FixedBitsDDVector } static TBlock constexpr kMask = (1 << Bits) - 1; + static TBlock constexpr kLargeValue = kMask - 1; + static TBlock constexpr kUndefined = kMask; TValue FindInVector(TSize index) const { @@ -88,7 +92,7 @@ public: size)); } - TValue Get(TSize index) const + bool Get(TSize index, TValue & value) const { ASSERT_LESS(index, m_size, ()); uint64_t const bitsOffset = index * Bits; @@ -101,7 +105,11 @@ public: TBlock v = ReadPrimitiveFromPos<TBlock>(m_bits, bytesOffset); v >>= (bitsOffset - bytesOffset * CHAR_BIT); v &= kMask; - return (v == kMask ? FindInVector(index) : v); + if (v == kUndefined) + return false; + + value = v < kLargeValue ? v : FindInVector(index); + return true; } template <class TWriter> class Builder @@ -147,9 +155,9 @@ public: void PushBack(TValue v) { - if (v >= kMask) + if (v >= kLargeValue) { - m_bits->WriteAtMost32Bits(kMask, Bits); + m_bits->WriteAtMost32Bits(kLargeValue, Bits); m_excepts.push_back({m_count, v}); } else @@ -161,6 +169,14 @@ public: ++m_count; } + // Pushes a special (undefined) value. + void PushBackUndefined() + { + m_bits->WriteAtMost32Bits(kUndefined, Bits); + ++m_optCount; + ++m_count; + } + /// @return (number of stored as-is elements, number of all elements) pair<TSize, TSize> GetCount() const { return make_pair(m_optCount, m_count); } }; |