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