src/hash.c

   1 /* hash.c - The gdbm hash function. */
   2
   3 /* This file is part of GDBM, the GNU data base manager.
   4    Copyright (C) 1990, 1991, 1993, 2007, 2011, 2013 Free Software Foundation,
   5    Inc.
   6
   7    GDBM is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 3, or (at your option)
  10    any later version.
  11
  12    GDBM is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with GDBM. If not, see <http://www.gnu.org/licenses/>.    */
  19
  20 /* Include system configuration before all else. */
  21 #include "autoconf.h"
  22
  23 #include "gdbmdefs.h"
  24
  25
  26 /* This hash function computes a 31 bit value.  The value is used to index
  27    the hash directory using the top n bits.  It is also used in a hash bucket
  28    to find the home position of the element by taking the value modulo the
  29    bucket hash table size. */
  30
  31 int
  32 _gdbm_hash (datum key)
  33 {
  34   unsigned int value;   /* Used to compute the hash value.  */
  35   int   index;          /* Used to cycle through random values. */
  36
  37
  38   /* Set the initial value from key. */
  39   value = 0x238F13AF * key.dsize;
  40   for (index = 0; index < key.dsize; index++)
  41     value = (value + (key.dptr[index] << (index*5 % 24))) & 0x7FFFFFFF;
  42
  43   value = (1103515243 * value + 12345) & 0x7FFFFFFF;
  44
  45   /* Return the value. */
  46   return((int) value);
  47 }