Actual source code: hashtable.h
1: #pragma once
3: #include <petsc/private/petscimpl.h>
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
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
30: /* --- Useful extensions to khash --- */
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*/
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*/
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*/
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*/
105: /* --- Helper macro for error checking --- */
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
113: /* --- Low level iterator API --- */
115: typedef khiter_t PetscHashIter;
117: #define PetscHashIterAtEnd(ht, i) ((i) == kh_end(ht))
119: #define PetscHashIterAtBegin(ht, i) ((i) == kh_begin(ht))
121: #define PetscHashIterIncContinue(ht, it) (!PetscHashIterAtEnd((ht), (it)) && !kh_exist((ht), (it)))
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)
130: #define PetscHashIterNext(ht, i) \
131: do { \
132: ++(i); \
133: } while (PetscHashIterIncContinue((ht), (i)))
135: #define PetscHashIterEnd(ht, i) ((i) = kh_end(ht))
137: #define PetscHashIterDecContinue(ht, it) (PetscHashIterAtEnd((ht), (it)) || (!PetscHashIterAtBegin((ht), (it)) && !kh_exist((ht), (it))))
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)
149: #define PetscHashIterGetKey(ht, i, k) ((k) = kh_key((ht), (i)))
151: #define PetscHashIterGetVal(ht, i, v) ((v) = kh_val((ht), (i)))
153: #define PetscHashIterSetVal(ht, i, v) (kh_val((ht), (i)) = (v))
155: /* --- Thomas Wang integer hash functions --- */
157: typedef khint32_t PetscHash32_t;
158: typedef khint64_t PetscHash64_t;
159: typedef khint_t PetscHash_t;
161: /* Thomas Wang's first version for 32-bit integers */
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: }
173: /* Thomas Wang's second version for 32-bit integers */
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: }
185: static inline PetscHash_t PetscHash_UInt32(PetscHash32_t key)
186: {
187: return PetscHash_UInt32_v1(key);
188: }
190: /* Thomas Wang's version for 64-bit integer -> 32-bit hash */
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: }
202: /* Thomas Wang's version for 64-bit integer -> 64-bit hash */
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: }
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: }
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: }
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: }
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: }
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: }
254: #define PetscHashEqual(a, b) ((a) == (b))