ceph/src/rocksdb/util/hash.h

   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 // XXH3_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.
  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)
  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 // Convenient and equivalent version of Hash128 without depending on 128-bit
  67 // scalars
  68 void Hash2x64(const char* data, size_t n, uint64_t* high64, uint64_t* low64);
  69 void Hash2x64(const char* data, size_t n, uint64_t seed, uint64_t* high64,
  70               uint64_t* low64);
  71
  72 // Hash 128 bits to 128 bits, guaranteed not to lose data (equivalent to
  73 // Hash2x64 on 16 bytes little endian)
  74 void BijectiveHash2x64(uint64_t in_high64, uint64_t in_low64,
  75                        uint64_t* out_high64, uint64_t* out_low64);
  76 void BijectiveHash2x64(uint64_t in_high64, uint64_t in_low64, uint64_t seed,
  77                        uint64_t* out_high64, uint64_t* out_low64);
  78
  79 // Inverse of above (mostly for testing)
  80 void BijectiveUnhash2x64(uint64_t in_high64, uint64_t in_low64,
  81                          uint64_t* out_high64, uint64_t* out_low64);
  82 void BijectiveUnhash2x64(uint64_t in_high64, uint64_t in_low64, uint64_t seed,
  83                          uint64_t* out_high64, uint64_t* out_low64);
  84
  85 // Stable/persistent 32-bit hash. Moderate quality and high speed on
  86 // small inputs.
  87 // TODO: consider rename to Hash32
  88 // KNOWN FLAW: incrementing seed by 1 might not give sufficiently independent
  89 // results from previous seed. Recommend pseudorandom or hashed seeds.
  90 extern uint32_t Hash(const char* data, size_t n, uint32_t seed);
  91
  92 // TODO: consider rename to LegacyBloomHash32
  93 inline uint32_t BloomHash(const Slice& key) {
  94   return Hash(key.data(), key.size(), 0xbc9f1d34);
  95 }
  96
  97 inline uint64_t GetSliceHash64(const Slice& key) {
  98   return Hash64(key.data(), key.size());
  99 }
 100 // Provided for convenience for use with template argument deduction, where a
 101 // specific overload needs to be used.
 102 extern uint64_t (*kGetSliceNPHash64UnseededFnPtr)(const Slice&);
 103
 104 inline uint64_t GetSliceNPHash64(const Slice& s) {
 105   return NPHash64(s.data(), s.size());
 106 }
 107
 108 inline uint64_t GetSliceNPHash64(const Slice& s, uint64_t seed) {
 109   return NPHash64(s.data(), s.size(), seed);
 110 }
 111
 112 // Similar to `GetSliceNPHash64()` with `seed`, but input comes from
 113 // concatenation of `Slice`s in `data`.
 114 extern uint64_t GetSlicePartsNPHash64(const SliceParts& data, uint64_t seed);
 115
 116 inline size_t GetSliceRangedNPHash(const Slice& s, size_t range) {
 117   return FastRange64(NPHash64(s.data(), s.size()), range);
 118 }
 119
 120 // TODO: consider rename to GetSliceHash32
 121 inline uint32_t GetSliceHash(const Slice& s) {
 122   return Hash(s.data(), s.size(), 397);
 123 }
 124
 125 // Useful for splitting up a 64-bit hash
 126 inline uint32_t Upper32of64(uint64_t v) {
 127   return static_cast<uint32_t>(v >> 32);
 128 }
 129 inline uint32_t Lower32of64(uint64_t v) { return static_cast<uint32_t>(v); }
 130
 131 // std::hash compatible interface.
 132 // TODO: consider rename to SliceHasher32
 133 struct SliceHasher {
 134   uint32_t operator()(const Slice& s) const { return GetSliceHash(s); }
 135 };
 136
 137 }  // namespace ROCKSDB_NAMESPACE