| 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 | word_t
|
|---|
| 42 | _gdbm_hash (key)
|
|---|
| 43 | datum key;
|
|---|
| 44 | {
|
|---|
| 45 | #if LONG_64_BITS || !INT_16_BITS
|
|---|
| 46 | unsigned int value; /* Used to compute the hash value. */
|
|---|
| 47 | #else
|
|---|
| 48 | unsigned long value; /* Used to compute the hash value. */
|
|---|
| 49 | #endif
|
|---|
| 50 | int index; /* Used to cycle through random values. */
|
|---|
| 51 |
|
|---|
| 52 |
|
|---|
| 53 | /* Set the initial value from key. */
|
|---|
| 54 | value = 0x238F13AF * key.dsize;
|
|---|
| 55 | for (index = 0; index < key.dsize; index++)
|
|---|
| 56 | value = (value + (key.dptr[index] << (index*5 % 24))) & 0x7FFFFFFF;
|
|---|
| 57 |
|
|---|
| 58 | value = (1103515243 * value + 12345) & 0x7FFFFFFF;
|
|---|
| 59 |
|
|---|
| 60 | /* Return the value. */
|
|---|
| 61 | return((word_t) value);
|
|---|
| 62 | }
|
|---|
