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 {