1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
2 // This source code is licensed under both the GPLv2 (found in the
3 // COPYING file in the root directory) and Apache 2.0 License
4 // (found in the LICENSE.Apache file in the root directory).
5 //
6 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
7 // Use of this source code is governed by a BSD-style license that can be
8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
9 //
10 // Common hash functions with convenient interfaces. If hashing a
11 // statically-sized input in a performance-critical context, consider
12 // calling a specific hash implementation directly, such as
13 // XXH3p_64bits from xxhash.h.
14 //
15 // Since this is a very common header, implementation details are kept
16 // out-of-line. Out-of-lining also aids in tracking the time spent in
17 // hashing functions. Inlining is of limited benefit for runtime-sized
18 // hash inputs.
19
20 #pragma once
21
22 #include <cstddef>
23 #include <cstdint>
24
25 #include "rocksdb/slice.h"
26 #include "util/fastrange.h"
27
28 namespace ROCKSDB_NAMESPACE {
29
30 // Stable/persistent 64-bit hash. Higher quality and generally faster than
31 // Hash(), especially for inputs > 24 bytes.
32 // KNOWN FLAW: incrementing seed by 1 might not give sufficiently independent
33 // results from previous seed. Recommend incrementing by a large odd number.
34 extern uint64_t Hash64(const char* data, size_t n, uint64_t seed);
35
36 // Specific optimization without seed (same as seed = 0)
37 extern uint64_t Hash64(const char* data, size_t n);
38
39 // Non-persistent hash. Must only used for in-memory data structures.
40 // The hash results are thus subject to change between releases,
41 // architectures, build configuration, etc. (Thus, it rarely makes sense
42 // to specify a seed for this function, except for a "rolling" hash.)
43 // KNOWN FLAW: incrementing seed by 1 might not give sufficiently independent
44 // results from previous seed. Recommend incrementing by a large odd number.
NPHash64(const char * data,size_t n,uint64_t seed)45 inline uint64_t NPHash64(const char* data, size_t n, uint64_t seed) {
46 #ifdef ROCKSDB_MODIFY_NPHASH
47 // For testing "subject to change"
48 return Hash64(data, n, seed + 123456789);
49 #else
50 // Currently same as Hash64
51 return Hash64(data, n, seed);
52 #endif
53 }
54
55 // Specific optimization without seed (same as seed = 0)
NPHash64(const char * data,size_t n)56 inline uint64_t NPHash64(const char* data, size_t n) {
57 #ifdef ROCKSDB_MODIFY_NPHASH
58 // For testing "subject to change"
59 return Hash64(data, n, 123456789);
60 #else
61 // Currently same as Hash64
62 return Hash64(data, n);
63 #endif
64 }
65
66 // Stable/persistent 32-bit hash. Moderate quality and high speed on
67 // small inputs.
68 // TODO: consider rename to Hash32
69 // KNOWN FLAW: incrementing seed by 1 might not give sufficiently independent
70 // results from previous seed. Recommend pseudorandom or hashed seeds.
71 extern uint32_t Hash(const char* data, size_t n, uint32_t seed);
72
73 // TODO: consider rename to LegacyBloomHash32
BloomHash(const Slice & key)74 inline uint32_t BloomHash(const Slice& key) {
75 return Hash(key.data(), key.size(), 0xbc9f1d34);
76 }
77
GetSliceHash64(const Slice & key)78 inline uint64_t GetSliceHash64(const Slice& key) {
79 return Hash64(key.data(), key.size());
80 }
81 // Provided for convenience for use with template argument deduction, where a
82 // specific overload needs to be used.
83 extern uint64_t (*kGetSliceNPHash64UnseededFnPtr)(const Slice&);
84
GetSliceNPHash64(const Slice & s)85 inline uint64_t GetSliceNPHash64(const Slice& s) {
86 return NPHash64(s.data(), s.size());
87 }
88
GetSliceNPHash64(const Slice & s,uint64_t seed)89 inline uint64_t GetSliceNPHash64(const Slice& s, uint64_t seed) {
90 return NPHash64(s.data(), s.size(), seed);
91 }
92
93 // Similar to `GetSliceNPHash64()` with `seed`, but input comes from
94 // concatenation of `Slice`s in `data`.
95 extern uint64_t GetSlicePartsNPHash64(const SliceParts& data, uint64_t seed);
96
GetSliceRangedNPHash(const Slice & s,size_t range)97 inline size_t GetSliceRangedNPHash(const Slice& s, size_t range) {
98 return FastRange64(NPHash64(s.data(), s.size()), range);
99 }
100
101 // TODO: consider rename to GetSliceHash32
GetSliceHash(const Slice & s)102 inline uint32_t GetSliceHash(const Slice& s) {
103 return Hash(s.data(), s.size(), 397);
104 }
105
106 // Useful for splitting up a 64-bit hash
Upper32of64(uint64_t v)107 inline uint32_t Upper32of64(uint64_t v) {
108 return static_cast<uint32_t>(v >> 32);
109 }
Lower32of64(uint64_t v)110 inline uint32_t Lower32of64(uint64_t v) { return static_cast<uint32_t>(v); }
111
112 // std::hash compatible interface.
113 // TODO: consider rename to SliceHasher32
114 struct SliceHasher {
operatorSliceHasher115 uint32_t operator()(const Slice& s) const { return GetSliceHash(s); }
116 };
117
118 } // namespace ROCKSDB_NAMESPACE
119