1+ /*
2+ * Copyright (c) 2014-present, Facebook, Inc.
3+ * All rights reserved.
4+ *
5+ * This source code is licensed under the BSD-style license found in the
6+ * LICENSE file in the root directory of this source tree. An additional grant
7+ * of patent rights can be found in the PATENTS file in the same directory.
8+ *
9+ */
10+
11+ #import < Foundation/Foundation.h>
12+
13+ #import < string>
14+
15+ // From folly:
16+ // This is the Hash128to64 function from Google's cityhash (available
17+ // under the MIT License). We use it to reduce multiple 64 bit hashes
18+ // into a single hash.
19+ inline uint64_t CKHashCombine (const uint64_t upper, const uint64_t lower) {
20+ // Murmur-inspired hashing.
21+ const uint64_t kMul = 0x9ddfea08eb382d69ULL ;
22+ uint64_t a = (lower ^ upper) * kMul ;
23+ a ^= (a >> 47 );
24+ uint64_t b = (upper ^ a) * kMul ;
25+ b ^= (b >> 47 );
26+ b *= kMul ;
27+ return b;
28+ }
29+
30+ #if __LP64__
31+ inline size_t CKHash64ToNative (uint64_t key) {
32+ return key;
33+ }
34+ #else
35+
36+ // Thomas Wang downscaling hash function
37+ inline size_t CKHash64ToNative (uint64_t key) {
38+ key = (~key) + (key << 18 );
39+ key = key ^ (key >> 31 );
40+ key = key * 21 ;
41+ key = key ^ (key >> 11 );
42+ key = key + (key << 6 );
43+ key = key ^ (key >> 22 );
44+ return (uint32_t ) key;
45+ }
46+ #endif
47+
48+ NSUInteger CKIntegerArrayHash (const NSUInteger *subhashes, NSUInteger count);
49+
50+ namespace CK {
51+ // Default is not an ObjC class
52+ template<typename T, typename V = bool >
53+ struct is_objc_class : std::false_type { };
54+
55+ // Conditionally enable this template specialization on whether T is convertible to id, makes the is_objc_class a true_type
56+ template<typename T>
57+ struct is_objc_class<T, typename std::enable_if<std::is_convertible<T, id >::value, bool >::type> : std::true_type { };
58+
59+ // CKUtils::hash<T>()(value) -> either std::hash<T> if c++ or [o hash] if ObjC object.
60+ template <typename T, typename Enable = void > struct hash;
61+
62+ // For non-objc types, defer to std::hash
63+ template <typename T> struct hash<T, typename std::enable_if<!is_objc_class<T>::value>::type> {
64+ size_t operator ()(const T& a) {
65+ return std::hash<T>()(a);
66+ }
67+ };
68+
69+ // For objc types, call [o hash]
70+ template <typename T> struct hash<T, typename std::enable_if<is_objc_class<T>::value>::type> {
71+ size_t operator ()(id o) {
72+ return [o hash ];
73+ }
74+ };
75+
76+ template <typename T, typename Enable = void > struct is_equal;
77+
78+ // For non-objc types use == operator
79+ template <typename T> struct is_equal<T, typename std::enable_if<!is_objc_class<T>::value>::type> {
80+ bool operator ()(const T& a, const T& b) {
81+ return a == b;
82+ }
83+ };
84+
85+ // For objc types, check pointer equality, then use -isEqual:
86+ template <typename T> struct is_equal<T, typename std::enable_if<is_objc_class<T>::value>::type> {
87+ bool operator ()(id a, id b) {
88+ return a == b || [a isEqual: b];
89+ }
90+ };
91+
92+ };
93+
94+ namespace CKTupleOperations
95+ {
96+ // Recursive case (hash up to Index)
97+ template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1 >
98+ struct _hash_helper
99+ {
100+ static size_t hash (Tuple const & tuple)
101+ {
102+ size_t prev = _hash_helper<Tuple, Index-1 >::hash (tuple);
103+ using TypeForIndex = typename std::tuple_element<Index,Tuple>::type;
104+ size_t thisHash = CK::hash<TypeForIndex>()(std::get<Index>(tuple));
105+ return CKHashCombine (prev, thisHash);
106+ }
107+ };
108+
109+ // Base case (hash 0th element)
110+ template <class Tuple>
111+ struct _hash_helper<Tuple, 0 >
112+ {
113+ static size_t hash (Tuple const & tuple)
114+ {
115+ using TypeForIndex = typename std::tuple_element<0 ,Tuple>::type;
116+ return CK::hash<TypeForIndex>()(std::get<0 >(tuple));
117+ }
118+ };
119+
120+ // Recursive case (elements equal up to Index)
121+ template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1 >
122+ struct _eq_helper
123+ {
124+ static bool equal (Tuple const & a, Tuple const & b)
125+ {
126+ bool prev = _eq_helper<Tuple, Index-1 >::equal (a, b);
127+ using TypeForIndex = typename std::tuple_element<Index,Tuple>::type;
128+ auto aValue = std::get<Index>(a);
129+ auto bValue = std::get<Index>(b);
130+ return prev && CK::is_equal<TypeForIndex>()(aValue, bValue);
131+ }
132+ };
133+
134+ // Base case (0th elements equal)
135+ template <class Tuple>
136+ struct _eq_helper<Tuple, 0 >
137+ {
138+ static bool equal (Tuple const & a, Tuple const & b)
139+ {
140+ using TypeForIndex = typename std::tuple_element<0 ,Tuple>::type;
141+ auto & aValue = std::get<0 >(a);
142+ auto & bValue = std::get<0 >(b);
143+ return CK::is_equal<TypeForIndex>()(aValue, bValue);
144+ }
145+ };
146+
147+
148+ template <typename ... TT> struct hash;
149+
150+ template <typename ... TT>
151+ struct hash<std::tuple<TT...>>
152+ {
153+ size_t operator ()(std::tuple<TT...> const & tt) const
154+ {
155+ return _hash_helper<std::tuple<TT...>>::hash (tt);
156+ }
157+ };
158+
159+
160+ template <typename ... TT> struct equal_to;
161+
162+ template <typename ... TT>
163+ struct equal_to<std::tuple<TT...>>
164+ {
165+ bool operator ()(std::tuple<TT...> const & a, std::tuple<TT...> const & b) const
166+ {
167+ return _eq_helper<std::tuple<TT...>>::equal (a, b);
168+ }
169+ };
170+
171+ }
0 commit comments