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 (at) 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 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 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 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 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
