From 3381da9cdbe7d9516271154c765a369b70cf8f49 Mon Sep 17 00:00:00 2001 From: Karen Arutyunov Date: Thu, 25 May 2023 12:32:30 +0300 Subject: Optimize build_packages::collect_order_dependents() to skip already visited dependencies --- bpkg/pkg-build-collect.hxx | 25 ++++++++++++++++++++----- 1 file changed, 20 insertions(+), 5 deletions(-) (limited to 'bpkg/pkg-build-collect.hxx') diff --git a/bpkg/pkg-build-collect.hxx b/bpkg/pkg-build-collect.hxx index 30f993b..f237b11 100644 --- a/bpkg/pkg-build-collect.hxx +++ b/bpkg/pkg-build-collect.hxx @@ -1440,11 +1440,6 @@ namespace bpkg unsatisfied_dependents&); void - collect_order_dependents (iterator, - const repointed_dependents&, - unsatisfied_dependents&); - - void clear (); void @@ -1525,6 +1520,26 @@ namespace bpkg const function&, bool reorder); + // Skip the dependents collection/ordering for the specified dependency if + // that has already be done. + // + // Note that if this function has already been called for this dependency, + // then all its dependents are already in the map and the dependency + // constraints have been checked for them. Also they are in the list and + // are ordered to the left of this dependency, unless this dependency has + // been moved to the left itself since the previous visit. Such a move can + // only happen if this dependency is a dependent of some other dependency + // whose dependents have been collected/ordered since that previous visit. + // This function tracks such moves and just removes the moved dependencies + // from the visited set, so their dependents can be properly reordered + // after the move. + // + void + collect_order_dependents (iterator, + const repointed_dependents&, + unsatisfied_dependents&, + std::set& visited_deps); + private: struct data_type { -- cgit v1.1