[ORC-RT] Add a SymbolStringPool class to the ORC runtime.
This is a counterpart to llvm::orc::SymbolStringPool. It holds uniqued,
ref-counted strings; and can be used to avoid redundant storage of strings,
and speed up comparison of strings held in the pool (these become pointer
comparisons).
GitOrigin-RevId: 8fda8901e29bf80bd91574f29b50868958195a4e
diff --git a/lib/orc/string_pool.h b/lib/orc/string_pool.h
new file mode 100644
index 0000000..c0ba4ea
--- /dev/null
+++ b/lib/orc/string_pool.h
@@ -0,0 +1,172 @@
+//===------- string_pool.h - Thread-safe pool for strings -------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Contains a thread-safe string pool. Strings are ref-counted, but not
+// automatically deallocated. Unused entries can be cleared by calling
+// StringPool::clearDeadEntries.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef ORC_RT_STRING_POOL_H
+#define ORC_RT_STRING_POOL_H
+
+#include <atomic>
+#include <cassert>
+#include <functional>
+#include <mutex>
+#include <string>
+#include <unordered_map>
+
+namespace __orc_rt {
+
+class PooledStringPtr;
+
+/// String pool for strings names used by the ORC runtime.
+class StringPool {
+ friend class PooledStringPtr;
+
+public:
+ /// Destroy a StringPool.
+ ~StringPool();
+
+ /// Create a string pointer from the given string.
+ PooledStringPtr intern(std::string S);
+
+ /// Remove from the pool any entries that are no longer referenced.
+ void clearDeadEntries();
+
+ /// Returns true if the pool is empty.
+ bool empty() const;
+
+private:
+ using RefCountType = std::atomic<size_t>;
+ using PoolMap = std::unordered_map<std::string, RefCountType>;
+ using PoolMapEntry = PoolMap::value_type;
+ mutable std::mutex PoolMutex;
+ PoolMap Pool;
+};
+
+/// Pointer to a pooled string.
+class PooledStringPtr {
+ friend class StringPool;
+ friend struct std::hash<PooledStringPtr>;
+
+public:
+ PooledStringPtr() = default;
+ PooledStringPtr(std::nullptr_t) {}
+ PooledStringPtr(const PooledStringPtr &Other) : S(Other.S) {
+ if (S)
+ ++S->second;
+ }
+
+ PooledStringPtr &operator=(const PooledStringPtr &Other) {
+ if (S) {
+ assert(S->second && "Releasing PooledStringPtr with zero ref count");
+ --S->second;
+ }
+ S = Other.S;
+ if (S)
+ ++S->second;
+ return *this;
+ }
+
+ PooledStringPtr(PooledStringPtr &&Other) : S(nullptr) {
+ std::swap(S, Other.S);
+ }
+
+ PooledStringPtr &operator=(PooledStringPtr &&Other) {
+ if (S) {
+ assert(S->second && "Releasing PooledStringPtr with zero ref count");
+ --S->second;
+ }
+ S = nullptr;
+ std::swap(S, Other.S);
+ return *this;
+ }
+
+ ~PooledStringPtr() {
+ if (S) {
+ assert(S->second && "Releasing PooledStringPtr with zero ref count");
+ --S->second;
+ }
+ }
+
+ explicit operator bool() const { return S; }
+
+ const std::string &operator*() const { return S->first; }
+
+ friend bool operator==(const PooledStringPtr &LHS,
+ const PooledStringPtr &RHS) {
+ return LHS.S == RHS.S;
+ }
+
+ friend bool operator!=(const PooledStringPtr &LHS,
+ const PooledStringPtr &RHS) {
+ return !(LHS == RHS);
+ }
+
+ friend bool operator<(const PooledStringPtr &LHS,
+ const PooledStringPtr &RHS) {
+ return LHS.S < RHS.S;
+ }
+
+private:
+ using PoolEntry = StringPool::PoolMapEntry;
+ using PoolEntryPtr = PoolEntry *;
+
+ PooledStringPtr(StringPool::PoolMapEntry *S) : S(S) {
+ if (S)
+ ++S->second;
+ }
+
+ PoolEntryPtr S = nullptr;
+};
+
+inline StringPool::~StringPool() {
+#ifndef NDEBUG
+ clearDeadEntries();
+ assert(Pool.empty() && "Dangling references at pool destruction time");
+#endif // NDEBUG
+}
+
+inline PooledStringPtr StringPool::intern(std::string S) {
+ std::lock_guard<std::mutex> Lock(PoolMutex);
+ PoolMap::iterator I;
+ bool Added;
+ std::tie(I, Added) = Pool.try_emplace(std::move(S), 0);
+ return PooledStringPtr(&*I);
+}
+
+inline void StringPool::clearDeadEntries() {
+ std::lock_guard<std::mutex> Lock(PoolMutex);
+ for (auto I = Pool.begin(), E = Pool.end(); I != E;) {
+ auto Tmp = I++;
+ if (Tmp->second == 0)
+ Pool.erase(Tmp);
+ }
+}
+
+inline bool StringPool::empty() const {
+ std::lock_guard<std::mutex> Lock(PoolMutex);
+ return Pool.empty();
+}
+
+} // end namespace __orc_rt
+
+namespace std {
+
+// Make PooledStringPtrs hashable.
+template <> struct hash<__orc_rt::PooledStringPtr> {
+ size_t operator()(const __orc_rt::PooledStringPtr &A) const {
+ return hash<__orc_rt::PooledStringPtr::PoolEntryPtr>()(A.S);
+ }
+};
+
+} // namespace std
+
+#endif // ORC_RT_REF_COUNTED_STRING_POOL_H
diff --git a/lib/orc/tests/unit/CMakeLists.txt b/lib/orc/tests/unit/CMakeLists.txt
index a5b2a0e..e8cd2f9 100644
--- a/lib/orc/tests/unit/CMakeLists.txt
+++ b/lib/orc/tests/unit/CMakeLists.txt
@@ -8,6 +8,7 @@
orc_unit_test_main.cpp
wrapper_function_utils_test.cpp
simple_packed_serialization_test.cpp
+ string_pool_test.cpp
)
if (COMPILER_RT_CAN_EXECUTE_TESTS)
diff --git a/lib/orc/tests/unit/string_pool_test.cpp b/lib/orc/tests/unit/string_pool_test.cpp
new file mode 100644
index 0000000..15ee2ce
--- /dev/null
+++ b/lib/orc/tests/unit/string_pool_test.cpp
@@ -0,0 +1,66 @@
+//===---------- string_pool_test.cpp - Unit tests for StringPool ----------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "string_pool.h"
+#include "gtest/gtest.h"
+
+using namespace __orc_rt;
+
+namespace {
+
+TEST(StringPool, UniquingAndComparisons) {
+ StringPool SP;
+ auto P1 = SP.intern("hello");
+
+ std::string S("hel");
+ S += "lo";
+ auto P2 = SP.intern(S);
+
+ auto P3 = SP.intern("goodbye");
+
+ EXPECT_EQ(P1, P2) << "Failed to unique entries";
+ EXPECT_NE(P1, P3) << "Unequal pooled strings comparing equal";
+
+ // We want to test that less-than comparison of PooledStringPtrs compiles,
+ // however we can't test the actual result as this is a pointer comparison and
+ // PooledStringPtr doesn't expose the underlying address of the string.
+ (void)(P1 < P3);
+}
+
+TEST(StringPool, Dereference) {
+ StringPool SP;
+ auto Foo = SP.intern("foo");
+ EXPECT_EQ(*Foo, "foo") << "Equality on dereferenced string failed";
+}
+
+TEST(StringPool, ClearDeadEntries) {
+ StringPool SP;
+ {
+ auto P1 = SP.intern("s1");
+ SP.clearDeadEntries();
+ EXPECT_FALSE(SP.empty()) << "\"s1\" entry in pool should still be retained";
+ }
+ SP.clearDeadEntries();
+ EXPECT_TRUE(SP.empty()) << "pool should be empty";
+}
+
+TEST(StringPool, NullPtr) {
+ // Make sure that we can default construct and then destroy a null
+ // PooledStringPtr.
+ PooledStringPtr Null;
+}
+
+TEST(StringPool, Hashable) {
+ StringPool SP;
+ PooledStringPtr P1 = SP.intern("s1");
+ PooledStringPtr Null;
+ EXPECT_NE(std::hash<PooledStringPtr>()(P1),
+ std::hash<PooledStringPtr>()(Null));
+}
+
+} // end anonymous namespace
