aboutsummaryrefslogtreecommitdiffstats
path: root/library/cpp/containers/comptrie
diff options
context:
space:
mode:
authorRuslan Kovalev <ruslan.a.kovalev@gmail.com>2022-02-10 16:46:45 +0300
committerDaniil Cherednik <dcherednik@yandex-team.ru>2022-02-10 16:46:45 +0300
commit9123176b341b6f2658cff5132482b8237c1416c8 (patch)
tree49e222ea1c5804306084bb3ae065bb702625360f /library/cpp/containers/comptrie
parent59e19371de37995fcb36beb16cd6ec030af960bc (diff)
downloadydb-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')
-rw-r--r--library/cpp/containers/comptrie/array_with_size.h2
-rw-r--r--library/cpp/containers/comptrie/comptrie.h6
-rw-r--r--library/cpp/containers/comptrie/comptrie_builder.h26
-rw-r--r--library/cpp/containers/comptrie/comptrie_builder.inl54
-rw-r--r--library/cpp/containers/comptrie/comptrie_impl.h10
-rw-r--r--library/cpp/containers/comptrie/comptrie_trie.h196
-rw-r--r--library/cpp/containers/comptrie/comptrie_ut.cpp30
-rw-r--r--library/cpp/containers/comptrie/leaf_skipper.h2
-rw-r--r--library/cpp/containers/comptrie/make_fast_layout.cpp2
-rw-r--r--library/cpp/containers/comptrie/make_fast_layout.h2
-rw-r--r--library/cpp/containers/comptrie/minimize.cpp6
-rw-r--r--library/cpp/containers/comptrie/minimize.h2
-rw-r--r--library/cpp/containers/comptrie/node.cpp4
-rw-r--r--library/cpp/containers/comptrie/node.h2
-rw-r--r--library/cpp/containers/comptrie/opaque_trie_iterator.cpp6
-rw-r--r--library/cpp/containers/comptrie/opaque_trie_iterator.h4
-rw-r--r--library/cpp/containers/comptrie/ut/ya.make2
-rw-r--r--library/cpp/containers/comptrie/ya.make4
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()