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 */