xref: /minix3/minix/lib/libvtreefs/sdbm.c (revision 693ad767e8be89278b9f813545205b350fa1b686)
1*693ad767SDavid van Moolenbroek /* VTreeFS - sdbm.c - sdbm hash function */
2433d6423SLionel Sambuc 
3433d6423SLionel Sambuc /*
4433d6423SLionel Sambuc  * sdbm - ndbm work-alike hashed database library
5433d6423SLionel Sambuc  * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
6433d6423SLionel Sambuc  * author: oz@nexus.yorku.ca
7433d6423SLionel Sambuc  * status: public domain. keep it that way.
8433d6423SLionel Sambuc  *
9433d6423SLionel Sambuc  * hashing routine
10433d6423SLionel Sambuc  */
11433d6423SLionel Sambuc 
12433d6423SLionel Sambuc #include "inc.h"
13*693ad767SDavid van Moolenbroek 
14433d6423SLionel Sambuc /*
15433d6423SLionel Sambuc  * polynomial conversion ignoring overflows
16433d6423SLionel Sambuc  * [this seems to work remarkably well, in fact better
17433d6423SLionel Sambuc  * than the ndbm hash function. Replace at your own risk]
18433d6423SLionel Sambuc  * use: 65599	nice.
19433d6423SLionel Sambuc  *      65587   even better.
20433d6423SLionel Sambuc  */
21*693ad767SDavid van Moolenbroek long
sdbm_hash(const char * str,int len)22*693ad767SDavid van Moolenbroek sdbm_hash(const char *str, int len)
23433d6423SLionel Sambuc {
24433d6423SLionel Sambuc 	unsigned long n = 0;
25433d6423SLionel Sambuc 
26433d6423SLionel Sambuc 	while (len--)
27433d6423SLionel Sambuc 		n = *str++ + (n << 6) + (n << 16) - n;
28433d6423SLionel Sambuc 
29433d6423SLionel Sambuc 	return n;
30433d6423SLionel Sambuc }
31