Remove the misguided extension here that reserved two special values in

the hash_code. I'm not sure what I was thinking here, the use cases for
special values are in the *keys*, not in the hashes of those keys.

We can always resurrect this if needed, or clients can accomplish the
same goal themselves. This makes the general case somewhat faster (~5
cycles faster on my machine) and smaller with less branching.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151865 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 18 insertions, 62 deletions

diff --git a/include/llvm/ADT/Hashing.h b/include/llvm/ADT/Hashing.h
index e5969a3c05..1a4c555b29 100644
--- a/include/llvm/ADT/Hashing.h
+++ b/include/llvm/ADT/Hashing.h
@@ -82,35 +82,16 @@ class hash_code {
   size_t value;
 
 public:
-  /// \brief Default construct a hash_code. Constructs a null code.
-  hash_code() : value() {}
+  /// \brief Default construct a hash_code.
+  /// Note that this leaves the value uninitialized.
+  hash_code() {}
 
   /// \brief Form a hash code directly from a numerical value.
-  hash_code(size_t value) : value(value) {
-    // Ensure we don't form a hash_code with one of the prohibited values.
-    assert(value != get_null_code().value);
-    assert(value != get_invalid_code().value);
-  }
+  hash_code(size_t value) : value(value) {}
 
   /// \brief Convert the hash code to its numerical value for use.
   /*explicit*/ operator size_t() const { return value; }
 
-  /// \brief Get a hash_code object which corresponds to a null code.
-  ///
-  /// The null code must never be the result of any 'hash_value' calls and can
-  /// be used to detect an unset hash_code.
-  static hash_code get_null_code() { return hash_code(); }
-
-  /// \brief Get a hash_code object which corresponds to an invalid code.
-  ///
-  /// The invalid code must never be the result of any 'hash_value' calls. This
-  /// can be used to flag invalid hash_codes or mark entries in a hash table.
-  static hash_code get_invalid_code() {
-    hash_code invalid_code;
-    invalid_code.value = static_cast<size_t>(-1);
-    return invalid_code;
-  }
-
   friend bool operator==(const hash_code &lhs, const hash_code &rhs) {
     return lhs.value == rhs.value;
   }
@@ -223,27 +204,18 @@ inline uint64_t hash_33to64_bytes(const char *s, size_t len, uint64_t seed) {
 }
 
 inline uint64_t hash_short(const char *s, size_t length, uint64_t seed) {
-  uint64_t hash;
   if (length >= 4 && length <= 8)
-    hash = hash_4to8_bytes(s, length, seed);
-  else if (length > 8 && length <= 16)
-    hash = hash_9to16_bytes(s, length, seed);
-  else if (length > 16 && length <= 32)
-    hash = hash_17to32_bytes(s, length, seed);
-  else if (length > 32)
-    hash = hash_33to64_bytes(s, length, seed);
-  else if (length != 0)
-    hash = hash_1to3_bytes(s, length, seed);
-  else
-    return k2 ^ seed;
-
-  // FIXME: The invalid hash_code check is really expensive; there should be
-  // a better way of ensuring these invariants hold.
-  if (hash == static_cast<uint64_t>(hash_code::get_null_code()))
-    hash = k1 ^ seed;
-  else if (hash == static_cast<uint64_t>(hash_code::get_invalid_code()))
-    hash = k3 ^ seed;
-  return hash;
+    return hash_4to8_bytes(s, length, seed);
+  if (length > 8 && length <= 16)
+    return hash_9to16_bytes(s, length, seed);
+  if (length > 16 && length <= 32)
+    return hash_17to32_bytes(s, length, seed);
+  if (length > 32)
+    return hash_33to64_bytes(s, length, seed);
+  if (length != 0)
+    return hash_1to3_bytes(s, length, seed);
+
+  return k2 ^ seed;
 }
 
 /// \brief The intermediate state used during hashing.
@@ -299,14 +271,8 @@ struct hash_state {
   /// \brief Compute the final 64-bit hash code value based on the current
   /// state and the length of bytes hashed.
   uint64_t finalize(size_t length) {
-    uint64_t final_value
-      = hash_16_bytes(hash_16_bytes(h3, h5) + shift_mix(h1) * k1 + h2,
-                      hash_16_bytes(h4, h6) + shift_mix(length) * k1 + h0);
-    if (final_value == static_cast<uint64_t>(hash_code::get_null_code()))
-      final_value = k1 ^ seed;
-    if (final_value == static_cast<uint64_t>(hash_code::get_invalid_code()))
-      final_value = k3 ^ seed;
-    return final_value;
+    return hash_16_bytes(hash_16_bytes(h3, h5) + shift_mix(h1) * k1 + h2,
+                         hash_16_bytes(h4, h6) + shift_mix(length) * k1 + h0);
   }
 };
 
diff --git a/unittests/ADT/HashingTest.cpp b/unittests/ADT/HashingTest.cpp
index 07c0f31f6b..a6a0034129 100644
--- a/unittests/ADT/HashingTest.cpp
+++ b/unittests/ADT/HashingTest.cpp
@@ -53,7 +53,6 @@ TEST(HashingTest, HashValueBasicTest) {
   EXPECT_EQ(hash_value(42), hash_value(x));
   EXPECT_NE(hash_value(42), hash_value(y));
   EXPECT_NE(hash_value(42), hash_value(p));
-  EXPECT_NE(hash_code::get_null_code(), hash_value(p));
   EXPECT_EQ(hash_value(71), hash_value(i));
   EXPECT_EQ(hash_value(71), hash_value(ci));
   EXPECT_EQ(hash_value(71), hash_value(vi));
@@ -75,13 +74,10 @@ TEST(HashingTest, HashCombineRangeBasicTest) {
   // Leave this uninitialized in the hope that valgrind will catch bad reads.
   int dummy;
   hash_code dummy_hash = hash_combine_range(&dummy, &dummy);
-  EXPECT_NE(hash_code::get_null_code(), dummy_hash);
-  EXPECT_NE(hash_code::get_invalid_code(), dummy_hash);
+  EXPECT_NE(hash_code(0), dummy_hash);
 
   const int arr1[] = { 1, 2, 3 };
   hash_code arr1_hash = hash_combine_range(begin(arr1), end(arr1));
-  EXPECT_NE(hash_code::get_null_code(), arr1_hash);
-  EXPECT_NE(hash_code::get_invalid_code(), arr1_hash);
   EXPECT_NE(dummy_hash, arr1_hash);
   EXPECT_EQ(arr1_hash, hash_combine_range(begin(arr1), end(arr1)));
 
@@ -96,22 +92,16 @@ TEST(HashingTest, HashCombineRangeBasicTest) {
 
   const int arr2[] = { 3, 2, 1 };
   hash_code arr2_hash = hash_combine_range(begin(arr2), end(arr2));
-  EXPECT_NE(hash_code::get_null_code(), arr2_hash);
-  EXPECT_NE(hash_code::get_invalid_code(), arr2_hash);
   EXPECT_NE(dummy_hash, arr2_hash);
   EXPECT_NE(arr1_hash, arr2_hash);
 
   const int arr3[] = { 1, 1, 2, 3 };
   hash_code arr3_hash = hash_combine_range(begin(arr3), end(arr3));
-  EXPECT_NE(hash_code::get_null_code(), arr3_hash);
-  EXPECT_NE(hash_code::get_invalid_code(), arr3_hash);
   EXPECT_NE(dummy_hash, arr3_hash);
   EXPECT_NE(arr1_hash, arr3_hash);
 
   const int arr4[] = { 1, 2, 3, 3 };
   hash_code arr4_hash = hash_combine_range(begin(arr4), end(arr4));
-  EXPECT_NE(hash_code::get_null_code(), arr4_hash);
-  EXPECT_NE(hash_code::get_invalid_code(), arr4_hash);
   EXPECT_NE(dummy_hash, arr4_hash);
   EXPECT_NE(arr1_hash, arr4_hash);