1 #pragma once
2
3 #include <petsc/private/petscimpl.h>
4
5 #define kh_inline inline
6 #define klib_unused PETSC_UNUSED
7 #if !defined(kh_foreach_value)
8 #define undef_kh_foreach_value
9 #endif
10 #include <petsc/private/khash/khash.h>
11 #if defined(undef_kh_foreach_value)
12 #undef kh_foreach_value
13 #undef undef_kh_foreach_value
14 #endif
15
16 /* Required for khash <= 0.2.5 */
17 #if !defined(kcalloc)
18 #define kcalloc(N, Z) calloc(N, Z)
19 #endif
20 #if !defined(kmalloc)
21 #define kmalloc(Z) malloc(Z)
22 #endif
23 #if !defined(krealloc)
24 #define krealloc(P, Z) realloc(P, Z)
25 #endif
26 #if !defined(kfree)
27 #define kfree(P) free(P)
28 #endif
29
30 /* --- Useful extensions to khash --- */
31
32 #if !defined(kh_reset)
33 /*! @function
34 @abstract Reset a hash table to initial state.
35 @param name Name of the hash table [symbol]
36 @param h Pointer to the hash table [khash_t(name)*]
37 */
38 #define kh_reset(name, h) \
39 { \
40 if (h) { \
41 kfree((h)->keys); \
42 kfree((h)->flags); \
43 kfree((h)->vals); \
44 memset((h), 0x00, sizeof(*(h))); \
45 } \
46 }
47 #endif /*kh_reset*/
48
49 #if !defined(kh_foreach)
50 /*! @function
51 @abstract Iterate over the entries in the hash table
52 @param h Pointer to the hash table [khash_t(name)*]
53 @param kvar Variable to which key will be assigned
54 @param vvar Variable to which value will be assigned
55 @param code Block of code to execute
56 */
57 #define kh_foreach(h, kvar, vvar, code) \
58 { \
59 khint_t __i; \
60 for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \
61 if (!kh_exist(h, __i)) continue; \
62 (kvar) = kh_key(h, __i); \
63 (vvar) = kh_val(h, __i); \
64 code; \
65 } \
66 }
67 #endif /*kh_foreach*/
68
69 #if !defined(kh_foreach_key)
70 /*! @function
71 @abstract Iterate over the keys in the hash table
72 @param h Pointer to the hash table [khash_t(name)*]
73 @param kvar Variable to which key will be assigned
74 @param code Block of code to execute
75 */
76 #define kh_foreach_key(h, kvar, code) \
77 { \
78 khint_t __i; \
79 for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \
80 if (!kh_exist(h, __i)) continue; \
81 (kvar) = kh_key(h, __i); \
82 code; \
83 } \
84 }
85 #endif /*kh_foreach_key*/
86
87 #if !defined(kh_foreach_value)
88 /*! @function
89 @abstract Iterate over the values in the hash table
90 @param h Pointer to the hash table [khash_t(name)*]
91 @param vvar Variable to which value will be assigned
92 @param code Block of code to execute
93 */
94 #define kh_foreach_value(h, vvar, code) \
95 do { \
96 khint_t __i; \
97 for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \
98 if (!kh_exist(h, __i)) continue; \
99 (vvar) = kh_val(h, __i); \
100 code; \
101 } \
102 } while (0)
103 #endif /*kh_foreach_value*/
104
105 /* --- Helper macro for error checking --- */
106
107 #if defined(PETSC_USE_DEBUG)
108 #define PetscHashAssert(expr) PetscCheck(expr, PETSC_COMM_SELF, PETSC_ERR_LIB, "[khash] Assertion: `%s' failed.", PetscStringize(expr))
109 #else
110 #define PetscHashAssert(expr) ((void)(expr))
111 #endif
112
113 /* --- Low level iterator API --- */
114
115 typedef khiter_t PetscHashIter;
116
117 #define PetscHashIterAtEnd(ht, i) ((i) == kh_end(ht))
118
119 #define PetscHashIterAtBegin(ht, i) ((i) == kh_begin(ht))
120
121 #define PetscHashIterIncContinue(ht, it) (!PetscHashIterAtEnd((ht), (it)) && !kh_exist((ht), (it)))
122
123 #define PetscHashIterBegin(ht, i) \
124 do { \
125 PetscHashIter phib_it_ = kh_begin(ht); \
126 if (PetscHashIterIncContinue((ht), phib_it_)) PetscHashIterNext((ht), phib_it_); \
127 (i) = phib_it_; \
128 } while (0)
129
130 #define PetscHashIterNext(ht, i) \
131 do { \
132 ++(i); \
133 } while (PetscHashIterIncContinue((ht), (i)))
134
135 #define PetscHashIterEnd(ht, i) ((i) = kh_end(ht))
136
137 #define PetscHashIterDecContinue(ht, it) (PetscHashIterAtEnd((ht), (it)) || (!PetscHashIterAtBegin((ht), (it)) && !kh_exist((ht), (it))))
138
139 #define PetscHashIterPrevious(ht, i) \
140 do { \
141 PetscHashIter phip_it_ = (i); \
142 PetscAssertAbort(!PetscHashIterAtBegin((ht), phip_it_), PETSC_COMM_SELF, PETSC_ERR_PLIB, "Trying to decrement iterator past begin"); \
143 do { \
144 --phip_it_; \
145 } while (PetscHashIterDecContinue((ht), phip_it_)); \
146 (i) = phip_it_; \
147 } while (0)
148
149 #define PetscHashIterGetKey(ht, i, k) ((k) = kh_key((ht), (i)))
150
151 #define PetscHashIterGetVal(ht, i, v) ((v) = kh_val((ht), (i)))
152
153 #define PetscHashIterSetVal(ht, i, v) (kh_val((ht), (i)) = (v))
154
155 /* --- Thomas Wang integer hash functions --- */
156
157 typedef khint32_t PetscHash32_t;
158 typedef khint64_t PetscHash64_t;
159 typedef khint_t PetscHash_t;
160
161 /* Thomas Wang's first version for 32-bit integers */
PetscHash_UInt32_v0(PetscHash32_t key)162 static inline PetscHash_t PetscHash_UInt32_v0(PetscHash32_t key)
163 {
164 key += ~(key << 15);
165 key ^= (key >> 10);
166 key += (key << 3);
167 key ^= (key >> 6);
168 key += ~(key << 11);
169 key ^= (key >> 16);
170 return key;
171 }
172
173 /* Thomas Wang's second version for 32-bit integers */
PetscHash_UInt32_v1(PetscHash32_t key)174 static inline PetscHash_t PetscHash_UInt32_v1(PetscHash32_t key)
175 {
176 key = ~key + (key << 15); /* key = (key << 15) - key - 1; */
177 key = key ^ (key >> 12);
178 key = key + (key << 2);
179 key = key ^ (key >> 4);
180 key = key * 2057; /* key = (key + (key << 3)) + (key << 11); */
181 key = key ^ (key >> 16);
182 return key;
183 }
184
PetscHash_UInt32(PetscHash32_t key)185 static inline PetscHash_t PetscHash_UInt32(PetscHash32_t key)
186 {
187 return PetscHash_UInt32_v1(key);
188 }
189
190 /* Thomas Wang's version for 64-bit integer -> 32-bit hash */
PetscHash_UInt64_32(PetscHash64_t key)191 static inline PetscHash32_t PetscHash_UInt64_32(PetscHash64_t key)
192 {
193 key = ~key + (key << 18); /* key = (key << 18) - key - 1; */
194 key = key ^ (key >> 31);
195 key = key * 21; /* key = (key + (key << 2)) + (key << 4); */
196 key = key ^ (key >> 11);
197 key = key + (key << 6);
198 key = key ^ (key >> 22);
199 return (PetscHash32_t)key;
200 }
201
202 /* Thomas Wang's version for 64-bit integer -> 64-bit hash */
PetscHash_UInt64_64(PetscHash64_t key)203 static inline PetscHash64_t PetscHash_UInt64_64(PetscHash64_t key)
204 {
205 key = ~key + (key << 21); /* key = (key << 21) - key - 1; */
206 key = key ^ (key >> 24);
207 key = key * 265; /* key = (key + (key << 3)) + (key << 8); */
208 key = key ^ (key >> 14);
209 key = key * 21; /* key = (key + (key << 2)) + (key << 4); */
210 key = key ^ (key >> 28);
211 key = key + (key << 31);
212 return key;
213 }
214
PetscHash_UInt64(PetscHash64_t key)215 static inline PetscHash_t PetscHash_UInt64(PetscHash64_t key)
216 {
217 return sizeof(PetscHash_t) < sizeof(PetscHash64_t) ? (PetscHash_t)PetscHash_UInt64_32(key) : (PetscHash_t)PetscHash_UInt64_64(key);
218 }
219
PetscHashInt(PetscInt key)220 static inline PetscHash_t PetscHashInt(PetscInt key)
221 {
222 #if defined(PETSC_USE_64BIT_INDICES)
223 return PetscHash_UInt64((PetscHash64_t)key);
224 #else
225 return PetscHash_UInt32((PetscHash32_t)key);
226 #endif
227 }
228
PetscHashInt64(PetscInt64 key)229 static inline PetscHash_t PetscHashInt64(PetscInt64 key)
230 {
231 #if defined(PETSC_USE_64BIT_INDICES)
232 return PetscHash_UInt64((PetscHash64_t)key);
233 #else
234 return PetscHash_UInt32((PetscHash32_t)key);
235 #endif
236 }
237
PetscHashPointer(const void * key)238 static inline PetscHash_t PetscHashPointer(const void *key)
239 {
240 #if PETSC_SIZEOF_VOID_P == 8
241 return PetscHash_UInt64((PetscHash64_t)key);
242 #else
243 return PetscHash_UInt32((PetscHash32_t)key);
244 #endif
245 }
246
PetscHashCombine(PetscHash_t seed,PetscHash_t hash)247 static inline PetscHash_t PetscHashCombine(PetscHash_t seed, PetscHash_t hash)
248 {
249 /* https://doi.org/10.1002/asi.10170 */
250 /* https://dl.acm.org/citation.cfm?id=759509 */
251 return seed ^ (hash + (seed << 6) + (seed >> 2));
252 }
253
254 #define PetscHashEqual(a, b) ((a) == (b))
255