Re: toppological sorting and datastructures
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.
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.
Choosing which list to use will be called less often than
having a differentiating function to be called at each linked list
node, and most lookup functions, including ordering, work on one
relationship at a time.
I think this would result in significant time saving, and we
can another dependency type without impacting working code easier
this way.
Also, the data structure shall be closer to the underlying
logical structure; Packages do have different kinds of
relationships. I've found following the true nature of the data leads
to more scalable/adaptable code, and is less trouble in the long run.
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 ;-)
>> 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.
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.
Also, dependency satisfaction and conflict matches need to be
done for both the installed and candidate packages, and have to take
into account packages being marked for removal, either automatically
or by direct user action.
manoj
--
"I like a man who grins when he fights." Winston Churchill
Manoj Srivastava <srivasta@acm.org> <http://www.datasync.com/%7Esrivasta/>
Key C7261095 fingerprint = CB D9 F4 12 68 07 E4 05 CC 2D 27 12 1D F5 E8 6E
Reply to: