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