| 1 |
/* hash-pjw.c -- compute a hash value from a NUL-terminated string. |
| 2 |
|
| 3 |
Copyright (C) 2001, 2003, 2006, 2009-2024 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 |
#include "hash-pjw.h" |
| 21 |
|
| 22 |
#include <limits.h> |
| 23 |
|
| 24 |
#define SIZE_BITS (sizeof (size_t) * CHAR_BIT) |
| 25 |
|
| 26 |
/* A hash function for NUL-terminated char* strings using |
| 27 |
the method described by Bruno Haible. |
| 28 |
See https://www.haible.de/bruno/hashfunc.html. */ |
| 29 |
|
| 30 |
size_t |
| 31 |
hash_pjw (const void *x, size_t tablesize) |
| 32 |
{ |
| 33 |
const char *s; |
| 34 |
size_t h = 0; |
| 35 |
|
| 36 |
for (s = x; *s; s++) |
| 37 |
h = *s + ((h << 9) | (h >> (SIZE_BITS - 9))); |
| 38 |
|
| 39 |
return h % tablesize; |
| 40 |
} |