| 1 |
/* hashcode-string1.c -- compute a hash value from a NUL-terminated string. |
| 2 |
|
| 3 |
Copyright (C) 1998-2004, 2006-2007, 2009-2026 Free Software Foundation, Inc. |
| 4 |
|
| 5 |
This file is free software: you can redistribute it and/or modify |
| 6 |
it under the terms of the GNU Lesser General Public License as |
| 7 |
published by the Free Software Foundation; either version 2.1 of the |
| 8 |
License, or (at your option) any later version. |
| 9 |
|
| 10 |
This file is distributed in the hope that it will be useful, |
| 11 |
but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 12 |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 13 |
GNU Lesser General Public License for more details. |
| 14 |
|
| 15 |
You should have received a copy of the GNU Lesser General Public License |
| 16 |
along with this program. If not, see <https://www.gnu.org/licenses/>. */ |
| 17 |
|
| 18 |
#include <config.h> |
| 19 |
|
| 20 |
/* Specification. */ |
| 21 |
#include "hashcode-string1.h" |
| 22 |
|
| 23 |
#if USE_DIFF_HASH |
| 24 |
|
| 25 |
# include "bitrotate.h" |
| 26 |
|
| 27 |
/* About hashings, Paul Eggert writes to me (FP), on 1994-01-01: "Please see |
| 28 |
B. J. McKenzie, R. Harries & T. Bell, Selecting a hashing algorithm, |
| 29 |
Software--practice & experience 20, 2 (Feb 1990), 209-224. Good hash |
| 30 |
algorithms tend to be domain-specific, so what's good for [diffutils'] io.c |
| 31 |
may not be good for your application." */ |
| 32 |
|
| 33 |
size_t |
| 34 |
hash_string (const char *string, size_t tablesize) |
| 35 |
{ |
| 36 |
size_t value = 0; |
| 37 |
unsigned char ch; |
| 38 |
|
| 39 |
for (; (ch = *string); string++) |
| 40 |
value = ch + rotl_sz (value, 7); |
| 41 |
return value % tablesize; |
| 42 |
} |
| 43 |
|
| 44 |
#else /* not USE_DIFF_HASH */ |
| 45 |
|
| 46 |
/* This one comes from 'recode', and performs a bit better than the above as |
| 47 |
per a few experiments. It is inspired from a hashing routine found in the |
| 48 |
very old Cyber 'snoop', itself written in typical Greg Mansfield style. |
| 49 |
(By the way, what happened to this excellent man? Is he still alive?) */ |
| 50 |
|
| 51 |
size_t |
| 52 |
hash_string (const char *string, size_t tablesize) |
| 53 |
{ |
| 54 |
size_t value = 0; |
| 55 |
unsigned char ch; |
| 56 |
|
| 57 |
for (; (ch = *string); string++) |
| 58 |
value = (value * 31 + ch) % tablesize; |
| 59 |
return value; |
| 60 |
} |
| 61 |
|
| 62 |
#endif /* not USE_DIFF_HASH */ |