summaryrefslogtreecommitdiffabout
path: root/src/hash.c
blob: 498d51527c95f7b724ca279104a6eaaf95a3755d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/* hash.c - The gdbm hash function. */

/* This file is part of GDBM, the GNU data base manager.
   Copyright (C) 1990-1991, 1993, 2007, 2011, 2013, 2017-2018 Free
   Software Foundation, Inc.

   GDBM is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 3, or (at your option)
   any later version.

   GDBM is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with GDBM. If not, see <http://www.gnu.org/licenses/>.    */

/* Include system configuration before all else. */
#include "autoconf.h"

#include "gdbmdefs.h"

/* This hash function computes a GDBM_HASH_BITS-bit value.  The value is used
   to index the hash directory using the top n bits.  It is also used in a
   hash bucket to find the home position of the element by taking the value
   modulo the bucket hash table size. */

int
_gdbm_hash (datum key)
{
  unsigned int value;	/* Used to compute the hash value.  */
  int   index;		/* Used to cycle through random values. */

  /* Set the initial value from key. */
  value = 0x238F13AF * key.dsize;
  for (index = 0; index < key.dsize; index++)
    value = (value + (key.dptr[index] << (index*5 % 24))) & 0x7FFFFFFF;

  value = (1103515243 * value + 12345) & 0x7FFFFFFF;  

  /* Return the value. */
  return((int) value);
}

int
_gdbm_bucket_dir (GDBM_FILE dbf, int hash)
{
  return hash >> (GDBM_HASH_BITS - dbf->header->dir_bits);
}

void
_gdbm_hash_key (GDBM_FILE dbf, datum key, int *hash, int *bucket, int *offset)
{
  int hashval = _gdbm_hash (key);
  *hash = hashval;
  *bucket = _gdbm_bucket_dir (dbf, hashval);
  *offset = hashval % dbf->header->bucket_elems;
}

Return to:

Send suggestions and report system problems to the System administrator.