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 #if defined(CERES_NO_TR1) 37 # include <map> 38 # include <set> 39 #else 40 # if defined(_MSC_VER) 41 # include <unordered_map> 42 # include <unordered_set> 43 # else 44 # include <tr1/unordered_map> 45 # include <tr1/unordered_set> 46 # endif 47 #endif 48 #include <utility> 49 #include "ceres/integral_types.h" 50 #include "ceres/internal/port.h" 51 52 // Some systems don't have access to TR1. In that case, substitute the hash 53 // map/set with normal map/set. The price to pay is slightly slower speed for 54 // some operations. 55 #if defined(CERES_NO_TR1) 56 57 namespace ceres { 58 namespace internal { 59 60 template<typename K, typename V> 61 struct HashMap : map<K, V> {}; 62 63 template<typename K> 64 struct HashSet : set<K> {}; 65 66 } // namespace internal 67 } // namespace ceres 68 69 #else 70 71 namespace ceres { 72 namespace internal { 73 74 template<typename K, typename V> 75 struct HashMap : std::tr1::unordered_map<K, V> {}; 76 77 template<typename K> 78 struct HashSet : std::tr1::unordered_set<K> {}; 79 80 #ifdef _WIN32 81 #define GG_LONGLONG(x) x##I64 82 #define GG_ULONGLONG(x) x##UI64 83 #else 84 #define GG_LONGLONG(x) x##LL 85 #define GG_ULONGLONG(x) x##ULL 86 #endif 87 88 // The hash function is due to Bob Jenkins (see 89 // http://burtleburtle.net/bob/hash/index.html). Each mix takes 36 instructions, 90 // in 18 cycles if you're lucky. On x86 architectures, this requires 45 91 // instructions in 27 cycles, if you're lucky. 92 // 93 // 32bit version 94 inline void hash_mix(uint32& a, uint32& b, uint32& c) { 95 a -= b; a -= c; a ^= (c>>13); 96 b -= c; b -= a; b ^= (a<<8); 97 c -= a; c -= b; c ^= (b>>13); 98 a -= b; a -= c; a ^= (c>>12); 99 b -= c; b -= a; b ^= (a<<16); 100 c -= a; c -= b; c ^= (b>>5); 101 a -= b; a -= c; a ^= (c>>3); 102 b -= c; b -= a; b ^= (a<<10); 103 c -= a; c -= b; c ^= (b>>15); 104 } 105 106 // 64bit version 107 inline void hash_mix(uint64& a, uint64& b, uint64& c) { 108 a -= b; a -= c; a ^= (c>>43); 109 b -= c; b -= a; b ^= (a<<9); 110 c -= a; c -= b; c ^= (b>>8); 111 a -= b; a -= c; a ^= (c>>38); 112 b -= c; b -= a; b ^= (a<<23); 113 c -= a; c -= b; c ^= (b>>5); 114 a -= b; a -= c; a ^= (c>>35); 115 b -= c; b -= a; b ^= (a<<49); 116 c -= a; c -= b; c ^= (b>>11); 117 } 118 119 inline uint32 Hash32NumWithSeed(uint32 num, uint32 c) { 120 // The golden ratio; an arbitrary value. 121 uint32 b = 0x9e3779b9UL; 122 hash_mix(num, b, c); 123 return c; 124 } 125 126 inline uint64 Hash64NumWithSeed(uint64 num, uint64 c) { 127 // More of the golden ratio. 128 uint64 b = GG_ULONGLONG(0xe08c1d668b756f82); 129 hash_mix(num, b, c); 130 return c; 131 } 132 133 } // namespace internal 134 } // namespace ceres 135 136 // Since on some platforms this is a doubly-nested namespace (std::tr1) and 137 // others it is not, the entire namespace line must be in a macro. 138 CERES_HASH_NAMESPACE_START 139 140 // The outrageously annoying specializations below are for portability reasons. 141 // In short, it's not possible to have two overloads of hash<pair<T1, T2> 142 143 // Hasher for STL pairs. Requires hashers for both members to be defined. 144 template<typename T> 145 struct hash<pair<T, T> > { 146 size_t operator()(const pair<T, T>& p) const { 147 size_t h1 = hash<T>()(p.first); 148 size_t h2 = hash<T>()(p.second); 149 // The decision below is at compile time 150 return (sizeof(h1) <= sizeof(ceres::internal::uint32)) ? 151 ceres::internal::Hash32NumWithSeed(h1, h2) : 152 ceres::internal::Hash64NumWithSeed(h1, h2); 153 } 154 // Less than operator for MSVC. 155 bool operator()(const pair<T, T>& a, 156 const pair<T, T>& b) const { 157 return a < b; 158 } 159 static const size_t bucket_size = 4; // These are required by MSVC 160 static const size_t min_buckets = 8; // 4 and 8 are defaults. 161 }; 162 163 CERES_HASH_NAMESPACE_END 164 165 #endif // CERES_NO_TR1 166 167 #endif // CERES_INTERNAL_COLLECTIONS_PORT_H_ 168
