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