From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mp2 ([2001:41d0:2:4a6f::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by ms11 with LMTPS id mvF3FyHkNF99RwAA0tVLHw (envelope-from ) for ; Thu, 13 Aug 2020 06:56:33 +0000 Received: from aspmx1.migadu.com ([2001:41d0:2:4a6f::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by mp2 with LMTPS id 4OTDEiHkNF/1TgAAB5/wlQ (envelope-from ) for ; Thu, 13 Aug 2020 06:56:33 +0000 Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by aspmx1.migadu.com (Postfix) with ESMTPS id 1CC8B94051B for ; Thu, 13 Aug 2020 06:56:33 +0000 (UTC) Received: from localhost ([::1]:40222 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1k67A8-0007u4-2j for larch@yhetil.org; Thu, 13 Aug 2020 02:56:32 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:33240) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1k679Y-0007ro-Sd for guix-devel@gnu.org; Thu, 13 Aug 2020 02:55:56 -0400 Received: from relay3-d.mail.gandi.net ([217.70.183.195]:55365) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1k679W-0005Sh-Ig for guix-devel@gnu.org; Thu, 13 Aug 2020 02:55:56 -0400 X-Originating-IP: 86.246.37.13 Received: from mimimi (lfbn-idf2-1-572-13.w86-246.abo.wanadoo.fr [86.246.37.13]) (Authenticated sender: mail@ambrevar.xyz) by relay3-d.mail.gandi.net (Postfix) with ESMTPSA id 2B21F60007; Thu, 13 Aug 2020 06:55:50 +0000 (UTC) From: Pierre Neidhardt To: Ricardo Wurmus , Julien Lepiller Subject: Re: File search progress: database review and question on triggers In-Reply-To: <87zh6z33cm.fsf@elephly.net> References: <87sgcuh8rb.fsf@ambrevar.xyz> <87y2ml429i.fsf@elephly.net> <87364tgja3.fsf@ambrevar.xyz> <87y2mlf4jw.fsf@ambrevar.xyz> <87pn7x3pyw.fsf@elephly.net> <87r1sbel4f.fsf@ambrevar.xyz> <683CAE3A-8B38-4A41-9B3C-18D1284D3EFA@lepiller.eu> <87o8nfy4qu.fsf@ambrevar.xyz> <72845E8B-35E1-4A27-95E6-452D1D1F626B@lepiller.eu> <87zh6z33cm.fsf@elephly.net> Date: Thu, 13 Aug 2020 08:55:50 +0200 Message-ID: <87h7t7xceh.fsf@ambrevar.xyz> MIME-Version: 1.0 Content-Type: multipart/signed; boundary="=-=-="; micalg=pgp-sha256; protocol="application/pgp-signature" Received-SPF: pass client-ip=217.70.183.195; envelope-from=mail@ambrevar.xyz; helo=relay3-d.mail.gandi.net X-detected-operating-system: by eggs.gnu.org: First seen = 2020/08/13 02:55:52 X-ACL-Warn: Detected OS = Linux 3.11 and newer X-Spam_score_int: -5 X-Spam_score: -0.6 X-Spam_bar: / X-Spam_report: (-0.6 / 5.0 requ) BAYES_00=-1.9, FROM_SUSPICIOUS_NTLD=1, PDS_OTHER_BAD_TLD=1, RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001 autolearn=no autolearn_force=no X-Spam_action: no action X-BeenThere: guix-devel@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: "Development of GNU Guix and the GNU System distribution." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: guix-devel@gnu.org Errors-To: guix-devel-bounces+larch=yhetil.org@gnu.org Sender: "Guix-devel" X-Scanner: scn0 Authentication-Results: aspmx1.migadu.com; dkim=none; dmarc=none; spf=pass (aspmx1.migadu.com: domain of guix-devel-bounces@gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=guix-devel-bounces@gnu.org X-Spam-Score: -3.11 X-TUID: wClQnqWi0Ud5 --=-=-= Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Hi Ricardo, Ricardo Wurmus writes: >> Why wouldn't it help? Can't you make it a trie from basename -> complete= name? If I'm looking for "libcord.so" (which is a key in the trie), I don'= t think I need to look for every path. I only need to follow the trie until= I find a pointer to some structure that contains the data I look for (ex: = a list of complete filenames). > > Exactly! It=E2=80=99s somewhat less useful (without pre-processing) for = base > names and more useful for absolute file names, where you can quickly > toss out mismatches while traversing the trie. > > You could also optimize the data structure by swapping the base name and > the directory name, assuming that users would want to search for either > absolute file names and also for base names (and not for a directory in > between). By absolute file name, you mean relative to the Guix store item? As I mentioned in my reply to Julien, this would be a specific use-case optimization, like you said it won't work when you don't know the exact basename or full path, so I'm not sure it's worth going down that road. Thoughts? =2D-=20 Pierre Neidhardt https://ambrevar.xyz/ --=-=-= Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iQEzBAEBCAAdFiEEUPM+LlsMPZAEJKvom9z0l6S7zH8FAl804/YACgkQm9z0l6S7 zH8u+Af/e9gFSfwsF68FN7/qsWpvpXtaKckMhbs3LLhbiiFEBnM0Elwym9+fbk/S mtnoWseVgJC8RigIjll8v461UQQyEkwNlESEpN0rl3AKiiTklFP2OZpc5f3Cr2NB Ka1D3/+pZ7tJyL81UcGknAkEHObcJmnqqzmNCPd0fqLcGXu+WRK60yWWfmAwuI4p R7cipS9GtpCqu551Smnlgjly1JdnaMp8Rt2d+8ukZ+nOC28/udLgveDQILogc1yS 9MHjN/Co4Qy3Ri8JVyT63zWa87NLVklAPe7EMbOl3uUt/pO4FJG4bBsG5byex0zY fnKSKDAjvMuHoA0XRoIds/nBhEDP1g== =etcq -----END PGP SIGNATURE----- --=-=-=--