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