Replace OrderedSet<> instances with UniqueVector<>.
The OrderedSet<> template has a misleading name, because its
semantics are not those of an ordered set of items, but match
completely those of UniqueVector<>. The latter is also slightly
faster and uses less memory.
This CL replaces all instances of OrderedSet<> with UniqueVector<>
ones, and removes the template definition from the source tree.
Profiling shows no noticeable difference in performance or memory usage
with the Chrome and Fuchsia "gn gen" operations.
Change-Id: Ie9b8ecfc0724d07129f69c68db5e1205b49f3970
Reviewed-on: https://gn-review.googlesource.com/c/gn/+/11825
Commit-Queue: David Turner <digit@google.com>
Reviewed-by: Sylvain Defresne <sdefresne@chromium.org>
diff --git a/src/gn/desc_builder.cc b/src/gn/desc_builder.cc
index 325735a..2b4ac52 100644
--- a/src/gn/desc_builder.cc
+++ b/src/gn/desc_builder.cc
@@ -581,7 +581,7 @@
// Libs can be part of any target and get recursively pushed up the chain,
// so display them regardless of target type.
if (what(variables::kLibs)) {
- const OrderedSet<LibFile>& all_libs = target_->all_libs();
+ const UniqueVector<LibFile>& all_libs = target_->all_libs();
if (!all_libs.empty()) {
auto libs = std::make_unique<base::ListValue>();
for (size_t i = 0; i < all_libs.size(); i++)
@@ -591,7 +591,7 @@
}
if (what(variables::kLibDirs)) {
- const OrderedSet<SourceDir>& all_lib_dirs = target_->all_lib_dirs();
+ const UniqueVector<SourceDir>& all_lib_dirs = target_->all_lib_dirs();
if (!all_lib_dirs.empty()) {
auto lib_dirs = std::make_unique<base::ListValue>();
for (size_t i = 0; i < all_lib_dirs.size(); i++)
diff --git a/src/gn/ninja_binary_target_writer.cc b/src/gn/ninja_binary_target_writer.cc
index 3ad4320..50e3e29 100644
--- a/src/gn/ninja_binary_target_writer.cc
+++ b/src/gn/ninja_binary_target_writer.cc
@@ -307,7 +307,7 @@
// Followed by library search paths that have been recursively pushed
// through the dependency tree.
- const OrderedSet<SourceDir>& all_lib_dirs = target_->all_lib_dirs();
+ const UniqueVector<SourceDir>& all_lib_dirs = target_->all_lib_dirs();
if (!all_lib_dirs.empty()) {
// Since we're passing these on the command line to the linker and not
// to Ninja, we need to do shell escaping.
@@ -345,7 +345,7 @@
// Libraries that have been recursively pushed through the dependency tree.
EscapeOptions lib_escape_opts;
lib_escape_opts.mode = ESCAPE_NINJA_COMMAND;
- const OrderedSet<LibFile> all_libs = target_->all_libs();
+ const UniqueVector<LibFile>& all_libs = target_->all_libs();
for (size_t i = 0; i < all_libs.size(); i++) {
const LibFile& lib_file = all_libs[i];
const std::string& lib_value = lib_file.value();
diff --git a/src/gn/ninja_c_binary_target_writer.cc b/src/gn/ninja_c_binary_target_writer.cc
index c1432b2..cd76a16 100644
--- a/src/gn/ninja_c_binary_target_writer.cc
+++ b/src/gn/ninja_c_binary_target_writer.cc
@@ -755,7 +755,7 @@
}
// Libraries specified by paths.
- const OrderedSet<LibFile>& libs = target_->all_libs();
+ const UniqueVector<LibFile>& libs = target_->all_libs();
for (size_t i = 0; i < libs.size(); i++) {
if (libs[i].is_source_file()) {
implicit_deps.push_back(
diff --git a/src/gn/ordered_set.h b/src/gn/ordered_set.h
deleted file mode 100644
index fda4e12..0000000
--- a/src/gn/ordered_set.h
+++ /dev/null
@@ -1,63 +0,0 @@
-// Copyright (c) 2013 The Chromium Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file.
-
-#ifndef TOOLS_GN_ORDERED_SET_H_
-#define TOOLS_GN_ORDERED_SET_H_
-
-#include <stddef.h>
-
-#include <set>
-
-// An ordered set of items. Only appending is supported. Iteration is designed
-// to be by index.
-template <typename T>
-class OrderedSet {
- private:
- using set_type = std::set<T>;
- using set_iterator = typename set_type::const_iterator;
- using vector_type = std::vector<set_iterator>;
-
- public:
- static const size_t npos = static_cast<size_t>(-1);
-
- OrderedSet() {}
- ~OrderedSet() {}
-
- const T& operator[](size_t index) const { return *ordering_[index]; }
- size_t size() const { return ordering_.size(); }
- bool empty() const { return ordering_.empty(); }
-
- bool has_item(const T& t) const { return set_.find(t) != set_.end(); }
-
- // Returns true if the item was inserted. False if it was already in the
- // set.
- bool push_back(const T& t) {
- std::pair<set_iterator, bool> result = set_.insert(t);
- if (result.second)
- ordering_.push_back(result.first);
- return true;
- }
-
- // Appends a range of items, skipping ones that already exist.
- template <class InputIterator>
- void append(const InputIterator& insert_begin,
- const InputIterator& insert_end) {
- for (InputIterator i = insert_begin; i != insert_end; ++i) {
- const T& t = *i;
- push_back(t);
- }
- }
-
- // Appends all items from the given other set.
- void append(const OrderedSet<T>& other) {
- for (size_t i = 0; i < other.size(); i++)
- push_back(other[i]);
- }
-
- private:
- set_type set_;
- vector_type ordering_;
-};
-
-#endif // TOOLS_GN_ORDERED_SET_H_
diff --git a/src/gn/target.cc b/src/gn/target.cc
index cee2ed2..bd3fb58 100644
--- a/src/gn/target.cc
+++ b/src/gn/target.cc
@@ -374,13 +374,13 @@
// order (local ones first, then the dependency's).
for (ConfigValuesIterator iter(this); !iter.done(); iter.Next()) {
const ConfigValues& cur = iter.cur();
- all_lib_dirs_.append(cur.lib_dirs().begin(), cur.lib_dirs().end());
- all_libs_.append(cur.libs().begin(), cur.libs().end());
+ all_lib_dirs_.Append(cur.lib_dirs().begin(), cur.lib_dirs().end());
+ all_libs_.Append(cur.libs().begin(), cur.libs().end());
- all_framework_dirs_.append(cur.framework_dirs().begin(),
+ all_framework_dirs_.Append(cur.framework_dirs().begin(),
cur.framework_dirs().end());
- all_frameworks_.append(cur.frameworks().begin(), cur.frameworks().end());
- all_weak_frameworks_.append(cur.weak_frameworks().begin(),
+ all_frameworks_.Append(cur.frameworks().begin(), cur.frameworks().end());
+ all_weak_frameworks_.Append(cur.weak_frameworks().begin(),
cur.weak_frameworks().end());
}
@@ -722,12 +722,12 @@
// Library settings are always inherited across static library boundaries.
if (!dep->IsFinal() || dep->output_type() == STATIC_LIBRARY) {
- all_lib_dirs_.append(dep->all_lib_dirs());
- all_libs_.append(dep->all_libs());
+ all_lib_dirs_.Append(dep->all_lib_dirs());
+ all_libs_.Append(dep->all_libs());
- all_framework_dirs_.append(dep->all_framework_dirs());
- all_frameworks_.append(dep->all_frameworks());
- all_weak_frameworks_.append(dep->all_weak_frameworks());
+ all_framework_dirs_.Append(dep->all_framework_dirs());
+ all_frameworks_.Append(dep->all_frameworks());
+ all_weak_frameworks_.Append(dep->all_weak_frameworks());
}
}
diff --git a/src/gn/target.h b/src/gn/target.h
index 15fb635..96f80f2 100644
--- a/src/gn/target.h
+++ b/src/gn/target.h
@@ -21,7 +21,6 @@
#include "gn/label_ptr.h"
#include "gn/lib_file.h"
#include "gn/metadata.h"
-#include "gn/ordered_set.h"
#include "gn/output_file.h"
#include "gn/rust_values.h"
#include "gn/source_file.h"
@@ -286,16 +285,16 @@
RustValues& rust_values() { return rust_values_; }
const RustValues& rust_values() const { return rust_values_; }
- const OrderedSet<SourceDir>& all_lib_dirs() const { return all_lib_dirs_; }
- const OrderedSet<LibFile>& all_libs() const { return all_libs_; }
+ const UniqueVector<SourceDir>& all_lib_dirs() const { return all_lib_dirs_; }
+ const UniqueVector<LibFile>& all_libs() const { return all_libs_; }
- const OrderedSet<SourceDir>& all_framework_dirs() const {
+ const UniqueVector<SourceDir>& all_framework_dirs() const {
return all_framework_dirs_;
}
- const OrderedSet<std::string>& all_frameworks() const {
+ const UniqueVector<std::string>& all_frameworks() const {
return all_frameworks_;
}
- const OrderedSet<std::string>& all_weak_frameworks() const {
+ const UniqueVector<std::string>& all_weak_frameworks() const {
return all_weak_frameworks_;
}
@@ -460,14 +459,14 @@
// These libs and dirs are inherited from statically linked deps and all
// configs applying to this target.
- OrderedSet<SourceDir> all_lib_dirs_;
- OrderedSet<LibFile> all_libs_;
+ UniqueVector<SourceDir> all_lib_dirs_;
+ UniqueVector<LibFile> all_libs_;
// These frameworks and dirs are inherited from statically linked deps and
// all configs applying to this target.
- OrderedSet<SourceDir> all_framework_dirs_;
- OrderedSet<std::string> all_frameworks_;
- OrderedSet<std::string> all_weak_frameworks_;
+ UniqueVector<SourceDir> all_framework_dirs_;
+ UniqueVector<std::string> all_frameworks_;
+ UniqueVector<std::string> all_weak_frameworks_;
// All hard deps from this target and all dependencies. Filled in when this
// target is marked resolved. This will not include the current target.
diff --git a/src/gn/unique_vector.h b/src/gn/unique_vector.h
index 91bf726..821f55a 100644
--- a/src/gn/unique_vector.h
+++ b/src/gn/unique_vector.h
@@ -126,6 +126,10 @@
push_back(*i);
}
+ 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 {
