Actual source code: hashtable.h
1: #if !defined(PETSC_HASHTABLE_H)
2: #define PETSC_HASHTABLE_H
4: #include <petsc/private/petscimpl.h>
6: #define kh_inline PETSC_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: if (h) { \
34: kfree((h)->keys); kfree((h)->flags); \
35: kfree((h)->vals); \
36: memset((h), 0x00, sizeof(*(h))); \
37: } }
38: #endif /*kh_reset*/
40: #if !defined(kh_foreach)
41: /*! @function
42: @abstract Iterate over the entries in the hash table
43: @param h Pointer to the hash table [khash_t(name)*]
44: @param kvar Variable to which key will be assigned
45: @param vvar Variable to which value will be assigned
46: @param code Block of code to execute
47: */
48: #define kh_foreach(h, kvar, vvar, code) { khint_t __i; \
49: for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \
50: if (!kh_exist(h,__i)) continue; \
51: (kvar) = kh_key(h,__i); \
52: (vvar) = kh_val(h,__i); \
53: code; \
54: } }
55: #endif /*kh_foreach*/
57: #if !defined(kh_foreach_key)
58: /*! @function
59: @abstract Iterate over the keys in the hash table
60: @param h Pointer to the hash table [khash_t(name)*]
61: @param kvar Variable to which key will be assigned
62: @param code Block of code to execute
63: */
64: #define kh_foreach_key(h, kvar, code) { khint_t __i; \
65: for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \
66: if (!kh_exist(h,__i)) continue; \
67: (kvar) = kh_key(h,__i); \
68: code; \
69: } }
70: #endif /*kh_foreach_key*/
72: #if !defined(kh_foreach_value)
73: /*! @function
74: @abstract Iterate over the values in the hash table
75: @param h Pointer to the hash table [khash_t(name)*]
76: @param vvar Variable to which value will be assigned
77: @param code Block of code to execute
78: */
79: #define kh_foreach_value(h, vvar, code) { khint_t __i; \
80: for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \
81: if (!kh_exist(h,__i)) continue; \
82: (vvar) = kh_val(h,__i); \
83: code; \
84: } }
85: #endif /*kh_foreach_value*/
87: /* --- Helper macro for error checking --- */
89: #if defined(PETSC_USE_DEBUG)
90: #define PetscHashAssert(expr) do { \
91: if (PetscUnlikely(!(expr))) \
92: SETERRQ1(PETSC_COMM_SELF,PETSC_ERR_LIB, \
93: "[khash] Assertion: `%s' failed.", \
94: PetscStringize(expr)); \
95: } while (0)
96: #else
97: #define PetscHashAssert(expr) ((void)(expr))
98: #endif
100: /* --- Low level iterator API --- */
102: typedef khiter_t PetscHashIter;
104: #define PetscHashIterBegin(ht,i) do { \
105: (i) = kh_begin((ht)); \
106: if ((i) != kh_end((ht)) && !kh_exist((ht),(i))) \
107: PetscHashIterNext((ht),(i)); \
108: } while (0)
110: #define PetscHashIterNext(ht,i) \
111: do { ++(i); } while ((i) != kh_end((ht)) && !kh_exist((ht),(i)))
113: #define PetscHashIterAtEnd(ht,i) ((i) == kh_end((ht)))
115: #define PetscHashIterGetKey(ht,i,k) ((k) = kh_key((ht),(i)))
117: #define PetscHashIterGetVal(ht,i,v) ((v) = kh_val((ht),(i)))
119: #define PetscHashIterSetVal(ht,i,v) (kh_val((ht),(i)) = (v))
121: /* --- Thomas Wang integer hash functions --- */
123: typedef khint32_t PetscHash32_t;
124: typedef khint64_t PetscHash64_t;
125: typedef khint_t PetscHash_t;
127: /* Thomas Wang's first version for 32bit integers */
128: PETSC_STATIC_INLINE PetscHash_t PetscHash_UInt32_v0(PetscHash32_t key)
129: {
130: key += ~(key << 15);
131: key ^= (key >> 10);
132: key += (key << 3);
133: key ^= (key >> 6);
134: key += ~(key << 11);
135: key ^= (key >> 16);
136: return key;
137: }
139: /* Thomas Wang's second version for 32bit integers */
140: PETSC_STATIC_INLINE PetscHash_t PetscHash_UInt32_v1(PetscHash32_t key)
141: {
142: key = ~key + (key << 15); /* key = (key << 15) - key - 1; */
143: key = key ^ (key >> 12);
144: key = key + (key << 2);
145: key = key ^ (key >> 4);
146: key = key * 2057; /* key = (key + (key << 3)) + (key << 11); */
147: key = key ^ (key >> 16);
148: return key;
149: }
151: PETSC_STATIC_INLINE PetscHash_t PetscHash_UInt32(PetscHash32_t key)
152: {
153: return PetscHash_UInt32_v1(key);
154: }
156: /* Thomas Wang's version for 64bit integer -> 32bit hash */
157: PETSC_STATIC_INLINE PetscHash32_t PetscHash_UInt64_32(PetscHash64_t key)
158: {
159: key = ~key + (key << 18); /* key = (key << 18) - key - 1; */
160: key = key ^ (key >> 31);
161: key = key * 21; /* key = (key + (key << 2)) + (key << 4); */
162: key = key ^ (key >> 11);
163: key = key + (key << 6);
164: key = key ^ (key >> 22);
165: return (PetscHash32_t)key;
166: }
168: /* Thomas Wang's version for 64bit integer -> 64bit hash */
169: PETSC_STATIC_INLINE PetscHash64_t PetscHash_UInt64_64(PetscHash64_t key)
170: {
171: key = ~key + (key << 21); /* key = (key << 21) - key - 1; */
172: key = key ^ (key >> 24);
173: key = key * 265; /* key = (key + (key << 3)) + (key << 8); */
174: key = key ^ (key >> 14);
175: key = key * 21; /* key = (key + (key << 2)) + (key << 4); */
176: key = key ^ (key >> 28);
177: key = key + (key << 31);
178: return key;
179: }
181: PETSC_STATIC_INLINE PetscHash_t PetscHash_UInt64(PetscHash64_t key)
182: {
183: return sizeof(PetscHash_t) < sizeof(PetscHash64_t)
184: ? (PetscHash_t)PetscHash_UInt64_32(key)
185: : (PetscHash_t)PetscHash_UInt64_64(key);
186: }
188: PETSC_STATIC_INLINE PetscHash_t PetscHashInt(PetscInt key)
189: {
190: #if defined(PETSC_USE_64BIT_INDICES)
191: return PetscHash_UInt64((PetscHash64_t)key);
192: #else
193: return PetscHash_UInt32((PetscHash32_t)key);
194: #endif
195: }
197: PETSC_STATIC_INLINE PetscHash_t PetscHashPointer(void *key)
198: {
199: #if PETSC_SIZEOF_VOID_P == 8
200: return PetscHash_UInt64((PetscHash64_t)key);
201: #else
202: return PetscHash_UInt32((PetscHash32_t)key);
203: #endif
204: }
206: PETSC_STATIC_INLINE PetscHash_t PetscHashCombine(PetscHash_t seed, PetscHash_t hash)
207: {
208: /* https://doi.org/10.1002/asi.10170 */
209: /* https://dl.acm.org/citation.cfm?id=759509 */
210: return seed ^ (hash + (seed << 6) + (seed >> 2));
211: }
213: #define PetscHashEqual(a,b) ((a) == (b))
215: #endif /* PETSC_HASHTABLE_H */