Improve UniqueVector class.
This improves the UniqueVector template class in several ways,
which will be used by future CLs:
- Allow custom hash and equality operators to be used for
the items in the set.
- Make the UniqueVectorNode internal set type smaller by using
32-bit indices and hash values, reducing the RAM footproint of
each instance.
- Add Contains() method, and kIndexNone value, returned by IndexOf()
when the value is not found, replacing the hard-coded (size_t)-1
value.
- Add emplace_back() method for convenience.
- Add a release() method to move the final vector out of the
instance.
- Add PushBackWithIndex(), EmplaceBackWithIndex() methods to
perform push_back() / emplace_back() while returning a
(insertion_flag, item_index) value.
Bug: None
Change-Id: I381cd05f5fc8fadf06d66379a1ead67c9f940267
Reviewed-on: https://gn-review.googlesource.com/c/gn/+/12701
Reviewed-by: Brett Wilson <brettw@chromium.org>
Commit-Queue: David Turner <digit@google.com>
diff --git a/src/gn/ninja_c_binary_target_writer.cc b/src/gn/ninja_c_binary_target_writer.cc
index 376c943..5b518b3 100644
--- a/src/gn/ninja_c_binary_target_writer.cc
+++ b/src/gn/ninja_c_binary_target_writer.cc
@@ -213,7 +213,7 @@
AddSourceSetFiles(target_, &computed_obj);
DCHECK_EQ(obj_files.size(), computed_obj.size());
for (const auto& obj : obj_files)
- DCHECK_NE(static_cast<size_t>(-1), computed_obj.IndexOf(obj));
+ DCHECK(computed_obj.Contains(obj));
#endif
} else {
WriteLinkerStuff(obj_files, other_files, input_deps);
@@ -754,11 +754,10 @@
}
// Libraries specified by paths.
- const UniqueVector<LibFile>& libs = target_->all_libs();
- for (size_t i = 0; i < libs.size(); i++) {
- if (libs[i].is_source_file()) {
+ for (const auto& lib : target_->all_libs()) {
+ if (lib.is_source_file()) {
implicit_deps.push_back(
- OutputFile(settings_->build_settings(), libs[i].source_file()));
+ OutputFile(settings_->build_settings(), lib.source_file()));
}
}
diff --git a/src/gn/unique_vector.h b/src/gn/unique_vector.h
index 821f55a..da4edc2 100644
--- a/src/gn/unique_vector.h
+++ b/src/gn/unique_vector.h
@@ -6,6 +6,7 @@
#define TOOLS_GN_UNIQUE_VECTOR_H_
#include <stddef.h>
+#include <stdint.h>
#include <algorithm>
#include <vector>
@@ -17,10 +18,10 @@
// to follow the HashTableBase requirements (i.e. zero-initializable null
// value).
struct UniqueVectorNode {
- size_t hash;
- size_t index_plus1;
+ uint32_t hash32;
+ uint32_t index_plus1;
- size_t hash_value() const { return hash; }
+ size_t hash_value() const { return hash32; }
bool is_valid() const { return !is_null(); }
@@ -32,9 +33,11 @@
// Return vector index.
size_t index() const { return index_plus1 - 1u; }
+ static uint32_t ToHash32(size_t hash) { return static_cast<uint32_t>(hash); }
+
// Create new instance from hash value and vector index.
static UniqueVectorNode Make(size_t hash, size_t index) {
- return {hash, index + 1u};
+ return {ToHash32(hash), static_cast<uint32_t>(index + 1u)};
}
};
@@ -52,10 +55,11 @@
// |vector| is containing vector for existing items.
//
// Returns a non-null mutable Node pointer.
- template <typename T>
+ template <typename T, typename EqualTo = std::equal_to<T>>
Node* Lookup(size_t hash, const T& item, const std::vector<T>& vector) const {
- return BaseType::NodeLookup(hash, [&](const Node* node) {
- return node->hash == hash && vector[node->index()] == item;
+ uint32_t hash32 = Node::ToHash32(hash);
+ return BaseType::NodeLookup(hash32, [&](const Node* node) {
+ return hash32 == node->hash32 && EqualTo()(vector[node->index()], item);
});
}
@@ -72,7 +76,9 @@
// An ordered set optimized for GN's usage. Such sets are used to store lists
// of configs and libraries, and are appended to but not randomly inserted
// into.
-template <typename T>
+template <typename T,
+ typename Hash = std::hash<T>,
+ typename EqualTo = std::equal_to<T>>
class UniqueVector {
public:
using Vector = std::vector<T>;
@@ -93,32 +99,85 @@
const_iterator begin() const { return vector_.begin(); }
const_iterator end() const { return vector_.end(); }
+ // Extract the vector out of the instance, clearing it at the same time.
+ Vector release() {
+ Vector result = std::move(vector_);
+ clear();
+ return result;
+ }
+
// Returns true if the item was appended, false if it already existed (and
// thus the vector was not modified).
bool push_back(const T& t) {
- size_t hash = std::hash<T>()(t);
- auto* node = set_.Lookup(hash, t, vector_);
+ size_t hash;
+ auto* node = Lookup(t, &hash);
if (node->is_valid()) {
return false; // Already have this one.
}
-
vector_.push_back(t);
set_.Insert(node, hash, vector_.size() - 1);
return true;
}
+ // Same as above, but moves the item into the vector if possible.
bool push_back(T&& t) {
- size_t hash = std::hash<T>()(t);
- auto* node = set_.Lookup(hash, t, vector_);
+ size_t hash = Hash()(t);
+ auto* node = Lookup(t, &hash);
if (node->is_valid()) {
return false; // Already have this one.
}
-
vector_.push_back(std::move(t));
set_.Insert(node, hash, vector_.size() - 1);
return true;
}
+ // Construct an item in-place if possible. Return true if it was
+ // appended, false otherwise.
+ template <typename... ARGS>
+ bool emplace_back(ARGS... args) {
+ return push_back(T{std::forward<ARGS>(args)...});
+ }
+
+ // Try to add an item to the vector. Return (true, index) in
+ // case of insertion, or (false, index) otherwise. In both cases
+ // |index| will be the item's index in the set and will not be
+ // kIndexNone. This can be used to implement a map using a
+ // UniqueVector<> for keys, and a parallel array for values.
+ std::pair<bool, size_t> PushBackWithIndex(const T& t) {
+ size_t hash;
+ auto* node = Lookup(t, &hash);
+ if (node->is_valid()) {
+ return {false, node->index()};
+ }
+ size_t result = vector_.size();
+ vector_.push_back(t);
+ set_.Insert(node, hash, result);
+ return {true, result};
+ }
+
+ // Same as above, but moves the item into the set on success.
+ std::pair<bool, size_t> PushBackWithIndex(T&& t) {
+ size_t hash;
+ auto* node = Lookup(t, &hash);
+ if (node->is_valid()) {
+ return {false, node->index()};
+ }
+ size_t result = vector_.size();
+ vector_.push_back(std::move(t));
+ set_.Insert(node, hash, result);
+ return {true, result};
+ }
+
+ // Construct an item in-place if possible. If a corresponding
+ // item is already in the vector, return (false, index), otherwise
+ // perform the insertion and return (true, index). In both cases
+ // |index| will be the item's index in the vector and will not be
+ // kIndexNone.
+ template <typename... ARGS>
+ std::pair<bool, size_t> EmplaceBackWithIndex(ARGS... args) {
+ return PushBackWithIndex(T{std::forward<ARGS>(args)...});
+ }
+
// Appends a range of items from an iterator.
template <typename iter>
void Append(const iter& begin, const iter& end) {
@@ -126,19 +185,33 @@
push_back(*i);
}
+ // Append another vector into this one.
void Append(const UniqueVector& other) {
Append(other.begin(), other.end());
}
- // Returns the index of the item matching the given value in the list, or
- // (size_t)(-1) if it's not found.
- size_t IndexOf(const T& t) const {
- size_t hash = std::hash<T>()(t);
- auto* node = set_.Lookup(hash, t, vector_);
- return node->index();
+ // Returns true if the item is already in the vector.
+ bool Contains(const T& t) const {
+ size_t hash;
+ return Lookup(t, &hash)->is_valid();
}
+ // Returns the index of the item matching the given value in the list, or
+ // kIndexNone if it's not found.
+ size_t IndexOf(const T& t) const {
+ size_t hash;
+ return Lookup(t, &hash)->index();
+ }
+
+ static constexpr size_t kIndexNone = 0xffffffffu;
+
private:
+ // Lookup hash set node for item |t|, also sets |*hash| to the hash value.
+ UniqueVectorNode* Lookup(const T& t, size_t* hash) const {
+ *hash = Hash()(t);
+ return set_.Lookup<T, EqualTo>(*hash, t, vector_);
+ }
+
Vector vector_;
UniqueVectorHashSet set_;
};
diff --git a/src/gn/unique_vector_unittest.cc b/src/gn/unique_vector_unittest.cc
index 96303b4..186cefb 100644
--- a/src/gn/unique_vector_unittest.cc
+++ b/src/gn/unique_vector_unittest.cc
@@ -28,7 +28,8 @@
EXPECT_EQ(0u, foo.IndexOf(1));
EXPECT_EQ(1u, foo.IndexOf(2));
EXPECT_EQ(2u, foo.IndexOf(0));
- EXPECT_EQ(static_cast<size_t>(-1), foo.IndexOf(99));
+ EXPECT_FALSE(foo.Contains(98));
+ EXPECT_EQ(foo.kIndexNone, foo.IndexOf(99));
}
TEST(UniqueVector, PushBackMove) {
@@ -43,3 +44,85 @@
EXPECT_EQ(0u, vect.IndexOf("a"));
}
+
+TEST(UniqueVector, EmplaceBack) {
+ UniqueVector<std::string> vect;
+ EXPECT_TRUE(vect.emplace_back("a"));
+ EXPECT_FALSE(vect.emplace_back("a"));
+ EXPECT_EQ(1u, vect.size());
+ EXPECT_TRUE(vect.emplace_back("b"));
+
+ EXPECT_EQ(2u, vect.size());
+ EXPECT_TRUE(vect.Contains(std::string("a")));
+ EXPECT_TRUE(vect.Contains(std::string("b")));
+}
+
+static auto MakePair(bool first, size_t second) -> std::pair<bool, size_t> {
+ return {first, second};
+}
+
+TEST(UniqueVector, PushBackWithIndex) {
+ UniqueVector<int> foo;
+
+ EXPECT_EQ(MakePair(true, 0u), foo.PushBackWithIndex(1));
+ EXPECT_EQ(MakePair(false, 0u), foo.PushBackWithIndex(1));
+ EXPECT_EQ(MakePair(true, 1u), foo.PushBackWithIndex(2));
+ EXPECT_EQ(MakePair(true, 2u), foo.PushBackWithIndex(3));
+ EXPECT_EQ(MakePair(false, 0u), foo.PushBackWithIndex(1));
+ EXPECT_EQ(MakePair(false, 1u), foo.PushBackWithIndex(2));
+ EXPECT_EQ(MakePair(false, 2u), foo.PushBackWithIndex(3));
+
+ EXPECT_TRUE(foo.Contains(1));
+ EXPECT_TRUE(foo.Contains(2));
+ EXPECT_TRUE(foo.Contains(3));
+ EXPECT_EQ(0u, foo.IndexOf(1));
+ EXPECT_EQ(1u, foo.IndexOf(2));
+ EXPECT_EQ(2u, foo.IndexOf(3));
+ EXPECT_EQ(foo.kIndexNone, foo.IndexOf(98));
+}
+
+TEST(UniqueVector, PushBackMoveWithIndex) {
+ UniqueVector<std::string> vect;
+ std::string a("a");
+ EXPECT_EQ(MakePair(true, 0), vect.PushBackWithIndex(std::move(a)));
+ EXPECT_EQ("", a);
+
+ a = "a";
+ EXPECT_EQ(MakePair(false, 0), vect.PushBackWithIndex(std::move(a)));
+ EXPECT_EQ("a", a);
+
+ EXPECT_EQ(0u, vect.IndexOf("a"));
+}
+
+TEST(UniqueVector, EmplaceBackWithIndex) {
+ UniqueVector<std::string> vect;
+ EXPECT_EQ(MakePair(true, 0u), vect.EmplaceBackWithIndex("a"));
+ EXPECT_EQ(MakePair(false, 0u), vect.EmplaceBackWithIndex("a"));
+ EXPECT_EQ(1u, vect.size());
+
+ EXPECT_EQ(MakePair(true, 1u), vect.EmplaceBackWithIndex("b"));
+ EXPECT_EQ(2u, vect.size());
+
+ EXPECT_TRUE(vect.Contains(std::string("a")));
+ EXPECT_TRUE(vect.Contains(std::string("b")));
+}
+
+TEST(UniqueVector, Release) {
+ UniqueVector<std::string> vect;
+ EXPECT_TRUE(vect.emplace_back("a"));
+ EXPECT_TRUE(vect.emplace_back("b"));
+ EXPECT_TRUE(vect.emplace_back("c"));
+
+ std::vector<std::string> v = vect.release();
+ EXPECT_TRUE(vect.empty());
+ EXPECT_FALSE(v.empty());
+
+ EXPECT_FALSE(vect.Contains(std::string("a")));
+ EXPECT_FALSE(vect.Contains(std::string("b")));
+ EXPECT_FALSE(vect.Contains(std::string("a")));
+
+ EXPECT_EQ(3u, v.size());
+ EXPECT_EQ(std::string("a"), v[0]);
+ EXPECT_EQ(std::string("b"), v[1]);
+ EXPECT_EQ(std::string("c"), v[2]);
+}
