Back to index

glibc  2.9
hashval.h
Go to the documentation of this file.
00001 /* Implement simple hashing table with string based keys.
00002    Copyright (C) 1994-1997, 2000, 2001, 2002 Free Software Foundation, Inc.
00003    This file is part of the GNU C Library.
00004    Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, October 1994.
00005 
00006    The GNU C Library is free software; you can redistribute it and/or
00007    modify it under the terms of the GNU Lesser General Public
00008    License as published by the Free Software Foundation; either
00009    version 2.1 of the License, or (at your option) any later version.
00010 
00011    The GNU C Library is distributed in the hope that it will be useful,
00012    but WITHOUT ANY WARRANTY; without even the implied warranty of
00013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014    Lesser General Public License for more details.
00015 
00016    You should have received a copy of the GNU Lesser General Public
00017    License along with the GNU C Library; if not, write to the Free
00018    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
00019    02111-1307 USA.  */
00020 
00021 #ifndef hashval_t
00022 # define hashval_t unsigned long int
00023 #endif
00024 #include <limits.h>         /* For CHAR_BIT.  */
00025 
00026 hashval_t
00027 compute_hashval (const void *key, size_t keylen)
00028 {
00029   size_t cnt;
00030   hashval_t hval;
00031 
00032   /* Compute the hash value for the given string.  The algorithm
00033      is taken from [Aho,Sethi,Ullman], modified to reduce the number of
00034      collisions for short strings with very varied bit patterns.
00035      See http://www.clisp.org/haible/hashfunc.html.  */
00036   cnt = 0;
00037   hval = keylen;
00038   while (cnt < keylen)
00039     {
00040       hval = (hval << 9) | (hval >> (sizeof hval * CHAR_BIT - 9));
00041       hval += (hashval_t) *(((char *) key) + cnt++);
00042     }
00043   return hval != 0 ? hval : ~((hashval_t) 0);
00044 }