trace_processor: move stringpool to new containers folder
This allows us to remove the ugly "common" target which has existed for
a long time.
Context: go/perfetto-tp-refactor
Bug: 135177627
Change-Id: I6dd03c22f0b42f818a9a53ad9bfa1e7f382a05f4
diff --git a/src/trace_processor/containers/BUILD.gn b/src/trace_processor/containers/BUILD.gn
index c6c5d73..32e0d28 100644
--- a/src/trace_processor/containers/BUILD.gn
+++ b/src/trace_processor/containers/BUILD.gn
@@ -20,15 +20,18 @@
"bit_vector.h",
"bit_vector_iterators.cc",
"bit_vector_iterators.h",
+ "null_term_string_view.h",
"row_map.cc",
"row_map.h",
"sparse_vector.h",
+ "string_pool.cc",
+ "string_pool.h",
]
deps = [
- "../:common",
"../../../gn:default_deps",
"../../../include/perfetto/base",
"../../../include/perfetto/ext/base",
+ "../../../include/perfetto/protozero",
]
}
@@ -36,8 +39,10 @@
testonly = true
sources = [
"bit_vector_unittest.cc",
+ "null_term_string_view_unittest.cc",
"row_map_unittest.cc",
"sparse_vector_unittest.cc",
+ "string_pool_unittest.cc",
]
deps = [
":containers",
diff --git a/src/trace_processor/containers/null_term_string_view.h b/src/trace_processor/containers/null_term_string_view.h
new file mode 100644
index 0000000..5ae5a29
--- /dev/null
+++ b/src/trace_processor/containers/null_term_string_view.h
@@ -0,0 +1,60 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef SRC_TRACE_PROCESSOR_CONTAINERS_NULL_TERM_STRING_VIEW_H_
+#define SRC_TRACE_PROCESSOR_CONTAINERS_NULL_TERM_STRING_VIEW_H_
+
+#include "perfetto/ext/base/string_view.h"
+
+namespace perfetto {
+namespace trace_processor {
+
+// A string-like object that refers to a non-owned piece of memory which is
+// null terminated.
+class NullTermStringView : public base::StringView {
+ public:
+ // Creates an empty view.
+ NullTermStringView() : StringView() {}
+
+ // Make the view copy constructible.
+ NullTermStringView(const NullTermStringView&) = default;
+ NullTermStringView& operator=(const NullTermStringView&) = default;
+
+ // Creates a NullTermStringView from a null-terminated C string.
+ // Deliberately not "explicit".
+ NullTermStringView(const char* cstr) : StringView(cstr) {}
+
+ // Creates a NullTermStringView from a null terminated C-string where the
+ // size is known. This allows a call to strlen() to be avoided.
+ // Note: This string MUST be null terminated i.e. data[size] == '\0' MUST hold
+ // for this constructor to be valid.
+ NullTermStringView(const char* data, size_t size) : StringView(data, size) {
+ PERFETTO_DCHECK(data[size] == '\0');
+ }
+
+ // This instead has to be explicit, as creating a NullTermStringView out of a
+ // std::string can be subtle.
+ explicit NullTermStringView(const std::string& str) : StringView(str) {}
+
+ // Returns the null terminated C-string backing this string view. The same
+ // pointer as |data()| is returned.
+ const char* c_str() const { return data(); }
+};
+
+} // namespace trace_processor
+} // namespace perfetto
+
+#endif // SRC_TRACE_PROCESSOR_CONTAINERS_NULL_TERM_STRING_VIEW_H_
diff --git a/src/trace_processor/containers/null_term_string_view_unittest.cc b/src/trace_processor/containers/null_term_string_view_unittest.cc
new file mode 100644
index 0000000..eb4d23f
--- /dev/null
+++ b/src/trace_processor/containers/null_term_string_view_unittest.cc
@@ -0,0 +1,69 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "src/trace_processor/containers/null_term_string_view.h"
+
+#include "test/gtest_and_gmock.h"
+
+namespace perfetto {
+namespace trace_processor {
+namespace {
+
+TEST(NullTermStringViewTest, Comparisions) {
+ // Test the < operator.
+ EXPECT_FALSE(NullTermStringView() < NullTermStringView());
+ EXPECT_FALSE(NullTermStringView() < NullTermStringView(""));
+ EXPECT_TRUE(NullTermStringView() < NullTermStringView("foo"));
+ EXPECT_TRUE(NullTermStringView("") < NullTermStringView("foo"));
+ EXPECT_FALSE(NullTermStringView("foo") < NullTermStringView("foo"));
+ EXPECT_TRUE(NullTermStringView("foo") < NullTermStringView("fooo"));
+ EXPECT_FALSE(NullTermStringView("fooo") < NullTermStringView("foo"));
+ EXPECT_TRUE(NullTermStringView("bar") < NullTermStringView("foo"));
+
+ // Test the <= operator.
+ EXPECT_TRUE(NullTermStringView() <= NullTermStringView());
+ EXPECT_TRUE(NullTermStringView() <= NullTermStringView(""));
+ EXPECT_TRUE(NullTermStringView() <= NullTermStringView("foo"));
+ EXPECT_TRUE(NullTermStringView("") <= NullTermStringView("foo"));
+ EXPECT_TRUE(NullTermStringView("foo") <= NullTermStringView("foo"));
+ EXPECT_TRUE(NullTermStringView("foo") <= NullTermStringView("fooo"));
+ EXPECT_FALSE(NullTermStringView("fooo") <= NullTermStringView("foo"));
+ EXPECT_TRUE(NullTermStringView("bar") <= NullTermStringView("foo"));
+
+ // Test the > operator.
+ EXPECT_FALSE(NullTermStringView() > NullTermStringView());
+ EXPECT_FALSE(NullTermStringView() > NullTermStringView(""));
+ EXPECT_FALSE(NullTermStringView() > NullTermStringView("foo"));
+ EXPECT_FALSE(NullTermStringView("") > NullTermStringView("foo"));
+ EXPECT_FALSE(NullTermStringView("foo") > NullTermStringView("foo"));
+ EXPECT_FALSE(NullTermStringView("foo") > NullTermStringView("fooo"));
+ EXPECT_TRUE(NullTermStringView("fooo") > NullTermStringView("foo"));
+ EXPECT_FALSE(NullTermStringView("bar") > NullTermStringView("foo"));
+
+ // Test the >= operator.
+ EXPECT_TRUE(NullTermStringView() >= NullTermStringView());
+ EXPECT_TRUE(NullTermStringView() >= NullTermStringView(""));
+ EXPECT_FALSE(NullTermStringView() >= NullTermStringView("foo"));
+ EXPECT_FALSE(NullTermStringView("") >= NullTermStringView("foo"));
+ EXPECT_TRUE(NullTermStringView("foo") >= NullTermStringView("foo"));
+ EXPECT_FALSE(NullTermStringView("foo") >= NullTermStringView("fooo"));
+ EXPECT_TRUE(NullTermStringView("fooo") >= NullTermStringView("foo"));
+ EXPECT_FALSE(NullTermStringView("bar") >= NullTermStringView("foo"));
+}
+
+} // namespace
+} // namespace trace_processor
+} // namespace perfetto
diff --git a/src/trace_processor/containers/string_pool.cc b/src/trace_processor/containers/string_pool.cc
new file mode 100644
index 0000000..020de1c
--- /dev/null
+++ b/src/trace_processor/containers/string_pool.cc
@@ -0,0 +1,150 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "src/trace_processor/containers/string_pool.h"
+
+#include <limits>
+
+#include "perfetto/base/logging.h"
+#include "perfetto/ext/base/utils.h"
+
+namespace perfetto {
+namespace trace_processor {
+
+StringPool::StringPool(size_t block_size_bytes)
+ : block_size_bytes_(block_size_bytes > 0 ? block_size_bytes
+ : kDefaultBlockSize) {
+ blocks_.emplace_back(block_size_bytes_);
+
+ // Reserve a slot for the null string.
+ PERFETTO_CHECK(blocks_.back().TryInsert(NullTermStringView()));
+}
+
+StringPool::~StringPool() = default;
+
+StringPool::StringPool(StringPool&&) noexcept = default;
+StringPool& StringPool::operator=(StringPool&&) = default;
+
+StringPool::Id StringPool::InsertString(base::StringView str, uint64_t hash) {
+ // Try and find enough space in the current block for the string and the
+ // metadata (varint-encoded size + the string data + the null terminator).
+ const uint8_t* ptr = blocks_.back().TryInsert(str);
+ if (PERFETTO_UNLIKELY(!ptr)) {
+ // This means the block did not have enough space. This should only happen
+ // if the block size is small.
+ PERFETTO_CHECK(block_size_bytes_ <= std::numeric_limits<uint32_t>::max());
+
+ // Add a new block to store the data. If the string is larger that the
+ // default block size, add a bigger block exlusively for this string.
+ if (str.size() + kMaxMetadataSize > block_size_bytes_) {
+ blocks_.emplace_back(str.size() +
+ base::AlignUp<base::kPageSize>(kMaxMetadataSize));
+ } else {
+ blocks_.emplace_back(block_size_bytes_);
+ }
+
+ // Try and reserve space again - this time we should definitely succeed.
+ ptr = blocks_.back().TryInsert(str);
+ PERFETTO_CHECK(ptr);
+ }
+
+ // Finish by computing the id of the pointer and adding a mapping from the
+ // hash to the string_id.
+ Id string_id = PtrToId(ptr);
+ string_index_.emplace(hash, string_id);
+ return string_id;
+}
+
+const uint8_t* StringPool::Block::TryInsert(base::StringView str) {
+ auto str_size = str.size();
+ size_t max_pos = static_cast<size_t>(pos_) + str_size + kMaxMetadataSize;
+ if (max_pos > size_)
+ return nullptr;
+
+ // Ensure that we commit up until the end of the string to memory.
+ mem_.EnsureCommitted(max_pos);
+
+ // Get where we should start writing this string.
+ uint8_t* begin = Get(pos_);
+
+ // First write the size of the string using varint encoding.
+ uint8_t* end = protozero::proto_utils::WriteVarInt(str_size, begin);
+
+ // Next the string itself.
+ if (PERFETTO_LIKELY(str_size > 0)) {
+ memcpy(end, str.data(), str_size);
+ end += str_size;
+ }
+
+ // Finally add a null terminator.
+ *(end++) = '\0';
+
+ // Update the end of the block and return the pointer to the string.
+ pos_ = OffsetOf(end);
+
+ return begin;
+}
+
+StringPool::Iterator::Iterator(const StringPool* pool) : pool_(pool) {}
+
+StringPool::Iterator& StringPool::Iterator::operator++() {
+ PERFETTO_DCHECK(block_id_ < pool_->blocks_.size());
+
+ // Try and go to the next string in the current block.
+ const auto& block = pool_->blocks_[block_id_];
+
+ // Find the size of the string at the current offset in the block
+ // and increment the offset by that size.
+ uint32_t str_size = 0;
+ const uint8_t* ptr = block.Get(block_offset_);
+ ptr = ReadSize(ptr, &str_size);
+ ptr += str_size + 1;
+ block_offset_ = block.OffsetOf(ptr);
+
+ // If we're out of bounds for this block, go to the start of the next block.
+ if (block.pos() <= block_offset_) {
+ block_id_++;
+ block_offset_ = 0;
+ }
+ return *this;
+}
+
+StringPool::Iterator::operator bool() const {
+ return block_id_ < pool_->blocks_.size();
+}
+
+NullTermStringView StringPool::Iterator::StringView() {
+ PERFETTO_DCHECK(block_id_ < pool_->blocks_.size());
+ PERFETTO_DCHECK(block_offset_ < pool_->blocks_[block_id_].pos());
+
+ // If we're at (0, 0), we have the null string.
+ if (block_id_ == 0 && block_offset_ == 0)
+ return NullTermStringView();
+ return GetFromPtr(pool_->blocks_[block_id_].Get(block_offset_));
+}
+
+StringPool::Id StringPool::Iterator::StringId() {
+ PERFETTO_DCHECK(block_id_ < pool_->blocks_.size());
+ PERFETTO_DCHECK(block_offset_ < pool_->blocks_[block_id_].pos());
+
+ // If we're at (0, 0), we have the null string which has id 0.
+ if (block_id_ == 0 && block_offset_ == 0)
+ return 0;
+ return pool_->PtrToId(pool_->blocks_[block_id_].Get(block_offset_));
+}
+
+} // namespace trace_processor
+} // namespace perfetto
diff --git a/src/trace_processor/containers/string_pool.h b/src/trace_processor/containers/string_pool.h
new file mode 100644
index 0000000..bdfc39f
--- /dev/null
+++ b/src/trace_processor/containers/string_pool.h
@@ -0,0 +1,253 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef SRC_TRACE_PROCESSOR_CONTAINERS_STRING_POOL_H_
+#define SRC_TRACE_PROCESSOR_CONTAINERS_STRING_POOL_H_
+
+#include <stddef.h>
+#include <stdint.h>
+
+#include <unordered_map>
+#include <vector>
+
+#include "perfetto/ext/base/optional.h"
+#include "perfetto/ext/base/paged_memory.h"
+#include "perfetto/protozero/proto_utils.h"
+#include "src/trace_processor/containers/null_term_string_view.h"
+
+namespace perfetto {
+namespace trace_processor {
+
+// On 64-bit platforms, the string pool is implemented as a mmaped buffer
+// of 4GB with the id being equal ot the offset into this buffer of the string.
+// On 32-bit platforms instead, the implementation allocates 32MB blocks of
+// mmaped memory with the pointer being directly converted to the id.
+constexpr size_t kDefaultBlockSize =
+ sizeof(void*) == 8
+ ? static_cast<size_t>(4ull * 1024ull * 1024ull * 1024ull) /* 4GB */
+ : 32ull * 1024ull * 1024ull /* 32MB */;
+
+// Interns strings in a string pool and hands out compact StringIds which can
+// be used to retrieve the string in O(1).
+class StringPool {
+ public:
+ struct Id {
+ Id() = default;
+ constexpr Id(uint32_t i) : id(i) {}
+
+ bool operator==(const Id& other) const { return other.id == id; }
+ bool operator!=(const Id& other) const { return !(other == *this); }
+ bool operator<(const Id& other) const { return id < other.id; }
+
+ bool is_null() const { return id == 0u; }
+
+ uint32_t id;
+ };
+
+ // Iterator over the strings in the pool.
+ class Iterator {
+ public:
+ Iterator(const StringPool*);
+
+ explicit operator bool() const;
+ Iterator& operator++();
+
+ NullTermStringView StringView();
+ Id StringId();
+
+ private:
+ const StringPool* pool_ = nullptr;
+ uint32_t block_id_ = 0;
+ uint32_t block_offset_ = 0;
+ };
+
+ StringPool(size_t block_size_bytes = kDefaultBlockSize);
+ ~StringPool();
+
+ // Allow std::move().
+ StringPool(StringPool&&) noexcept;
+ StringPool& operator=(StringPool&&);
+
+ // Disable implicit copy.
+ StringPool(const StringPool&) = delete;
+ StringPool& operator=(const StringPool&) = delete;
+
+ Id InternString(base::StringView str) {
+ if (str.data() == nullptr)
+ return Id(0);
+
+ auto hash = str.Hash();
+ auto id_it = string_index_.find(hash);
+ if (id_it != string_index_.end()) {
+ PERFETTO_DCHECK(Get(id_it->second) == str);
+ return id_it->second;
+ }
+ return InsertString(str, hash);
+ }
+
+ base::Optional<Id> GetId(base::StringView str) const {
+ if (str.data() == nullptr)
+ return Id(0u);
+
+ auto hash = str.Hash();
+ auto id_it = string_index_.find(hash);
+ if (id_it != string_index_.end()) {
+ PERFETTO_DCHECK(Get(id_it->second) == str);
+ return id_it->second;
+ }
+ return base::nullopt;
+ }
+
+ NullTermStringView Get(Id id) const {
+ if (id.id == 0)
+ return NullTermStringView();
+ return GetFromPtr(IdToPtr(id));
+ }
+
+ Iterator CreateIterator() const { return Iterator(this); }
+
+ size_t size() const { return string_index_.size(); }
+
+ private:
+ using StringHash = uint64_t;
+
+ struct Block {
+ explicit Block(size_t size)
+ : mem_(base::PagedMemory::Allocate(size,
+ base::PagedMemory::kDontCommit)),
+ size_(size) {}
+ ~Block() = default;
+
+ // Allow std::move().
+ Block(Block&&) noexcept = default;
+ Block& operator=(Block&&) = default;
+
+ // Disable implicit copy.
+ Block(const Block&) = delete;
+ Block& operator=(const Block&) = delete;
+
+ uint8_t* Get(uint32_t offset) const {
+ return static_cast<uint8_t*>(mem_.Get()) + offset;
+ }
+
+ const uint8_t* TryInsert(base::StringView str);
+
+ uint32_t OffsetOf(const uint8_t* ptr) const {
+ PERFETTO_DCHECK(Get(0) < ptr &&
+ ptr < Get(static_cast<uint32_t>(size_ - 1)));
+ return static_cast<uint32_t>(ptr - Get(0));
+ }
+
+ uint32_t pos() const { return pos_; }
+
+ private:
+ base::PagedMemory mem_;
+ uint32_t pos_ = 0;
+ size_t size_ = 0;
+ };
+
+ friend class Iterator;
+
+ // Number of bytes to reserve for size and null terminator.
+ // This is the upper limit on metadata size: 5 bytes for max uint32,
+ // plus 1 byte for null terminator. The actual size may be lower.
+ static constexpr uint8_t kMaxMetadataSize = 6;
+
+ // Inserts the string with the given hash into the pool
+ Id InsertString(base::StringView, uint64_t hash);
+
+ // |ptr| should point to the start of the string metadata (i.e. the first byte
+ // of the size).
+ Id PtrToId(const uint8_t* ptr) const {
+ // For a 64 bit architecture, the id is the offset of the pointer inside
+ // the one and only 4GB block.
+ if (sizeof(void*) == 8) {
+ PERFETTO_DCHECK(blocks_.size() == 1);
+ return Id(blocks_.back().OffsetOf(ptr));
+ }
+
+ // On 32 bit architectures, the size of the pointer is 32-bit so we simply
+ // use the pointer itself as the id.
+ // Double cast needed because, on 64 archs, the compiler complains that we
+ // are losing information.
+ return Id(static_cast<uint32_t>(reinterpret_cast<uintptr_t>(ptr)));
+ }
+
+ // The returned pointer points to the start of the string metadata (i.e. the
+ // first byte of the size).
+ const uint8_t* IdToPtr(Id id) const {
+ // For a 64 bit architecture, the pointer is simply the found by taking
+ // the base of the 4GB block and adding the offset given by |id|.
+ if (sizeof(void*) == 8) {
+ PERFETTO_DCHECK(blocks_.size() == 1);
+ return blocks_.back().Get(id.id);
+ }
+ // On a 32 bit architecture, the pointer is the same as the id.
+ return reinterpret_cast<uint8_t*>(id.id);
+ }
+
+ // |ptr| should point to the start of the string metadata (i.e. the first byte
+ // of the size).
+ // Returns pointer to the start of the string.
+ static const uint8_t* ReadSize(const uint8_t* ptr, uint32_t* size) {
+ uint64_t value = 0;
+ const uint8_t* str_ptr = protozero::proto_utils::ParseVarInt(
+ ptr, ptr + kMaxMetadataSize, &value);
+ PERFETTO_DCHECK(str_ptr != ptr);
+ PERFETTO_DCHECK(value < std::numeric_limits<uint32_t>::max());
+ *size = static_cast<uint32_t>(value);
+ return str_ptr;
+ }
+
+ // |ptr| should point to the start of the string metadata (i.e. the first byte
+ // of the size).
+ static NullTermStringView GetFromPtr(const uint8_t* ptr) {
+ uint32_t size = 0;
+ const uint8_t* str_ptr = ReadSize(ptr, &size);
+ return NullTermStringView(reinterpret_cast<const char*>(str_ptr), size);
+ }
+
+ // The minimum size of a new block. A larger block may be created if a string
+ // is added that is larger than this size.
+ size_t block_size_bytes_;
+
+ // The actual memory storing the strings.
+ std::vector<Block> blocks_;
+
+ // Maps hashes of strings to the Id in the string pool.
+ // TODO(lalitm): At some point we should benchmark just using a static
+ // hashtable of 1M elements, we can afford paying a fixed 8MB here
+ std::unordered_map<StringHash, Id> string_index_;
+};
+
+} // namespace trace_processor
+} // namespace perfetto
+
+namespace std {
+
+template <>
+struct hash< ::perfetto::trace_processor::StringPool::Id> {
+ using argument_type = ::perfetto::trace_processor::StringPool::Id;
+ using result_type = size_t;
+
+ result_type operator()(const argument_type& r) const {
+ return std::hash<uint32_t>{}(r.id);
+ }
+};
+
+} // namespace std
+
+#endif // SRC_TRACE_PROCESSOR_CONTAINERS_STRING_POOL_H_
diff --git a/src/trace_processor/containers/string_pool_unittest.cc b/src/trace_processor/containers/string_pool_unittest.cc
new file mode 100644
index 0000000..0144d7c
--- /dev/null
+++ b/src/trace_processor/containers/string_pool_unittest.cc
@@ -0,0 +1,148 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "src/trace_processor/containers/string_pool.h"
+
+#include <random>
+
+#include "test/gtest_and_gmock.h"
+
+namespace perfetto {
+namespace trace_processor {
+namespace {
+
+TEST(StringPoolTest, EmptyPool) {
+ StringPool pool;
+
+ ASSERT_EQ(pool.Get(0).c_str(), nullptr);
+
+ auto it = pool.CreateIterator();
+ ASSERT_TRUE(it);
+ ASSERT_EQ(it.StringView().c_str(), nullptr);
+ ASSERT_FALSE(++it);
+}
+
+TEST(StringPoolTest, InternAndRetrieve) {
+ StringPool pool;
+
+ static char kString[] = "Test String";
+ auto id = pool.InternString(kString);
+ ASSERT_STREQ(pool.Get(id).c_str(), kString);
+ ASSERT_EQ(pool.Get(id), kString);
+ ASSERT_EQ(id, pool.InternString(kString));
+}
+
+TEST(StringPoolTest, NullPointerHandling) {
+ StringPool pool;
+
+ auto id = pool.InternString(NullTermStringView());
+ ASSERT_EQ(id, 0u);
+ ASSERT_EQ(pool.Get(id).c_str(), nullptr);
+}
+
+TEST(StringPoolTest, Iterator) {
+ StringPool pool;
+
+ auto it = pool.CreateIterator();
+ ASSERT_TRUE(it);
+ ASSERT_EQ(it.StringView().c_str(), nullptr);
+ ASSERT_FALSE(++it);
+
+ static char kString[] = "Test String";
+ pool.InternString(kString);
+
+ it = pool.CreateIterator();
+ ASSERT_TRUE(++it);
+ ASSERT_STREQ(it.StringView().c_str(), kString);
+ ASSERT_FALSE(++it);
+}
+
+TEST(StringPoolTest, ConstIterator) {
+ StringPool pool;
+ static char kString[] = "Test String";
+ pool.InternString(kString);
+
+ const StringPool& const_pool = pool;
+
+ auto it = const_pool.CreateIterator();
+ ASSERT_TRUE(it);
+ ASSERT_TRUE(++it);
+ ASSERT_STREQ(it.StringView().c_str(), kString);
+ ASSERT_FALSE(++it);
+}
+
+TEST(StringPoolTest, StressTest) {
+ // First create a buffer with 8MB of random characters.
+ constexpr size_t kBufferSize = 8 * 1024 * 1024;
+ std::minstd_rand0 rnd_engine(0);
+ std::unique_ptr<char[]> buffer(new char[kBufferSize]);
+ for (size_t i = 0; i < kBufferSize; i++)
+ buffer.get()[i] = 'A' + (rnd_engine() % 26);
+
+ // Next create strings of length 0 to 16k in length from this buffer and
+ // intern them, storing their ids.
+ StringPool pool;
+ std::multimap<StringPool::Id, base::StringView> string_map;
+ constexpr uint16_t kMaxStrSize = 16u * 1024u - 1;
+ for (size_t i = 0;;) {
+ size_t length = static_cast<uint64_t>(rnd_engine()) % (kMaxStrSize + 1);
+ if (i + length > kBufferSize)
+ break;
+
+ auto str = base::StringView(&buffer.get()[i], length);
+ string_map.emplace(pool.InternString(str), str);
+ i += length;
+ }
+
+ // Finally, iterate through each string in the string pool, check that all ids
+ // that match in the multimap are equal, and finish by checking we've removed
+ // every item in the multimap.
+ for (auto it = pool.CreateIterator(); it; ++it) {
+ ASSERT_EQ(it.StringView(), pool.Get(it.StringId()));
+
+ auto it_pair = string_map.equal_range(it.StringId());
+ for (auto in_it = it_pair.first; in_it != it_pair.second; ++in_it) {
+ ASSERT_EQ(it.StringView(), in_it->second);
+ }
+ string_map.erase(it_pair.first, it_pair.second);
+ }
+ ASSERT_EQ(string_map.size(), 0u);
+}
+
+TEST(StringPoolTest, BigString) {
+ constexpr size_t kBigStringSize = 33 * 1024 * 1024;
+ std::unique_ptr<char[]> str1(new char[kBigStringSize + 1]);
+ std::unique_ptr<char[]> str2(new char[kBigStringSize + 1]);
+ for (size_t i = 0; i < kBigStringSize; i++) {
+ str1.get()[i] = 'A' + static_cast<char>(i % 32);
+ str2.get()[i] = 'A' + static_cast<char>((i + 7) % 32);
+ }
+ str1.get()[kBigStringSize] = '\0';
+ str2.get()[kBigStringSize] = '\0';
+
+ StringPool pool;
+ StringPool::Id id1 =
+ pool.InternString(base::StringView(str1.get(), kBigStringSize));
+ StringPool::Id id2 =
+ pool.InternString(base::StringView(str2.get(), kBigStringSize));
+
+ ASSERT_EQ(str1.get(), pool.Get(id1));
+ ASSERT_EQ(str2.get(), pool.Get(id2));
+}
+
+} // namespace
+} // namespace trace_processor
+} // namespace perfetto
