Add 3-way comparisons to the resolver layer instead of using operator<.

A 3-way comparison is the traditional "return <0, =0, or >0" protocol.
The implementation supports compile-time polymorphism to select the most
appropriate comparison, defaulting to operator<.

This yields a huge improvement in the program run-time, probably because
the program compares lots of complex objects, especially things like
imm::set objects that build their comparison from sub-comparisons.

It would still be good to overload compare3<> on the types used in the
aptitude resolver universe -- although the core types are simple enough
that the compiler will probably be able to optimize the extra
comparisons away (I hope, anyway).

1 files changed, 23 insertions, 0 deletions

diff --git a/src/generic/problemresolver/incremental_expression.h b/src/generic/problemresolver/incremental_expression.h
index 8d7bd1bb..b62794ff 100644
--- a/src/generic/problemresolver/incremental_expression.h
+++ b/src/generic/problemresolver/incremental_expression.h
@@ -24,6 +24,7 @@
 #include <cwidget/generic/util/eassert.h>
 #include <cwidget/generic/util/ref_ptr.h>
 
+#include <generic/util/compare3.h>
 #include <generic/util/refcounted_base.h>
 
 #include <algorithm>
@@ -123,6 +124,11 @@ public:
     return expr == other;
   }
 
+  int compare(const expression_weak_ref &other) const
+  {
+    return aptitude::util::compare3(expr, other.expr);
+  }
+
   bool operator<(const expression_weak_ref &other) const
   {
     return expr < other.expr;
@@ -131,6 +137,23 @@ public:
   ~expression_weak_ref();
 };
 
+namespace aptitude
+{
+  namespace util
+  {
+    template<typename T>
+    class compare3_f<expression_weak_ref<T> >
+    {
+    public:
+      int operator()(const expression_weak_ref<T> &r1,
+		     const expression_weak_ref<T> &r2) const
+      {
+	return r1.compare(r2);
+      }
+    };
+  }
+}
+
 template<typename T>
 class expression_container;