YugabyteDB (2.13.1.0-b60, 21121d69985fbf76aa6958d8f04a9bfa936293b5)

//

// Copyright (C) 1999 and onwards Google, Inc.

//

// The following only applies to changes made to this file as part of YugaByte development.

//

// Portions Copyright (c) YugaByte, Inc.

//

// Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except

// in compliance with the License.  You may obtain a copy of the License at

//

// http://www.apache.org/licenses/LICENSE-2.0

//

// Unless required by applicable law or agreed to in writing, software distributed under the License

// is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express

// or implied.  See the License for the specific language governing permissions and limitations

// under the License.

//

//

// This file contains routines for hashing and fingerprinting.

//

// A hash function takes an arbitrary input bitstring (string, char*,

// number) and turns it into a hash value (a fixed-size number) such

// that unequal input values have a high likelihood of generating

// unequal hash values.  A fingerprint is a hash whose design is

// biased towards avoiding hash collisions, possibly at the expense of

// other characteristics such as execution speed.

//

// In general, if you are only using the hash values inside a single

// executable -- you're not writing the values to disk, and you don't

// depend on another instance of your program, running on another

// machine, generating the same hash values as you -- you want to use

// a HASH.  Otherwise, you want to use a FINGERPRINT.

//

// RECOMMENDED HASH FOR STRINGS:    GoodFastHash

//

// It is a functor, so you can use it like this:

//     hash_map<string, xxx, GoodFastHash<string> >

//     hash_set<char *, GoodFastHash<char*> >

//

// RECOMMENDED HASH FOR NUMBERS:    hash<>

//

// Note that this is likely the identity hash, so if your

// numbers are "non-random" (especially in the low bits), another

// choice is better.  You can use it like this:

//     hash_map<int, xxx>

//     hash_set<uint64>

//

// RECOMMENDED HASH FOR POINTERS:    hash<>

//

// This is also likely the identity hash.

//

// RECOMMENDED HASH FOR STRUCTS:    hash<some_fingerprint(struct)>

//

// Take a fingerprint of the struct, and use that as the key.

// For instance: const uint64 hash_data[] = { s.foo, bit_cast<uint64>(s.bar) };

//    uint64 fprint = <fingerprint fn>(reinterpret_cast<const char*>(hash_data),

//                                     sizeof(hash_data));

//    hash_map[fprint] = whatever;

//

// RECOMMENDED FINGERPRINT:         Fingerprint2011

//

// (In util/hash/fingerprint2011.h)

// In particular, do *not* use Fingerprint in new code; it has

// problems with excess collisions.

//

// OTHER HASHES AND FINGERPRINTS:

//

//

// The wiki page also has good advice for when to use a fingerprint vs

// a hash.

//

//

// Note: if your file declares hash_map<string, ...> or

// hash_set<string>, it will use the default hash function,

// hash<string>.  This is not a great choice.  Always provide an

// explicit functor, such as GoodFastHash, as a template argument.

// (Either way, you will need to #include this file to get the

// necessary definition.)

//

// Some of the hash functions below are documented to be fixed

// forever; the rest (whether they're documented as so or not) may

// change over time.  If you require a hash function that does not

// change over time, you should have unittests enforcing this

// property.  We already have several such functions; see

// hash_unittest.cc for the details and unittests.

#ifndef YB_GUTIL_HASH_HASH_H

#define YB_GUTIL_HASH_HASH_H

#include <stddef.h>

#include <stdint.h>     // for uintptr_t

#include <string.h>

#include <algorithm>

#include <string>

#include <utility>

#include "yb/gutil/casts.h"

#include "yb/gutil/int128.h"

#include "yb/gutil/integral_types.h"

#include "yb/gutil/macros.h"

#include "yb/gutil/port.h"

#include "yb/gutil/hash/city.h"

#include "yb/gutil/hash/hash128to64.h"

#include "yb/gutil/hash/jenkins.h"

#include "yb/gutil/hash/jenkins_lookup2.h"

#include "yb/gutil/hash/legacy_hash.h"

#include "yb/gutil/hash/string_hash.h"

// ----------------------------------------------------------------------

// Fingerprint()

//   Not recommended for new code.  Instead, use Fingerprint2011(),

//   a higher-quality and faster hash function.  See fingerprint2011.h.

//

//   Fingerprinting a string (or char*) will never return 0 or 1,

//   in case you want a couple of special values.  However,

//   fingerprinting a numeric type may produce 0 or 1.

//

//   The hash mapping of Fingerprint() will never change.

//

//   Note: AVOID USING FINGERPRINT if at all possible.  Use

//   Fingerprint2011 (in fingerprint2011.h) instead.

//   Fingerprint() is susceptible to collisions for even short

//   strings with low edit distance; see

//   Example collisions:

//     "01056/02" vs. "11057/02"

//     "LTA 02" vs. "MTA 12"

//   The same study found only one collision each for CityHash64() and

//   MurmurHash64(), from more than 2^32 inputs, and on medium-length

//   strings with large edit distances.These issues, among others,

//   led to the recommendation that new code should avoid Fingerprint().

// ----------------------------------------------------------------------

extern uint64 FingerprintReferenceImplementation(const char *s, uint32 len);

extern uint64 FingerprintInterleavedImplementation(const char *s, uint32 len);

inline uint64 Fingerprint(const char *s, uint32 len) {

  if (sizeof(s) == 8) {  // 64-bit systems have 8-byte pointers.

    // The better choice when we have a decent number of registers.

    return FingerprintInterleavedImplementation(s, len);

  } else {

    return FingerprintReferenceImplementation(s, len);

  }

}

// Routine that combines together the hi/lo part of a fingerprint

// and changes the result appropriately to avoid returning 0/1.

inline uint64 CombineFingerprintHalves(uint32 hi, uint32 lo) {

  uint64 result = (static_cast<uint64>(hi) << 32) | static_cast<uint64>(lo);

  if ((hi == 0) && (lo < 2)) {

    result ^= GG_ULONGLONG(0x130f9bef94a0a928);

  }

  return result;

}

Unexecuted instantiation: CombineFingerprintHalves(unsigned int, unsigned int)

Unexecuted instantiation: CombineFingerprintHalves(unsigned int, unsigned int)

inline uint64 Fingerprint(const std::string& s) {

  return Fingerprint(s.data(), static_cast<uint32>(s.size()));

}

inline uint64 Hash64StringWithSeed(const std::string& s, uint64 c) {

  return Hash64StringWithSeed(s.data(), static_cast<uint32>(s.size()), c);

}

inline uint64 Fingerprint(schar c) {

  return Hash64NumWithSeed(static_cast<uint64>(c), MIX64);

}

inline uint64 Fingerprint(char c) {

  return Hash64NumWithSeed(static_cast<uint64>(c), MIX64);

}

inline uint64 Fingerprint(uint16 c) {

  return Hash64NumWithSeed(static_cast<uint64>(c), MIX64);

}

inline uint64 Fingerprint(int16 c) {

  return Hash64NumWithSeed(static_cast<uint64>(c), MIX64);

}

inline uint64 Fingerprint(uint32 c) {

  return Hash64NumWithSeed(static_cast<uint64>(c), MIX64);

}

inline uint64 Fingerprint(int32 c) {

  return Hash64NumWithSeed(static_cast<uint64>(c), MIX64);

}

inline uint64 Fingerprint(uint64 c) {

  return Hash64NumWithSeed(static_cast<uint64>(c), MIX64);

}

inline uint64 Fingerprint(int64 c) {

  return Hash64NumWithSeed(static_cast<uint64>(c), MIX64);

}

// This concatenates two 64-bit fingerprints. It is a convenience function to

// get a fingerprint for a combination of already fingerprinted components.

// It assumes that each input is already a good fingerprint itself.

// Note that this is legacy code and new code should use its replacement

// FingerprintCat2011().

//

// Note that in general it's impossible to construct Fingerprint(str)

// from the fingerprints of substrings of str.  One shouldn't expect

// FingerprintCat(Fingerprint(x), Fingerprint(y)) to indicate

// anything about Fingerprint(StrCat(x, y)).

inline uint64 FingerprintCat(uint64 fp1, uint64 fp2) {

  return Hash64NumWithSeed(fp1, fp2);

}

// If you want an excellent string hash function, and you don't mind if it

// might change when you sync and recompile, please use GoodFastHash<>.

// For most applications, GoodFastHash<> is a good choice, better than

// hash<string> or hash<char*> or similar.  GoodFastHash<> can change

// from time to time and may differ across platforms, and we'll strive

// to keep improving it.

//

// By the way, when deleting the contents of a hash_set of pointers, it is

// unsafe to delete *iterator because the hash function may be called on

// the next iterator advance.  Use STLDeleteContainerPointers().

template<class X> struct GoodFastHash;

// This intended to be a "good" hash function.  It may change from time to time.

template<> struct GoodFastHash<char*> {

  size_t operator()(const char* s) const {

    return HashStringThoroughly(s, strlen(s));

  }

  // Less than operator for MSVC.

  bool operator()(const char* a, const char* b) const {

    return strcmp(a, b) < 0;

  }

  static const size_t bucket_size = 4;  // These are required by MSVC

  static const size_t min_buckets = 8;  // 4 and 8 are defaults.

};

// This intended to be a "good" hash function.  It may change from time to time.

template<> struct GoodFastHash<const char*> {

  size_t operator()(const char* s) const {

    return HashStringThoroughly(s, strlen(s));

  }

  // Less than operator for MSVC.

  bool operator()(const char* a, const char* b) const {

    return strcmp(a, b) < 0;

  }

  static const size_t bucket_size = 4;  // These are required by MSVC

  static const size_t min_buckets = 8;  // 4 and 8 are defaults.

};

// This intended to be a "good" hash function.  It may change from time to time.

template<class _CharT, class _Traits, class _Alloc>

struct GoodFastHash<std::basic_string<_CharT, _Traits, _Alloc> > {

  size_t operator()(const std::basic_string<_CharT, _Traits, _Alloc>& k) const {

    return HashStringThoroughly(k.data(), k.length() * sizeof(k[0]));

  }

  // Less than operator for MSVC.

  bool operator()(const std::basic_string<_CharT, _Traits, _Alloc>& a,

                  const std::basic_string<_CharT, _Traits, _Alloc>& b) const {

    return a < b;

  }

  static const size_t bucket_size = 4;  // These are required by MSVC

  static const size_t min_buckets = 8;  // 4 and 8 are defaults.

};

// This intended to be a "good" hash function.  It may change from time to time.

template<class _CharT, class _Traits, class _Alloc>

struct GoodFastHash<const std::basic_string<_CharT, _Traits, _Alloc> > {

  size_t operator()(const std::basic_string<_CharT, _Traits, _Alloc>& k) const {

    return HashStringThoroughly(k.data(), k.length() * sizeof(k[0]));

  }

  // Less than operator for MSVC.

  bool operator()(const std::basic_string<_CharT, _Traits, _Alloc>& a,

                  const std::basic_string<_CharT, _Traits, _Alloc>& b) const {

    return a < b;

  }

  static const size_t bucket_size = 4;  // These are required by MSVC

  static const size_t min_buckets = 8;  // 4 and 8 are defaults.

};

#endif  // YB_GUTIL_HASH_HASH_H