diff options
-rw-r--r-- | src/build.cc | 40 |
1 files changed, 11 insertions, 29 deletions
diff --git a/src/build.cc b/src/build.cc index 7e2ccfa..fb29732 100644 --- a/src/build.cc +++ b/src/build.cc @@ -16,11 +16,13 @@ #include <assert.h> #include <errno.h> +#include <stdint.h> #include <stdio.h> #include <stdlib.h> + #include <climits> -#include <stdint.h> #include <functional> +#include <unordered_set> #if defined(__SVR4) && defined(__sun) #include <sys/termios.h> @@ -451,18 +453,6 @@ void Plan::UnmarkDependents(const Node* node, set<Node*>* dependents) { namespace { -template <typename T> -struct SeenBefore { - std::set<const T*>* seen_; - - SeenBefore(std::set<const T*>* seen) : seen_(seen) {} - - bool operator() (const T* item) { - // Return true if the item has been seen before - return !seen_->insert(item).second; - } -}; - // Heuristic for edge priority weighting. // Phony edges are free (0 cost), all other edges are weighted equally. int64_t EdgeWeightHeuristic(Edge *edge) { @@ -474,28 +464,22 @@ int64_t EdgeWeightHeuristic(Edge *edge) { void Plan::ComputeCriticalPath() { METRIC_RECORD("ComputeCriticalPath"); // Remove duplicate targets - { - std::set<const Node*> seen; - SeenBefore<Node> seen_before(&seen); - targets_.erase(std::remove_if(targets_.begin(), targets_.end(), seen_before), - targets_.end()); - } + std::unordered_set<const Node*> unique_targets(targets_.begin(), + targets_.end()); // Use backflow algorithm to compute the critical path for all // nodes, starting from the destination nodes. // XXX: ignores pools std::queue<Edge*> work_queue; // Queue, for breadth-first traversal // The set of edges currently in work_queue, to avoid duplicates. - std::set<const Edge*> active_edges; - SeenBefore<Edge> seen_edge(&active_edges); + std::unordered_set<const Edge*> active_edges; - for (size_t i = 0; i < targets_.size(); ++i) { - const Node* target = targets_[i]; + for (const Node* target : unique_targets) { if (Edge* in = target->in_edge()) { int64_t edge_weight = EdgeWeightHeuristic(in); in->set_critical_path_weight( std::max<int64_t>(edge_weight, in->critical_path_weight())); - if (!seen_edge(in)) { + if (active_edges.insert(in).second) { work_queue.push(in); } } @@ -508,10 +492,8 @@ void Plan::ComputeCriticalPath() { // edge may need to be processed again. So re-allow insertion. active_edges.erase(e); - for (std::vector<Node*>::iterator it = e->inputs_.begin(), - end = e->inputs_.end(); - it != end; ++it) { - Edge* in = (*it)->in_edge(); + for (const Node* input : e->inputs_) { + Edge* in = input->in_edge(); if (!in) { continue; } @@ -520,7 +502,7 @@ void Plan::ComputeCriticalPath() { const int64_t proposed_weight = e->critical_path_weight() + edge_weight; if (proposed_weight > in->critical_path_weight()) { in->set_critical_path_weight(proposed_weight); - if (!seen_edge(in)) { + if (active_edges.insert(in).second) { work_queue.push(in); } } |