From owner-freebsd-hackers@FreeBSD.ORG Fri Dec 28 00:30:39 2007 Return-Path: Delivered-To: hackers@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 1720916A417 for ; Fri, 28 Dec 2007 00:30:39 +0000 (UTC) (envelope-from youshi10@u.washington.edu) Received: from mxout4.cac.washington.edu (mxout4.cac.washington.edu [140.142.33.19]) by mx1.freebsd.org (Postfix) with ESMTP id 061FA13C45A for ; Fri, 28 Dec 2007 00:30:39 +0000 (UTC) (envelope-from youshi10@u.washington.edu) Received: from smtp.washington.edu (smtp.washington.edu [140.142.32.139]) by mxout4.cac.washington.edu (8.13.7+UW06.06/8.13.7+UW07.09) with ESMTP id lBS0UciV031699 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Thu, 27 Dec 2007 16:30:38 -0800 X-Auth-Received: from [128.208.5.27] (shiina-1.dyn.cs.washington.edu [128.208.5.27]) (authenticated authid=youshi10) by smtp.washington.edu (8.13.7+UW06.06/8.13.7+UW07.09) with ESMTP id lBS0UclA023811 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=NOT) for ; Thu, 27 Dec 2007 16:30:38 -0800 Mime-Version: 1.0 (Apple Message framework v753) X-Gpgmail-State: !signed Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Message-Id: <5950EE0C-383D-4D6B-9991-A0DEABD2ADE4@u.washington.edu> Content-Transfer-Encoding: 7bit From: Garrett Cooper Date: Thu, 27 Dec 2007 16:30:40 -0800 To: hackers@freebsd.org X-Mailer: Apple Mail (2.753) X-PMX-Version: 5.4.1.325704, Antispam-Engine: 2.6.0.325393, Antispam-Data: 2007.12.27.161552 X-Uwash-Spam: Gauge=IIIIIII, Probability=7%, Report='BODY_SIZE_900_999 0, __CT 0, __CTE 0, __CT_TEXT_PLAIN 0, __HAS_MSGID 0, __HAS_X_MAILER 0, __MIME_TEXT_ONLY 0, __MIME_VERSION 0, __SANE_MSGID 0' Cc: Subject: BSD license compatible hash algorithm? X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 28 Dec 2007 00:30:39 -0000 Hi all, Just wondering if anyone knew of a good BSD license compatible key- based hash placement / retrieval algorithm that was available anywhere. I'm looking for a reliable way to lookup objects to see if a given action would be performed in my revised pkg_install(1), to thus efficiently pre-plan out the installation dependencies and fully utilize multiprocessing capabilities of contemporary machines / eliminate duplicate dependency install requirements. I know I can use tree structures or hash(3), but I want to avoid trees (inefficient with large data sets of course) and I was looking for a non-BDB based solution (for right now, with this given structure as I don't want to write everything to disk). Later on it might be a good idea to cache the results using BDB on disk, but for now I was just wondering if there were any non-BDB based hashing solutions that anyone knew of. Thanks, -Garrett