1 // Ceres Solver - A fast non-linear least squares minimizer
2 // Copyright 2010, 2011, 2012 Google Inc. All rights reserved.
3 // http://code.google.com/p/ceres-solver/
4 //
5 // Redistribution and use in source and binary forms, with or without
6 // modification, are permitted provided that the following conditions are met:
7 //
8 // * Redistributions of source code must retain the above copyright notice,
9 // this list of conditions and the following disclaimer.
10 // * Redistributions in binary form must reproduce the above copyright notice,
11 // this list of conditions and the following disclaimer in the documentation
12 // and/or other materials provided with the distribution.
13 // * Neither the name of Google Inc. nor the names of its contributors may be
14 // used to endorse or promote products derived from this software without
15 // specific prior written permission.
16 //
17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
21 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 // POSSIBILITY OF SUCH DAMAGE.
28 //
29 // Author: keir@google.com (Keir Mierle)
30 //
31 // Portable HashMap and HashSet, and a specialized overload for hashing pairs.
32
33 #ifndef CERES_INTERNAL_COLLECTIONS_PORT_H_
34 #define CERES_INTERNAL_COLLECTIONS_PORT_H_
35
36 #include "ceres/internal/port.h"
37
38 #if defined(CERES_NO_UNORDERED_MAP)
39 # include <map>
40 # include <set>
41 #endif
42
43 #if defined(CERES_TR1_UNORDERED_MAP)
44 # include <tr1/unordered_map>
45 # include <tr1/unordered_set>
46 # define CERES_HASH_NAMESPACE_START namespace std { namespace tr1 {
47 # define CERES_HASH_NAMESPACE_END } }
48 #endif
49
50 #if defined(CERES_STD_UNORDERED_MAP)
51 # include <unordered_map>
52 # include <unordered_set>
53 # define CERES_HASH_NAMESPACE_START namespace std {
54 # define CERES_HASH_NAMESPACE_END }
55 #endif
56
57 #if defined(CERES_STD_UNORDERED_MAP_IN_TR1_NAMESPACE)
58 # include <unordered_map>
59 # include <unordered_set>
60 # define CERES_HASH_NAMESPACE_START namespace std { namespace tr1 {
61 # define CERES_HASH_NAMESPACE_END } }
62 #endif
63
64 #if !defined(CERES_NO_UNORDERED_MAP) && !defined(CERES_TR1_UNORDERED_MAP) && \
65 !defined(CERES_STD_UNORDERED_MAP) && !defined(CERES_STD_UNORDERED_MAP_IN_TR1_NAMESPACE) // NOLINT
66 # error One of: CERES_NO_UNORDERED_MAP, CERES_TR1_UNORDERED_MAP,\
67 CERES_STD_UNORDERED_MAP, CERES_STD_UNORDERED_MAP_IN_TR1_NAMESPACE must be defined! // NOLINT
68 #endif
69
70 #include <utility>
71 #include "ceres/integral_types.h"
72 #include "ceres/internal/port.h"
73
74 // Some systems don't have access to unordered_map/unordered_set. In
75 // that case, substitute the hash map/set with normal map/set. The
76 // price to pay is slower speed for some operations.
77 #if defined(CERES_NO_UNORDERED_MAP)
78
79 namespace ceres {
80 namespace internal {
81
82 template<typename K, typename V>
83 struct HashMap : map<K, V> {};
84
85 template<typename K>
86 struct HashSet : set<K> {};
87
88 } // namespace internal
89 } // namespace ceres
90
91 #else
92
93 namespace ceres {
94 namespace internal {
95
96 #if defined(CERES_TR1_UNORDERED_MAP) || \
97 defined(CERES_STD_UNORDERED_MAP_IN_TR1_NAMESPACE)
98 template<typename K, typename V>
99 struct HashMap : std::tr1::unordered_map<K, V> {};
100 template<typename K>
101 struct HashSet : std::tr1::unordered_set<K> {};
102 #endif
103
104 #if defined(CERES_STD_UNORDERED_MAP)
105 template<typename K, typename V>
106 struct HashMap : std::unordered_map<K, V> {};
107 template<typename K>
108 struct HashSet : std::unordered_set<K> {};
109 #endif
110
111 #if defined(_WIN32) && !defined(__MINGW64__) && !defined(__MINGW32__)
112 #define GG_LONGLONG(x) x##I64
113 #define GG_ULONGLONG(x) x##UI64
114 #else
115 #define GG_LONGLONG(x) x##LL
116 #define GG_ULONGLONG(x) x##ULL
117 #endif
118
119 // The hash function is due to Bob Jenkins (see
120 // http://burtleburtle.net/bob/hash/index.html). Each mix takes 36 instructions,
121 // in 18 cycles if you're lucky. On x86 architectures, this requires 45
122 // instructions in 27 cycles, if you're lucky.
123 //
124 // 32bit version
hash_mix(uint32 & a,uint32 & b,uint32 & c)125 inline void hash_mix(uint32& a, uint32& b, uint32& c) {
126 a -= b; a -= c; a ^= (c>>13);
127 b -= c; b -= a; b ^= (a<<8);
128 c -= a; c -= b; c ^= (b>>13);
129 a -= b; a -= c; a ^= (c>>12);
130 b -= c; b -= a; b ^= (a<<16);
131 c -= a; c -= b; c ^= (b>>5);
132 a -= b; a -= c; a ^= (c>>3);
133 b -= c; b -= a; b ^= (a<<10);
134 c -= a; c -= b; c ^= (b>>15);
135 }
136
137 // 64bit version
hash_mix(uint64 & a,uint64 & b,uint64 & c)138 inline void hash_mix(uint64& a, uint64& b, uint64& c) {
139 a -= b; a -= c; a ^= (c>>43);
140 b -= c; b -= a; b ^= (a<<9);
141 c -= a; c -= b; c ^= (b>>8);
142 a -= b; a -= c; a ^= (c>>38);
143 b -= c; b -= a; b ^= (a<<23);
144 c -= a; c -= b; c ^= (b>>5);
145 a -= b; a -= c; a ^= (c>>35);
146 b -= c; b -= a; b ^= (a<<49);
147 c -= a; c -= b; c ^= (b>>11);
148 }
149
Hash32NumWithSeed(uint32 num,uint32 c)150 inline uint32 Hash32NumWithSeed(uint32 num, uint32 c) {
151 // The golden ratio; an arbitrary value.
152 uint32 b = 0x9e3779b9UL;
153 hash_mix(num, b, c);
154 return c;
155 }
156
Hash64NumWithSeed(uint64 num,uint64 c)157 inline uint64 Hash64NumWithSeed(uint64 num, uint64 c) {
158 // More of the golden ratio.
159 uint64 b = GG_ULONGLONG(0xe08c1d668b756f82);
160 hash_mix(num, b, c);
161 return c;
162 }
163
164 } // namespace internal
165 } // namespace ceres
166
167 // Since on some platforms this is a doubly-nested namespace (std::tr1) and
168 // others it is not, the entire namespace line must be in a macro.
169 CERES_HASH_NAMESPACE_START
170
171 // The outrageously annoying specializations below are for portability reasons.
172 // In short, it's not possible to have two overloads of hash<pair<T1, T2>
173
174 // Hasher for STL pairs. Requires hashers for both members to be defined.
175 template<typename T>
176 struct hash<pair<T, T> > {
177 size_t operator()(const pair<T, T>& p) const {
178 size_t h1 = hash<T>()(p.first);
179 size_t h2 = hash<T>()(p.second);
180 // The decision below is at compile time
181 return (sizeof(h1) <= sizeof(ceres::internal::uint32)) ?
182 ceres::internal::Hash32NumWithSeed(h1, h2) :
183 ceres::internal::Hash64NumWithSeed(h1, h2);
184 }
185 // Less than operator for MSVC.
186 bool operator()(const pair<T, T>& a,
187 const pair<T, T>& b) const {
188 return a < b;
189 }
190 static const size_t bucket_size = 4; // These are required by MSVC
191 static const size_t min_buckets = 8; // 4 and 8 are defaults.
192 };
193
194 CERES_HASH_NAMESPACE_END
195
196 #endif // CERES_NO_UNORDERED_MAP
197 #endif // CERES_INTERNAL_COLLECTIONS_PORT_H_
198