aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAvatar Ciaran McCreesh <ciaran.mccreesh@googlemail.com> 2010-06-29 20:51:01 +0100
committerAvatar Ciaran McCreesh <ciaran.mccreesh@googlemail.com> 2010-06-29 20:51:01 +0100
commit0bb5b18aceff1894ca456d21e836af7d878c87ac (patch)
treeff53749c24b7377dc09cb9139389283cd4596c27
parent1dfabf2c0cf23fa422234beceef4c177863e8e12 (diff)
downloadpaludis-0bb5b18aceff1894ca456d21e836af7d878c87ac.tar.gz
paludis-0bb5b18aceff1894ca456d21e836af7d878c87ac.tar.xz
Let the orderer specify node earliness
-rw-r--r--paludis/resolver/nag.cc27
-rw-r--r--paludis/resolver/nag.hh6
-rw-r--r--paludis/resolver/orderer.cc23
-rw-r--r--paludis/resolver/orderer.hh8
4 files changed, 47 insertions, 17 deletions
diff --git a/paludis/resolver/nag.cc b/paludis/resolver/nag.cc
index ee6e351..0f5b04e 100644
--- a/paludis/resolver/nag.cc
+++ b/paludis/resolver/nag.cc
@@ -32,6 +32,7 @@
#include <paludis/util/set-impl.hh>
#include <paludis/util/member_iterator-impl.hh>
#include <paludis/util/join.hh>
+#include <paludis/util/tribool.hh>
#include <paludis/serialise-impl.hh>
#include <tr1/unordered_set>
#include <tr1/unordered_map>
@@ -228,16 +229,23 @@ namespace
return node_data;
}
- int order_score_one(const NAGIndex & n)
+ int order_score_one(const NAGIndex & n, const std::tr1::function<Tribool (const NAGIndex &)> & order_early_fn)
{
/* lower scores are 'better' and mean 'order earlier' */
+ Tribool order_early(order_early_fn(n));
+ int bias(0);
+ if (order_early.is_indeterminate())
+ bias = 1;
+ else if (order_early.is_false())
+ bias = 2;
+
switch (n.role())
{
case nir_fetched:
- return 10;
+ return 10 + bias;
case nir_done:
- return 20;
+ return 20 + bias;
case last_nir:
break;
@@ -246,14 +254,15 @@ namespace
throw InternalError(PALUDIS_HERE, "bad nir");
}
- std::pair<int, NAGIndex> order_score(const NAGIndex & r, const StronglyConnectedComponent & scc)
+ std::pair<int, NAGIndex> order_score(const NAGIndex & r, const StronglyConnectedComponent & scc,
+ const std::tr1::function<Tribool (const NAGIndex &)> & order_early_fn)
{
int best_score(-1);
for (Set<NAGIndex>::ConstIterator e(scc.nodes()->begin()), e_end(scc.nodes()->end()) ;
e != e_end ; ++e)
{
- int score(order_score_one(*e));
+ int score(order_score_one(*e, order_early_fn));
if (best_score == -1 || score < best_score)
best_score = score;
}
@@ -263,7 +272,9 @@ namespace
}
const std::tr1::shared_ptr<const SortedStronglyConnectedComponents>
-NAG::sorted_strongly_connected_components() const
+NAG::sorted_strongly_connected_components(
+ const std::tr1::function<Tribool (const NAGIndex &)> & order_early_fn
+ ) const
{
StronglyConnectedComponentsByRepresentative sccs;
TarjanDataMap data;
@@ -318,7 +329,7 @@ NAG::sorted_strongly_connected_components() const
for (StronglyConnectedComponentsByRepresentative::const_iterator c(sccs.begin()), c_end(sccs.end()) ;
c != c_end ; ++c)
if (scc_edges.end() == scc_edges.find(c->first))
- orderable_now.insert(order_score(c->first, c->second));
+ orderable_now.insert(order_score(c->first, c->second, order_early_fn));
while (! orderable_now.empty())
{
@@ -336,7 +347,7 @@ NAG::sorted_strongly_connected_components() const
throw InternalError(PALUDIS_HERE, "huh?");
reverse_edges->second.erase(ordering_now->second);
if (reverse_edges->second.empty())
- orderable_now.insert(order_score(*e, sccs.find(*e)->second));
+ orderable_now.insert(order_score(*e, sccs.find(*e)->second, order_early_fn));
ordering_now_edges->second.erase(e++);
}
diff --git a/paludis/resolver/nag.hh b/paludis/resolver/nag.hh
index 900f747..714a553 100644
--- a/paludis/resolver/nag.hh
+++ b/paludis/resolver/nag.hh
@@ -28,6 +28,7 @@
#include <paludis/util/named_value.hh>
#include <paludis/serialise-fwd.hh>
#include <tr1/memory>
+#include <tr1/functional>
namespace paludis
{
@@ -79,8 +80,9 @@ namespace paludis
void verify_edges() const;
- const std::tr1::shared_ptr<const SortedStronglyConnectedComponents>
- sorted_strongly_connected_components() const PALUDIS_ATTRIBUTE((warn_unused_result));
+ const std::tr1::shared_ptr<const SortedStronglyConnectedComponents> sorted_strongly_connected_components(
+ const std::tr1::function<Tribool (const NAGIndex &)> & order_early_fn
+ ) const PALUDIS_ATTRIBUTE((warn_unused_result));
struct EdgesFromConstIteratorTag;
typedef WrappedForwardIterator<EdgesFromConstIteratorTag, const std::pair<const NAGIndex, NAGEdgeProperties> > EdgesFromConstIterator;
diff --git a/paludis/resolver/orderer.cc b/paludis/resolver/orderer.cc
index a193917..3ce4eaa 100644
--- a/paludis/resolver/orderer.cc
+++ b/paludis/resolver/orderer.cc
@@ -42,6 +42,7 @@
#include <paludis/util/make_shared_ptr.hh>
#include <paludis/util/make_shared_copy.hh>
#include <paludis/util/simple_visitor_cast.hh>
+#include <paludis/util/tribool.hh>
#include <paludis/environment.hh>
#include <paludis/notifier_callback.hh>
#include <tr1/unordered_set>
@@ -439,6 +440,12 @@ namespace
}
}
+Tribool
+Orderer::_order_early(const NAGIndex &) const
+{
+ return indeterminate;
+}
+
void
Orderer::resolve()
{
@@ -484,8 +491,11 @@ Orderer::resolve()
_imp->resolved->nag()->verify_edges();
+ const std::tr1::function<Tribool (const NAGIndex &)> order_early_fn(std::tr1::bind(&Orderer::_order_early, this, std::tr1::placeholders::_1));
+
_imp->env->trigger_notifier_callback(NotifierCallbackResolverStageEvent("Finding NAG SCCs"));
- const std::tr1::shared_ptr<const SortedStronglyConnectedComponents> ssccs(_imp->resolved->nag()->sorted_strongly_connected_components());
+ const std::tr1::shared_ptr<const SortedStronglyConnectedComponents> ssccs(
+ _imp->resolved->nag()->sorted_strongly_connected_components(order_early_fn));
_imp->env->trigger_notifier_callback(NotifierCallbackResolverStageEvent("Ordering SCCs"));
for (SortedStronglyConnectedComponents::ConstIterator scc(ssccs->begin()), scc_end(ssccs->end()) ;
@@ -542,8 +552,8 @@ Orderer::resolve()
scc_nag.verify_edges();
/* now we try again, hopefully with lots of small SCCs now */
- const std::tr1::shared_ptr<const SortedStronglyConnectedComponents> sub_ssccs(scc_nag.sorted_strongly_connected_components());
- _order_sub_ssccs(scc_nag, *scc, sub_ssccs, true);
+ const std::tr1::shared_ptr<const SortedStronglyConnectedComponents> sub_ssccs(scc_nag.sorted_strongly_connected_components(order_early_fn));
+ _order_sub_ssccs(scc_nag, *scc, sub_ssccs, true, order_early_fn);
}
}
}
@@ -564,7 +574,8 @@ Orderer::_order_sub_ssccs(
const NAG & scc_nag,
const StronglyConnectedComponent & top_scc,
const std::tr1::shared_ptr<const SortedStronglyConnectedComponents> & sub_ssccs,
- const bool can_recurse)
+ const bool can_recurse,
+ const std::tr1::function<Tribool (const NAGIndex &)> & order_early_fn)
{
Context context("When ordering SSCCs" + std::string(can_recurse ? " for the first time" : " for the second time") + ":");
@@ -623,8 +634,8 @@ Orderer::_order_sub_ssccs(
scc_nag_without_met_deps.verify_edges();
const std::tr1::shared_ptr<const SortedStronglyConnectedComponents> sub_ssccs_without_met_deps(
- scc_nag_without_met_deps.sorted_strongly_connected_components());
- _order_sub_ssccs(scc_nag_without_met_deps, top_scc, sub_ssccs_without_met_deps, false);
+ scc_nag_without_met_deps.sorted_strongly_connected_components(order_early_fn));
+ _order_sub_ssccs(scc_nag_without_met_deps, top_scc, sub_ssccs_without_met_deps, false, order_early_fn);
}
else
{
diff --git a/paludis/resolver/orderer.hh b/paludis/resolver/orderer.hh
index 37dc01b..72e656f 100644
--- a/paludis/resolver/orderer.hh
+++ b/paludis/resolver/orderer.hh
@@ -28,7 +28,9 @@
#include <paludis/resolver/nag-fwd.hh>
#include <paludis/resolver/resolvent-fwd.hh>
#include <paludis/util/private_implementation_pattern.hh>
+#include <paludis/util/tribool-fwd.hh>
#include <paludis/environment-fwd.hh>
+#include <tr1/functional>
namespace paludis
{
@@ -52,7 +54,11 @@ namespace paludis
const NAG &,
const StronglyConnectedComponent & top_scc,
const std::tr1::shared_ptr<const SortedStronglyConnectedComponents> & sub_ssccs,
- const bool can_recurse);
+ const bool can_recurse,
+ const std::tr1::function<Tribool (const NAGIndex &)> & order_early_fn);
+
+ Tribool _order_early(
+ const NAGIndex &) const PALUDIS_ATTRIBUTE((warn_unused_result));
NAGIndexRole _role_for_fetching(
const Resolvent & resolvent) const PALUDIS_ATTRIBUTE((warn_unused_result));