1/* Implement simple hashing table with string based keys.
2 Copyright (C) 1994-2020 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4 Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, October 1994.
5
6 The GNU C Library is free software; you can redistribute it and/or
7 modify it under the terms of the GNU Lesser General Public
8 License as published by the Free Software Foundation; either
9 version 2.1 of the License, or (at your option) any later version.
10
11 The GNU C Library is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 Lesser General Public License for more details.
15
16 You should have received a copy of the GNU Lesser General Public
17 License along with the GNU C Library; if not, see
18 <https://www.gnu.org/licenses/>. */
19
20#ifndef hashval_t
21# define hashval_t unsigned long int
22#endif
23#include <limits.h> /* For CHAR_BIT. */
24
25hashval_t
26compute_hashval (const void *key, size_t keylen)
27{
28 size_t cnt;
29 hashval_t hval;
30
31 /* Compute the hash value for the given string. The algorithm
32 is taken from [Aho,Sethi,Ullman], modified to reduce the number of
33 collisions for short strings with very varied bit patterns.
34 See http://www.clisp.org/haible/hashfunc.html. */
35 cnt = 0;
36 hval = keylen;
37 while (cnt < keylen)
38 {
39 hval = (hval << 9) | (hval >> (sizeof hval * CHAR_BIT - 9));
40 hval += (hashval_t) ((const unsigned char *) key)[cnt++];
41 }
42 return hval != 0 ? hval : ~((hashval_t) 0);
43}
44