diff options
author | ironpeter <ironpeter@yandex-team.ru> | 2022-02-10 16:49:51 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:49:51 +0300 |
commit | ff97837ecc5972a00cb395483d8856566738375c (patch) | |
tree | b2e9b0b27c06242cc2390f3fe726bd2d40758c8f | |
parent | ec31dbabb2178819f10e1dec8f2ae9b2ba551ab1 (diff) | |
download | ydb-ff97837ecc5972a00cb395483d8856566738375c.tar.gz |
Restoring authorship annotation for <ironpeter@yandex-team.ru>. Commit 1 of 2.
26 files changed, 502 insertions, 502 deletions
diff --git a/library/cpp/balloc/balloc.cpp b/library/cpp/balloc/balloc.cpp index fab489db4c..02ce67383c 100644 --- a/library/cpp/balloc/balloc.cpp +++ b/library/cpp/balloc/balloc.cpp @@ -1,7 +1,7 @@ #include <library/cpp/balloc/lib/balloc.h> #include <errno.h> -namespace NBalloc { +namespace NBalloc { static constexpr size_t ALIVE_SIGNATURE = 0xaULL << 56; static constexpr size_t DISABLED_SIGNATURE = 0xbULL << 56; @@ -26,9 +26,9 @@ namespace NBalloc { TAllocHeader* allocHeader = (TAllocHeader*)LibcMalloc(extsize); allocHeader->Encode(allocHeader, size, DISABLED_SIGNATURE); return allocHeader + 1; - } + } } - + static void Y_FORCE_INLINE Free(void* ptr) { if (ptr == nullptr) { return; @@ -50,8 +50,8 @@ namespace NBalloc { } else { NMalloc::AbortFromCorruptedAllocator(); } - } - + } + static bool Y_FORCE_INLINE IsOwnedByBalloc(void* ptr) { TAllocHeader* allocHeader = ((TAllocHeader*)ptr) - 1; size_t size = allocHeader->AllocSize; @@ -64,7 +64,7 @@ namespace NBalloc { NMalloc::AbortFromCorruptedAllocator(); Y_UNREACHABLE(); } - + static void Y_FORCE_INLINE Disable() { #if defined(_musl_) // just skip it @@ -80,8 +80,8 @@ namespace NBalloc { static bool Y_FORCE_INLINE IsDisabled() { return tls.Mode == Disabled; } -}; - +}; + #if defined(Y_COVER_PTR) void* CoverPtr(void* ptr, size_t len) noexcept; void* UncoverPtr(void* ptr) noexcept; @@ -91,18 +91,18 @@ extern "C" void* malloc(size_t size) { #if defined(Y_COVER_PTR) return CoverPtr(NBalloc::Malloc(size + 32), size); #else - return NBalloc::Malloc(size); + return NBalloc::Malloc(size); #endif -} - +} + extern "C" void free(void* data) { #if defined(Y_COVER_PTR) NBalloc::Free(UncoverPtr(data)); #else - NBalloc::Free(data); + NBalloc::Free(data); #endif -} - +} + #if defined(USE_INTELCC) || defined(_darwin_) || defined(_freebsd_) || defined(_STLPORT_VERSION) #define OP_THROWNOTHING noexcept #else @@ -113,10 +113,10 @@ void* operator new(size_t size) { #if defined(Y_COVER_PTR) return malloc(size); #else - return NBalloc::Malloc(size); + return NBalloc::Malloc(size); #endif -} - +} + int posix_memalign(void** memptr, const size_t alignment, const size_t size) { #if defined(Y_COVER_PTR) (void)alignment; @@ -125,7 +125,7 @@ int posix_memalign(void** memptr, const size_t alignment, const size_t size) { #else if (((alignment - 1) & alignment) != 0 || alignment < sizeof(void*)) { return EINVAL; - } + } if (alignment <= NBalloc::MINIMAL_ALIGNMENT) { *memptr = NBalloc::Malloc(size); return 0; @@ -140,66 +140,66 @@ int posix_memalign(void** memptr, const size_t alignment, const size_t size) { newAllocHeader->Encode(block, size, NBalloc::ALIVE_SIGNATURE); } *memptr = alignedPtr; - return 0; + return 0; #endif -} - +} + void* operator new(size_t size, const std::nothrow_t&) OP_THROWNOTHING { #if defined(Y_COVER_PTR) return malloc(size); #else - return NBalloc::Malloc(size); + return NBalloc::Malloc(size); #endif -} - +} + void operator delete(void* p)OP_THROWNOTHING { #if defined(Y_COVER_PTR) free(p); #else - NBalloc::Free(p); + NBalloc::Free(p); #endif -} - +} + void operator delete(void* p, const std::nothrow_t&)OP_THROWNOTHING { #if defined(Y_COVER_PTR) free(p); #else - NBalloc::Free(p); + NBalloc::Free(p); #endif -} - +} + void* operator new[](size_t size) { #if defined(Y_COVER_PTR) return malloc(size); #else - return NBalloc::Malloc(size); + return NBalloc::Malloc(size); #endif -} - +} + void* operator new[](size_t size, const std::nothrow_t&) OP_THROWNOTHING { #if defined(Y_COVER_PTR) return malloc(size); #else - return NBalloc::Malloc(size); + return NBalloc::Malloc(size); #endif -} - +} + void operator delete[](void* p) OP_THROWNOTHING { #if defined(Y_COVER_PTR) free(p); #else - NBalloc::Free(p); + NBalloc::Free(p); #endif -} - +} + void operator delete[](void* p, const std::nothrow_t&) OP_THROWNOTHING { #if defined(Y_COVER_PTR) free(p); #else - NBalloc::Free(p); + NBalloc::Free(p); #endif -} - +} + extern "C" void* calloc(size_t n, size_t elemSize) { const size_t size = n * elemSize; @@ -210,44 +210,44 @@ extern "C" void* calloc(size_t n, size_t elemSize) { #if defined(Y_COVER_PTR) void* result = malloc(size); #else - void* result = NBalloc::Malloc(size); + void* result = NBalloc::Malloc(size); #endif if (result) { - memset(result, 0, size); - } - - return result; -} + memset(result, 0, size); + } -extern "C" void cfree(void* ptr) { + return result; +} + +extern "C" void cfree(void* ptr) { #if defined(Y_COVER_PTR) free(ptr); #else NBalloc::Free(ptr); #endif -} - +} + #if defined(Y_COVER_PTR) static inline void* DoRealloc(void* oldPtr, size_t newSize) { #else extern "C" void* realloc(void* oldPtr, size_t newSize) { #endif if (!oldPtr) { - void* result = NBalloc::Malloc(newSize); - return result; - } - if (newSize == 0) { + void* result = NBalloc::Malloc(newSize); + return result; + } + if (newSize == 0) { NBalloc::Free(oldPtr); return nullptr; - } + } void* newPtr = NBalloc::Malloc(newSize); if (!newPtr) { return nullptr; - } + } NBalloc::TAllocHeader* header = (NBalloc::TAllocHeader*)oldPtr - 1; - const size_t oldSize = header->AllocSize & ~NBalloc::SIGNATURE_MASK; - const size_t signature = header->AllocSize & NBalloc::SIGNATURE_MASK; + const size_t oldSize = header->AllocSize & ~NBalloc::SIGNATURE_MASK; + const size_t signature = header->AllocSize & NBalloc::SIGNATURE_MASK; if (Y_LIKELY((signature == NBalloc::ALIVE_SIGNATURE) || (signature == NBalloc::DISABLED_SIGNATURE))) { memcpy(newPtr, oldPtr, oldSize < newSize ? oldSize : newSize); NBalloc::Free(oldPtr); @@ -255,7 +255,7 @@ extern "C" void* realloc(void* oldPtr, size_t newSize) { } NMalloc::AbortFromCorruptedAllocator(); return nullptr; -} +} #if defined(Y_COVER_PTR) extern "C" void* realloc(void* oldPtr, size_t newSize) { diff --git a/library/cpp/balloc/ya.make b/library/cpp/balloc/ya.make index d4457fbba9..2dd7ca6895 100644 --- a/library/cpp/balloc/ya.make +++ b/library/cpp/balloc/ya.make @@ -1,13 +1,13 @@ -LIBRARY() +LIBRARY() OWNER( ironpeter g:base ) - + NO_UTIL() NO_COMPILER_WARNINGS() - + IF (OS_WINDOWS) PEERDIR( library/cpp/lfalloc @@ -23,6 +23,6 @@ ELSE() ) ENDIF() -END() +END() NEED_CHECK() diff --git a/library/cpp/codecs/float_huffman.cpp b/library/cpp/codecs/float_huffman.cpp index c4a8bd228f..f913b3c6f7 100644 --- a/library/cpp/codecs/float_huffman.cpp +++ b/library/cpp/codecs/float_huffman.cpp @@ -1,5 +1,5 @@ -#include "float_huffman.h" - +#include "float_huffman.h" + #include <util/generic/array_ref.h> #include <util/generic/bitops.h> #include <util/generic/cast.h> @@ -56,12 +56,12 @@ namespace NCodecs::NFloatHuff { {0x3b000000, 0x26, 6, 34}, // [0.001953125, end of range), 40 bits, prefix [011001] {0x00000000, 0x16, 5, 32}, // whole range, 37 bits, prefix [01101] }; - + [[noreturn]] Y_NO_INLINE void ThrowInvalidOffset(size_t size, size_t byteOffset) { ythrow yexception() << "Decompression error: requested decoding 8 bytes past end of input buffer of " << size << " bytes size at position " << byteOffset << ". "; } - + struct THuffInfo { constexpr THuffInfo() { for (size_t i = 0; i < 64; ++i) { diff --git a/library/cpp/codecs/float_huffman.h b/library/cpp/codecs/float_huffman.h index 786a8eae1d..9084fe1b15 100644 --- a/library/cpp/codecs/float_huffman.h +++ b/library/cpp/codecs/float_huffman.h @@ -1,14 +1,14 @@ -#pragma once +#pragma once #include <util/generic/array_ref.h> #include <util/generic/vector.h> #include <util/generic/strbuf.h> - + #include <array> namespace NCodecs::NFloatHuff { TString Encode(TArrayRef<const float> factors); - + class TDecoder { public: explicit TDecoder(TStringBuf data); diff --git a/library/cpp/compproto/bit.h b/library/cpp/compproto/bit.h index 6a421b65f7..15022bd374 100644 --- a/library/cpp/compproto/bit.h +++ b/library/cpp/compproto/bit.h @@ -1,4 +1,4 @@ -#pragma once +#pragma once #include <util/generic/array_ref.h> #include <util/generic/vector.h> @@ -6,9 +6,9 @@ #include <util/stream/input.h> #include "huff.h" -#include "compressor.h" +#include "compressor.h" #include "metainfo.h" - + namespace NCompProto { struct TBitBuffer { TVector<ui8> Out; @@ -29,13 +29,13 @@ namespace NCompProto { ui64 Read(ui64 position, size_t size) { return Read(&Out[0], position, size); } - + void Code(ui64 value, size_t size) { if (++Counter == 0) { Junk(257 * 64); } Position = Code(value, size, Position); - } + } ui64 Code(ui64 value, size_t size, ui64 position) { ui8* dst = &Out[size_t(position >> 3)]; ui64& outCode = *(ui64*)dst; @@ -43,7 +43,7 @@ namespace NCompProto { ui64 mask = ((1ULL << size) - 1) << shift; outCode = ((value << shift) & mask) | (outCode & ~mask); return position + size; - } + } void Junk(size_t junk = 1024) { size_t need = size_t(Position >> 3); if (Out.size() * 8 < Position + junk) { @@ -55,16 +55,16 @@ namespace NCompProto { ui64 newVal = Read(position, 56); position = Code(value, size, position); value = newVal; - + while (position < Position + 64) { newVal = Read(position + 56 - size, 56); position = Code(value, 56, position); value = newVal; } - + Position += size; - } - + } + size_t ByteLength() const { return (Position + 7) / 8; } @@ -116,7 +116,7 @@ namespace NCompProto { } } } - + void Save(IOutputStream& stream, TString offset) { TString step = " "; for (size_t i = 0; i < Coder.Entries.size(); ++i) { @@ -126,13 +126,13 @@ namespace NCompProto { stream << (ui32)Coder.Entries[i].PrefixBits << " "; stream << (ui32)Coder.Entries[i].AllBits << " "; stream << Endl; - } + } stream << offset << "end" << Endl; - } - + } + void BeginElement(TBitBuffer& out) { Position = out.Position; - } + } void Add(ui32 value, TBitBuffer& out) { size_t val = 0; ui64 code = Coder.Code(value, val); @@ -148,12 +148,12 @@ namespace NCompProto { out.Junk(); } }; - + struct THist { TAccum Accum; THist() { - } - + } + void Load(IInputStream& stream) { TString name; while (1) { @@ -168,14 +168,14 @@ namespace NCompProto { void Add(ui32 value, TEmpty& /*empty*/) { Accum.Add(value); - } + } void AddDelayed(ui32 value, TEmpty& /*empty*/) { Accum.Add(value); } void BeginElement(TEmpty& /*empty*/) { } }; - + struct THistToHuff { static THistToHuff Instance() { return THistToHuff(); @@ -188,7 +188,7 @@ namespace NCompProto { info.Coder.Normalize(); } }; - + struct IDecompressor { // sequentially decompresses whole structure according to metainfo, starts at position offset virtual void Decompress(const TMetaInfo<TTable>* table, const ui8* codes, ui64& offset) = 0; @@ -196,14 +196,14 @@ namespace NCompProto { virtual void DecompressOne(const TMetaInfo<TTable>* table, const ui8* codes, ui64& offset, ui32 prevIndex = -1) = 0; virtual ~IDecompressor() = default; }; - + template <class X> struct TMetaIterator: public IDecompressor { X Self; TMetaIterator() { Self.Parent = this; } - + private: inline void DecompressSingle(ui32 repeatedIndex, const TMetaInfo<TTable>* table, const ui8* codes, ui64& offset) { Self.BeginElement(repeatedIndex); @@ -227,7 +227,7 @@ namespace NCompProto { } Self.EndElement(); } - + inline void DecompressSingleScalarsOnly(ui32 repeatedIndex, const TMetaInfo<TTable>* table, const ui8* codes, ui64& offset) { Self.BeginElement(repeatedIndex); ui32 mask = table->Mask.Decompress(codes, offset); @@ -236,7 +236,7 @@ namespace NCompProto { while (scalarMask) { if (mask & 1) { ui32 val = table->Scalar[index].Decompress(codes, offset); - Self.SetScalar(index, val); + Self.SetScalar(index, val); } else if (table->Default[index].Type == TScalarDefaultValue::Fixed) { Self.SetScalar(index, table->Default[index].Value); } @@ -275,7 +275,7 @@ namespace NCompProto { void DecompressOne(const TMetaInfo<TTable>* table, const ui8* codes, ui64& offset, ui32 prevIndex = -1) override { table->Index.Decompress(codes, offset); DecompressSingle(prevIndex, table, codes, offset); - } + } ui32 DecompressCount(const TMetaInfo<TTable>* table, const ui8* codes, ui64& offset) { return table->Count.Decompress(codes, offset); @@ -290,7 +290,7 @@ namespace NCompProto { { } }; - + struct TEmptyDecompressor: public TParentHold<TEmptyDecompressor> { void BeginSelf(ui32 /*count*/, ui32 /*id*/) { } @@ -307,12 +307,12 @@ namespace NCompProto { return *Parent; } }; - + inline TMetaIterator<TEmptyDecompressor>& GetEmptyDecompressor() { static TMetaIterator<TEmptyDecompressor> empty; return empty; - } - + } + struct THuffToTable { static THuffToTable Instance() { return THuffToTable(); @@ -330,13 +330,13 @@ namespace NCompProto { } } }; - + struct THuffToTableWithDecompressor: private THuffToTable { TSimpleSharedPtr<IDecompressor> Decompressor; THuffToTableWithDecompressor(TSimpleSharedPtr<IDecompressor> decompressor) : Decompressor(decompressor) { - } + } TSimpleSharedPtr<IDecompressor> Build() const { return Decompressor; } diff --git a/library/cpp/compproto/compproto_ut.cpp b/library/cpp/compproto/compproto_ut.cpp index 9393be967a..b93eb7d99a 100644 --- a/library/cpp/compproto/compproto_ut.cpp +++ b/library/cpp/compproto/compproto_ut.cpp @@ -66,7 +66,7 @@ void TestWithParams(const TString& metainfo, const ECompMode mode, const TTestPa ui64 codedSize = buffer.Position; - TMetaInfo<TTable> decompressor(*meta, THuffToTable::Instance()); + TMetaInfo<TTable> decompressor(*meta, THuffToTable::Instance()); // verify that no memory read beyond buffer occurs const size_t byteSize = buffer.ByteLength(); @@ -87,7 +87,7 @@ void TestWithParams(const TString& metainfo, const ECompMode mode, const TTestPa memcpy(dataStart, buffer.Out.data(), byteSize); ui64 position = 0; - TMetaIterator<TDecompressor> instance; + TMetaIterator<TDecompressor> instance; // we should not read beyond dataEnd here instance.Decompress(&decompressor, dataStart, position); const ui64 decodedSize = position; @@ -177,70 +177,70 @@ Y_UNIT_TEST_SUITE(CompProtoTestBasic) { struct TRegClicks: public TParentHold<TRegClicks> { const TData* Data; const TRegInfo* Elem; - TRegClicks() + TRegClicks() : Data(nullptr) , Elem(nullptr) - { - } + { + } void BeginSelf(ui32 /*count*/, ui32 /*id*/) { - } - void EndSelf() { - } - void BeginElement(ui32 element) { + } + void EndSelf() { + } + void BeginElement(ui32 element) { TMap<ui32, TRegInfo>::const_iterator it = Data->RegClicks.find(element); - if (it == Data->RegClicks.end()) { - UNIT_ASSERT(0); - } - Elem = &it->second; - } - void EndElement() { - } - void SetScalar(size_t index, ui32 val) { - if (index == 0) - UNIT_ASSERT_EQUAL(val, Elem->Clicks); - if (index == 1) - UNIT_ASSERT_EQUAL(val, Elem->Shows); - } + if (it == Data->RegClicks.end()) { + UNIT_ASSERT(0); + } + Elem = &it->second; + } + void EndElement() { + } + void SetScalar(size_t index, ui32 val) { + if (index == 0) + UNIT_ASSERT_EQUAL(val, Elem->Clicks); + if (index == 1) + UNIT_ASSERT_EQUAL(val, Elem->Shows); + } IDecompressor& GetDecompressor(size_t) { - UNIT_ASSERT(0); - return GetEmptyDecompressor(); - } - }; - + UNIT_ASSERT(0); + return GetEmptyDecompressor(); + } + }; + const TData* Elem; - TMetaIterator<TRegClicks> RegClicks; + TMetaIterator<TRegClicks> RegClicks; void BeginSelf(ui32 /*count*/, ui32 /*id*/) { - } - void EndSelf() { - } - void BeginElement(ui32 element) { - UNIT_ASSERT(element < data.size()); - Elem = &data[element]; - } - void EndElement() { - } - void SetScalar(size_t index, ui32 val) { - if (index == 0) - UNIT_ASSERT_EQUAL(val, Elem->Clicks); - if (index == 1) - UNIT_ASSERT_EQUAL(val, Elem->Shows); + } + void EndSelf() { + } + void BeginElement(ui32 element) { + UNIT_ASSERT(element < data.size()); + Elem = &data[element]; + } + void EndElement() { + } + void SetScalar(size_t index, ui32 val) { + if (index == 0) + UNIT_ASSERT_EQUAL(val, Elem->Clicks); + if (index == 1) + UNIT_ASSERT_EQUAL(val, Elem->Shows); if (index == 31) UNIT_ASSERT_EQUAL(val, Elem->Extra); - } + } IDecompressor& GetDecompressor(size_t index) { - if (index == 2) { - RegClicks.Self.Data = Elem; - return RegClicks; - } - UNIT_ASSERT(0); - return GetEmptyDecompressor(); - } - TMultiDecompressor() + if (index == 2) { + RegClicks.Self.Data = Elem; + return RegClicks; + } + UNIT_ASSERT(0); + return GetEmptyDecompressor(); + } + TMultiDecompressor() : Elem(nullptr) - { - } - }; - + { + } + }; + struct TVerifyingDecompressor: public TParentHold<TVerifyingDecompressor> { enum EState { Startstop, @@ -255,14 +255,14 @@ Y_UNIT_TEST_SUITE(CompProtoTestBasic) { TMetaIterator<TVerifyingDecompressor>& GetDecompressor(size_t index) { Y_UNUSED(index); - return *Parent; - } - + return *Parent; + } + TVerifyingDecompressor() : State(Startstop) , DataInd(0) - { - } + { + } void BeginSelf(ui32 /*count*/, ui32 id) { switch (State) { case Startstop: @@ -361,14 +361,14 @@ Y_UNIT_TEST_SUITE(CompProtoTestBasic) { Y_UNIT_TEST(VerifyHistDecompression) { Test<TVerifyingDecompressor, TSerialize>(metainfo, CM_TWOPASS); } - + Y_UNIT_TEST(VerifyDecompressionMulti) { - Test<TMultiDecompressor, TSerialize>(metainfo, CM_SINGLEPASS); - } - + Test<TMultiDecompressor, TSerialize>(metainfo, CM_SINGLEPASS); + } + Y_UNIT_TEST(VerifyHistDecompressionMulti) { - Test<TMultiDecompressor, TSerialize>(metainfo, CM_TWOPASS); - } + Test<TMultiDecompressor, TSerialize>(metainfo, CM_TWOPASS); + } } Y_UNIT_TEST_SUITE(CompProtoTestExtended) { @@ -443,14 +443,14 @@ Y_UNIT_TEST_SUITE(CompProtoTestExtended) { : State(Startstop) , DataInd(0) , ArrayInd(0) - { - } + { + } TMetaIterator<TVerifyingDecompressor>& GetDecompressor(size_t index) { Y_UNUSED(index); - return *Parent; - } - + return *Parent; + } + void BeginSelf(ui32 /*count*/, ui32 id) { switch (State) { case Startstop: diff --git a/library/cpp/compproto/compressor.h b/library/cpp/compproto/compressor.h index 14b335e13c..1fb678e04e 100644 --- a/library/cpp/compproto/compressor.h +++ b/library/cpp/compproto/compressor.h @@ -1,5 +1,5 @@ -#pragma once - +#pragma once + #include <util/system/defaults.h> namespace NCompProto { @@ -15,7 +15,7 @@ namespace NCompProto { PrefLength[i] = 0; Id[i] = 0; } - } + } ui32 CodeBase[64]; ui32 CodeMask[64]; ui8 Length[64]; @@ -23,15 +23,15 @@ namespace NCompProto { ui8 Id[64]; enum { PAGE_BOUND = 4096, -#ifdef WITH_VALGRIND +#ifdef WITH_VALGRIND SAFE_MODE = 1, -#else +#else #if defined(__has_feature) #if __has_feature(address_sanitizer) SAFE_MODE = 1, #else SAFE_MODE = 0, -#endif +#endif #else SAFE_MODE = 0, #endif @@ -44,7 +44,7 @@ namespace NCompProto { if (pageOff > PAGE_BOUND - 8 || SAFE_MODE) { size_t off = 8; ui64 res = codes[0]; - ++codes; + ++codes; ui64 indexCur = ((res + 0x0000) >> readOff) & 63; ui64 indexAlt = ((res + 0xff00) >> readOff) & 63; if (Id[indexCur] != Id[indexAlt]) { @@ -63,12 +63,12 @@ namespace NCompProto { offset += length; ui64 code = res >> readOff; return (((ui32)(code >> PrefLength[index])) & CodeMask[index]) + CodeBase[index]; - } + } ui64 code = ((const ui64*)(codes))[0] >> readOff; ui64 index = code & 63; offset += Length[index]; - return (((ui32)(code >> PrefLength[index])) & CodeMask[index]) + CodeBase[index]; - } + return (((ui32)(code >> PrefLength[index])) & CodeMask[index]) + CodeBase[index]; + } }; } diff --git a/library/cpp/compproto/huff.h b/library/cpp/compproto/huff.h index fa5c139189..da2b8ca4f6 100644 --- a/library/cpp/compproto/huff.h +++ b/library/cpp/compproto/huff.h @@ -1,5 +1,5 @@ -#pragma once - +#pragma once + #include <util/system/defaults.h> #include <util/generic/yexception.h> #include <util/generic/ptr.h> @@ -9,8 +9,8 @@ #include <queue> -#include "compressor.h" - +#include "compressor.h" + namespace NCompProto { template <size_t CacheSize, typename TEntry> struct TCache { @@ -47,17 +47,17 @@ namespace NCompProto { , Start(start) , Bits(bits) { - } - + } + bool operator<(const TCode& code) const { return Probability < code.Probability; } - + bool operator>(const TCode& code) const { return Probability > code.Probability; } }; - + struct TAccum { struct TTable { TAutoPtr<TTable> Tables[16]; @@ -74,25 +74,25 @@ namespace NCompProto { for (auto& count : Counts) count = 0; } - + i64 GetCellCount(size_t i) { i64 count = Counts[i]; if (Tables[i].Get()) { for (size_t j = 0; j < 16; ++j) { count += Tables[i]->GetCellCount(j); } - } + } return count; - } - + } + i64 GetCount() { i64 count = 0; - for (size_t j = 0; j < 16; ++j) { + for (size_t j = 0; j < 16; ++j) { count += GetCellCount(j); - } + } return count; - } - + } + void GenerateFreqs(TVector<std::pair<i64, TCode>>& codes, int depth, int termDepth, ui32 code, i64 cnt) { if (depth == termDepth) { for (size_t i = 0; i < 16; ++i) { @@ -101,7 +101,7 @@ namespace NCompProto { Counts[i] = iCount; Tables[i].Reset(nullptr); } - + if (iCount > cnt || (termDepth == 0 && iCount > 0)) { std::pair<i64, TCode> codep; codep.first = iCount; @@ -113,32 +113,32 @@ namespace NCompProto { } } } - for (size_t i = 0; i < 16; ++i) { + for (size_t i = 0; i < 16; ++i) { if (Tables[i].Get()) { Tables[i]->GenerateFreqs(codes, depth + 4, termDepth, code + (i << (28 - depth)), cnt); - } - } - } + } + } + } }; - + TTable Root; int TableCount; i64 Total; ui64 Max; - + TAccum() { TableCount = 0; Total = 0; Max = 0; } - + void GenerateFreqs(TVector<std::pair<i64, TCode>>& codes, int mul) const { TTable root(Root); - + for (int i = 28; i > 0; i -= 4) { root.GenerateFreqs(codes, 0, i, 0, Total / mul); } - + i64 iCount = root.GetCount(); if (iCount == 0) return; @@ -154,10 +154,10 @@ namespace NCompProto { } codep.second.Bits = bits; codes.push_back(codep); - } - + } + TCache<256, i64*> Cache; - + void AddMap(ui32 value, i64 weight = 1) { ui32 index = Cache.Hash(value); if (Cache.CacheKey[index] == value) { @@ -177,22 +177,22 @@ namespace NCompProto { root->Counts[index2] += weight; return; } - } + } root = root->Tables[index2].Get(); - } + } Cache.CacheKey[index] = value; Cache.CacheVal[index] = &root->Counts[value & 0xf]; root->Counts[value & 0xf] += weight; - } - + } + void Add(ui32 value, i64 weight = 1) { Max = ::Max(Max, (ui64)value); Total += weight; AddMap(value, weight); }; - }; - + }; + struct THuffNode { i64 Weight; i64 Priority; @@ -206,7 +206,7 @@ namespace NCompProto { Nodes[0] = nullptr; Nodes[1] = nullptr; } - + void BuildPrefixes(ui32 depth, ui32 prefix) { if (Code) { Code->Prefix = prefix; @@ -216,44 +216,44 @@ namespace NCompProto { Nodes[0]->BuildPrefixes(depth + 1, prefix + (0UL << depth)); Nodes[1]->BuildPrefixes(depth + 1, prefix + (1UL << depth)); } - + i64 Iterate(size_t depth) const { if (Code) { return (depth + Code->Bits) * Code->Probability; } return Nodes[0]->Iterate(depth + 1) + Nodes[1]->Iterate(depth + 1); - } - + } + size_t Depth() const { if (Code) { return 0; } return Max(Nodes[0]->Depth(), Nodes[1]->Depth()) + 1; - } + } }; - + struct THLess { bool operator()(const THuffNode* a, const THuffNode* b) { if (a->Weight > b->Weight) return 1; if (a->Weight == b->Weight && a->Priority > b->Priority) return 1; - return 0; - } + return 0; + } }; - + inline i64 BuildHuff(TVector<TCode>& codes) { TVector<TSimpleSharedPtr<THuffNode>> hold; std::priority_queue<THuffNode*, TVector<THuffNode*>, THLess> nodes; i64 ret = 0; - + int priority = 0; for (size_t i = 0; i < codes.size(); ++i) { TSimpleSharedPtr<THuffNode> node(new THuffNode(codes[i].Probability, priority++, &codes[i])); hold.push_back(node); nodes.push(node.Get()); } - + while (nodes.size() > 1) { THuffNode* nodea = nodes.top(); nodes.pop(); @@ -265,27 +265,27 @@ namespace NCompProto { hold.push_back(node); nodes.push(node.Get()); } - + if (nodes.size()) { THuffNode* node = nodes.top(); node->BuildPrefixes(0, 0); ret = node->Iterate(0); } - + return ret; }; - + struct TCoderEntry { ui32 MinValue; ui16 Prefix; ui8 PrefixBits; ui8 AllBits; - + ui64 MaxValue() const { return MinValue + (1ULL << (AllBits - PrefixBits)); } }; - + inline i64 Analyze(const TAccum& acc, TVector<TCoderEntry>& retCodes) { i64 ret; for (int k = 256; k > 0; --k) { @@ -296,9 +296,9 @@ namespace NCompProto { for (size_t i = 0; i < pairs.size(); ++i) { codes.push_back(pairs[i].second); } - + StableSort(codes.begin(), codes.end(), std::greater<TCode>()); - + ret = BuildHuff(codes); bool valid = true; for (size_t i = 0; i < codes.size(); ++i) { @@ -313,17 +313,17 @@ namespace NCompProto { } if (valid) return ret; - } - + } + return ret; } - + struct TComparer { bool operator()(const TCoderEntry& e0, const TCoderEntry& e1) const { return e0.AllBits < e1.AllBits; - } + } }; - + struct TCoder { TVector<TCoderEntry> Entries; void Normalize() { @@ -355,14 +355,14 @@ namespace NCompProto { } }; } - + TCache<1024, TCoderEntry> Cache; - + ui64 RealCode(ui32 value, const TCoderEntry& entry, size_t& length) { length = entry.AllBits; return (ui64(value - entry.MinValue) << entry.PrefixBits) + entry.Prefix; } - + bool Empty() const { return Entries.empty(); } @@ -374,17 +374,17 @@ namespace NCompProto { id = ui8(i); return entry; } - } + } ythrow yexception() << "bad entry"; return Entries[0]; - } - + } + ui64 Code(ui32 entry, size_t& length) { ui32 index = Cache.Hash(entry); if (Cache.CacheKey[index] == entry) { ++Cache.Hits; - return RealCode(entry, Cache.CacheVal[index], length); - } + return RealCode(entry, Cache.CacheVal[index], length); + } ++Cache.Misses; for (size_t i = 0; i < Entries.size(); ++i) { if (entry >= Entries[i].MinValue && entry < Entries[i].MaxValue()) { @@ -396,7 +396,7 @@ namespace NCompProto { ythrow yexception() << "bad huff tree"; return 0; - } + } }; - + } diff --git a/library/cpp/compproto/metainfo.h b/library/cpp/compproto/metainfo.h index 6e68f86e12..05d328a766 100644 --- a/library/cpp/compproto/metainfo.h +++ b/library/cpp/compproto/metainfo.h @@ -1,5 +1,5 @@ -#pragma once - +#pragma once + #include <util/system/defaults.h> #include <util/generic/yexception.h> #include <util/generic/ptr.h> @@ -7,8 +7,8 @@ #include <util/stream/input.h> #include <util/stream/str.h> -#include "compressor.h" - +#include "compressor.h" + namespace NCompProto { const size_t MAX_ELEMENTS = 32; @@ -25,7 +25,7 @@ namespace NCompProto { EType Type; ui32 Value; }; - + template <class X> struct TMetaInfo { X Index; @@ -42,7 +42,7 @@ namespace NCompProto { TString ChildName[MAX_ELEMENTS]; size_t Id; TMetaInfo* Parent; - + struct TCheck { ui32 Count; ui32 Mask; @@ -74,7 +74,7 @@ namespace NCompProto { ClearAll(); } }; - + TCheck Serializer; void SetDefaults(TMetaInfo* parent) { @@ -108,12 +108,12 @@ namespace NCompProto { info->Parent = this; Repeated[i].Reset(info.Release()); } - } - } + } + } TMetaInfo(TMetaInfo* parent) { SetDefaults(parent); - } + } template <class T> TMetaInfo& BeginRepeated(size_t id, T& functor) { @@ -121,13 +121,13 @@ namespace NCompProto { TMetaInfo& res = *Repeated[id].Get(); res.Count.BeginElement(functor); return res; - } + } template <class T> void BeginSelf(T& functor) { Serializer.ClearAll(); Count.BeginElement(functor); - } + } template <class T> void EndRepeated(T& functor) { @@ -135,7 +135,7 @@ namespace NCompProto { Serializer.ClearCount(); Serializer.ClearIndex(); Y_ENSURE(Serializer.Mask == 0, "Serializer.Mask != 0"); - } + } template <class T> void BeginElement(ui32 index, T& functor) { @@ -147,7 +147,7 @@ namespace NCompProto { Serializer.LastIndex = index; ++Serializer.Count; } - + template <class TFunctor> void Iterate(TFunctor& functor) { Cout << Name << " " @@ -157,7 +157,7 @@ namespace NCompProto { functor.Process(Count); Cout << "Mask" << Endl; functor.Process(Mask); - + for (size_t i = 0; i < Size; ++i) { ui32 index = (1UL << i); if (ScalarMask & index) { @@ -170,15 +170,15 @@ namespace NCompProto { << " " << i << Endl; Repeated[i]->Iterate(functor); } - } - } - + } + } + template <class T> void EndElement(T& functor) { Mask.AddDelayed(Serializer.Mask, functor); Serializer.ClearMask(); } - + template <class T> void SetScalar(size_t id, ui32 value, T& functor) { if (Default[id].Type != TScalarDefaultValue::Fixed || value != Default[id].Value) { @@ -186,32 +186,32 @@ namespace NCompProto { Scalar[id].Add(value, functor); } } - + ui32 Check(size_t id) { Y_ENSURE(id < MAX_ELEMENTS, "id >= MAX_ELEMENTS"); - + ui32 mask = 1UL << id; if (ScalarMask & mask) { ythrow yexception() << "ScalarMask & mask"; - } + } if (RepeatedMask & mask) { ythrow yexception() << "RepeatedMask & mask"; - } + } Size = Max(id + 1, Size); return mask; - } - + } + TMetaInfo(IInputStream& stream) { SetDefaults(nullptr); Load(stream); - } - + } + TMetaInfo(const TString& str) { SetDefaults(nullptr); TStringInput stream(str); Load(stream); - } - + } + void Save(IOutputStream& stream, const TString& offset = TString()) { stream << offset << "repeated " << Name << " id " << Id << Endl; TString step = " "; @@ -221,7 +221,7 @@ namespace NCompProto { Count.Save(stream, step + offset); stream << step << offset << "mask" << Endl; Mask.Save(stream, step + offset); - + for (size_t i = 0; i < MAX_ELEMENTS; ++i) { ui32 mask = 1UL << i; if (mask & RepeatedMask) { @@ -237,13 +237,13 @@ namespace NCompProto { << "id " << i << Endl; Scalar[i].Save(stream, step + offset); } - } + } stream << offset << "end" << Endl; - } - + } + void Load(IInputStream& stream) { TString name; - stream >> name; + stream >> name; if (name == "repeated") { stream >> name; } @@ -251,9 +251,9 @@ namespace NCompProto { stream >> name; Y_ENSURE(name == "id", "Name mismatch: " << name.Quote() << " != id. "); stream >> Id; - + while (1) { - stream >> name; + stream >> name; if (name == "index") { Index.Load(stream); } else if (name == "count") { @@ -297,8 +297,8 @@ namespace NCompProto { } else if (name == "end" /* || stream.IsEOF()*/) { return; } - } - } + } + } }; } diff --git a/library/cpp/compproto/ya.make b/library/cpp/compproto/ya.make index 60d5cfa08d..9957cd23b5 100644 --- a/library/cpp/compproto/ya.make +++ b/library/cpp/compproto/ya.make @@ -1,13 +1,13 @@ -LIBRARY() - +LIBRARY() + OWNER(ironpeter) -SRCS( - bit.h - compressor.h - huff.h - metainfo.h +SRCS( + bit.h + compressor.h + huff.h + metainfo.h lib.cpp ) -END() +END() diff --git a/library/cpp/comptable/usage/usage.cpp b/library/cpp/comptable/usage/usage.cpp index 9997c83686..209950b08c 100644 --- a/library/cpp/comptable/usage/usage.cpp +++ b/library/cpp/comptable/usage/usage.cpp @@ -51,7 +51,7 @@ int main(int argc, const char* argv[]) { }*/ //for (size_t i = 0; i < 10000000; ++i) { //for (size_t i = 0; i < 1000000; ++i) { - for (size_t i = 0; i < 1000000; ++i) { + for (size_t i = 0; i < 1000000; ++i) { size_t size = rr.Uniform(32); TString res = "www.yandex.ru/yandsearch?text="; for (size_t j = 0; j < size; ++j) { diff --git a/library/cpp/lfalloc/lf_allocX64.cpp b/library/cpp/lfalloc/lf_allocX64.cpp index 2eb90761fe..2a06e778ec 100644 --- a/library/cpp/lfalloc/lf_allocX64.cpp +++ b/library/cpp/lfalloc/lf_allocX64.cpp @@ -1,5 +1,5 @@ #include "lf_allocX64.h" - + ////////////////////////////////////////////////////////////////////////// // hooks #if defined(USE_INTELCC) || defined(_darwin_) || defined(_freebsd_) || defined(_STLPORT_VERSION) diff --git a/library/cpp/lfalloc/lf_allocX64.h b/library/cpp/lfalloc/lf_allocX64.h index fd2a906d6f..eace32fd97 100644 --- a/library/cpp/lfalloc/lf_allocX64.h +++ b/library/cpp/lfalloc/lf_allocX64.h @@ -1,9 +1,9 @@ #pragma once -#include <stdlib.h> -#include <stdio.h> -#include <stdarg.h> - +#include <stdlib.h> +#include <stdio.h> +#include <stdarg.h> + #include <library/cpp/malloc/api/malloc.h> #include <util/system/compat.h> @@ -442,7 +442,7 @@ static void LargeBlockUnmap(void* p, size_t pages) { ////////////////////////////////////////////////////////////////////////// const size_t LB_BUF_SIZE = 250; -const size_t LB_BUF_HASH = 977; +const size_t LB_BUF_HASH = 977; static int LB_LIMIT_TOTAL_SIZE = 500 * 1024 * 1024 / 4096; // do not keep more then this mem total in lbFreePtrs[] static void* volatile lbFreePtrs[LB_BUF_HASH][LB_BUF_SIZE]; static TAtomic lbFreePageCount; @@ -1120,7 +1120,7 @@ struct TThreadAllocInfo { i = THREAD_BUF; #ifdef _win_ BOOL b = DuplicateHandle( - GetCurrentProcess(), GetCurrentThread(), + GetCurrentProcess(), GetCurrentThread(), GetCurrentProcess(), &hThread, 0, FALSE, DUPLICATE_SAME_ACCESS); Y_ASSERT_NOBT(b); @@ -1305,7 +1305,7 @@ static void AllocThreadInfo() { ////////////////////////////////////////////////////////////////////////// #if defined(LFALLOC_DBG) - + struct TAllocHeader { uint64_t Size; int Tag; @@ -1529,18 +1529,18 @@ static Y_FORCE_INLINE void* LFAllocImpl(size_t _nSize) { // check per thread buffer TThreadAllocInfo* thr = pThreadInfo; - if (!thr) { - AllocThreadInfo(); - thr = pThreadInfo; - if (!thr) { + if (!thr) { + AllocThreadInfo(); + thr = pThreadInfo; + if (!thr) { void* ptr = LFAllocNoCache(nSizeIdx, MEM_DEFRAG); #if defined(LFALLOC_DBG) ptr = TrackAllocation(ptr, size, nSizeIdx); #endif return ptr; - } - } - { + } + } + { int& freePtrIdx = thr->FreePtrIndex[nSizeIdx]; if (freePtrIdx < THREAD_BUF) { void* ptr = thr->FreePtrs[nSizeIdx][freePtrIdx++]; @@ -1568,7 +1568,7 @@ static Y_FORCE_INLINE void* LFAllocImpl(size_t _nSize) { ptr = TrackAllocation(ptr, size, nSizeIdx); #endif return ptr; - } + } } static Y_FORCE_INLINE void* LFAlloc(size_t _nSize) { @@ -1792,13 +1792,13 @@ static void DumpMemoryBlockUtilizationLocked() { } void FlushThreadFreeList() { - if (pThreadInfo) - MoveSingleThreadFreeToGlobal(pThreadInfo); -} - + if (pThreadInfo) + MoveSingleThreadFreeToGlobal(pThreadInfo); +} + void DumpMemoryBlockUtilization() { // move current thread free to global lists to get better statistics - FlushThreadFreeList(); + FlushThreadFreeList(); { TLFLockHolder ls(&LFGlobalLock); DumpMemoryBlockUtilizationLocked(); diff --git a/library/cpp/malloc/api/malloc.cpp b/library/cpp/malloc/api/malloc.cpp index eed1c58a38..a1a987a820 100644 --- a/library/cpp/malloc/api/malloc.cpp +++ b/library/cpp/malloc/api/malloc.cpp @@ -34,4 +34,4 @@ namespace NMalloc { IsAllocatorCorrupted = true; abort(); } -} +} diff --git a/library/cpp/yt/string/format-inl.h b/library/cpp/yt/string/format-inl.h index 5484d4a216..6167c2e09c 100644 --- a/library/cpp/yt/string/format-inl.h +++ b/library/cpp/yt/string/format-inl.h @@ -472,12 +472,12 @@ void FormatValueViaSprintf( *formatEnd = '\0'; } - char* result = builder->Preallocate(SmallResultSize); + char* result = builder->Preallocate(SmallResultSize); size_t resultSize = ::snprintf(result, SmallResultSize, formatBuf, value); - if (resultSize >= SmallResultSize) { - result = builder->Preallocate(resultSize + 1); + if (resultSize >= SmallResultSize) { + result = builder->Preallocate(resultSize + 1); YT_VERIFY(::snprintf(result, resultSize + 1, formatBuf, value) == static_cast<int>(resultSize)); - } + } builder->Advance(resultSize); } diff --git a/util/generic/guid.cpp b/util/generic/guid.cpp index 8b907457bc..285a7bd25a 100644 --- a/util/generic/guid.cpp +++ b/util/generic/guid.cpp @@ -1,4 +1,4 @@ -#include "guid.h" +#include "guid.h" #include "ylimits.h" #include "string.h" diff --git a/util/memory/pool.h b/util/memory/pool.h index 13c8b6b9ed..fa36fac01d 100644 --- a/util/memory/pool.h +++ b/util/memory/pool.h @@ -4,7 +4,7 @@ #include <util/system/align.h> #include <util/system/yassert.h> -#include <util/generic/bitops.h> +#include <util/generic/bitops.h> #include <util/generic/utility.h> #include <util/generic/intrlist.h> #include <util/generic/strbuf.h> diff --git a/util/system/atomic_gcc.h b/util/system/atomic_gcc.h index ed8dc2bdc5..00bea6fd90 100644 --- a/util/system/atomic_gcc.h +++ b/util/system/atomic_gcc.h @@ -4,7 +4,7 @@ : \ : \ : "memory") - + static inline TAtomicBase AtomicGet(const TAtomic& a) { TAtomicBase tmp; #if defined(_arm64_) diff --git a/util/system/atomic_win.h b/util/system/atomic_win.h index 65c290e6cc..6cbe8e86b6 100644 --- a/util/system/atomic_win.h +++ b/util/system/atomic_win.h @@ -49,45 +49,45 @@ static inline intptr_t AtomicGetAndCas(TAtomic* a, intptr_t exchange, intptr_t c } #else // _x86_64_ - + #pragma intrinsic(_InterlockedIncrement64) #pragma intrinsic(_InterlockedDecrement64) #pragma intrinsic(_InterlockedExchangeAdd64) #pragma intrinsic(_InterlockedExchange64) #pragma intrinsic(_InterlockedCompareExchange64) - + static inline intptr_t AtomicIncrement(TAtomic& a) { return _InterlockedIncrement64((volatile __int64*)&a); -} - +} + static inline intptr_t AtomicGetAndIncrement(TAtomic& a) { return _InterlockedIncrement64((volatile __int64*)&a) - 1; } static inline intptr_t AtomicDecrement(TAtomic& a) { return _InterlockedDecrement64((volatile __int64*)&a); -} - +} + static inline intptr_t AtomicGetAndDecrement(TAtomic& a) { return _InterlockedDecrement64((volatile __int64*)&a) + 1; } static inline intptr_t AtomicAdd(TAtomic& a, intptr_t b) { return _InterlockedExchangeAdd64((volatile __int64*)&a, b) + b; -} - +} + static inline intptr_t AtomicGetAndAdd(TAtomic& a, intptr_t b) { return _InterlockedExchangeAdd64((volatile __int64*)&a, b); } static inline intptr_t AtomicSwap(TAtomic* a, intptr_t b) { return _InterlockedExchange64((volatile __int64*)a, b); -} - +} + static inline bool AtomicCas(TAtomic* a, intptr_t exchange, intptr_t compare) { return _InterlockedCompareExchange64((volatile __int64*)a, exchange, compare) == compare; -} - +} + static inline intptr_t AtomicGetAndCas(TAtomic* a, intptr_t exchange, intptr_t compare) { return _InterlockedCompareExchange64((volatile __int64*)a, exchange, compare); } diff --git a/util/system/file.cpp b/util/system/file.cpp index 4a261d020c..60a2ea666c 100644 --- a/util/system/file.cpp +++ b/util/system/file.cpp @@ -255,9 +255,9 @@ TFileHandle::TFileHandle(const TString& fName, EOpenMode oMode) noexcept { if (oMode & NoReadAhead) { ::posix_fadvise(Fd_, 0, 0, POSIX_FADV_RANDOM); } - } + } #endif - + //temp file if (Fd_ >= 0 && (oMode & Transient)) { unlink(fName.data()); diff --git a/util/system/hp_timer.cpp b/util/system/hp_timer.cpp index e4c3f21e6b..3b458428a0 100644 --- a/util/system/hp_timer.cpp +++ b/util/system/hp_timer.cpp @@ -1,6 +1,6 @@ -#include "hp_timer.h" +#include "hp_timer.h" -#include <util/generic/algorithm.h> +#include <util/generic/algorithm.h> #include <util/generic/singleton.h> #include <util/datetime/cputimer.h> diff --git a/util/system/shmat.cpp b/util/system/shmat.cpp index 07ff0d6caa..3e82016614 100644 --- a/util/system/shmat.cpp +++ b/util/system/shmat.cpp @@ -1,6 +1,6 @@ #include "shmat.h" -#include <util/generic/guid.h> +#include <util/generic/guid.h> #if defined(_win_) #include <stdio.h> diff --git a/util/system/shmat.h b/util/system/shmat.h index d9da3c151a..a2d289a9fd 100644 --- a/util/system/shmat.h +++ b/util/system/shmat.h @@ -3,7 +3,7 @@ #include "fhandle.h" #include <util/generic/ptr.h> -#include <util/generic/guid.h> +#include <util/generic/guid.h> class TSharedMemory: public TThrRefBase { TGUID Id; diff --git a/util/system/thread.i b/util/system/thread.i index 8cba505473..77067844d7 100644 --- a/util/system/thread.i +++ b/util/system/thread.i @@ -1,5 +1,5 @@ //do not use directly -#pragma once +#pragma once #include "platform.h" #if defined(_win_) diff --git a/util/thread/lfqueue.h b/util/thread/lfqueue.h index ab523631e4..510c91e788 100644 --- a/util/thread/lfqueue.h +++ b/util/thread/lfqueue.h @@ -1,12 +1,12 @@ #pragma once - + #include "fwd.h" #include <util/generic/ptr.h> -#include <util/system/atomic.h> +#include <util/system/atomic.h> #include <util/system/yassert.h> #include "lfstack.h" - + struct TDefaultLFCounter { template <class T> void IncCount(const T& data) { @@ -40,137 +40,137 @@ class TLockFreeQueue: public TNonCopyable { } TListNode* volatile Next; - T Data; - }; - + T Data; + }; + // using inheritance to be able to use 0 bytes for TCounter when we don't need one struct TRootNode: public TCounter { TListNode* volatile PushQueue; TListNode* volatile PopQueue; TListNode* volatile ToDelete; TRootNode* volatile NextFree; - + TRootNode() : PushQueue(nullptr) , PopQueue(nullptr) , ToDelete(nullptr) , NextFree(nullptr) - { - } + { + } void CopyCounter(TRootNode* x) { *(TCounter*)this = *(TCounter*)x; } - }; - + }; + static void EraseList(TListNode* n) { - while (n) { + while (n) { TListNode* keepNext = AtomicGet(n->Next); - delete n; - n = keepNext; - } - } + delete n; + n = keepNext; + } + } alignas(64) TRootNode* volatile JobQueue; alignas(64) volatile TAtomic FreememCounter; alignas(64) volatile TAtomic FreeingTaskCounter; alignas(64) TRootNode* volatile FreePtr; - + void TryToFreeAsyncMemory() { TAtomic keepCounter = AtomicAdd(FreeingTaskCounter, 0); TRootNode* current = AtomicGet(FreePtr); if (current == nullptr) - return; + return; if (AtomicAdd(FreememCounter, 0) == 1) { - // we are the last thread, try to cleanup + // we are the last thread, try to cleanup // check if another thread have cleaned up if (keepCounter != AtomicAdd(FreeingTaskCounter, 0)) { return; } if (AtomicCas(&FreePtr, (TRootNode*)nullptr, current)) { - // free list - while (current) { + // free list + while (current) { TRootNode* p = AtomicGet(current->NextFree); EraseList(AtomicGet(current->ToDelete)); - delete current; - current = p; - } + delete current; + current = p; + } AtomicAdd(FreeingTaskCounter, 1); - } - } - } + } + } + } void AsyncRef() { AtomicAdd(FreememCounter, 1); - } + } void AsyncUnref() { - TryToFreeAsyncMemory(); + TryToFreeAsyncMemory(); AtomicAdd(FreememCounter, -1); - } + } void AsyncDel(TRootNode* toDelete, TListNode* lst) { AtomicSet(toDelete->ToDelete, lst); for (;;) { AtomicSet(toDelete->NextFree, AtomicGet(FreePtr)); if (AtomicCas(&FreePtr, toDelete, AtomicGet(toDelete->NextFree))) - break; - } - } + break; + } + } void AsyncUnref(TRootNode* toDelete, TListNode* lst) { - TryToFreeAsyncMemory(); + TryToFreeAsyncMemory(); if (AtomicAdd(FreememCounter, -1) == 0) { - // no other operations in progress, can safely reclaim memory - EraseList(lst); - delete toDelete; - } else { - // Dequeue()s in progress, put node to free list - AsyncDel(toDelete, lst); - } - } - + // no other operations in progress, can safely reclaim memory + EraseList(lst); + delete toDelete; + } else { + // Dequeue()s in progress, put node to free list + AsyncDel(toDelete, lst); + } + } + struct TListInvertor { TListNode* Copy; TListNode* Tail; TListNode* PrevFirst; - + TListInvertor() : Copy(nullptr) , Tail(nullptr) , PrevFirst(nullptr) - { - } + { + } ~TListInvertor() { - EraseList(Copy); - } + EraseList(Copy); + } void CopyWasUsed() { Copy = nullptr; Tail = nullptr; PrevFirst = nullptr; - } + } void DoCopy(TListNode* ptr) { TListNode* newFirst = ptr; TListNode* newCopy = nullptr; TListNode* newTail = nullptr; - while (ptr) { - if (ptr == PrevFirst) { - // short cut, we have copied this part already + while (ptr) { + if (ptr == PrevFirst) { + // short cut, we have copied this part already AtomicSet(Tail->Next, newCopy); - newCopy = Copy; + newCopy = Copy; Copy = nullptr; // do not destroy prev try - if (!newTail) - newTail = Tail; // tried to invert same list - break; - } + if (!newTail) + newTail = Tail; // tried to invert same list + break; + } TListNode* newElem = new TListNode(ptr->Data, newCopy); - newCopy = newElem; + newCopy = newElem; ptr = AtomicGet(ptr->Next); - if (!newTail) - newTail = newElem; - } - EraseList(Copy); // copy was useless - Copy = newCopy; - PrevFirst = newFirst; - Tail = newTail; - } - }; - + if (!newTail) + newTail = newElem; + } + EraseList(Copy); // copy was useless + Copy = newCopy; + PrevFirst = newFirst; + Tail = newTail; + } + }; + void EnqueueImpl(TListNode* head, TListNode* tail) { TRootNode* newRoot = new TRootNode; AsyncRef(); @@ -224,21 +224,21 @@ class TLockFreeQueue: public TNonCopyable { return lst; } -public: +public: TLockFreeQueue() - : JobQueue(new TRootNode) - , FreememCounter(0) + : JobQueue(new TRootNode) + , FreememCounter(0) , FreeingTaskCounter(0) , FreePtr(nullptr) - { - } + { + } ~TLockFreeQueue() { AsyncRef(); AsyncUnref(); // should free FreeList - EraseList(JobQueue->PushQueue); - EraseList(JobQueue->PopQueue); - delete JobQueue; - } + EraseList(JobQueue->PushQueue); + EraseList(JobQueue->PopQueue); + delete JobQueue; + } template <typename U> void Enqueue(U&& data) { TListNode* newNode = new TListNode(std::forward<U>(data)); @@ -268,21 +268,21 @@ public: for (++i; i != dataEnd; ++i) { TListNode* nextNode = node; node = new TListNode(*i, nextNode); - } + } EnqueueImpl(node, tail); - } + } bool Dequeue(T* data) { TRootNode* newRoot = nullptr; - TListInvertor listInvertor; - AsyncRef(); - for (;;) { + TListInvertor listInvertor; + AsyncRef(); + for (;;) { TRootNode* curRoot = AtomicGet(JobQueue); TListNode* tail = AtomicGet(curRoot->PopQueue); - if (tail) { - // has elems to pop - if (!newRoot) - newRoot = new TRootNode; - + if (tail) { + // has elems to pop + if (!newRoot) + newRoot = new TRootNode; + AtomicSet(newRoot->PushQueue, AtomicGet(curRoot->PushQueue)); AtomicSet(newRoot->PopQueue, AtomicGet(tail->Next)); newRoot->CopyCounter(curRoot); @@ -291,19 +291,19 @@ public: if (AtomicCas(&JobQueue, newRoot, curRoot)) { *data = std::move(tail->Data); AtomicSet(tail->Next, nullptr); - AsyncUnref(curRoot, tail); - return true; - } - continue; - } + AsyncUnref(curRoot, tail); + return true; + } + continue; + } if (AtomicGet(curRoot->PushQueue) == nullptr) { - delete newRoot; - AsyncUnref(); - return false; // no elems to pop - } - - if (!newRoot) - newRoot = new TRootNode; + delete newRoot; + AsyncUnref(); + return false; // no elems to pop + } + + if (!newRoot) + newRoot = new TRootNode; AtomicSet(newRoot->PushQueue, nullptr); listInvertor.DoCopy(AtomicGet(curRoot->PushQueue)); AtomicSet(newRoot->PopQueue, listInvertor.Copy); @@ -311,13 +311,13 @@ public: Y_ASSERT(AtomicGet(curRoot->PopQueue) == nullptr); if (AtomicCas(&JobQueue, newRoot, curRoot)) { newRoot = nullptr; - listInvertor.CopyWasUsed(); + listInvertor.CopyWasUsed(); AsyncDel(curRoot, AtomicGet(curRoot->PushQueue)); - } else { + } else { AtomicSet(newRoot->PopQueue, nullptr); - } - } - } + } + } + } template <typename TCollection> void DequeueAll(TCollection* res) { AsyncRef(); @@ -344,12 +344,12 @@ public: AsyncUnref(curRoot, toDeleteHead); } bool IsEmpty() { - AsyncRef(); + AsyncRef(); TRootNode* curRoot = AtomicGet(JobQueue); bool res = AtomicGet(curRoot->PushQueue) == nullptr && AtomicGet(curRoot->PopQueue) == nullptr; - AsyncUnref(); - return res; - } + AsyncUnref(); + return res; + } TCounter GetCounter() { AsyncRef(); TRootNode* curRoot = AtomicGet(JobQueue); @@ -357,7 +357,7 @@ public: AsyncUnref(); return res; } -}; +}; template <class T, class TCounter> class TAutoLockFreeQueue { diff --git a/util/thread/lfstack.h b/util/thread/lfstack.h index ca3d95f3c3..a85b6100b6 100644 --- a/util/thread/lfstack.h +++ b/util/thread/lfstack.h @@ -1,16 +1,16 @@ #pragma once - + #include <util/generic/noncopyable.h> -#include <util/system/atomic.h> - -////////////////////////////// -// lock free lifo stack +#include <util/system/atomic.h> + +////////////////////////////// +// lock free lifo stack template <class T> class TLockFreeStack: TNonCopyable { struct TNode { - T Value; + T Value; TNode* Next; - + TNode() = default; template <class U> @@ -19,29 +19,29 @@ class TLockFreeStack: TNonCopyable { , Next(nullptr) { } - }; - + }; + TNode* Head; TNode* FreePtr; - TAtomic DequeueCount; - + TAtomic DequeueCount; + void TryToFreeMemory() { TNode* current = AtomicGet(FreePtr); - if (!current) - return; + if (!current) + return; if (AtomicAdd(DequeueCount, 0) == 1) { - // node current is in free list, we are the last thread so try to cleanup + // node current is in free list, we are the last thread so try to cleanup if (AtomicCas(&FreePtr, (TNode*)nullptr, current)) - EraseList(current); - } - } + EraseList(current); + } + } void EraseList(TNode* volatile p) { - while (p) { + while (p) { TNode* next = p->Next; - delete p; - p = next; - } - } + delete p; + p = next; + } + } void EnqueueImpl(TNode* volatile head, TNode* volatile tail) { for (;;) { tail->Next = AtomicGet(Head); @@ -55,7 +55,7 @@ class TLockFreeStack: TNonCopyable { EnqueueImpl(node, node); } -public: +public: TLockFreeStack() : Head(nullptr) , FreePtr(nullptr) @@ -63,9 +63,9 @@ public: { } ~TLockFreeStack() { - EraseList(Head); - EraseList(FreePtr); - } + EraseList(Head); + EraseList(FreePtr); + } void Enqueue(const T& t) { EnqueueImpl(t); @@ -83,7 +83,7 @@ public: void EnqueueAll(TIter dataBegin, TIter dataEnd) { if (dataBegin == dataEnd) { return; - } + } TIter i = dataBegin; TNode* volatile node = new TNode(*i); TNode* volatile tail = node; @@ -94,33 +94,33 @@ public: node->Next = nextNode; } EnqueueImpl(node, tail); - } + } bool Dequeue(T* res) { AtomicAdd(DequeueCount, 1); for (TNode* current = AtomicGet(Head); current; current = AtomicGet(Head)) { if (AtomicCas(&Head, AtomicGet(current->Next), current)) { *res = std::move(current->Value); - // delete current; // ABA problem - // even more complex node deletion - TryToFreeMemory(); + // delete current; // ABA problem + // even more complex node deletion + TryToFreeMemory(); if (AtomicAdd(DequeueCount, -1) == 0) { - // no other Dequeue()s, can safely reclaim memory - delete current; - } else { - // Dequeue()s in progress, put node to free list + // no other Dequeue()s, can safely reclaim memory + delete current; + } else { + // Dequeue()s in progress, put node to free list for (;;) { AtomicSet(current->Next, AtomicGet(FreePtr)); if (AtomicCas(&FreePtr, current, current->Next)) - break; - } - } - return true; - } - } - TryToFreeMemory(); + break; + } + } + return true; + } + } + TryToFreeMemory(); AtomicAdd(DequeueCount, -1); - return false; - } + return false; + } // add all elements to *res // elements are returned in order of dequeue (top to bottom; see example in unittest) template <typename TCollection> @@ -184,5 +184,5 @@ public: bool IsEmpty() { AtomicAdd(DequeueCount, 0); // mem barrier return AtomicGet(Head) == nullptr; // without lock, so result is approximate - } -}; + } +}; |