diff options
author | Anton Samokhvalov <pg83@yandex.ru> | 2022-02-10 16:45:15 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:45:15 +0300 |
commit | 72cb13b4aff9bc9cf22e49251bc8fd143f82538f (patch) | |
tree | da2c34829458c7d4e74bdfbdf85dff449e9e7fb8 /library/cpp/containers/comptrie/write_trie_backwards.cpp | |
parent | 778e51ba091dc39e7b7fcab2b9cf4dbedfb6f2b5 (diff) | |
download | ydb-72cb13b4aff9bc9cf22e49251bc8fd143f82538f.tar.gz |
Restoring authorship annotation for Anton Samokhvalov <pg83@yandex.ru>. Commit 1 of 2.
Diffstat (limited to 'library/cpp/containers/comptrie/write_trie_backwards.cpp')
-rw-r--r-- | library/cpp/containers/comptrie/write_trie_backwards.cpp | 188 |
1 files changed, 94 insertions, 94 deletions
diff --git a/library/cpp/containers/comptrie/write_trie_backwards.cpp b/library/cpp/containers/comptrie/write_trie_backwards.cpp index fd8c28b0ed..f7459b1c49 100644 --- a/library/cpp/containers/comptrie/write_trie_backwards.cpp +++ b/library/cpp/containers/comptrie/write_trie_backwards.cpp @@ -7,104 +7,104 @@ #include <util/generic/vector.h> namespace NCompactTrie { - size_t WriteTrieBackwards(IOutputStream& os, TReverseNodeEnumerator& enumerator, bool verbose) { - if (verbose) { - Cerr << "Writing down the trie..." << Endl; - } - - // Rewrite everything from the back, removing unused pieces. - const size_t chunksize = 0x10000; - TVector<char*> resultData; - - resultData.push_back(new char[chunksize]); - char* chunkend = resultData.back() + chunksize; - - size_t resultLength = 0; - size_t chunkLength = 0; - - size_t counter = 0; - TBuffer bufferHolder; - while (enumerator.Move()) { - if (verbose) - ShowProgress(++counter); - - size_t bufferLength = 64 + enumerator.GetLeafLength(); // never know how big leaf data can be - bufferHolder.Clear(); - bufferHolder.Resize(bufferLength); - char* buffer = bufferHolder.Data(); - - size_t nodelength = enumerator.RecreateNode(buffer, resultLength); - Y_ASSERT(nodelength <= bufferLength); - - resultLength += nodelength; - - if (chunkLength + nodelength <= chunksize) { - chunkLength += nodelength; - memcpy(chunkend - chunkLength, buffer, nodelength); - } else { // allocate a new chunk - memcpy(chunkend - chunksize, buffer + nodelength - (chunksize - chunkLength), chunksize - chunkLength); - chunkLength = chunkLength + nodelength - chunksize; - - resultData.push_back(new char[chunksize]); - chunkend = resultData.back() + chunksize; - - while (chunkLength > chunksize) { // allocate a new chunks - chunkLength -= chunksize; - memcpy(chunkend - chunksize, buffer + chunkLength, chunksize); - - resultData.push_back(new char[chunksize]); - chunkend = resultData.back() + chunksize; - } - - memcpy(chunkend - chunkLength, buffer, chunkLength); + size_t WriteTrieBackwards(IOutputStream& os, TReverseNodeEnumerator& enumerator, bool verbose) { + if (verbose) { + Cerr << "Writing down the trie..." << Endl; + } + + // Rewrite everything from the back, removing unused pieces. + const size_t chunksize = 0x10000; + TVector<char*> resultData; + + resultData.push_back(new char[chunksize]); + char* chunkend = resultData.back() + chunksize; + + size_t resultLength = 0; + size_t chunkLength = 0; + + size_t counter = 0; + TBuffer bufferHolder; + while (enumerator.Move()) { + if (verbose) + ShowProgress(++counter); + + size_t bufferLength = 64 + enumerator.GetLeafLength(); // never know how big leaf data can be + bufferHolder.Clear(); + bufferHolder.Resize(bufferLength); + char* buffer = bufferHolder.Data(); + + size_t nodelength = enumerator.RecreateNode(buffer, resultLength); + Y_ASSERT(nodelength <= bufferLength); + + resultLength += nodelength; + + if (chunkLength + nodelength <= chunksize) { + chunkLength += nodelength; + memcpy(chunkend - chunkLength, buffer, nodelength); + } else { // allocate a new chunk + memcpy(chunkend - chunksize, buffer + nodelength - (chunksize - chunkLength), chunksize - chunkLength); + chunkLength = chunkLength + nodelength - chunksize; + + resultData.push_back(new char[chunksize]); + chunkend = resultData.back() + chunksize; + + while (chunkLength > chunksize) { // allocate a new chunks + chunkLength -= chunksize; + memcpy(chunkend - chunksize, buffer + chunkLength, chunksize); + + resultData.push_back(new char[chunksize]); + chunkend = resultData.back() + chunksize; + } + + memcpy(chunkend - chunkLength, buffer, chunkLength); } + } + + if (verbose) + Cerr << counter << Endl; + + // Write the whole thing down + while (!resultData.empty()) { + char* chunk = resultData.back(); + os.Write(chunk + chunksize - chunkLength, chunkLength); + chunkLength = chunksize; + delete[] chunk; + resultData.pop_back(); } - - if (verbose) - Cerr << counter << Endl; - - // Write the whole thing down - while (!resultData.empty()) { - char* chunk = resultData.back(); - os.Write(chunk + chunksize - chunkLength, chunkLength); - chunkLength = chunksize; - delete[] chunk; - resultData.pop_back(); - } - - return resultLength; + + return resultLength; } - size_t WriteTrieBackwardsNoAlloc(IOutputStream& os, TReverseNodeEnumerator& enumerator, TOpaqueTrie& trie, EMinimizeMode mode) { - char* data = const_cast<char*>(trie.Data); - char* end = data + trie.Length; - char* pos = end; - - TVector<char> buf(64); - while (enumerator.Move()) { - size_t nodeLength = enumerator.RecreateNode(nullptr, end - pos); - if (nodeLength > buf.size()) - buf.resize(nodeLength); - - size_t realLength = enumerator.RecreateNode(buf.data(), end - pos); - Y_ASSERT(realLength == nodeLength); - - pos -= nodeLength; - memcpy(pos, buf.data(), nodeLength); - } - - switch (mode) { - case MM_NOALLOC: - os.Write(pos, end - pos); - break; - case MM_INPLACE: - memmove(data, pos, end - pos); - break; - default: - Y_VERIFY(false); - } - - return end - pos; + size_t WriteTrieBackwardsNoAlloc(IOutputStream& os, TReverseNodeEnumerator& enumerator, TOpaqueTrie& trie, EMinimizeMode mode) { + char* data = const_cast<char*>(trie.Data); + char* end = data + trie.Length; + char* pos = end; + + TVector<char> buf(64); + while (enumerator.Move()) { + size_t nodeLength = enumerator.RecreateNode(nullptr, end - pos); + if (nodeLength > buf.size()) + buf.resize(nodeLength); + + size_t realLength = enumerator.RecreateNode(buf.data(), end - pos); + Y_ASSERT(realLength == nodeLength); + + pos -= nodeLength; + memcpy(pos, buf.data(), nodeLength); + } + + switch (mode) { + case MM_NOALLOC: + os.Write(pos, end - pos); + break; + case MM_INPLACE: + memmove(data, pos, end - pos); + break; + default: + Y_VERIFY(false); + } + + return end - pos; } } |