diff options
author | Ruslan Kovalev <ruslan.a.kovalev@gmail.com> | 2022-02-10 16:46:45 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:46:45 +0300 |
commit | 9123176b341b6f2658cff5132482b8237c1416c8 (patch) | |
tree | 49e222ea1c5804306084bb3ae065bb702625360f /library/cpp/containers/comptrie | |
parent | 59e19371de37995fcb36beb16cd6ec030af960bc (diff) | |
download | ydb-9123176b341b6f2658cff5132482b8237c1416c8.tar.gz |
Restoring authorship annotation for Ruslan Kovalev <ruslan.a.kovalev@gmail.com>. Commit 2 of 2.
Diffstat (limited to 'library/cpp/containers/comptrie')
18 files changed, 180 insertions, 180 deletions
diff --git a/library/cpp/containers/comptrie/array_with_size.h b/library/cpp/containers/comptrie/array_with_size.h index 267692b8bc..36e61c7410 100644 --- a/library/cpp/containers/comptrie/array_with_size.h +++ b/library/cpp/containers/comptrie/array_with_size.h @@ -1,4 +1,4 @@ -#pragma once +#pragma once #include <util/generic/ptr.h> #include <util/generic/noncopyable.h> diff --git a/library/cpp/containers/comptrie/comptrie.h b/library/cpp/containers/comptrie/comptrie.h index b9a4c65280..f77024327e 100644 --- a/library/cpp/containers/comptrie/comptrie.h +++ b/library/cpp/containers/comptrie/comptrie.h @@ -1,4 +1,4 @@ -#pragma once +#pragma once -#include "comptrie_trie.h" -#include "comptrie_builder.h" +#include "comptrie_trie.h" +#include "comptrie_builder.h" diff --git a/library/cpp/containers/comptrie/comptrie_builder.h b/library/cpp/containers/comptrie/comptrie_builder.h index 8254c4f592..cf7d2e39a3 100644 --- a/library/cpp/containers/comptrie/comptrie_builder.h +++ b/library/cpp/containers/comptrie/comptrie_builder.h @@ -1,4 +1,4 @@ -#pragma once +#pragma once #include "comptrie_packer.h" #include "minimize.h" @@ -17,7 +17,7 @@ // then all the keys that we add between these two also have the same prefix. // Actually in this mode the builder can accept even more freely ordered input, // but for input as above it is guaranteed to work. -enum ECompactTrieBuilderFlags { +enum ECompactTrieBuilderFlags { CTBF_NONE = 0, CTBF_PREFIX_GROUPED = 1 << 0, CTBF_VERBOSE = 1 << 1, @@ -25,7 +25,7 @@ enum ECompactTrieBuilderFlags { }; using TCompactTrieBuilderFlags = ECompactTrieBuilderFlags; - + inline TCompactTrieBuilderFlags operator|(TCompactTrieBuilderFlags first, TCompactTrieBuilderFlags second) { return static_cast<TCompactTrieBuilderFlags>(static_cast<int>(first) | second); } @@ -51,13 +51,13 @@ public: // All Add.. methods return true if it was a new key, false if the key already existed. bool Add(const TSymbol* key, size_t keylen, const TData& value); - bool Add(const TKeyBuf& key, const TData& value) { + bool Add(const TKeyBuf& key, const TData& value) { return Add(key.data(), key.size(), value); } // add already serialized data bool AddPtr(const TSymbol* key, size_t keylen, const char* data); - bool AddPtr(const TKeyBuf& key, const char* data) { + bool AddPtr(const TKeyBuf& key, const char* data) { return AddPtr(key.data(), key.size(), data); } @@ -88,8 +88,8 @@ public: return Save(out); } - void Clear(); // Returns all memory to the system and resets the builder state. - + void Clear(); // Returns all memory to the system and resets the builder state. + size_t GetEntryCount() const; size_t GetNodeCount() const; @@ -98,7 +98,7 @@ public: return Impl->MeasureByteSize(); } -protected: +protected: class TCompactTrieBuilderImpl; THolder<TCompactTrieBuilderImpl> Impl; }; @@ -133,12 +133,12 @@ size_t CompactTrieMinimize(IOutputStream& os, const TTrieBuilder& builder, bool // by Maxim Babenko and Ivan Puzyrevsky. The difference is that when we cut the tree into levels // two nodes connected by a forward link are put into the same level (because they usually lie near each other in the original tree). // The original paper (describing the layout in Section 2.1) is: -// Michael A. Bender, Erik D. Demaine, Martin Farach-Colton. Cache-Oblivious B-Trees -// SIAM Journal on Computing, volume 35, number 2, 2005, pages 341-358. +// Michael A. Bender, Erik D. Demaine, Martin Farach-Colton. Cache-Oblivious B-Trees +// SIAM Journal on Computing, volume 35, number 2, 2005, pages 341-358. // Available on the web: http://erikdemaine.org/papers/CacheObliviousBTrees_SICOMP/ -// Or: Michael A. Bender, Erik D. Demaine, and Martin Farach-Colton. Cache-Oblivious B-Trees -// Proceedings of the 41st Annual Symposium -// on Foundations of Computer Science (FOCS 2000), Redondo Beach, California, November 12-14, 2000, pages 399-409. +// Or: Michael A. Bender, Erik D. Demaine, and Martin Farach-Colton. Cache-Oblivious B-Trees +// Proceedings of the 41st Annual Symposium +// on Foundations of Computer Science (FOCS 2000), Redondo Beach, California, November 12-14, 2000, pages 399-409. // Available on the web: http://erikdemaine.org/papers/FOCS2000b/ // (there is not much difference between these papers, actually). // diff --git a/library/cpp/containers/comptrie/comptrie_builder.inl b/library/cpp/containers/comptrie/comptrie_builder.inl index ea151b946e..f273fa6571 100644 --- a/library/cpp/containers/comptrie/comptrie_builder.inl +++ b/library/cpp/containers/comptrie/comptrie_builder.inl @@ -1,6 +1,6 @@ -#pragma once +#pragma once -#include "comptrie_impl.h" +#include "comptrie_impl.h" #include "comptrie_trie.h" #include "make_fast_layout.h" #include "array_with_size.h" @@ -26,7 +26,7 @@ template <class T, class D, class S> class TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl { -protected: +protected: TMemoryPool Pool; size_t PayloadSize; THolder<TFixedSizeAllocator> NodeAllocator; @@ -45,7 +45,7 @@ protected: DATA_IN_MEMPOOL, }; -protected: +protected: void ConvertSymbolArrayToChar(const TSymbol* key, size_t keylen, TTempBuf& buf, size_t ckeylen) const; void NodeLinkTo(TNode* thiz, const TBlob& label, TNode* node); TNode* NodeForwardAdd(TNode* thiz, const char* label, size_t len, size_t& passed, size_t* nodeCount); @@ -335,10 +335,10 @@ public: union { char ArcsData[CONSTEXPR_MAX3(sizeof(TArcSet), sizeof(TBufferedSubtree), sizeof(TSubtreeInFile))]; - union { - void* Data1; - long long int Data2; - } Aligner; + union { + void* Data1; + long long int Data2; + } Aligner; }; inline ISubtree* Subtree() { @@ -451,7 +451,7 @@ bool TCompactTrieBuilder<T, D, S>::Find(const TSymbol* key, size_t keylen, TData } template <class T, class D, class S> -bool TCompactTrieBuilder<T, D, S>::FindLongestPrefix( +bool TCompactTrieBuilder<T, D, S>::FindLongestPrefix( const TSymbol* key, size_t keylen, size_t* prefixlen, TData* value) const { return Impl->FindLongestPrefix(key, keylen, prefixlen, value); } @@ -502,8 +502,8 @@ TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::~TCompactTrieBuilderImpl( } template <class T, class D, class S> -void TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::ConvertSymbolArrayToChar( - const TSymbol* key, size_t keylen, TTempBuf& buf, size_t buflen) const { +void TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::ConvertSymbolArrayToChar( + const TSymbol* key, size_t keylen, TTempBuf& buf, size_t buflen) const { char* ckeyptr = buf.Data(); for (size_t i = 0; i < keylen; ++i) { @@ -544,7 +544,7 @@ void TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::NodeReleasePayload(T template <class T, class D, class S> bool TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::AddEntry( - const TSymbol* key, size_t keylen, const TData& value) { + const TSymbol* key, size_t keylen, const TData& value) { size_t datalen = Packer.MeasureLeaf(value); bool isNewAddition = false; @@ -555,7 +555,7 @@ bool TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::AddEntry( template <class T, class D, class S> bool TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::AddEntryPtr( - const TSymbol* key, size_t keylen, const char* value) { + const TSymbol* key, size_t keylen, const char* value) { size_t datalen = Packer.SkipLeaf(value); bool isNewAddition = false; @@ -597,8 +597,8 @@ bool TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::AddSubtreeInBuffer( } template <class T, class D, class S> -typename TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::TNode* - TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::AddEntryForSomething( +typename TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::TNode* + TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::AddEntryForSomething( const TSymbol* key, size_t keylen, bool& isNewAddition) { using namespace NCompactTrie; @@ -684,7 +684,7 @@ bool TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::FindEntryImpl(const } template <class T, class D, class S> -bool TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::FindLongestPrefix( +bool TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::FindLongestPrefix( const TSymbol* key, size_t keylen, size_t* prefixlen, TData* value) const { using namespace NCompactTrie; @@ -778,8 +778,8 @@ size_t TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::GetNodeCount() con } template <class T, class D, class S> -typename TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::TNode* - TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::NodeForwardAdd( +typename TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::TNode* + TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::NodeForwardAdd( TNode* thiz, const char* label, size_t len, size_t& passed, size_t* nodeCount) { typename TNode::TArcSet* arcSet = dynamic_cast<typename TNode::TArcSet*>(thiz->Subtree()); if (!arcSet) @@ -892,8 +892,8 @@ TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::TArc::TArc(const TBlob& l {} template <class T, class D, class S> -ui64 TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::ArcMeasure( - const TArc* thiz, size_t leftsize, size_t rightsize) const { +ui64 TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::ArcMeasure( + const TArc* thiz, size_t leftsize, size_t rightsize) const { using namespace NCompactTrie; size_t coresize = 2 + NodeMeasureLeafValue(thiz->Node); // 2 == (char + flags) @@ -978,8 +978,8 @@ ui64 TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::ArcSaveAndDestroy(co // TCompactTrieBuilder::TCompactTrieBuilderImpl::TNode::TArcSet template <class T, class D, class S> -typename TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::TNode::TArcSet::iterator - TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::TNode::TArcSet::Find(char ch) { +typename TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::TNode::TArcSet::iterator + TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::TNode::TArcSet::Find(char ch) { using namespace NCompTriePrivate; iterator it = LowerBound(this->begin(), this->end(), ch, TCmp()); @@ -1083,12 +1083,12 @@ size_t CompactTrieMinimize(IOutputStream& os, const TTrieBuilder& builder, bool // by Maxim Babenko and Ivan Puzyrevsky. The difference is that when we cut the tree into levels // two nodes connected by a forward link are put into the same level (because they usually lie near each other in the original tree). // The original paper (describing the layout in Section 2.1) is: -// Michael A. Bender, Erik D. Demaine, Martin Farach-Colton. Cache-Oblivious B-Trees -// SIAM Journal on Computing, volume 35, number 2, 2005, pages 341-358. +// Michael A. Bender, Erik D. Demaine, Martin Farach-Colton. Cache-Oblivious B-Trees +// SIAM Journal on Computing, volume 35, number 2, 2005, pages 341-358. // Available on the web: http://erikdemaine.org/papers/CacheObliviousBTrees_SICOMP/ -// Or: Michael A. Bender, Erik D. Demaine, and Martin Farach-Colton. Cache-Oblivious B-Trees -// Proceedings of the 41st Annual Symposium -// on Foundations of Computer Science (FOCS 2000), Redondo Beach, California, November 12-14, 2000, pages 399-409. +// Or: Michael A. Bender, Erik D. Demaine, and Martin Farach-Colton. Cache-Oblivious B-Trees +// Proceedings of the 41st Annual Symposium +// on Foundations of Computer Science (FOCS 2000), Redondo Beach, California, November 12-14, 2000, pages 399-409. // Available on the web: http://erikdemaine.org/papers/FOCS2000b/ // (there is not much difference between these papers, actually). // diff --git a/library/cpp/containers/comptrie/comptrie_impl.h b/library/cpp/containers/comptrie/comptrie_impl.h index 37e5fa6221..f41c38311a 100644 --- a/library/cpp/containers/comptrie/comptrie_impl.h +++ b/library/cpp/containers/comptrie/comptrie_impl.h @@ -1,11 +1,11 @@ -#pragma once +#pragma once #include <util/stream/output.h> -#ifndef COMPTRIE_DATA_CHECK -#define COMPTRIE_DATA_CHECK 1 -#endif - +#ifndef COMPTRIE_DATA_CHECK +#define COMPTRIE_DATA_CHECK 1 +#endif + // NCompactTrie namespace NCompactTrie { diff --git a/library/cpp/containers/comptrie/comptrie_trie.h b/library/cpp/containers/comptrie/comptrie_trie.h index 5049be2831..40ec1e52b3 100644 --- a/library/cpp/containers/comptrie/comptrie_trie.h +++ b/library/cpp/containers/comptrie/comptrie_trie.h @@ -1,6 +1,6 @@ -#pragma once +#pragma once -#include "comptrie_impl.h" +#include "comptrie_impl.h" #include "comptrie_packer.h" #include "opaque_trie_iterator.h" #include "leaf_skipper.h" @@ -28,7 +28,7 @@ class TSearchIterator; template <class TTrie> class TPrefixIterator; -// in case of <char> specialization cannot distinguish between "" and "\0" keys +// in case of <char> specialization cannot distinguish between "" and "\0" keys template <class T = char, class D = ui64, class S = TCompactTriePacker<D>> class TCompactTrie { public: @@ -45,8 +45,8 @@ public: typedef TCompactTrieBuilder<T, D, S> TBuilder; -protected: - TBlob DataHolder; +protected: + TBlob DataHolder; const char* EmptyValue = nullptr; TPacker Packer; NCompactTrie::TPackerLeafSkipper<TPacker> Skipper = &Packer; // This should be true for every constructor. @@ -70,12 +70,12 @@ public: TCompactTrie& operator=(const TCompactTrie& other); TCompactTrie& operator=(TCompactTrie&& other) noexcept; - explicit operator bool() const { - return !IsEmpty(); - } - + explicit operator bool() const { + return !IsEmpty(); + } + void Init(const char* d, size_t len, TPacker packer = TPacker()); - void Init(const TBlob& data, TPacker packer = TPacker()); + void Init(const TBlob& data, TPacker packer = TPacker()); bool IsInitialized() const; bool IsEmpty() const; @@ -91,10 +91,10 @@ public: ythrow yexception() << "key " << TKey(key, keylen).Quote() << " not found in trie"; return value; } - TData Get(const TKeyBuf& key) const { + TData Get(const TKeyBuf& key) const { return Get(key.data(), key.size()); } - TData GetDefault(const TKeyBuf& key, const TData& def) const { + TData GetDefault(const TKeyBuf& key, const TData& def) const { TData value; if (!Find(key.data(), key.size(), &value)) return def; @@ -102,7 +102,7 @@ public: return value; } - const TBlob& Data() const { + const TBlob& Data() const { return DataHolder; }; @@ -119,7 +119,7 @@ public: } void FindPhrases(const TSymbol* key, size_t keylen, TPhraseMatchVector& matches, TSymbol separator = TSymbol(' ')) const; - void FindPhrases(const TKeyBuf& key, TPhraseMatchVector& matches, TSymbol separator = TSymbol(' ')) const { + void FindPhrases(const TKeyBuf& key, TPhraseMatchVector& matches, TSymbol separator = TSymbol(' ')) const { return FindPhrases(key.data(), key.size(), matches, separator); } bool FindLongestPrefix(const TSymbol* key, size_t keylen, size_t* prefixLen, TData* value = nullptr, bool* hasNext = nullptr) const; @@ -128,12 +128,12 @@ public: } // Return trie, containing all tails for the given key - inline TCompactTrie<T, D, S> FindTails(const TSymbol* key, size_t keylen) const; - TCompactTrie<T, D, S> FindTails(const TKeyBuf& key) const { + inline TCompactTrie<T, D, S> FindTails(const TSymbol* key, size_t keylen) const; + TCompactTrie<T, D, S> FindTails(const TKeyBuf& key) const { return FindTails(key.data(), key.size()); } - bool FindTails(const TSymbol* key, size_t keylen, TCompactTrie<T, D, S>& res) const; - bool FindTails(const TKeyBuf& key, TCompactTrie<T, D, S>& res) const { + bool FindTails(const TSymbol* key, size_t keylen, TCompactTrie<T, D, S>& res) const; + bool FindTails(const TKeyBuf& key, TCompactTrie<T, D, S>& res) const { return FindTails(key.data(), key.size(), res); } @@ -164,7 +164,7 @@ public: TValueType operator*(); TKey GetKey() const; - size_t GetKeySize() const; + size_t GetKeySize() const; TData GetValue() const; void GetValue(TData& data) const; const char* GetValuePtr() const; @@ -180,22 +180,22 @@ public: TConstIterator end() const; // Returns an iterator pointing to the smallest key in the trie >= the argument. - // TODO: misleading name. Should be called LowerBound for consistency with stl. + // TODO: misleading name. Should be called LowerBound for consistency with stl. // No. It is the STL that has a misleading name. // LowerBound of X cannot be greater than X. - TConstIterator UpperBound(const TKeyBuf& key) const; + TConstIterator UpperBound(const TKeyBuf& key) const; void Print(IOutputStream& os); - size_t Size() const; - + size_t Size() const; + friend class NCompactTrie::TFirstSymbolIterator<TCompactTrie>; friend class TSearchIterator<TCompactTrie>; friend class TPrefixIterator<TCompactTrie>; -protected: +protected: explicit TCompactTrie(const char* emptyValue); - TCompactTrie(const TBlob& data, const char* emptyValue, TPacker packer = TPacker()); + TCompactTrie(const TBlob& data, const char* emptyValue, TPacker packer = TPacker()); bool LookupLongestPrefix(const TSymbol* key, size_t keylen, size_t& prefixLen, const char*& valuepos, bool& hasNext) const; bool LookupLongestPrefix(const TSymbol* key, size_t keylen, size_t& prefixLen, const char*& valuepos) const { @@ -221,36 +221,36 @@ public: // TCompactTrie -template <class T, class D, class S> -TCompactTrie<T, D, S>::TCompactTrie(const TBlob& data, TPacker packer) +template <class T, class D, class S> +TCompactTrie<T, D, S>::TCompactTrie(const TBlob& data, TPacker packer) : DataHolder(data) , Packer(packer) { Init(data, packer); } -template <class T, class D, class S> -TCompactTrie<T, D, S>::TCompactTrie(const char* d, size_t len, TPacker packer) +template <class T, class D, class S> +TCompactTrie<T, D, S>::TCompactTrie(const char* d, size_t len, TPacker packer) : Packer(packer) { Init(d, len, packer); } -template <class T, class D, class S> -TCompactTrie<T, D, S>::TCompactTrie(const char* emptyValue) +template <class T, class D, class S> +TCompactTrie<T, D, S>::TCompactTrie(const char* emptyValue) : EmptyValue(emptyValue) { } -template <class T, class D, class S> -TCompactTrie<T, D, S>::TCompactTrie(const TBlob& data, const char* emptyValue, TPacker packer) +template <class T, class D, class S> +TCompactTrie<T, D, S>::TCompactTrie(const TBlob& data, const char* emptyValue, TPacker packer) : DataHolder(data) , EmptyValue(emptyValue) , Packer(packer) { } -template <class T, class D, class S> +template <class T, class D, class S> TCompactTrie<T, D, S>::TCompactTrie(const TCompactTrie& other) : DataHolder(other.DataHolder) , EmptyValue(other.EmptyValue) @@ -287,19 +287,19 @@ TCompactTrie<T, D, S>& TCompactTrie<T, D, S>::operator=(TCompactTrie&& other) no } template <class T, class D, class S> -void TCompactTrie<T, D, S>::Init(const char* d, size_t len, TPacker packer) { - Init(TBlob::NoCopy(d, len), packer); +void TCompactTrie<T, D, S>::Init(const char* d, size_t len, TPacker packer) { + Init(TBlob::NoCopy(d, len), packer); } -template <class T, class D, class S> -void TCompactTrie<T, D, S>::Init(const TBlob& data, TPacker packer) { +template <class T, class D, class S> +void TCompactTrie<T, D, S>::Init(const TBlob& data, TPacker packer) { using namespace NCompactTrie; DataHolder = data; Packer = packer; const char* datapos = DataHolder.AsCharPtr(); - size_t len = DataHolder.Length(); + size_t len = DataHolder.Length(); if (!len) return; @@ -313,17 +313,17 @@ void TCompactTrie<T, D, S>::Init(const TBlob& data, TPacker packer) { } } -template <class T, class D, class S> -bool TCompactTrie<T, D, S>::IsInitialized() const { +template <class T, class D, class S> +bool TCompactTrie<T, D, S>::IsInitialized() const { return DataHolder.Data() != nullptr; } -template <class T, class D, class S> -bool TCompactTrie<T, D, S>::IsEmpty() const { +template <class T, class D, class S> +bool TCompactTrie<T, D, S>::IsEmpty() const { return DataHolder.Size() == 0 && EmptyValue == nullptr; } -template <class T, class D, class S> +template <class T, class D, class S> bool TCompactTrie<T, D, S>::Find(const TSymbol* key, size_t keylen, TData* value) const { size_t prefixLen = 0; const char* valuepos = nullptr; @@ -335,20 +335,20 @@ bool TCompactTrie<T, D, S>::Find(const TSymbol* key, size_t keylen, TData* value return true; } -template <class T, class D, class S> -void TCompactTrie<T, D, S>::FindPhrases(const TSymbol* key, size_t keylen, TPhraseMatchVector& matches, TSymbol separator) const { +template <class T, class D, class S> +void TCompactTrie<T, D, S>::FindPhrases(const TSymbol* key, size_t keylen, TPhraseMatchVector& matches, TSymbol separator) const { LookupPhrases(DataHolder.AsCharPtr(), DataHolder.Length(), key, keylen, matches, separator); } -template <class T, class D, class S> -inline TCompactTrie<T, D, S> TCompactTrie<T, D, S>::FindTails(const TSymbol* key, size_t keylen) const { - TCompactTrie<T, D, S> ret; +template <class T, class D, class S> +inline TCompactTrie<T, D, S> TCompactTrie<T, D, S>::FindTails(const TSymbol* key, size_t keylen) const { + TCompactTrie<T, D, S> ret; FindTails(key, keylen, ret); return ret; } -template <class T, class D, class S> -bool TCompactTrie<T, D, S>::FindTails(const TSymbol* key, size_t keylen, TCompactTrie<T, D, S>& res) const { +template <class T, class D, class S> +bool TCompactTrie<T, D, S>::FindTails(const TSymbol* key, size_t keylen, TCompactTrie<T, D, S>& res) const { using namespace NCompactTrie; size_t len = DataHolder.Length(); @@ -376,7 +376,7 @@ bool TCompactTrie<T, D, S>::FindTails(const TSymbol* key, size_t keylen, TCompac if (key == keyend) { if (datapos) { Y_ASSERT(datapos >= datastart); - res = TCompactTrie<T, D, S>(TBlob::NoCopy(datapos, dataend - datapos), value); + res = TCompactTrie<T, D, S>(TBlob::NoCopy(datapos, dataend - datapos), value); } else { res = TCompactTrie<T, D, S>(value); } @@ -389,11 +389,11 @@ bool TCompactTrie<T, D, S>::FindTails(const TSymbol* key, size_t keylen, TCompac return false; } -template <class T, class D, class S> +template <class T, class D, class S> inline bool TCompactTrie<T, D, S>::FindTails(TSymbol label, TCompactTrie<T, D, S>& res) const { using namespace NCompactTrie; - const size_t len = DataHolder.Length(); + const size_t len = DataHolder.Length(); if (!len) return false; @@ -415,43 +415,43 @@ inline bool TCompactTrie<T, D, S>::FindTails(TSymbol label, TCompactTrie<T, D, S return true; } -template <class T, class D, class S> -typename TCompactTrie<T, D, S>::TConstIterator TCompactTrie<T, D, S>::Begin() const { +template <class T, class D, class S> +typename TCompactTrie<T, D, S>::TConstIterator TCompactTrie<T, D, S>::Begin() const { NCompactTrie::TOpaqueTrie self(DataHolder.AsCharPtr(), DataHolder.Length(), Skipper); return TConstIterator(self, EmptyValue, false, Packer); } -template <class T, class D, class S> +template <class T, class D, class S> typename TCompactTrie<T, D, S>::TConstIterator TCompactTrie<T, D, S>::begin() const { return Begin(); } template <class T, class D, class S> -typename TCompactTrie<T, D, S>::TConstIterator TCompactTrie<T, D, S>::End() const { +typename TCompactTrie<T, D, S>::TConstIterator TCompactTrie<T, D, S>::End() const { NCompactTrie::TOpaqueTrie self(DataHolder.AsCharPtr(), DataHolder.Length(), Skipper); return TConstIterator(self, EmptyValue, true, Packer); } -template <class T, class D, class S> +template <class T, class D, class S> typename TCompactTrie<T, D, S>::TConstIterator TCompactTrie<T, D, S>::end() const { return End(); } template <class T, class D, class S> -size_t TCompactTrie<T, D, S>::Size() const { - size_t res = 0; - for (TConstIterator it = Begin(); it != End(); ++it) - ++res; - return res; -} - -template <class T, class D, class S> -typename TCompactTrie<T, D, S>::TConstIterator TCompactTrie<T, D, S>::UpperBound(const TKeyBuf& key) const { +size_t TCompactTrie<T, D, S>::Size() const { + size_t res = 0; + for (TConstIterator it = Begin(); it != End(); ++it) + ++res; + return res; +} + +template <class T, class D, class S> +typename TCompactTrie<T, D, S>::TConstIterator TCompactTrie<T, D, S>::UpperBound(const TKeyBuf& key) const { NCompactTrie::TOpaqueTrie self(DataHolder.AsCharPtr(), DataHolder.Length(), Skipper); return TConstIterator(self, EmptyValue, key, Packer); } -template <class T, class D, class S> +template <class T, class D, class S> void TCompactTrie<T, D, S>::Print(IOutputStream& os) { typedef typename ::TCompactTrieKeySelector<T>::TKeyBuf TSBuffer; for (TConstIterator it = Begin(); it != End(); ++it) { @@ -459,7 +459,7 @@ void TCompactTrie<T, D, S>::Print(IOutputStream& os) { } } -template <class T, class D, class S> +template <class T, class D, class S> bool TCompactTrie<T, D, S>::FindLongestPrefix(const TSymbol* key, size_t keylen, size_t* prefixLen, TData* value, bool* hasNext) const { const char* valuepos = nullptr; size_t tempPrefixLen = 0; @@ -474,12 +474,12 @@ bool TCompactTrie<T, D, S>::FindLongestPrefix(const TSymbol* key, size_t keylen, return found; } -template <class T, class D, class S> +template <class T, class D, class S> bool TCompactTrie<T, D, S>::LookupLongestPrefix(const TSymbol* key, size_t keylen, size_t& prefixLen, const char*& valuepos, bool& hasNext) const { using namespace NCompactTrie; const char* datapos = DataHolder.AsCharPtr(); - size_t len = DataHolder.Length(); + size_t len = DataHolder.Length(); prefixLen = 0; hasNext = false; @@ -526,8 +526,8 @@ bool TCompactTrie<T, D, S>::LookupLongestPrefix(const TSymbol* key, size_t keyle return found; } -template <class T, class D, class S> -void TCompactTrie<T, D, S>::LookupPhrases( +template <class T, class D, class S> +void TCompactTrie<T, D, S>::LookupPhrases( const char* datapos, size_t len, const TSymbol* key, size_t keylen, TVector<TPhraseMatch>& matches, TSymbol separator) const { using namespace NCompactTrie; @@ -570,14 +570,14 @@ TCompactTrieHolder<T, D, S>::TCompactTrieHolder(IInputStream& is, size_t len) //---------------------------------------------------------------------------------------------------------------- // TCompactTrie::TConstIterator -template <class T, class D, class S> +template <class T, class D, class S> TCompactTrie<T, D, S>::TConstIterator::TConstIterator(const TOpaqueTrie& trie, const char* emptyValue, bool atend, TPacker packer) : Packer(packer) , Impl(new TOpaqueTrieIterator(trie, emptyValue, atend)) { } -template <class T, class D, class S> +template <class T, class D, class S> TCompactTrie<T, D, S>::TConstIterator::TConstIterator(const TOpaqueTrie& trie, const char* emptyValue, const TKeyBuf& key, TPacker packer) : Packer(packer) , Impl(new TOpaqueTrieIterator(trie, emptyValue, true)) @@ -585,7 +585,7 @@ TCompactTrie<T, D, S>::TConstIterator::TConstIterator(const TOpaqueTrie& trie, c Impl->UpperBound<TSymbol>(key); } -template <class T, class D, class S> +template <class T, class D, class S> bool TCompactTrie<T, D, S>::TConstIterator::operator==(const TConstIterator& other) const { if (!Impl) return !other.Impl; @@ -594,70 +594,70 @@ bool TCompactTrie<T, D, S>::TConstIterator::operator==(const TConstIterator& oth return *Impl == *other.Impl; } -template <class T, class D, class S> +template <class T, class D, class S> bool TCompactTrie<T, D, S>::TConstIterator::operator!=(const TConstIterator& other) const { return !operator==(other); } -template <class T, class D, class S> -typename TCompactTrie<T, D, S>::TConstIterator& TCompactTrie<T, D, S>::TConstIterator::operator++() { +template <class T, class D, class S> +typename TCompactTrie<T, D, S>::TConstIterator& TCompactTrie<T, D, S>::TConstIterator::operator++() { Impl->Forward(); return *this; } -template <class T, class D, class S> -typename TCompactTrie<T, D, S>::TConstIterator TCompactTrie<T, D, S>::TConstIterator::operator++(int /*unused*/) { +template <class T, class D, class S> +typename TCompactTrie<T, D, S>::TConstIterator TCompactTrie<T, D, S>::TConstIterator::operator++(int /*unused*/) { TConstIterator copy(*this); Impl->Forward(); return copy; } -template <class T, class D, class S> -typename TCompactTrie<T, D, S>::TConstIterator& TCompactTrie<T, D, S>::TConstIterator::operator--() { +template <class T, class D, class S> +typename TCompactTrie<T, D, S>::TConstIterator& TCompactTrie<T, D, S>::TConstIterator::operator--() { Impl->Backward(); return *this; } -template <class T, class D, class S> -typename TCompactTrie<T, D, S>::TConstIterator TCompactTrie<T, D, S>::TConstIterator::operator--(int /*unused*/) { +template <class T, class D, class S> +typename TCompactTrie<T, D, S>::TConstIterator TCompactTrie<T, D, S>::TConstIterator::operator--(int /*unused*/) { TConstIterator copy(*this); Impl->Backward(); return copy; } -template <class T, class D, class S> -typename TCompactTrie<T, D, S>::TValueType TCompactTrie<T, D, S>::TConstIterator::operator*() { +template <class T, class D, class S> +typename TCompactTrie<T, D, S>::TValueType TCompactTrie<T, D, S>::TConstIterator::operator*() { return TValueType(GetKey(), GetValue()); } -template <class T, class D, class S> +template <class T, class D, class S> typename TCompactTrie<T, D, S>::TKey TCompactTrie<T, D, S>::TConstIterator::GetKey() const { return Impl->GetKey<TSymbol>(); } -template <class T, class D, class S> +template <class T, class D, class S> size_t TCompactTrie<T, D, S>::TConstIterator::GetKeySize() const { return Impl->MeasureKey<TSymbol>(); -} - -template <class T, class D, class S> +} + +template <class T, class D, class S> const char* TCompactTrie<T, D, S>::TConstIterator::GetValuePtr() const { return Impl->GetValuePtr(); -} - -template <class T, class D, class S> +} + +template <class T, class D, class S> typename TCompactTrie<T, D, S>::TData TCompactTrie<T, D, S>::TConstIterator::GetValue() const { D data; GetValue(data); return data; } -template <class T, class D, class S> +template <class T, class D, class S> void TCompactTrie<T, D, S>::TConstIterator::GetValue(typename TCompactTrie<T, D, S>::TData& data) const { const char* ptr = GetValuePtr(); if (ptr) { Packer.UnpackLeaf(ptr, data); } else { - data = typename TCompactTrie<T, D, S>::TData(); + data = typename TCompactTrie<T, D, S>::TData(); } } diff --git a/library/cpp/containers/comptrie/comptrie_ut.cpp b/library/cpp/containers/comptrie/comptrie_ut.cpp index d73883afdc..74bee09b5d 100644 --- a/library/cpp/containers/comptrie/comptrie_ut.cpp +++ b/library/cpp/containers/comptrie/comptrie_ut.cpp @@ -36,7 +36,7 @@ private: UNIT_TEST(TestTrie8); UNIT_TEST(TestTrie16); UNIT_TEST(TestTrie32); - + UNIT_TEST(TestFastTrie8); UNIT_TEST(TestFastTrie16); UNIT_TEST(TestFastTrie32); @@ -44,7 +44,7 @@ private: UNIT_TEST(TestMinimizedTrie8); UNIT_TEST(TestMinimizedTrie16); UNIT_TEST(TestMinimizedTrie32); - + UNIT_TEST(TestFastMinimizedTrie8); UNIT_TEST(TestFastMinimizedTrie16); UNIT_TEST(TestFastMinimizedTrie32); @@ -52,11 +52,11 @@ private: UNIT_TEST(TestTrieIterator8); UNIT_TEST(TestTrieIterator16); UNIT_TEST(TestTrieIterator32); - + UNIT_TEST(TestMinimizedTrieIterator8); UNIT_TEST(TestMinimizedTrieIterator16); UNIT_TEST(TestMinimizedTrieIterator32); - + UNIT_TEST(TestPhraseSearch); UNIT_TEST(TestAddGet); UNIT_TEST(TestEmpty); @@ -169,11 +169,11 @@ private: public: void TestPackers(); - + void TestTrie8(); void TestTrie16(); void TestTrie32(); - + void TestFastTrie8(); void TestFastTrie16(); void TestFastTrie32(); @@ -181,7 +181,7 @@ public: void TestMinimizedTrie8(); void TestMinimizedTrie16(); void TestMinimizedTrie32(); - + void TestFastMinimizedTrie8(); void TestFastMinimizedTrie16(); void TestFastMinimizedTrie32(); @@ -189,11 +189,11 @@ public: void TestTrieIterator8(); void TestTrieIterator16(); void TestTrieIterator32(); - + void TestMinimizedTrieIterator8(); void TestMinimizedTrieIterator16(); void TestMinimizedTrieIterator32(); - + void TestPhraseSearch(); void TestAddGet(); void TestEmpty(); @@ -277,7 +277,7 @@ const char* TCompactTrieTest::SampleData[] = { }; template <class T> -typename TCompactTrie<T>::TKey MakeWideKey(const char* str, size_t len) { +typename TCompactTrie<T>::TKey MakeWideKey(const char* str, size_t len) { typename TCompactTrie<T>::TKey buffer; for (size_t i = 0; i < len; i++) { unsigned int ch = (str[i] & 0xFF); @@ -302,7 +302,7 @@ void TCompactTrieTest::CreateTrie(IOutputStream& out, bool minimize, bool useFas for (auto& i : SampleData) { size_t len = strlen(i); - + builder.Add(MakeWideKey<T>(i, len), len * 2); } @@ -362,7 +362,7 @@ void TCompactTrieTest::CheckData(const char* data, size_t datalen) { TCompactTrie<T> trie(data, datalen); UNIT_ASSERT_VALUES_EQUAL(Y_ARRAY_SIZE(SampleData), trie.Size()); - + for (auto& i : SampleData) { size_t len = strlen(i); ui64 value = 0; @@ -421,7 +421,7 @@ void TCompactTrieTest::CheckData(const char* data, size_t datalen) { template <class T> void TCompactTrieTest::CheckIterator(const char* data, size_t datalen) { - typedef typename TCompactTrie<T>::TKey TKey; + typedef typename TCompactTrie<T>::TKey TKey; typedef typename TCompactTrie<T>::TValueType TValue; TMap<TKey, ui64> stored; @@ -437,7 +437,7 @@ void TCompactTrieTest::CheckIterator(const char* data, size_t datalen) { size_t entry_count = 0; TMap<TKey, ui64> received; while (it != trie.End()) { - UNIT_ASSERT_VALUES_EQUAL(it.GetKeySize(), it.GetKey().size()); + UNIT_ASSERT_VALUES_EQUAL(it.GetKeySize(), it.GetKey().size()); received.insert(*it); items.push_back(*it); entry_count++; @@ -509,7 +509,7 @@ void TCompactTrieTest::TestTrie16() { void TCompactTrieTest::TestTrie32() { TestTrie<wchar32>(false, false); } - + void TCompactTrieTest::TestFastTrie8() { TestTrie<char>(false, true); } diff --git a/library/cpp/containers/comptrie/leaf_skipper.h b/library/cpp/containers/comptrie/leaf_skipper.h index e3aab8596f..3959258948 100644 --- a/library/cpp/containers/comptrie/leaf_skipper.h +++ b/library/cpp/containers/comptrie/leaf_skipper.h @@ -1,4 +1,4 @@ -#pragma once +#pragma once #include <cstddef> diff --git a/library/cpp/containers/comptrie/make_fast_layout.cpp b/library/cpp/containers/comptrie/make_fast_layout.cpp index 779146df1f..ade78d7899 100644 --- a/library/cpp/containers/comptrie/make_fast_layout.cpp +++ b/library/cpp/containers/comptrie/make_fast_layout.cpp @@ -4,7 +4,7 @@ #include "write_trie_backwards.h" #include "comptrie_impl.h" -#include <util/generic/hash.h> +#include <util/generic/hash.h> #include <util/generic/utility.h> // Lay the trie in memory in such a way that there are less cache misses when jumping from root to leaf. diff --git a/library/cpp/containers/comptrie/make_fast_layout.h b/library/cpp/containers/comptrie/make_fast_layout.h index f176de6b73..b8fab5d65b 100644 --- a/library/cpp/containers/comptrie/make_fast_layout.h +++ b/library/cpp/containers/comptrie/make_fast_layout.h @@ -1,4 +1,4 @@ -#pragma once +#pragma once #include "leaf_skipper.h" #include <cstddef> diff --git a/library/cpp/containers/comptrie/minimize.cpp b/library/cpp/containers/comptrie/minimize.cpp index 7346668c57..80d0b25217 100644 --- a/library/cpp/containers/comptrie/minimize.cpp +++ b/library/cpp/containers/comptrie/minimize.cpp @@ -4,7 +4,7 @@ #include "write_trie_backwards.h" #include "comptrie_impl.h" -#include <util/generic/hash.h> +#include <util/generic/hash.h> #include <util/generic/algorithm.h> namespace NCompactTrie { @@ -42,7 +42,7 @@ namespace NCompactTrie { if (Data.size() <= hikey) Data.resize(hikey + 1); - + TSizePairVector& sublist = Data[hikey]; for (auto& it : sublist) { @@ -296,7 +296,7 @@ namespace NCompactTrie { if (iit == subtries.end()) continue; // fast forward to the next available length value - + TOffsetList& batch = iit->second; TPieceComparer comparer(trie.Data, curlen); Sort(batch.begin(), batch.end(), comparer); diff --git a/library/cpp/containers/comptrie/minimize.h b/library/cpp/containers/comptrie/minimize.h index 7b991584e9..baaa431d04 100644 --- a/library/cpp/containers/comptrie/minimize.h +++ b/library/cpp/containers/comptrie/minimize.h @@ -1,4 +1,4 @@ -#pragma once +#pragma once #include "leaf_skipper.h" #include <cstddef> diff --git a/library/cpp/containers/comptrie/node.cpp b/library/cpp/containers/comptrie/node.cpp index 99a56fe83a..5fd22f15ec 100644 --- a/library/cpp/containers/comptrie/node.cpp +++ b/library/cpp/containers/comptrie/node.cpp @@ -1,6 +1,6 @@ #include "node.h" #include "leaf_skipper.h" -#include "comptrie_impl.h" +#include "comptrie_impl.h" #include <util/system/yassert.h> #include <util/generic/yexception.h> @@ -56,7 +56,7 @@ namespace NCompactTrie { Offsets[D_FINAL] = datapos - data; LeafLength = skipFunction.SkipLeaf(datapos); } - + CoreLength = 2 + leftsize + rightsize + LeafLength; if (flags & MT_NEXT) { size_t& forwardOffset = Offsets[D_NEXT]; diff --git a/library/cpp/containers/comptrie/node.h b/library/cpp/containers/comptrie/node.h index d4d90201ef..d6f4317db0 100644 --- a/library/cpp/containers/comptrie/node.h +++ b/library/cpp/containers/comptrie/node.h @@ -32,7 +32,7 @@ namespace NCompactTrie { size_t GetOffset() const { return Offset; } - + size_t GetLeafOffset() const { return Offsets[D_FINAL]; } diff --git a/library/cpp/containers/comptrie/opaque_trie_iterator.cpp b/library/cpp/containers/comptrie/opaque_trie_iterator.cpp index 1c812d9521..5fd3914be6 100644 --- a/library/cpp/containers/comptrie/opaque_trie_iterator.cpp +++ b/library/cpp/containers/comptrie/opaque_trie_iterator.cpp @@ -1,5 +1,5 @@ #include "opaque_trie_iterator.h" -#include "comptrie_impl.h" +#include "comptrie_impl.h" #include "node.h" namespace NCompactTrie { @@ -157,8 +157,8 @@ namespace NCompactTrie { } else { return Key.size() == 1 && Key[0] == '\0'; } - } - + } + size_t TForkStack::MeasureKey() const { size_t result = Key.size() + (TopHasLabelInKey() ? 1 : 0); if (result == 1 && HasEmptyKey()) { diff --git a/library/cpp/containers/comptrie/opaque_trie_iterator.h b/library/cpp/containers/comptrie/opaque_trie_iterator.h index e136270163..195da3c191 100644 --- a/library/cpp/containers/comptrie/opaque_trie_iterator.h +++ b/library/cpp/containers/comptrie/opaque_trie_iterator.h @@ -1,6 +1,6 @@ -#pragma once +#pragma once -#include "comptrie_impl.h" +#include "comptrie_impl.h" #include "node.h" #include "key_selector.h" #include "leaf_skipper.h" diff --git a/library/cpp/containers/comptrie/ut/ya.make b/library/cpp/containers/comptrie/ut/ya.make index ed3048f0e3..c4f4666009 100644 --- a/library/cpp/containers/comptrie/ut/ya.make +++ b/library/cpp/containers/comptrie/ut/ya.make @@ -1,7 +1,7 @@ UNITTEST_FOR(library/cpp/containers/comptrie) OWNER(alzobnin) - + SRCS( comptrie_ut.cpp ) diff --git a/library/cpp/containers/comptrie/ya.make b/library/cpp/containers/comptrie/ya.make index 4480a4f01b..81352da4b2 100644 --- a/library/cpp/containers/comptrie/ya.make +++ b/library/cpp/containers/comptrie/ya.make @@ -1,7 +1,7 @@ LIBRARY() OWNER(velavokr) - + SRCS( array_with_size.h chunked_helpers_trie.h @@ -29,7 +29,7 @@ PEERDIR( library/cpp/packers library/cpp/containers/compact_vector library/cpp/on_disk/chunks - util/draft + util/draft ) END() |