From owner-freebsd-hackers@FreeBSD.ORG Fri Dec 28 00:34:30 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 559D716A418 for ; Fri, 28 Dec 2007 00:34:30 +0000 (UTC) (envelope-from youshi10@u.washington.edu) Received: from mxout2.cac.washington.edu (mxout2.cac.washington.edu [140.142.33.4]) by mx1.freebsd.org (Postfix) with ESMTP id 43A8A13C465 for ; Fri, 28 Dec 2007 00:34:30 +0000 (UTC) (envelope-from youshi10@u.washington.edu) Received: from smtp.washington.edu (smtp.washington.edu [140.142.32.139]) by mxout2.cac.washington.edu (8.13.7+UW06.06/8.13.7+UW07.09) with ESMTP id lBS0YTMF030320 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Thu, 27 Dec 2007 16:34:29 -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 lBS0YTSo024117 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=NOT); Thu, 27 Dec 2007 16:34:29 -0800 In-Reply-To: <5950EE0C-383D-4D6B-9991-A0DEABD2ADE4@u.washington.edu> References: <5950EE0C-383D-4D6B-9991-A0DEABD2ADE4@u.washington.edu> 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: <7F9D2F63-B5E6-41DE-843A-8D673C2DC88E@u.washington.edu> Content-Transfer-Encoding: 7bit From: Garrett Cooper Date: Thu, 27 Dec 2007 16:34:32 -0800 To: Garrett Cooper X-Mailer: Apple Mail (2.753) X-PMX-Version: 5.4.1.325704, Antispam-Engine: 2.6.0.325393, Antispam-Data: 2007.12.27.162337 X-Uwash-Spam: Gauge=IIIIIII, Probability=7%, Report='__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: hackers@freebsd.org Subject: Re: 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:34:30 -0000 On Dec 27, 2007, at 4:30 PM, Garrett Cooper wrote: > 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 A few clarifications. 1. It needs to be in C, not C++. 2. I meant hash table / bucket when I said "hash" in the subject. Thanks, -Garrett