hash.h revision b8c8be7f8abe72f4cb4f315f3078ad864fd6a2d8 
1/******************************************************************************/
2#ifdef JEMALLOC_H_TYPES
3
4#endif /* JEMALLOC_H_TYPES */
5/******************************************************************************/
6#ifdef JEMALLOC_H_STRUCTS
7
8#endif /* JEMALLOC_H_STRUCTS */
9/******************************************************************************/
10#ifdef JEMALLOC_H_EXTERNS
11
12#endif /* JEMALLOC_H_EXTERNS */
13/******************************************************************************/
14#ifdef JEMALLOC_H_INLINES
15
16#ifndef JEMALLOC_ENABLE_INLINE
17uint64_t	hash(const void *key, size_t len, uint64_t seed);
18#endif
19
20#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_HASH_C_))
21/*
22 * The following hash function is based on MurmurHash64A(), placed into the
23 * public domain by Austin Appleby.  See http://murmurhash.googlepages.com/ for
24 * details.
25 */
26JEMALLOC_INLINE uint64_t
27hash(const void *key, size_t len, uint64_t seed)
28{
29	const uint64_t m = UINT64_C(0xc6a4a7935bd1e995);
30	const int r = 47;
31	uint64_t h = seed ^ (len * m);
32	const uint64_t *data = (const uint64_t *)key;
33	const uint64_t *end = data + (len/8);
34	const unsigned char *data2;
35
36	assert(((uintptr_t)key & 0x7) == 0);
37
38	while(data != end) {
39		uint64_t k = *data++;
40
41		k *= m;
42		k ^= k >> r;
43		k *= m;
44
45		h ^= k;
46		h *= m;
47	}
48
49	data2 = (const unsigned char *)data;
50	switch(len & 7) {
51		case 7: h ^= ((uint64_t)(data2[6])) << 48;
52		case 6: h ^= ((uint64_t)(data2[5])) << 40;
53		case 5: h ^= ((uint64_t)(data2[4])) << 32;
54		case 4: h ^= ((uint64_t)(data2[3])) << 24;
55		case 3: h ^= ((uint64_t)(data2[2])) << 16;
56		case 2: h ^= ((uint64_t)(data2[1])) << 8;
57		case 1: h ^= ((uint64_t)(data2[0]));
58			h *= m;
59	}
60
61	h ^= h >> r;
62	h *= m;
63	h ^= h >> r;
64
65	return (h);
66}
67#endif
68
69#endif /* JEMALLOC_H_INLINES */
70/******************************************************************************/
71