From 24d1f5f0c130338b382c60eb32731d2638b47d03 Mon Sep 17 00:00:00 2001
From: Peter Bell <peterbell10@live.co.uk>
Date: Mon, 7 Mar 2022 16:48:04 +0000
Subject: Address review comments

1. Move EdgePriorityQueue to graph.h and inherit from priority_queue
2. Add comment about edge->critical_time()
---
 src/build.cc | 18 ++++++------------
 src/build.h  | 36 ------------------------------------
 src/graph.h  | 33 +++++++++++++++++++++++++++++++++
 3 files changed, 39 insertions(+), 48 deletions(-)

diff --git a/src/build.cc b/src/build.cc
index 6f9cf27..d747b8a 100644
--- a/src/build.cc
+++ b/src/build.cc
@@ -76,15 +76,6 @@ bool DryRunCommandRunner::WaitForCommand(Result* result) {
 }  // namespace
 
 
-bool EdgeQueue::EdgePriorityCompare::operator()(const Edge* e1, const Edge* e2) const {
-  const int64_t ct1 = e1->critical_time();
-  const int64_t ct2 = e2->critical_time();
-  if (ct1 != ct2) {
-    return ct1 < ct2;
-  }
-  return e1->id_ < e2->id_;
-}
-
 Plan::Plan(Builder* builder)
   : builder_(builder)
   , command_edges_(0)
@@ -162,7 +153,10 @@ void Plan::EdgeWanted(const Edge* edge) {
 Edge* Plan::FindWork() {
   if (ready_.empty())
     return NULL;
-  return ready_.pop();
+
+  Edge* work = ready_.top();
+  ready_.pop();
+  return work;
 }
 
 void Plan::ScheduleWork(map<Edge*, Want>::iterator want_e) {
@@ -182,7 +176,7 @@ void Plan::ScheduleWork(map<Edge*, Want>::iterator want_e) {
     pool->DelayEdge(edge);
     EdgeSet new_edges;
     pool->RetrieveReadyEdges(&new_edges);
-    ready_.push(new_edges.begin(), new_edges.end());
+    ready_.push_multiple(new_edges.begin(), new_edges.end());
   } else {
     pool->EdgeScheduled(*edge);
     ready_.push(edge);
@@ -199,7 +193,7 @@ bool Plan::EdgeFinished(Edge* edge, EdgeResult result, string* err) {
     edge->pool()->EdgeFinished(*edge);
   EdgeSet new_edges;
   edge->pool()->RetrieveReadyEdges(&new_edges);
-  ready_.push(new_edges.begin(), new_edges.end());
+  ready_.push_multiple(new_edges.begin(), new_edges.end());
 
   // The rest of this function only applies to successful commands.
   if (result != kEdgeSucceeded)
diff --git a/src/build.h b/src/build.h
index 9b49ffb..652bc40 100644
--- a/src/build.h
+++ b/src/build.h
@@ -18,7 +18,6 @@
 #include <cstdio>
 #include <map>
 #include <memory>
-#include <queue>
 #include <string>
 #include <vector>
 
@@ -36,41 +35,6 @@ struct State;
 struct Status;
 
 
-// Set of ready edges, sorted by priority
-class EdgeQueue {
-  struct EdgePriorityCompare {
-    bool operator()(const Edge* e1, const Edge* e2) const;
-  };
-
-  std::priority_queue<Edge*, std::vector<Edge*>, EdgePriorityCompare> queue_;
-
- public:
-  void push(Edge* edge) {
-    queue_.push(edge);
-  }
-
-  template <typename It>
-  void push(It first, It last) {
-    for (; first != last; ++first) {
-      push(*first);
-    }
-  }
-
-  Edge* pop() {
-    Edge* ret = queue_.top();
-    queue_.pop();
-    return ret;
-  }
-
-  void clear() {
-    queue_ = std::priority_queue<Edge*, std::vector<Edge*>, EdgePriorityCompare>();
-  }
-
-  size_t size() const { return queue_.size(); }
-
-  bool empty() const { return queue_.empty(); }
-};
-
 /// Plan stores the state of a build plan: what we intend to build,
 /// which steps we're ready to execute.
 struct Plan {
diff --git a/src/graph.h b/src/graph.h
index 7851504..a8bf0cd 100644
--- a/src/graph.h
+++ b/src/graph.h
@@ -18,6 +18,7 @@
 #include <set>
 #include <string>
 #include <vector>
+#include <queue>
 
 #include "dyndep.h"
 #include "eval_env.h"
@@ -172,6 +173,10 @@ struct Edge {
 
   void Dump(const char* prefix="") const;
 
+  // Critical time is the estimated exection time in ms of the edges
+  // forming the longest time-weighted path to the target output.
+  // This quantity is used as a priority during build scheduling.
+  // NOTE: Defaults to -1 as a marker smaller than any valid time
   int64_t critical_time() const { return critical_time_; }
   void set_critical_time(int64_t critical_time) {
     critical_time_ = critical_time;
@@ -343,4 +348,32 @@ struct DependencyScan {
   DyndepLoader dyndep_loader_;
 };
 
+// Prioritize edges by largest critical time first
+struct EdgePriorityCompare {
+  bool operator()(const Edge* e1, const Edge* e2) const {
+    const int64_t ct1 = e1->critical_time();
+    const int64_t ct2 = e2->critical_time();
+    if (ct1 != ct2) {
+      return ct1 < ct2;
+    }
+    return e1->id_ < e2->id_;
+  }
+};
+
+// Set of ready edges, sorted by priority
+class EdgeQueue:
+  public std::priority_queue<Edge*, std::vector<Edge*>, EdgePriorityCompare>{
+public:
+  void clear() {
+    c.clear();
+  }
+
+  template <typename It>
+  void push_multiple(It first, It last) {
+    for (; first != last; ++first) {
+      push(*first);
+    }
+  }
+};
+
 #endif  // NINJA_GRAPH_H_
-- 
cgit v0.12