1 /* Copyright (c) 2015-2016 The Khronos Group Inc.
2 * Copyright (c) 2015-2016 Valve Corporation
3 * Copyright (c) 2015-2016 LunarG, Inc.
4 * Copyright (C) 2015-2016 Google Inc.
5 *
6 * Licensed under the Apache License, Version 2.0 (the "License");
7 * you may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 *
18 * Author: John Zulauf <jzulauf@lunarg.com>
19 */
20 #ifndef HASH_UTIL_H_
21 #define HASH_UTIL_H_
22
23 #define NOMINMAX
24 #include <cstdint>
25 #include <functional>
26 #include <limits>
27 #include <memory>
28 #include <mutex>
29 #include <type_traits>
30 #include <unordered_set>
31 #include <vector>
32
33 // Hash and equality utilities for supporting hashing containers (e.g. unordered_set, unordered_map)
34 namespace hash_util {
35
36 // True iff both pointers are null or both are non-null
37 template <typename T>
similar_for_nullity(const T * const lhs,const T * const rhs)38 bool similar_for_nullity(const T *const lhs, const T *const rhs) {
39 return ((lhs != nullptr) && (rhs != nullptr)) || ((lhs == nullptr) && (rhs == nullptr));
40 }
41
42 // Wrap std hash to avoid manual casts for the holes in std::hash (in C++11)
43 template <typename Value>
44 size_t HashWithUnderlying(Value value, typename std::enable_if<!std::is_enum<Value>::value, void *>::type = nullptr) {
45 return std::hash<Value>()(value);
46 }
47
48 template <typename Value>
49 size_t HashWithUnderlying(Value value, typename std::enable_if<std::is_enum<Value>::value, void *>::type = nullptr) {
50 using Underlying = typename std::underlying_type<Value>::type;
51 return std::hash<Underlying>()(static_cast<const Underlying &>(value));
52 }
53
54 class HashCombiner {
55 public:
56 using Key = size_t;
57
58 template <typename Value>
59 struct WrappedHash {
operatorWrappedHash60 size_t operator()(const Value &value) const { return HashWithUnderlying(value); }
61 };
62
combined_(combined)63 HashCombiner(Key combined = 0) : combined_(combined) {}
64 // magic and combination algorithm based on boost::hash_combine
65 // http://www.boost.org/doc/libs/1_43_0/doc/html/hash/reference.html#boost.hash_combine
66 // Magic value is 2^size / ((1-sqrt(5)/2)
67 static const uint64_t kMagic = sizeof(Key) > 4 ? Key(0x9e3779b97f4a7c16UL) : Key(0x9e3779b9U);
68
69 // If you need to override the default hash
70 template <typename Value, typename Hasher = WrappedHash<Value>>
Combine(const Value & value)71 HashCombiner &Combine(const Value &value) {
72 combined_ ^= Hasher()(value) + kMagic + (combined_ << 6) + (combined_ >> 2);
73 return *this;
74 }
75
76 template <typename Iterator, typename Hasher = WrappedHash<typename std::iterator_traits<Iterator>::value_type>>
Combine(Iterator first,Iterator end)77 HashCombiner &Combine(Iterator first, Iterator end) {
78 using Value = typename std::iterator_traits<Iterator>::value_type;
79 auto current = first;
80 for (; current != end; ++current) {
81 Combine<Value, Hasher>(*current);
82 }
83 return *this;
84 }
85
86 template <typename Value, typename Hasher = WrappedHash<Value>>
Combine(const std::vector<Value> & vector)87 HashCombiner &Combine(const std::vector<Value> &vector) {
88 return Combine(vector.cbegin(), vector.cend());
89 }
90
91 template <typename Value>
92 HashCombiner &operator<<(const Value &value) {
93 return Combine(value);
94 }
95
Value()96 Key Value() const { return combined_; }
97 void Reset(Key combined = 0) { combined_ = combined; }
98
99 private:
100 Key combined_;
101 };
102
103 // A template to inherit std::hash overloads from when T::hash() is defined
104 template <typename T>
105 struct HasHashMember {
operatorHasHashMember106 size_t operator()(const T &value) const { return value.hash(); }
107 };
108
109 // A template to inherit std::hash overloads from when is an *ordered* constainer
110 template <typename T>
111 struct IsOrderedContainer {
operatorIsOrderedContainer112 size_t operator()(const T &value) const { return HashCombiner().Combine(value.cbegin(), value.cend()).Value(); }
113 };
114
115 // The dictionary provides a way of referencing canonical/reference
116 // data by id, such that the id's are invariant with dictionary
117 // resize/insert and that no entries point to identical data. This
118 // approach uses the address of the unique data and as the unique
119 // ID for a give value of T.
120 //
121 // Note: This ID is unique for a given application execution, neither
122 // globally unique, invariant, nor repeatable from execution to
123 // execution.
124 //
125 // The entries of the dictionary are shared_pointers (the contents of
126 // which are invariant with resize/insert), with the hash and equality
127 // template arguments wrapped in a shared pointer dereferencing
128 // function object
129 template <typename T, typename Hasher = std::hash<T>, typename KeyEqual = std::equal_to<T>>
130 class Dictionary {
131 public:
132 using Def = T;
133 using Id = std::shared_ptr<const Def>;
134
135 // Find the unique entry match the provided value, adding if needed
136 // TODO: segregate lookup from insert, using reader/write locks to reduce contention -- if needed
137 template <typename U = T>
look_up(U && value)138 Id look_up(U &&value) {
139 // We create an Id from the value, which will either be retained by dict (if new) or deleted on return (if extant)
140 Id from_input = std::make_shared<T>(std::forward<U>(value));
141
142 // Insert takes care of the "unique" id part by rejecting the insert if a key matching by_value exists, but returning us
143 // the Id of the extant shared_pointer(id->def) instead.
144 // return the value of the Iterator from the <Iterator, bool> pair returned by insert
145 Guard g(lock); // Dict isn't thread safe, and use is presumed to be multi-threaded
146 return *dict.insert(from_input).first;
147 }
148
149 private:
150 struct HashKeyValue {
operatorHashKeyValue151 size_t operator()(const Id &value) const { return Hasher()(*value); }
152 };
153 struct KeyValueEqual {
operatorKeyValueEqual154 bool operator()(const Id &lhs, const Id &rhs) const { return KeyEqual()(*lhs, *rhs); }
155 };
156 using Dict = std::unordered_set<Id, HashKeyValue, KeyValueEqual>;
157 using Lock = std::mutex;
158 using Guard = std::lock_guard<Lock>;
159 Lock lock;
160 Dict dict;
161 };
162 } // namespace hash_util
163
164 #endif // HASH_UTILS_H_
165