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