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 79namespace ceres { 80namespace internal { 81 82template<typename K, typename V> 83struct HashMap : map<K, V> {}; 84 85template<typename K> 86struct HashSet : set<K> {}; 87 88} // namespace internal 89} // namespace ceres 90 91#else 92 93namespace ceres { 94namespace internal { 95 96#if defined(CERES_TR1_UNORDERED_MAP) || \ 97 defined(CERES_STD_UNORDERED_MAP_IN_TR1_NAMESPACE) 98template<typename K, typename V> 99struct HashMap : std::tr1::unordered_map<K, V> {}; 100template<typename K> 101struct HashSet : std::tr1::unordered_set<K> {}; 102#endif 103 104#if defined(CERES_STD_UNORDERED_MAP) 105template<typename K, typename V> 106struct HashMap : std::unordered_map<K, V> {}; 107template<typename K> 108struct 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 125inline 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 138inline 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 150inline 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 157inline 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. 169CERES_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. 175template<typename T> 176struct 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 194CERES_HASH_NAMESPACE_END 195 196#endif // CERES_NO_UNORDERED_MAP 197#endif // CERES_INTERNAL_COLLECTIONS_PORT_H_ 198