diff options
author | Jim Meyering <jim@meyering.net> | 2003-10-25 15:29:56 +0000 |
---|---|---|
committer | Jim Meyering <jim@meyering.net> | 2003-10-25 15:29:56 +0000 |
commit | bd67ac6ff2e2da0e77df949405406c6bca0e4903 (patch) | |
tree | bccd55e25fe59c95eaea73fdb6e920d7c0ed900c /lib/hash-pjw.c | |
parent | fdb31735a27b7ee6f61a24d698ace9d98d166822 (diff) | |
download | coreutils-bd67ac6ff2e2da0e77df949405406c6bca0e4903.tar.xz |
Update from gnulib.
Diffstat (limited to 'lib/hash-pjw.c')
-rw-r--r-- | lib/hash-pjw.c | 33 |
1 files changed, 15 insertions, 18 deletions
diff --git a/lib/hash-pjw.c b/lib/hash-pjw.c index 0a14b3e7a..3328467e4 100644 --- a/lib/hash-pjw.c +++ b/lib/hash-pjw.c @@ -1,5 +1,5 @@ /* hash-pjw.c -- compute a hash value from a NUL-terminated string. - Copyright 2001, 2003 Free Software Foundation, Inc. + Copyright (C) 2001, 2003 Free Software Foundation, Inc. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -21,25 +21,22 @@ #include "hash-pjw.h" +#include <limits.h> + +#define SIZE_BITS (sizeof (size_t) * CHAR_BIT) + /* A hash function for NUL-terminated char* strings using - the method described in Aho, Sethi, & Ullman, p 436. - Note that this hash function produces a lot of collisions when used - with short strings with very varied bit patterns. + the method described by Bruno Haible. See http://www.haible.de/bruno/hashfunc.html. */ -unsigned int -hash_pjw (const void *x, unsigned int tablesize) +size_t +hash_pjw (const void *x, size_t tablesize) { - const char *s = x; - unsigned int h = 0; - unsigned int g; - - while (*s != 0) - { - h = (h << 4) + *s++; - if ((g = h & (unsigned int) 0xf0000000) != 0) - h = (h ^ (g >> 24)) ^ g; - } - - return (h % tablesize); + const char *s; + size_t h = 0; + + for (s = x; *s; s++) + h = *s + ((h << 9) | (h >> (SIZE_BITS - 9))); + + return h % tablesize; } |