aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authormelton <melton@yandex-team.ru>2022-02-10 16:50:39 +0300
committerDaniil Cherednik <dcherednik@yandex-team.ru>2022-02-10 16:50:39 +0300
commita5ac8f28158417d00b78e19c6ccd17954884c61f (patch)
tree32d02eaee0c8ab494d8e2b2e3fe94c12b0fbcc45
parent351478f45647e95dd78ef336009c498001b6917f (diff)
downloadydb-a5ac8f28158417d00b78e19c6ccd17954884c61f.tar.gz
Restoring authorship annotation for <melton@yandex-team.ru>. Commit 1 of 2.
-rw-r--r--library/cpp/containers/comptrie/comptrie_trie.h28
-rw-r--r--library/cpp/containers/comptrie/comptrie_ut.cpp54
2 files changed, 41 insertions, 41 deletions
diff --git a/library/cpp/containers/comptrie/comptrie_trie.h b/library/cpp/containers/comptrie/comptrie_trie.h
index 40ec1e52b3..276583cb41 100644
--- a/library/cpp/containers/comptrie/comptrie_trie.h
+++ b/library/cpp/containers/comptrie/comptrie_trie.h
@@ -329,10 +329,10 @@ bool TCompactTrie<T, D, S>::Find(const TSymbol* key, size_t keylen, TData* value
const char* valuepos = nullptr;
bool hasNext;
if (!LookupLongestPrefix(key, keylen, prefixLen, valuepos, hasNext) || prefixLen != keylen)
- return false;
- if (value)
+ return false;
+ if (value)
Packer.UnpackLeaf(valuepos, *value);
- return true;
+ return true;
}
template <class T, class D, class S>
@@ -467,31 +467,31 @@ bool TCompactTrie<T, D, S>::FindLongestPrefix(const TSymbol* key, size_t keylen,
bool found = LookupLongestPrefix(key, keylen, tempPrefixLen, valuepos, tempHasNext);
if (prefixLen)
*prefixLen = tempPrefixLen;
- if (found && value)
+ if (found && value)
Packer.UnpackLeaf(valuepos, *value);
if (hasNext)
*hasNext = tempHasNext;
- return found;
-}
-
+ return found;
+}
+
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();
-
+
prefixLen = 0;
hasNext = false;
- bool found = false;
-
+ bool found = false;
+
if (EmptyValue) {
valuepos = EmptyValue;
found = true;
}
if (!key || !len)
- return found;
+ return found;
const char* const dataend = datapos + len;
@@ -509,8 +509,8 @@ bool TCompactTrie<T, D, S>::LookupLongestPrefix(const TSymbol* key, size_t keyle
prefixLen = keylen - (keyend - key) - (i ? 1 : 0);
valuepos = datapos;
hasNext = flags & MT_NEXT;
- found = true;
-
+ found = true;
+
if (!i && key == keyend) { // last byte, and got a match
return found;
}
@@ -523,7 +523,7 @@ bool TCompactTrie<T, D, S>::LookupLongestPrefix(const TSymbol* key, size_t keyle
}
}
- return found;
+ return found;
}
template <class T, class D, class S>
diff --git a/library/cpp/containers/comptrie/comptrie_ut.cpp b/library/cpp/containers/comptrie/comptrie_ut.cpp
index 74bee09b5d..be830dd2be 100644
--- a/library/cpp/containers/comptrie/comptrie_ut.cpp
+++ b/library/cpp/containers/comptrie/comptrie_ut.cpp
@@ -366,55 +366,55 @@ void TCompactTrieTest::CheckData(const char* data, size_t datalen) {
for (auto& i : SampleData) {
size_t len = strlen(i);
ui64 value = 0;
- size_t prefixLen = 0;
+ size_t prefixLen = 0;
typename TCompactTrie<T>::TKey key = MakeWideKey<T>(i, len);
UNIT_ASSERT(trie.Find(key, &value));
UNIT_ASSERT_EQUAL(len * 2, value);
UNIT_ASSERT(trie.FindLongestPrefix(key, &prefixLen, &value));
- UNIT_ASSERT_EQUAL(len, prefixLen);
- UNIT_ASSERT_EQUAL(len * 2, value);
+ UNIT_ASSERT_EQUAL(len, prefixLen);
+ UNIT_ASSERT_EQUAL(len * 2, value);
TString badkey("bb");
badkey += i;
key = MakeWideKey<T>(badkey);
UNIT_ASSERT(!trie.Find(key));
- value = 123;
+ value = 123;
UNIT_ASSERT(!trie.Find(key, &value));
- UNIT_ASSERT_EQUAL(123, value);
+ UNIT_ASSERT_EQUAL(123, value);
UNIT_ASSERT(trie.FindLongestPrefix(key, &prefixLen, &value));
- UNIT_ASSERT_EQUAL(1, prefixLen);
- UNIT_ASSERT_EQUAL(2, value);
+ UNIT_ASSERT_EQUAL(1, prefixLen);
+ UNIT_ASSERT_EQUAL(2, value);
badkey = i;
badkey += "x";
key = MakeWideKey<T>(badkey);
UNIT_ASSERT(!trie.Find(key));
- value = 1234;
+ value = 1234;
UNIT_ASSERT(!trie.Find(key, &value));
- UNIT_ASSERT_EQUAL(1234, value);
+ UNIT_ASSERT_EQUAL(1234, value);
UNIT_ASSERT(trie.FindLongestPrefix(key, &prefixLen, &value));
- UNIT_ASSERT_EQUAL(len, prefixLen);
- UNIT_ASSERT_EQUAL(len * 2, value);
+ UNIT_ASSERT_EQUAL(len, prefixLen);
+ UNIT_ASSERT_EQUAL(len * 2, value);
UNIT_ASSERT(trie.FindLongestPrefix(key, &prefixLen, nullptr));
- UNIT_ASSERT_EQUAL(len, prefixLen);
+ UNIT_ASSERT_EQUAL(len, prefixLen);
}
-
+
TString testkey("fbbaa");
typename TCompactTrie<T>::TKey key = MakeWideKey<T>(testkey);
- ui64 value = 0;
- size_t prefixLen = 0;
+ ui64 value = 0;
+ size_t prefixLen = 0;
UNIT_ASSERT(trie.FindLongestPrefix(key.data(), testkey.length() - 1, &prefixLen, &value));
- UNIT_ASSERT_EQUAL(prefixLen, 3);
- UNIT_ASSERT_EQUAL(6, value);
-
- testkey = "fbbax";
+ UNIT_ASSERT_EQUAL(prefixLen, 3);
+ UNIT_ASSERT_EQUAL(6, value);
+
+ testkey = "fbbax";
key = MakeWideKey<T>(testkey);
UNIT_ASSERT(trie.FindLongestPrefix(key, &prefixLen, &value));
- UNIT_ASSERT_EQUAL(prefixLen, 3);
- UNIT_ASSERT_EQUAL(6, value);
+ UNIT_ASSERT_EQUAL(prefixLen, 3);
+ UNIT_ASSERT_EQUAL(6, value);
- value = 12345678;
+ value = 12345678;
UNIT_ASSERT(!trie.Find(key, &value));
UNIT_ASSERT_EQUAL(12345678, value); //Failed Find() should not change value
}
@@ -601,8 +601,8 @@ void TCompactTrieTest::TestAddGet() {
void TCompactTrieTest::TestEmpty() {
TCompactTrieBuilder<char> builder;
- ui64 dummy = 12345;
- size_t prefixLen;
+ ui64 dummy = 12345;
+ size_t prefixLen;
UNIT_ASSERT(!builder.Find("abc", 3, &dummy));
TBufferOutput bufout;
builder.Save(bufout);
@@ -610,9 +610,9 @@ void TCompactTrieTest::TestEmpty() {
TCompactTrie<char> trie(bufout.Buffer().Data(), bufout.Buffer().Size());
UNIT_ASSERT(!trie.Find("abc", 3, &dummy));
UNIT_ASSERT(!trie.Find("", 0, &dummy));
- UNIT_ASSERT(!trie.FindLongestPrefix("abc", 3, &prefixLen, &dummy));
- UNIT_ASSERT(!trie.FindLongestPrefix("", 0, &prefixLen, &dummy));
- UNIT_ASSERT_EQUAL(12345, dummy);
+ UNIT_ASSERT(!trie.FindLongestPrefix("abc", 3, &prefixLen, &dummy));
+ UNIT_ASSERT(!trie.FindLongestPrefix("", 0, &prefixLen, &dummy));
+ UNIT_ASSERT_EQUAL(12345, dummy);
UNIT_ASSERT(trie.Begin() == trie.End());