From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: Stephen Compall Newsgroups: gmane.lisp.guile.devel Subject: Re: Does anyone have a better scm_string_hash ? Date: Thu, 20 Nov 2003 15:48:58 GMT Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Message-ID: <200311201548.hAKFmwM1021085@csserver.evansville.edu> NNTP-Posting-Host: deer.gmane.org X-Trace: sea.gmane.org 1069344061 9461 80.91.224.253 (20 Nov 2003 16:01:01 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Thu, 20 Nov 2003 16:01:01 +0000 (UTC) Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Thu Nov 20 17:00:59 2003 Return-path: Original-Received: from monty-python.gnu.org ([199.232.76.173]) by deer.gmane.org with esmtp (Exim 3.35 #1 (Debian)) id 1AMrEo-0001Qn-00 for ; Thu, 20 Nov 2003 17:00:58 +0100 Original-Received: from localhost ([127.0.0.1] helo=monty-python.gnu.org) by monty-python.gnu.org with esmtp (Exim 4.24) id 1AMs9E-0006wB-3k for guile-devel@m.gmane.org; Thu, 20 Nov 2003 11:59:16 -0500 Original-Received: from list by monty-python.gnu.org with tmda-scanned (Exim 4.24) id 1AMs71-0006kA-NN for guile-devel@gnu.org; Thu, 20 Nov 2003 11:56:59 -0500 Original-Received: from mail by monty-python.gnu.org with spam-scanned (Exim 4.24) id 1AMs6U-0006SM-Jb for guile-devel@gnu.org; Thu, 20 Nov 2003 11:56:57 -0500 Original-Received: from [192.195.228.35] (helo=csserver.evansville.edu) by monty-python.gnu.org with esmtp (TLSv1:DES-CBC3-SHA:168) (Exim 4.24) id 1AMs6T-0006Qw-40 for guile-devel@gnu.org; Thu, 20 Nov 2003 11:56:25 -0500 Original-Received: from csserver.evansville.edu (localhost.localdomain [127.0.0.1]) by csserver.evansville.edu (8.12.8/8.12.8) with ESMTP id hAKFmwvS021089 for ; Thu, 20 Nov 2003 09:48:58 -0600 Original-Received: (from sc87@localhost) by csserver.evansville.edu (8.12.8/8.12.8/Submit) id hAKFmwM1021085; Thu, 20 Nov 2003 15:48:58 GMT Original-To: guile-devel@gnu.org X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.2 Precedence: list List-Id: Developers list for Guile, the GNU extensibility library List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: main.gmane.org gmane.lisp.guile.devel:3077 X-Report-Spam: http://spam.gmane.org/gmane.lisp.guile.devel:3077 Being ever so useful, I was reading through gnulib in coreutils when I spotted "hash.c". Thought, I'd better take a look. Anyway, here's the string hashing code in there, even if you really don't want to explore this further. Er, of course, this is GPLed.... /* Return a hash index for a NUL-terminated STRING between 0 and N_BUCKETS-1. This is a convenience routine for constructing other hashing functions. */ #if USE_DIFF_HASH /* About hashings, Paul Eggert writes to me (FP), on 1994-01-01: "Please see B. J. McKenzie, R. Harries & T. Bell, Selecting a hashing algorithm, Software--practice & experience 20, 2 (Feb 1990), 209-224. Good hash algorithms tend to be domain-specific, so what's good for [diffutils'] io.c may not be good for your application." */ size_t hash_string (const char *string, size_t n_buckets) { # define ROTATE_LEFT(Value, Shift) \ ((Value) << (Shift) | (Value) >> ((sizeof (size_t) * CHAR_BIT) - (Shift))) # define HASH_ONE_CHAR(Value, Byte) \ ((Byte) + ROTATE_LEFT (Value, 7)) size_t value = 0; for (; *string; string++) value = HASH_ONE_CHAR (value, (unsigned char) *string); return value % n_buckets; # undef ROTATE_LEFT # undef HASH_ONE_CHAR } #else /* not USE_DIFF_HASH */ /* This one comes from `recode', and performs a bit better than the above as per a few experiments. It is inspired from a hashing routine found in the very old Cyber `snoop', itself written in typical Greg Mansfield style. (By the way, what happened to this excellent man? Is he still alive?) */ size_t hash_string (const char *string, size_t n_buckets) { size_t value = 0; while (*string) value = (value * 31 + (unsigned char) *string++) % n_buckets; return value; } #endif /* not USE_DIFF_HASH */ -- Stephen Compall or s11 or sirian Better to use medicines at the outset than at the last moment. Sears Tower rs9512c Sundevil AK-47 lynch red noise Treasury global SHA SRI Clinton kibo blackjack Rand Corporation Crypto AG _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel