From e722f2409d7615676acb115a101d6ee1d99c07ce Mon Sep 17 00:00:00 2001 From: Klaus Kaempf Date: Sat, 4 Feb 2006 18:39:24 +0000 Subject: [PATCH] Improve 'provides' lookup. Solving 'STABLE' (~7000 packages) speeds up from 5 minutes down to 50 seconds :-)) --- zypp/ResPool.cc | 6 ++++++ zypp/ResPool.h | 9 +++++++++ zypp/pool/PoolImpl.cc | 24 ++++++++++++++++++++++-- zypp/pool/PoolImpl.h | 30 +++++++++++++++++++++++++++++- zypp/pool/PoolTraits.h | 4 ++++ zypp/solver/detail/InstallOrder.cc | 10 +++++++++- zypp/solver/detail/QueueItemConflict.cc | 25 ++++++++++++++++++++----- zypp/solver/detail/QueueItemRequire.cc | 11 +++++++++++ zypp/solver/detail/ResolverContext.cc | 21 ++++++++++++++++++--- zypp/solver/detail/ResolverUpgrade.cc | 11 +++++++++-- 10 files changed, 137 insertions(+), 14 deletions(-) diff --git a/zypp/ResPool.cc b/zypp/ResPool.cc index eb2778e..182086e 100644 --- a/zypp/ResPool.cc +++ b/zypp/ResPool.cc @@ -56,6 +56,12 @@ namespace zypp ResPool::const_iterator ResPool::end() const { return _pimpl->end(); } + ResPool::const_indexiterator ResPool::providesbegin(const std::string & tag_r) const + { return _pimpl->providesbegin(tag_r); } + + ResPool::const_indexiterator ResPool::providesend(const std::string & tag_r) const + { return _pimpl->providesend(tag_r); } + /****************************************************************** ** ** FUNCTION NAME : operator<< diff --git a/zypp/ResPool.h b/zypp/ResPool.h index 341f175..1030916 100644 --- a/zypp/ResPool.h +++ b/zypp/ResPool.h @@ -43,6 +43,7 @@ namespace zypp typedef pool::PoolTraits::Item Item; typedef pool::PoolTraits::size_type size_type; typedef pool::PoolTraits::const_iterator const_iterator; + typedef pool::PoolTraits::const_indexiterator const_indexiterator; public: /** Dtor */ @@ -64,6 +65,14 @@ namespace zypp const_iterator end() const; //@} + /** \name Iterate through all ResObjects which provide tag_r. */ + //@{ + /** */ + const_indexiterator providesbegin(const std::string & tag_r) const; + /** */ + const_indexiterator providesend(const std::string & tar_r) const; + //@} + public: /** \name Iterate through all ResObjects of a certain kind. */ //@{ diff --git a/zypp/pool/PoolImpl.cc b/zypp/pool/PoolImpl.cc index 1b703c2..f98b2fd 100644 --- a/zypp/pool/PoolImpl.cc +++ b/zypp/pool/PoolImpl.cc @@ -13,6 +13,7 @@ //#include "zypp/base/Logger.h" #include "zypp/pool/PoolImpl.h" +#include "zypp/CapSet.h" using std::endl; @@ -50,10 +51,29 @@ namespace zypp } void PoolImplInserter::operator()( ResObject::constPtr ptr_r, bool installed ) - { _poolImpl.store().insert( PoolImpl::Item( ptr_r, ResStatus (installed) ) ); } + { + PoolImpl::Item item ( ptr_r, ResStatus (installed) ); + _poolImpl.store().insert( item ); + CapSet provides = item->dep( Dep::PROVIDES ); + for (CapSet::iterator ic = provides.begin(); ic != provides.end(); ++ic) { + _poolImpl.providesstore().insert( PoolImpl::IndexContainerT::value_type (ic->index(), std::make_pair( *ic, item ) ) ); + } + } void PoolImplDeleter::operator()( ResObject::constPtr ptr_r ) - { _poolImpl.store().erase( PoolImpl::Item( ptr_r ) ); } + { + PoolImpl::Item item( ptr_r ); + _poolImpl.store().erase( item ); + CapSet provides = ptr_r->dep( Dep::PROVIDES ); + for (CapSet::iterator ic = provides.begin(); ic != provides.end(); ++ic) { + for (PoolImpl::indexiterator iit = _poolImpl.providesstore().lower_bound (ic->index()); + iit != _poolImpl.providesstore().upper_bound (ic->index()); ++iit) + { + if (iit->second.second == item) + _poolImpl.providesstore().erase (iit); + } + } + } ///////////////////////////////////////////////////////////////// } // namespace pool diff --git a/zypp/pool/PoolImpl.h b/zypp/pool/PoolImpl.h index 67e6797..dce2c24 100644 --- a/zypp/pool/PoolImpl.h +++ b/zypp/pool/PoolImpl.h @@ -36,9 +36,12 @@ namespace zypp /** */ typedef PoolTraits::Item Item; typedef PoolTraits::ContainerT ContainerT; + typedef PoolTraits::IndexContainerT IndexContainerT; typedef PoolTraits::size_type size_type; typedef PoolTraits::iterator iterator; typedef PoolTraits::const_iterator const_iterator; + typedef PoolTraits::indexiterator indexiterator; + typedef PoolTraits::const_indexiterator const_indexiterator; typedef PoolTraits::Inserter Inserter; typedef PoolTraits::Deleter Deleter; @@ -57,6 +60,13 @@ namespace zypp { return _store; } /** */ + IndexContainerT & providesstore() + { return _providesstore; } + /** */ + const IndexContainerT & providesstore() const + { return _providesstore; } + + /** */ bool empty() const { return _store.empty(); } /** */ @@ -71,6 +81,13 @@ namespace zypp { return _store.begin(); } /** */ + indexiterator providesbegin(const std::string & tag_r) + { return _providesstore.lower_bound (tag_r); } + /** */ + const_indexiterator providesbegin(const std::string & tag_r) const + { return _providesstore.lower_bound (tag_r); } + + /** */ iterator end() { return _store.end(); } /** */ @@ -78,12 +95,23 @@ namespace zypp { return _store.end(); } /** */ + indexiterator providesend(const std::string & tag_r) + { return _providesstore.upper_bound (tag_r); } + /** */ + const_indexiterator providesend(const std::string & tag_r) const + { return _providesstore.upper_bound (tag_r); } + + /** */ void clear() - { return _store.clear(); } + { _store.clear(); + _providesstore.clear(); + return; + } public: /** */ ContainerT _store; + IndexContainerT _providesstore; }; /////////////////////////////////////////////////////////////////// diff --git a/zypp/pool/PoolTraits.h b/zypp/pool/PoolTraits.h index a530c0d..aef0fa1 100644 --- a/zypp/pool/PoolTraits.h +++ b/zypp/pool/PoolTraits.h @@ -13,6 +13,7 @@ #define ZYPP_POOL_POOLTRAITS_H #include +#include #include "zypp/PoolItem.h" @@ -58,9 +59,12 @@ namespace zypp /** */ typedef PoolItem Item; typedef std::set ContainerT; + typedef std::multimap > IndexContainerT; typedef ContainerT::size_type size_type; typedef ContainerT::iterator iterator; typedef ContainerT::const_iterator const_iterator; + typedef IndexContainerT::iterator indexiterator; + typedef IndexContainerT::const_iterator const_indexiterator; typedef PoolImpl Impl; typedef shared_ptr Impl_Ptr; diff --git a/zypp/solver/detail/InstallOrder.cc b/zypp/solver/detail/InstallOrder.cc index f964395..a8c54a3 100644 --- a/zypp/solver/detail/InstallOrder.cc +++ b/zypp/solver/detail/InstallOrder.cc @@ -261,11 +261,19 @@ InstallOrder::rdfsvisit (const PoolItem_Ref item) // _world->foreachProvidingResItem (requirement, collect_providers, &info); - +#if 0 Dep dep (Dep::PROVIDES); invokeOnEach( _pool.byCapabilityIndexBegin( requirement.index(), dep ), _pool.byCapabilityIndexEnd( requirement.index(), dep ), resfilter::callOnCapMatchIn( dep, requirement, functor::functorRef(info) ) ); +#endif + ResPool::const_indexiterator pend = _pool.providesend(requirement.index()); + for (ResPool::const_indexiterator it = _pool.providesbegin(requirement.index()); it != pend; ++it) { + if (requirement.matches (it->second.first) == CapMatch::yes) { + if (!info( it->second.second, it->second.first)) + break; + } + } for (PoolItemSet::iterator it = tovisit.begin(); it != tovisit.end(); ++it) { diff --git a/zypp/solver/detail/QueueItemConflict.cc b/zypp/solver/detail/QueueItemConflict.cc index 56b543a..49f394f 100644 --- a/zypp/solver/detail/QueueItemConflict.cc +++ b/zypp/solver/detail/QueueItemConflict.cc @@ -110,7 +110,7 @@ struct UpgradeCandidate : public resfilter::OnCapMatchCallbackFunctor , context (ctx) { } - bool operator() (PoolItem_Ref & candidate, const Capability & cap) + bool operator() (const PoolItem & candidate, const Capability & cap) { MIL << "UpgradeCandidate? " << candidate << ":[" << context->getStatus (candidate) << "]" << (item->edition().compare(candidate->edition())) << "<" << item->arch() << "," << candidate->arch() << ">" << endl; @@ -153,7 +153,7 @@ struct ConflictProcess : public resfilter::OnCapMatchCallbackFunctor , actually_an_obsolete (ao) { } - bool operator()( PoolItem_Ref & provider, const Capability & provides ) + bool operator()( const PoolItem_Ref & provider, const Capability & provides ) { ResStatus status; ResolverInfo_Ptr log_info; @@ -208,14 +208,21 @@ struct ConflictProcess : public resfilter::OnCapMatchCallbackFunctor UpgradeCandidate upgrade_info (provider, context); Capability maybe_upgrade_cap = factory.parse ( provider->kind(), provider->name(), Rel::ANY, Edition::noedition ); - +#if 0 // pool->foreachProvidingResItem (maybe_upgrade_dep, upgrade_candidates_cb, (void *)&upgrade_info); Dep dep( Dep::PROVIDES ); invokeOnEach( pool.byCapabilityIndexBegin( maybe_upgrade_cap.index(), dep ), pool.byCapabilityIndexEnd( maybe_upgrade_cap.index(), dep ), resfilter::callOnCapMatchIn( dep, maybe_upgrade_cap, functor::functorRef(upgrade_info) ) ); - +#endif + ResPool::const_indexiterator pend = pool.providesend(maybe_upgrade_cap.index()); + for (ResPool::const_indexiterator it = pool.providesbegin(maybe_upgrade_cap.index()); it != pend; ++it) { + if (maybe_upgrade_cap.matches (it->second.first) == CapMatch::yes) { + if (!upgrade_info( it->second.second, it->second.first)) + break; + } + } MIL << "found " << upgrade_info.upgrades.size() << " upgrade candidates" << endl; #endif @@ -305,11 +312,19 @@ QueueItemConflict::process (ResolverContext_Ptr context, QueueItemList & new_ite ConflictProcess info (pool(), _conflicting_item, _capability, context, new_items, _actually_an_obsolete); // world()->foreachProvidingPoolItem (_capability, conflict_process_cb, (void *)&info); - +#if 0 Dep dep( Dep::PROVIDES ); invokeOnEach( pool().byCapabilityIndexBegin( _capability.index(), dep ), pool().byCapabilityIndexEnd( _capability.index(), dep ), resfilter::callOnCapMatchIn( dep, _capability, functor::functorRef(info) ) ); +#endif + ResPool::const_indexiterator pend = pool().providesend(_capability.index()); + for (ResPool::const_indexiterator it = pool().providesbegin(_capability.index()); it != pend; ++it) { + if (_capability.matches (it->second.first) == CapMatch::yes) { + if (!info( it->second.second, it->second.first)) + break; + } + } return true; } diff --git a/zypp/solver/detail/QueueItemRequire.cc b/zypp/solver/detail/QueueItemRequire.cc index 1c8b18b..fea6a06 100644 --- a/zypp/solver/detail/QueueItemRequire.cc +++ b/zypp/solver/detail/QueueItemRequire.cc @@ -299,12 +299,23 @@ QueueItemRequire::process (ResolverContext_Ptr context, QueueItemList & new_item if (! _remove_only) { +#if 0 Dep dep( Dep::PROVIDES ); MIL << "Look for providers of " << _capability << endl; // world->foreachProvidingResItem (_capability, require_process_cb, &info); invokeOnEach( pool().byCapabilityIndexBegin( _capability.index(), dep ), pool().byCapabilityIndexEnd( _capability.index(), dep ), resfilter::callOnCapMatchIn( dep, _capability, functor::functorRef(info) ) ); +#endif + MIL << "Look for providers of " << _capability << endl; + // world->foreachProvidingResItem (_capability, require_process_cb, &info); + ResPool::const_indexiterator pend = pool().providesend(_capability.index()); + for (ResPool::const_indexiterator it = pool().providesbegin(_capability.index()); it != pend; ++it) { + if (_capability.matches (it->second.first) == CapMatch::yes) { + if (!info( it->second.second, it->second.first)) + break; + } + } num_providers = info.providers.size(); diff --git a/zypp/solver/detail/ResolverContext.cc b/zypp/solver/detail/ResolverContext.cc index 41aca90..94d81e4 100644 --- a/zypp/solver/detail/ResolverContext.cc +++ b/zypp/solver/detail/ResolverContext.cc @@ -1178,7 +1178,7 @@ ResolverContext::requirementIsMet (const Capability & dependency, bool is_child) RequirementMet info (this, is_child ? dependency : Capability::noCap); // world()->foreachProviding (dependency, requirement_met_cb, (void *)&info); - +#if 0 Dep dep( Dep::PROVIDES ); // world->foreachProvidingResItem (dependency, require_process_cb, &info); @@ -1186,7 +1186,14 @@ ResolverContext::requirementIsMet (const Capability & dependency, bool is_child) invokeOnEach( pool().byCapabilityIndexBegin( dependency.index(), dep ), pool().byCapabilityIndexEnd( dependency.index(), dep ), resfilter::callOnCapMatchIn( dep, dependency, functor::functorRef(info) ) ); - +#endif + ResPool::const_indexiterator pend = pool().providesend(dependency.index()); + for (ResPool::const_indexiterator it = pool().providesbegin(dependency.index()); it != pend; ++it) { + if (dependency.matches (it->second.first) == CapMatch::yes) { + if (!info( it->second.second, it->second.first)) + break; + } + } return info.flag; } @@ -1222,12 +1229,20 @@ ResolverContext::requirementIsPossible (const Capability & dependency) const RequirementPossible info; // world()->foreachProviding (dep, requirement_possible_cb, (void *)&info); - +#if 0 Dep dep( Dep::PROVIDES ); invokeOnEach( pool().byCapabilityIndexBegin( dependency.index(), dep ), pool().byCapabilityIndexEnd( dependency.index(), dep ), resfilter::callOnCapMatchIn( dep, dependency, functor::functorRef(info) ) ); +#endif + ResPool::const_indexiterator pend = pool().providesend(dependency.index()); + for (ResPool::const_indexiterator it = pool().providesbegin(dependency.index()); it != pend; ++it) { + if (dependency.matches (it->second.first) == CapMatch::yes) { + if (!info( it->second.second, it->second.first)) + break; + } + } _DEBUG("requirementIsPossible( " << dependency << ") = " << (info.flag ? "Y" : "N")); return info.flag; } diff --git a/zypp/solver/detail/ResolverUpgrade.cc b/zypp/solver/detail/ResolverUpgrade.cc index 0f41589..23dd4bc 100644 --- a/zypp/solver/detail/ResolverUpgrade.cc +++ b/zypp/solver/detail/ResolverUpgrade.cc @@ -460,12 +460,19 @@ MIL << "has split cap " << *scap << endl; Capability installedCap = factory.parse ( installed->kind(), installed->name(), Rel::EQ, installed->edition()); FindProviders info; - +#if 0 invokeOnEach( _pool.byCapabilityIndexBegin( installed->name(), dep ), _pool.byCapabilityIndexEnd( installed->name(), dep ), resfilter::ByUninstalled (), resfilter::callOnCapMatchIn( dep, installedCap, functor::functorRef(info) ) ); - +#endif + ResPool::const_indexiterator pend = pool().providesend(installed->name()); + for (ResPool::const_indexiterator it = pool().providesbegin(installed->name()); it != pend; ++it) { + if (installedCap.matches (it->second.first) == CapMatch::yes) { + if (!info( it->second.second, it->second.first)) + break; + } + } int num_providers = info.providers.size(); -- 2.7.4