From a643af2207f8f090d2a7aefeec954fcd2725c39c Mon Sep 17 00:00:00 2001
From: Peter Bell <peterbell10@live.co.uk>
Date: Tue, 8 Mar 2022 02:44:03 +0000
Subject: Pool: sort equally-weighted edges by priority

---
 src/graph.h | 13 ++++++++++---
 src/state.h |  5 ++++-
 2 files changed, 14 insertions(+), 4 deletions(-)

diff --git a/src/graph.h b/src/graph.h
index 728cdc8..4fc34ca 100644
--- a/src/graph.h
+++ b/src/graph.h
@@ -384,14 +384,14 @@ struct DependencyScan {
   DyndepLoader dyndep_loader_;
 };
 
-// Implements a less comarison for edges by priority, where highest
+// Implements a less comparison for edges by priority, where highest
 // priority is defined lexicographically first by largest critical
 // time, then lowest ID.
 //
 // Including ID means that wherever the critical times are the same,
 // the edges are executed in ascending ID order which was historically
 // how all tasks were scheduled.
-struct EdgePriorityCompare {
+struct EdgePriorityLess {
   bool operator()(const Edge* e1, const Edge* e2) const {
     const int64_t ct1 = e1->critical_time();
     const int64_t ct2 = e2->critical_time();
@@ -402,11 +402,18 @@ struct EdgePriorityCompare {
   }
 };
 
+// Reverse of EdgePriorityLess, e.g. to sort by highest priority first
+struct EdgePriorityGreater {
+  bool operator()(const Edge* e1, const Edge* e2) const {
+    return EdgePriorityLess()(e2, e1);
+  }
+};
+
 // A priority queue holding non-owning Edge pointers. top() will
 // return the edge with the largest critical time, and lowest ID if
 // more than one edge has the same critical time.
 class EdgePriorityQueue:
-  public std::priority_queue<Edge*, std::vector<Edge*>, EdgePriorityCompare>{
+  public std::priority_queue<Edge*, std::vector<Edge*>, EdgePriorityLess>{
 public:
   void clear() {
     c.clear();
diff --git a/src/state.h b/src/state.h
index 2b0fa90..05fb50e 100644
--- a/src/state.h
+++ b/src/state.h
@@ -80,7 +80,10 @@ struct Pool {
       if (!a) return b;
       if (!b) return false;
       int weight_diff = a->weight() - b->weight();
-      return ((weight_diff < 0) || (weight_diff == 0 && EdgeCmp()(a, b)));
+      if (weight_diff != 0) {
+        return weight_diff < 0;
+      }
+      return EdgePriorityGreater()(a, b);
     }
   };
 
-- 
cgit v0.12