Re: toppological sorting and datastructures
On 13 Nov 1997, Manoj Srivastava wrote:
> Hi,
> >>"Jason" == Jason Gunthorpe <jgg@gpu.srv.ualberta.ca> writes:
>
> Jason> On 13 Nov 1997, Manoj Srivastava wrote:
>
> >> Hi, "Jason" == Jason Gunthorpe <jgg@gpu.srv.ualberta.ca> writes:
> >>
> >> I'd be happier if all these dependency types were in separate
> >> linked lists, so I don't have an overhead for each node of the
> >> linked list. The advantage of having one linked list is that one
> >> does not need to modify the structure if a new kind of dependency
> >> comes up (however low the probability of that is), however, we can
> >> have a linked list of headers of linked lists, and can tack on
> >> another linked list as we please.
>
> Jason> If you really need this then it can be done, but so far it
> Jason> hasn't really been required, I'm not overly keen to add new
> Jason> structures because it makes things more complex.
>
> Well, I think that it is easy enough to add to the proper list
> while populating the tree (they all can be different instances of the
> same class, and a simple discriminator can determin which object to
> catuall add an item to.). Anyway, the parser wuld be working on one
> relationship when parsing the package data, so different lists are
> not that cumbersome.
It's not so bad to build, it just means I need to add another structure
which is a bit of work. Also consider the size impact, their is going to
be > 2000 of these new items, there are only 3000 dependancies though!
With 3000 deps and 1000 packages that is an average of 3 deps per package,
I know some have more, ie 10. I'm not convinced any speed concerns can be
applied here.
> Most look ups Have to differentiate between the actions needed
> to be taken for different relationships; and, if not, it should be
> easy enough to iterate over all lists required.
Most look ups actually process a number of the lists at once so making one
pass over the dep list works very nicely for them.
> I think this would result in significant time saving, and we
> can another dependency type without impacting working code easier
> this way.
I doubt the time savings, it would result in increased size and no benifit
to adding new types.
> Jason> Okay, the pruning can be done before it hits the ordering
> Jason> code. The determination of the install version is more complex
> Jason> and is not simply the highest availble version.
>
> Ok (I don't really see how else one selects a candidate for
> installation, offhand, but I'm willing to be instructed ;-)
Hm, read the context menus thread, it delves into that somewhat.
> Jason> It's never a linear search. You see, if you have a package you
> Jason> have a pointer to it, never a simple name. If you want to check
> Jason> a version then you are almost always checking a
> Jason> dependancy. Dependancies are linked to the packages they
> Jason> target. Even more usefull I think I will be able to add a flag
> Jason> that indicates if a dependancy is already satisfied.
>
> Suppose I have a dependency that says package X depends on
> package Y, version >> 1.2.1. I have a list of packages installed. How
> do I create the dependency link without having to search for the
> installed version of Y, and looking to see if the dependency is
> satisfied? (this is while running through te packages and filling out
> dependency lists). A similair situation occurs when doing conflicts.
Right now:
pkgCache::Dependancy *Dep = ?;
if (Cache.IsSatisfiedDep(Dep) == true) {...}
Future:
if ((Dep->Flags & pkgDEP_NowOkay) == pkgDEP_NowOkay) {..}
'Flags' will mearly act as a cache for various types of IsSatisfiedDep
calls. The only lengthy thing IsSatisfiedDep does is the actual version
comparision, and support for provided packages.
I don't know what you want to do with provides so IsSatisfied dep might
not be good enough.
Notice you don't use a 'List of Packages Installed' that information is
already present in the cache. All of the lists you have requested are
already present in the cache ;>
Jason
Reply to: