diff options
author | Ivan Komarov <Ivan.Komarov@dfyz.info> | 2022-02-10 16:46:49 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:46:49 +0300 |
commit | 59aca5c5180c31691884667783dc966eb99d743a (patch) | |
tree | 49e222ea1c5804306084bb3ae065bb702625360f /library/cpp/containers/bitseq | |
parent | 4de97ab2fe437cbe83e4c63234e809ddd5ac34f2 (diff) | |
download | ydb-59aca5c5180c31691884667783dc966eb99d743a.tar.gz |
Restoring authorship annotation for Ivan Komarov <Ivan.Komarov@dfyz.info>. Commit 2 of 2.
Diffstat (limited to 'library/cpp/containers/bitseq')
-rw-r--r-- | library/cpp/containers/bitseq/bitvector.h | 14 | ||||
-rw-r--r-- | library/cpp/containers/bitseq/bitvector_ut.cpp | 40 | ||||
-rw-r--r-- | library/cpp/containers/bitseq/readonly_bitvector.cpp | 2 | ||||
-rw-r--r-- | library/cpp/containers/bitseq/readonly_bitvector.h | 136 | ||||
-rw-r--r-- | library/cpp/containers/bitseq/traits.h | 40 | ||||
-rw-r--r-- | library/cpp/containers/bitseq/ya.make | 2 |
6 files changed, 117 insertions, 117 deletions
diff --git a/library/cpp/containers/bitseq/bitvector.h b/library/cpp/containers/bitseq/bitvector.h index 5c6495d1bd..3f8fd81ee5 100644 --- a/library/cpp/containers/bitseq/bitvector.h +++ b/library/cpp/containers/bitseq/bitvector.h @@ -8,16 +8,16 @@ #include <util/ysaveload.h> template <typename T> -class TReadonlyBitVector; - -template <typename T> +class TReadonlyBitVector; + +template <typename T> class TBitVector { public: using TWord = T; using TTraits = TBitSeqTraits<TWord>; private: - friend class TReadonlyBitVector<T>; + friend class TReadonlyBitVector<T>; ui64 Size_; TVector<TWord> Data_; @@ -61,7 +61,7 @@ public: } bool Test(ui64 pos) const { - return TTraits::Test(Data(), pos, Size_); + return TTraits::Test(Data(), pos, Size_); } void Reset(ui64 pos) { @@ -70,7 +70,7 @@ public: } TWord Get(ui64 pos, ui8 width, TWord mask) const { - return TTraits::Get(Data(), pos, width, mask, Size_); + return TTraits::Get(Data(), pos, width, mask, Size_); } TWord Get(ui64 pos, ui8 width) const { @@ -127,7 +127,7 @@ public: } const TWord* Data() const { - return Data_.data(); + return Data_.data(); } void Save(IOutputStream* out) const { diff --git a/library/cpp/containers/bitseq/bitvector_ut.cpp b/library/cpp/containers/bitseq/bitvector_ut.cpp index 3ba2791354..6137adab1e 100644 --- a/library/cpp/containers/bitseq/bitvector_ut.cpp +++ b/library/cpp/containers/bitseq/bitvector_ut.cpp @@ -1,11 +1,11 @@ #include "bitvector.h" -#include "readonly_bitvector.h" +#include "readonly_bitvector.h" #include <library/cpp/testing/unittest/registar.h> -#include <util/memory/blob.h> -#include <util/stream/buffer.h> - +#include <util/memory/blob.h> +#include <util/stream/buffer.h> + Y_UNIT_TEST_SUITE(TBitVectorTest) { Y_UNIT_TEST(TestEmpty) { TBitVector<ui64> v64; @@ -66,21 +66,21 @@ Y_UNIT_TEST_SUITE(TBitVectorTest) { v.Set(10 * 32, 100500, 32); UNIT_ASSERT_EQUAL(v.Get(10 * 32, 32), 100500); } - + Y_UNIT_TEST(TestReadonlyVector) { - TBitVector<ui64> v(100); - for (ui64 i = 0; i < v.Size(); ++i) { - if (i % 3 == 0) { - v.Set(i); - } - } - TBufferStream bs; - TReadonlyBitVector<ui64>::SaveForReadonlyAccess(&bs, v); - const auto blob = TBlob::FromBuffer(bs.Buffer()); - TReadonlyBitVector<ui64> rv; - rv.LoadFromBlob(blob); - for (ui64 i = 0; i < rv.Size(); ++i) { - UNIT_ASSERT_VALUES_EQUAL(rv.Test(i), i % 3 == 0); - } - } + TBitVector<ui64> v(100); + for (ui64 i = 0; i < v.Size(); ++i) { + if (i % 3 == 0) { + v.Set(i); + } + } + TBufferStream bs; + TReadonlyBitVector<ui64>::SaveForReadonlyAccess(&bs, v); + const auto blob = TBlob::FromBuffer(bs.Buffer()); + TReadonlyBitVector<ui64> rv; + rv.LoadFromBlob(blob); + for (ui64 i = 0; i < rv.Size(); ++i) { + UNIT_ASSERT_VALUES_EQUAL(rv.Test(i), i % 3 == 0); + } + } } diff --git a/library/cpp/containers/bitseq/readonly_bitvector.cpp b/library/cpp/containers/bitseq/readonly_bitvector.cpp index e38b381838..891aa7cde2 100644 --- a/library/cpp/containers/bitseq/readonly_bitvector.cpp +++ b/library/cpp/containers/bitseq/readonly_bitvector.cpp @@ -1 +1 @@ -#include "readonly_bitvector.h" +#include "readonly_bitvector.h" diff --git a/library/cpp/containers/bitseq/readonly_bitvector.h b/library/cpp/containers/bitseq/readonly_bitvector.h index bed2cfc061..8612739c3f 100644 --- a/library/cpp/containers/bitseq/readonly_bitvector.h +++ b/library/cpp/containers/bitseq/readonly_bitvector.h @@ -1,76 +1,76 @@ -#pragma once - -#include "bitvector.h" -#include "traits.h" - -#include <util/memory/blob.h> - -#include <cstring> - -template <typename T> -class TReadonlyBitVector { -public: - using TWord = T; - using TTraits = TBitSeqTraits<TWord>; - - TReadonlyBitVector() - : Size_() - , Data_() +#pragma once + +#include "bitvector.h" +#include "traits.h" + +#include <util/memory/blob.h> + +#include <cstring> + +template <typename T> +class TReadonlyBitVector { +public: + using TWord = T; + using TTraits = TBitSeqTraits<TWord>; + + TReadonlyBitVector() + : Size_() + , Data_() { } - + explicit TReadonlyBitVector(const TBitVector<T>& vector) : Size_(vector.Size_) , Data_(vector.Data_.data()) { } - bool Test(ui64 pos) const { - return TTraits::Test(Data_, pos, Size_); - } - - TWord Get(ui64 pos, ui8 width, TWord mask) const { - return TTraits::Get(Data_, pos, width, mask, Size_); - } - - TWord Get(ui64 pos, ui8 width) const { - return Get(pos, width, TTraits::ElemMask(width)); - } - - ui64 Size() const { - return Size_; - } - - const T* Data() const { - return Data_; - } - - static void SaveForReadonlyAccess(IOutputStream* out, const TBitVector<T>& bv) { - ::Save(out, bv.Size_); - ::Save(out, static_cast<ui64>(bv.Data_.size())); - ::SavePodArray(out, bv.Data_.data(), bv.Data_.size()); - } - - virtual TBlob LoadFromBlob(const TBlob& blob) { - size_t read = 0; - auto cursor = [&]() { return blob.AsUnsignedCharPtr() + read; }; - auto readToPtr = [&](auto* ptr) { - memcpy(ptr, cursor(), sizeof(*ptr)); - read += sizeof(*ptr); - }; - - readToPtr(&Size_); - - ui64 wordCount{}; - readToPtr(&wordCount); - - Data_ = reinterpret_cast<const T*>(cursor()); - read += wordCount * sizeof(T); - - return blob.SubBlob(read, blob.Size()); - } - -private: - ui64 Size_; - const T* Data_; -}; + bool Test(ui64 pos) const { + return TTraits::Test(Data_, pos, Size_); + } + + TWord Get(ui64 pos, ui8 width, TWord mask) const { + return TTraits::Get(Data_, pos, width, mask, Size_); + } + + TWord Get(ui64 pos, ui8 width) const { + return Get(pos, width, TTraits::ElemMask(width)); + } + + ui64 Size() const { + return Size_; + } + + const T* Data() const { + return Data_; + } + + static void SaveForReadonlyAccess(IOutputStream* out, const TBitVector<T>& bv) { + ::Save(out, bv.Size_); + ::Save(out, static_cast<ui64>(bv.Data_.size())); + ::SavePodArray(out, bv.Data_.data(), bv.Data_.size()); + } + + virtual TBlob LoadFromBlob(const TBlob& blob) { + size_t read = 0; + auto cursor = [&]() { return blob.AsUnsignedCharPtr() + read; }; + auto readToPtr = [&](auto* ptr) { + memcpy(ptr, cursor(), sizeof(*ptr)); + read += sizeof(*ptr); + }; + + readToPtr(&Size_); + + ui64 wordCount{}; + readToPtr(&wordCount); + + Data_ = reinterpret_cast<const T*>(cursor()); + read += wordCount * sizeof(T); + + return blob.SubBlob(read, blob.Size()); + } + +private: + ui64 Size_; + const T* Data_; +}; diff --git a/library/cpp/containers/bitseq/traits.h b/library/cpp/containers/bitseq/traits.h index 99047363de..2330b1b4f2 100644 --- a/library/cpp/containers/bitseq/traits.h +++ b/library/cpp/containers/bitseq/traits.h @@ -2,7 +2,7 @@ #include <util/generic/bitops.h> #include <util/generic/typetraits.h> -#include <util/system/yassert.h> +#include <util/system/yassert.h> template <typename TWord> struct TBitSeqTraits { @@ -25,25 +25,25 @@ struct TBitSeqTraits { return (bits + NumBits - 1) >> DivShift; } - static bool Test(const TWord* data, ui64 pos, ui64 size) { - Y_ASSERT(pos < size); - return data[pos >> DivShift] & BitMask(pos & ModMask); - } - - static TWord Get(const TWord* data, ui64 pos, ui8 width, TWord mask, ui64 size) { - if (!width) - return 0; - Y_ASSERT((pos + width) <= size); - size_t word = pos >> DivShift; - TWord shift1 = pos & ModMask; - TWord shift2 = NumBits - shift1; - TWord res = data[word] >> shift1 & mask; - if (shift2 < width) { - res |= data[word + 1] << shift2 & mask; - } - return res; - } - + static bool Test(const TWord* data, ui64 pos, ui64 size) { + Y_ASSERT(pos < size); + return data[pos >> DivShift] & BitMask(pos & ModMask); + } + + static TWord Get(const TWord* data, ui64 pos, ui8 width, TWord mask, ui64 size) { + if (!width) + return 0; + Y_ASSERT((pos + width) <= size); + size_t word = pos >> DivShift; + TWord shift1 = pos & ModMask; + TWord shift2 = NumBits - shift1; + TWord res = data[word] >> shift1 & mask; + if (shift2 < width) { + res |= data[word + 1] << shift2 & mask; + } + return res; + } + static_assert(std::is_unsigned<TWord>::value, "Expected std::is_unsigned<T>::value."); static_assert((NumBits & (NumBits - 1)) == 0, "NumBits should be a power of 2."); }; diff --git a/library/cpp/containers/bitseq/ya.make b/library/cpp/containers/bitseq/ya.make index c69d13b721..7090956c55 100644 --- a/library/cpp/containers/bitseq/ya.make +++ b/library/cpp/containers/bitseq/ya.make @@ -9,7 +9,7 @@ PEERDIR( SRCS( bitvector.cpp - readonly_bitvector.cpp + readonly_bitvector.cpp ) END() |