| /** |
| * Copyright 2011-2015 Quickstep Technologies LLC. |
| * Copyright 2015 Pivotal Software, 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. |
| **/ |
| |
| #ifndef QUICKSTEP_UTILITY_HASH_PAIR_HPP_ |
| #define QUICKSTEP_UTILITY_HASH_PAIR_HPP_ |
| |
| #include <cstddef> |
| #include <cstdint> |
| #include <functional> |
| #include <type_traits> |
| #include <utility> |
| |
| namespace quickstep { |
| |
| // Nested namespace for helper classes used by CombineHashes(). Not intended |
| // for public use. |
| namespace hash_combine_detail { |
| |
| // Template with specializations for size_t that provide a CombineHashes |
| // method. The base version is empty and will cause compilation to fail if |
| // accidentally used with a type other than size_t. |
| template <typename HashT, typename Enable = void> |
| struct HashCombiner { |
| }; |
| |
| // Specialization for 64-bit size_t. |
| template <typename HashT> |
| struct HashCombiner<HashT, |
| typename std::enable_if<std::is_same<HashT, std::size_t>::value |
| && (sizeof(HashT) == 8)>::type> { |
| static inline std::size_t CombineHashes(std::size_t first_hash, |
| std::size_t second_hash) { |
| // Based on Hash128to64() from cityhash. |
| static constexpr std::size_t kMul = UINT64_C(0x9ddfea08eb382d69); |
| HashT a = (first_hash ^ second_hash) * kMul; |
| a ^= (a >> 47); |
| HashT b = (second_hash ^ a) * kMul; |
| b ^= (b >> 47); |
| b *= kMul; |
| return b; |
| } |
| }; |
| |
| // Specialization for 32-bit size_t. |
| template <typename HashT> |
| struct HashCombiner<HashT, |
| typename std::enable_if<std::is_same<HashT, std::size_t>::value |
| && sizeof(HashT) == 4>::type> { |
| static inline std::size_t CombineHashes(std::size_t first_hash, |
| std::size_t second_hash) { |
| // Based on hash_combine from Boost. |
| first_hash ^= second_hash + 0x9e3779b9u + (first_hash << 6) + (first_hash >> 2); |
| return first_hash; |
| } |
| }; |
| |
| } // namespace hash_combine_detail |
| |
| /** \addtogroup Utility |
| * @{ |
| */ |
| |
| /** |
| * @brief Mix bits from two hashes to make a new composite hash. |
| * |
| * @note Combining hashes is not commutative, so CombineHashes(a, b) will |
| * not equal CombineHashes(b, a) (except in rare collisions). |
| * |
| * @param first_hash The first hash to combine. |
| * @param second_hash The second hash to combine. |
| * @return A composite hash mixing first_hash and second_hash. |
| **/ |
| inline std::size_t CombineHashes(std::size_t first_hash, |
| std::size_t second_hash) { |
| return hash_combine_detail::HashCombiner<std::size_t>::CombineHashes(first_hash, second_hash); |
| } |
| |
| /** @} */ |
| |
| } // namespace quickstep |
| |
| namespace std { |
| |
| // Add an additional specialization of the std::hash() functor for pairs of |
| // hashable types. This allows std::pair<X, Y> to be used as a key in |
| // std::unordered_set or std::unordered_map so long as std::hash is specialized |
| // for X and Y. |
| template <typename FirstT, typename SecondT> |
| struct hash<pair<FirstT, SecondT>> { |
| size_t operator()(const pair<FirstT, SecondT> &arg) const { |
| size_t first_hash = hash<FirstT>()(arg.first); |
| size_t second_hash = hash<SecondT>()(arg.second); |
| return ::quickstep::CombineHashes(first_hash, second_hash); |
| } |
| }; |
| |
| } // namespace std |
| |
| #endif // QUICKSTEP_UTILITY_HASH_PAIR_HPP_ |