Debian Codegraph @

lib/hashcode-string1.c

raw
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 */