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))