|
Last change
on this file was 2595, checked in by bird, 12 years ago |
|
gnu grep version 2.12 (grep-2.12.tar.xz, md5sum=8d2f0346d08b13c18afb81f0e8aa1e2f)
|
-
Property svn:eol-style
set to
native
|
|
File size:
1.2 KB
|
| Line | |
|---|
| 1 | /* hash-pjw.c -- compute a hash value from a NUL-terminated string.
|
|---|
| 2 |
|
|---|
| 3 | Copyright (C) 2001, 2003, 2006, 2009-2012 Free Software Foundation, Inc.
|
|---|
| 4 |
|
|---|
| 5 | This program is free software: you can redistribute it and/or modify
|
|---|
| 6 | it under the terms of the GNU General Public License as published by
|
|---|
| 7 | the Free Software Foundation; either version 3 of the License, or
|
|---|
| 8 | (at your option) any later version.
|
|---|
| 9 |
|
|---|
| 10 | This program 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 General Public License for more details.
|
|---|
| 14 |
|
|---|
| 15 | You should have received a copy of the GNU General Public License
|
|---|
| 16 | along with this program. If not, see <http://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 http://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 | }
|
|---|
Note:
See
TracBrowser
for help on using the repository browser.