Re: toppological sorting and datastructures
On 13 Nov 1997, Manoj Srivastava wrote:
> Hi,
> >>"Jason" == Jason Gunthorpe <jgg@gpu.srv.ualberta.ca> writes:
>
> Jason> Check the cache.sgml on the last point there, the depends get
> Jason> dropped into a single big linked list. You might as well use
> Jason> all of the depends data in the ordering, with varying degrees
> Jason> of strictness. A package that suggests another package should
> Jason> 'gently try' to install itself first. Remember, an important
> Jason> goal is to have predictability in the algorithm.
>
> 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.
If you really need this then it can be done, but so far it hasn't really
been required, I'm not overly keen to add new structures because it makes
things more complex.
> Jason> So I can give you a list of versions to install, a list of
> Jason> versions that are installed and a list of versions that could
> Jason> possibly be installed if you really wanted to. Note that there
> Jason> can be multiple versions to be possibly installed for each
> Jason> package and so on.
>
> Umm, The list would have to be pruned so that only one version
> per package would be a candidate prior to the ordering step. What
> criteria do we use to select the preferred version? The one with the
> highest version, as described in chapter 5 of the packaging manual?
Okay, the pruning can be done before it hits the ordering code. The
determination of the install version is more complex and is not simply the
highest availble version.
> >> What I need are some kind of a separate index/list. The operations
> >> it wouls have to support are does package X belong to list? for
> >> each package that belongs to list X do {} I have used an efficient
> >> RB-tree implementation to simulate a set in the past. If there are
> >> indices in the cache generator that fit the needs, then I'll gladly
> >> forego writing the tree ;-)
>
> Jason> If you really need 'member of set' then this is a job for the
> Jason> extension structures, it will be many times faster and easier
> Jason> to use that sort of scheme then to use a RB tree. Also,
> Jason> depending on the nature of the data you are deriving it may
> Jason> already be present in the cache, ie it is trivial to tell if a
> Jason> version is marked for removal (see above). It is similary
> Jason> trivial to tell if a version is marked for install or upgrade.
>
> That sounds good. How about search for a package, and test the
> version number, like, if I want to know if the version installed
> matches (>>2.1.10)? A linear search could get tedious.
It's never a linear search. You see, if you have a package you have a
pointer to it, never a simple name. If you want to check a version then
you are almost always checking a dependancy. Dependancies are linked to
the packages they target. Even more usefull I think I will be able to add
a flag that indicates if a dependancy is already satisfied.
Jason
Reply to: