OR-Tools  8.2
hash.h
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14#ifndef OR_TOOLS_BASE_HASH_H_
15#define OR_TOOLS_BASE_HASH_H_
16
17#include <array>
18#include <string>
19#include <utility>
20
22
23// In SWIG mode, we don't want anything besides these top-level includes.
24#if !defined(SWIG)
25
26namespace operations_research {
27// 32 bit version.
28static inline void mix(uint32& a, uint32& b, uint32& c) { // NOLINT
29 a -= b;
30 a -= c;
31 a ^= (c >> 13);
32 b -= c;
33 b -= a;
34 b ^= (a << 8);
35 c -= a;
36 c -= b;
37 c ^= (b >> 13);
38 a -= b;
39 a -= c;
40 a ^= (c >> 12);
41 b -= c;
42 b -= a;
43 b ^= (a << 16);
44 c -= a;
45 c -= b;
46 c ^= (b >> 5);
47 a -= b;
48 a -= c;
49 a ^= (c >> 3);
50 b -= c;
51 b -= a;
52 b ^= (a << 10);
53 c -= a;
54 c -= b;
55 c ^= (b >> 15);
56}
57
58// 64 bit version.
59static inline void mix(uint64& a, uint64& b, uint64& c) { // NOLINT
60 a -= b;
61 a -= c;
62 a ^= (c >> 43);
63 b -= c;
64 b -= a;
65 b ^= (a << 9);
66 c -= a;
67 c -= b;
68 c ^= (b >> 8);
69 a -= b;
70 a -= c;
71 a ^= (c >> 38);
72 b -= c;
73 b -= a;
74 b ^= (a << 23);
75 c -= a;
76 c -= b;
77 c ^= (b >> 5);
78 a -= b;
79 a -= c;
80 a ^= (c >> 35);
81 b -= c;
82 b -= a;
83 b ^= (a << 49);
84 c -= a;
85 c -= b;
86 c ^= (b >> 11);
87 a -= b;
88 a -= c;
89 a ^= (c >> 12);
90 b -= c;
91 b -= a;
92 b ^= (a << 18);
93 c -= a;
94 c -= b;
95 c ^= (b >> 22);
96}
98 uint32 b = 0x9e3779b9UL; // The golden ratio; an arbitrary value.
100 return c;
101}
102
104 uint64 b = uint64_t{0xe08c1d668b756f82}; // More of the golden ratio.
106 return c;
107}
108} // namespace operations_research
109
110// Support a few hash<> operators, in the hash namespace.
111namespace std {
112template <class First, class Second>
113struct hash<std::pair<First, Second>> {
114 size_t operator()(const std::pair<First, Second>& p) const {
115 size_t h1 = hash<First>()(p.first);
116 size_t h2 = hash<Second>()(p.second);
117 // The decision below is at compile time
118 return (sizeof(h1) <= sizeof(uint32))
119 ? // NOLINT
122 }
123};
124
125template <class T, std::size_t N>
126struct hash<std::array<T, N>> {
127 public:
128 size_t operator()(const std::array<T, N>& t) const {
129 uint64 current = 71;
130 for (int index = 0; index < N; ++index) {
131 const T& elem = t[index];
132 const uint64 new_hash = hash<T>()(elem);
133 current = operations_research::Hash64NumWithSeed(current, new_hash);
134 }
135 return current;
136 }
137 // Less than operator for MSVC.
138 bool operator()(const std::array<T, N>& a, const std::array<T, N>& b) const {
139 return a < b;
140 }
141 static const size_t bucket_size = 4; // These are required by MSVC.
142 static const size_t min_buckets = 8; // 4 and 8 are defaults.
143};
144} // namespace std
145
146#endif // SWIG
147
148namespace util_hash {
149
150inline uint64 Hash(uint64 num, uint64 c) {
151 uint64 b = uint64_t{0xe08c1d668b756f82}; // More of the golden ratio.
153 return c;
154}
155
158 return c;
159}
160
161} // namespace util_hash
162
163#endif // OR_TOOLS_BASE_HASH_H_
unsigned int uint32
uint64_t uint64
int64 hash
Definition: matrix_utils.cc:60
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
uint64 Hash64NumWithSeed(uint64 num, uint64 c)
Definition: hash.h:103
uint32 Hash32NumWithSeed(uint32 num, uint32 c)
Definition: hash.h:97
static void mix(uint32 &a, uint32 &b, uint32 &c)
Definition: hash.h:28
STL namespace.
uint64 Hash(uint64 num, uint64 c)
Definition: hash.h:150
int index
Definition: pack.cc:508
bool operator()(const std::array< T, N > &a, const std::array< T, N > &b) const
Definition: hash.h:138
size_t operator()(const std::array< T, N > &t) const
Definition: hash.h:128
size_t operator()(const std::pair< First, Second > &p) const
Definition: hash.h:114