utils: Add UniqueAllocator
UniqueAllocator is used to allocate unique instances of the template type.
This will be used to clean up duplicated code we have throughout Tint.
Change-Id: I79d5834bf7c7c31cdefd38d4fa3b9240f7ebbf5f
Reviewed-on: https://dawn-review.googlesource.com/c/tint/+/82741
Reviewed-by: James Price <jrprice@google.com>
Kokoro: Kokoro <noreply+kokoro@google.com>
Commit-Queue: Ben Clayton <bclayton@google.com>
diff --git a/src/tint/BUILD.gn b/src/tint/BUILD.gn
index 91784c4..1b008a7 100644
--- a/src/tint/BUILD.gn
+++ b/src/tint/BUILD.gn
@@ -511,6 +511,7 @@
"utils/math.h",
"utils/scoped_assignment.h",
"utils/string.h",
+ "utils/unique_allocator.h",
"utils/unique_vector.h",
"writer/append_vector.cc",
"writer/append_vector.h",
diff --git a/src/tint/CMakeLists.txt b/src/tint/CMakeLists.txt
index 0735873..4a87d2c 100644
--- a/src/tint/CMakeLists.txt
+++ b/src/tint/CMakeLists.txt
@@ -435,6 +435,7 @@
utils/math.h
utils/scoped_assignment.h
utils/string.h
+ utils/unique_allocator.h
utils/unique_vector.h
writer/append_vector.cc
writer/append_vector.h
@@ -795,6 +796,7 @@
utils/scoped_assignment_test.cc
utils/string_test.cc
utils/transform_test.cc
+ utils/unique_allocator_test.cc
utils/unique_vector_test.cc
writer/append_vector_test.cc
writer/float_to_string_test.cc
diff --git a/src/tint/utils/unique_allocator.h b/src/tint/utils/unique_allocator.h
new file mode 100644
index 0000000..264ff4c
--- /dev/null
+++ b/src/tint/utils/unique_allocator.h
@@ -0,0 +1,72 @@
+// Copyright 2022 The Tint Authors.
+//
+// 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_TINT_UTILS_UNIQUE_ALLOCATOR_H_
+#define SRC_TINT_UTILS_UNIQUE_ALLOCATOR_H_
+
+#include <functional>
+#include <unordered_set>
+#include <utility>
+
+#include "src/tint/utils/block_allocator.h"
+
+namespace tint::utils {
+
+/// UniqueAllocator is used to allocate unique instances of the template type
+/// `T`.
+template <typename T,
+ typename HASH = std::hash<T>,
+ typename EQUAL = std::equal_to<T>>
+class UniqueAllocator {
+ public:
+ /// @param args the arguments used to construct the object.
+ /// @return a pointer to an instance of `T` with the provided arguments.
+ /// If an existing instance of `T` has been constructed, then the same
+ /// pointer is returned.
+ template <typename... ARGS>
+ T* Get(ARGS&&... args) {
+ // Create a temporary T instance on the stack so that we can hash it, and
+ // use it for equality lookup for the std::unordered_set. If the item is not
+ // found in the set, then we create the persisted instance with the
+ // allocator.
+ T key{args...};
+ auto hash = HASH{}(key);
+ auto it = items.find(Entry{hash, &key});
+ if (it != items.end()) {
+ return it->ptr;
+ }
+ auto* ptr = allocator.Create(std::forward<ARGS>(args)...);
+ items.emplace_hint(it, Entry{hash, ptr});
+ return ptr;
+ }
+
+ private:
+ struct Entry {
+ size_t hash;
+ T* ptr;
+ };
+ struct Hasher {
+ size_t operator()(Entry e) const { return e.hash; }
+ };
+ struct Comparator {
+ bool operator()(Entry a, Entry b) const { return EQUAL{}(*a.ptr, *b.ptr); }
+ };
+
+ BlockAllocator<T> allocator;
+ std::unordered_set<Entry, Hasher, Comparator> items;
+};
+
+} // namespace tint::utils
+
+#endif // SRC_TINT_UTILS_UNIQUE_ALLOCATOR_H_
diff --git a/src/tint/utils/unique_allocator_test.cc b/src/tint/utils/unique_allocator_test.cc
new file mode 100644
index 0000000..d8d62df
--- /dev/null
+++ b/src/tint/utils/unique_allocator_test.cc
@@ -0,0 +1,52 @@
+// Copyright 2022 The Tint Authors.
+//
+// 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/tint/utils/unique_allocator.h"
+
+#include <string>
+
+#include "gtest/gtest.h"
+
+namespace tint::utils {
+namespace {
+
+TEST(UniqueAllocator, Int) {
+ UniqueAllocator<int> a;
+ EXPECT_NE(a.Get(0), a.Get(1));
+ EXPECT_NE(a.Get(1), a.Get(2));
+ EXPECT_EQ(a.Get(0), a.Get(0));
+ EXPECT_EQ(a.Get(1), a.Get(1));
+ EXPECT_EQ(a.Get(2), a.Get(2));
+}
+
+TEST(UniqueAllocator, Float) {
+ UniqueAllocator<float> a;
+ EXPECT_NE(a.Get(0.1f), a.Get(1.1f));
+ EXPECT_NE(a.Get(1.1f), a.Get(2.1f));
+ EXPECT_EQ(a.Get(0.1f), a.Get(0.1f));
+ EXPECT_EQ(a.Get(1.1f), a.Get(1.1f));
+ EXPECT_EQ(a.Get(2.1f), a.Get(2.1f));
+}
+
+TEST(UniqueAllocator, String) {
+ UniqueAllocator<std::string> a;
+ EXPECT_NE(a.Get("x"), a.Get("y"));
+ EXPECT_NE(a.Get("z"), a.Get("w"));
+ EXPECT_EQ(a.Get("x"), a.Get("x"));
+ EXPECT_EQ(a.Get("y"), a.Get("y"));
+ EXPECT_EQ(a.Get("z"), a.Get("z"));
+}
+
+} // namespace
+} // namespace tint::utils
diff --git a/test/tint/BUILD.gn b/test/tint/BUILD.gn
index 8099317..1da094b 100644
--- a/test/tint/BUILD.gn
+++ b/test/tint/BUILD.gn
@@ -361,6 +361,7 @@
"../../src/tint/utils/scoped_assignment_test.cc",
"../../src/tint/utils/string_test.cc",
"../../src/tint/utils/transform_test.cc",
+ "../../src/tint/utils/unique_allocator_test.cc",
"../../src/tint/utils/unique_vector_test.cc",
]
}
