[Yum-devel] Getting rid of the linear searches

[Florian Festi]

Hi!

After doing several optimizations on the depsolver I think we got most of 
the easy stuff fixed. What now really needs to be done is removing all 
linear searches from the mytscheck code. Which can be found in:

  * _provideToPkg()
  * _checkInstall()
  * _checkRemove()
  * _requiredByPkg()

Look for "self.tsInfo.getMembersWithState(None," and 
"self.tsInfo.getMembersWithState(output_states =".

There are two possible solutions:

1. Build in memory hashes

Simply push all TS_INSTALL_STATES pkgs into a PackageSack and use it for 
searching. The PackageSack would have to be extended to keep its hashes 
uptodate (if build yet) so we don't need to rebuild them from scratch after 
every change.

2. Use the repositories

self.whatProvides and a still to implement self.whatRequires can be used to 
get a list of what pkgs might be of interest. They could then be filtered to
those that are really in the transaction. This is very similar to the code 
already in place for the not yet deleted pkgs that are searched in the rpmdb 
and then filtered by the transaction.
In fact _provideToPkg more or less contains all the code needed. It 
currently just has to do a linear search for the localinstall cases as these 
pkgs may  not be found in the repositories. Some other places of the code 
also mix searches within the repository with linear search.

To make this work with local installs local pkgs have to be put into a 
PackagesSack to be able to search them. But as they are given once the 
PackageSack doesn't need to update its hashes. May be we can just join them 
to the regular repository using a MetaSack

I suggest to use option 2 as it uses less memory, doesn't touch unneeded 
data is comparably close to the current code and has proven to be fast enough.

I'd suggest to implement a whatProvides and whatProvides for the transaction 
that returns the matches from the pkgs going to be installed or being 
installed and not removed. Those would combine searches in the rpmdb and the 
repository and filter both (but in different ways) to the transactionInfo.
These methods will allow to simply _checkInstall and _checkRemove a lot.

OK, this is just a short wrap up. Feel free to ask questions or bug me on IRC.

I plan to start this as soon as we reach consensus that this is the way to 
go and the 3.2 branch is open.

Florian