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