From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from lists.gentoo.org ([140.105.134.102] helo=robin.gentoo.org) by nuthatch.gentoo.org with esmtp (Exim 4.54) id 1ErdQH-0004eU-4J for garchives@archives.gentoo.org; Wed, 28 Dec 2005 15:41:05 +0000 Received: from robin.gentoo.org (localhost [127.0.0.1]) by robin.gentoo.org (8.13.5/8.13.5) with SMTP id jBSFdnFN010973; Wed, 28 Dec 2005 15:39:49 GMT Received: from psmtp01.wxs.nl (psmtp01-real.wxs.nl [195.121.247.14]) by robin.gentoo.org (8.13.5/8.13.5) with ESMTP id jBSFakbG007756 for ; Wed, 28 Dec 2005 15:36:46 GMT Received: from pavlvs2.devrieze.net (ip5457f303.direct-adsl.nl [84.87.243.3]) by psmtp01.wxs.nl (8.12.10/8.12.10) with ESMTP id jBSFakkh012378 for ; Wed, 28 Dec 2005 16:36:46 +0100 Received: from hex.local.devrieze.net (hex.local.devrieze.net [192.168.1.7]) by pavlvs2.devrieze.net (Postfix) with ESMTP id 30B8B1004C for ; Wed, 28 Dec 2005 16:36:46 +0100 (CET) From: Paul de Vrieze To: gentoo-dev@lists.gentoo.org Subject: Re: [gentoo-dev] Multiple Repo Support Date: Wed, 28 Dec 2005 16:36:28 +0100 User-Agent: KMail/1.9 References: <43A235AD.6030604@leetworks.com> <20051227170740.5216bac8@snowdrop.home> <200512271837.14038.carlo@gentoo.org> In-Reply-To: <200512271837.14038.carlo@gentoo.org> X-Face: #Lb+'V@sGJ;ptgo5}V"W+5OCoo{LZv;bh,s,`WKLi/J)ed1_$0;6X<=?utf-8?q?700LVV/=3BLqPhiDP=5E=0A=09=27f=5Dfnv?=@%6M8\'HR1t=aFx;ePfp{ZQoBe+e)JOQ8T5*(_;mHY+cltLGq<;@$Y,=?utf-8?q?O=5C=24=0A=09Tm=23G6M?=,g![Q62J{na*S9d;R[^8pc%u\aiLqU@`kJtYl"^6pxdW Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-Id: Gentoo Linux mail X-BeenThere: gentoo-dev@gentoo.org Reply-to: gentoo-dev@lists.gentoo.org MIME-Version: 1.0 Content-Type: multipart/signed; boundary="nextPart4545559.vjME3xN6BD"; protocol="application/pgp-signature"; micalg=pgp-sha1 Content-Transfer-Encoding: 7bit Message-Id: <200512281636.45418.pauldv@gentoo.org> X-Archives-Salt: 91e3a031-457d-4e80-9b24-3ad28e32408b X-Archives-Hash: 7bb0c21bccb9f3dc0ba3e0ed37bfcbba --nextPart4545559.vjME3xN6BD Content-Type: text/plain; charset="iso-8859-6" Content-Transfer-Encoding: quoted-printable Content-Disposition: inline On Tuesday 27 December 2005 18:37, Carsten Lohrke wrote: > On Tuesday 27 December 2005 18:07, Ciaran McCreesh wrote: > > It's worse than O(n^n) if you try to do USE dep conflict resolution > > too... > > Theoretically yes, practically the worst number of dependency levels we > speak of to walk up/down is not infinite ;). Of course there's no chance = to > get this linear (speak: walking down the dependencies once), unless you > store the information which ebuild depends (or more exactly DEPENDs && > RDEPENDs) on foo in a list in foo's pkg db entry. The dependency resoluti= on > of the packages needed to rebuild on top of it is not different as usual. It's never linear. Changing n doesn't make it so. It just circumventing the= =20 problem. And what is "n" here exactly. I'd guess the average number of=20 dependencies of a package. This does however not say anything about the dep= th=20 of the tree. We can now however that in most cases based from an empty tree= =20 (or only a very minimal tree) the total number of packages (and as such=20 dependencies) is less than 1000. A number that is well manageable. The problem is caused by packages being dependencies from multiple sides. T= he=20 trick is that if a package is pulled in by one side it should be taken for= =20 granted by the other side if it satisfies it's dependencies. Detecting that= =20 can be done by hashtables which have O(log n) complexity on the number of=20 packages in the tree. In any case not that expensive. Paul =2D-=20 Paul de Vrieze Gentoo Developer Mail: pauldv@gentoo.org Homepage: http://www.devrieze.net --nextPart4545559.vjME3xN6BD Content-Type: application/pgp-signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.2-ecc0.1.6 (GNU/Linux) iD8DBQBDsrENbKx5DBjWFdsRAlXdAJ93Hbweula92LFZxrGHl2o7BkWjgQCgxnSb HPVs9XmBL3bO2R8BzvRgT9E= =K8ZR -----END PGP SIGNATURE----- --nextPart4545559.vjME3xN6BD-- -- gentoo-dev@gentoo.org mailing list