Line data    Source code

       1             : /* hash-pjw.c -- compute a hash value from a NUL-terminated string.
       2             : 
       3             :    Copyright (C) 2001, 2003, 2006 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           5 : hash_pjw (const void *x, size_t tablesize)
      32             : {
      33             :   const char *s;
      34           5 :   size_t h = 0;
      35             : 
      36          15 :   for (s = x; *s; s++)
      37          10 :     h = *s + ((h << 9) | (h >> (SIZE_BITS - 9)));
      38             : 
      39           5 :   return h % tablesize;
      40             : }