Actual source code: hashtable.h

petsc-master 2019-11-11
Report Typos and Errors
  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/kernels/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*/


 88: /* --- Helper macro for error checking --- */

 90: #if defined(PETSC_USE_DEBUG)
 91: #define PetscHashAssert(expr) do {                 \
 92:   if (PetscUnlikely(!(expr)))                      \
 93:     SETERRQ1(PETSC_COMM_SELF,PETSC_ERR_LIB,        \
 94:              "[khash] Assertion: `%s' failed.",    \
 95:              PetscStringize(expr));                \
 96: } while(0)
 97: #else
 98: #define PetscHashAssert(expr) ((void)(expr))
 99: #endif


102: /* --- Low level iterator API --- */

104: typedef khiter_t PetscHashIter;

106: #define PetscHashIterBegin(ht,i) do {              \
107:   (i) = kh_begin((ht));                            \
108:   if ((i) != kh_end((ht)) && !kh_exist((ht),(i)))  \
109:     PetscHashIterNext((ht),(i));                   \
110: } while (0)

112: #define PetscHashIterNext(ht,i) \
113:   do { ++(i); } while ((i) != kh_end((ht)) && !kh_exist((ht),(i)))

115: #define PetscHashIterAtEnd(ht,i) ((i) == kh_end((ht)))

117: #define PetscHashIterGetKey(ht,i,k) ((k) = kh_key((ht),(i)))

119: #define PetscHashIterGetVal(ht,i,v) ((v) = kh_val((ht),(i)))

121: #define PetscHashIterSetVal(ht,i,v) (kh_val((ht),(i)) = (v))


124: /* --- Thomas Wang integer hash functions --- */

126: typedef khint32_t PetscHash32_t;
127: typedef khint64_t PetscHash64_t;
128: typedef khint_t   PetscHash_t;

130: /* Thomas Wang's first version for 32bit integers */
131: PETSC_STATIC_INLINE PetscHash_t PetscHash_UInt32_v0(PetscHash32_t key)
132: {
133:   key += ~(key << 15);
134:   key ^=  (key >> 10);
135:   key +=  (key <<  3);
136:   key ^=  (key >>  6);
137:   key += ~(key << 11);
138:   key ^=  (key >> 16);
139:   return key;
140: }

142: /* Thomas Wang's second version for 32bit integers */
143: PETSC_STATIC_INLINE PetscHash_t PetscHash_UInt32_v1(PetscHash32_t key)
144: {
145:   key = ~key + (key << 15); /* key = (key << 15) - key - 1; */
146:   key =  key ^ (key >> 12);
147:   key =  key + (key <<  2);
148:   key =  key ^ (key >>  4);
149:   key =  key * 2057;        /* key = (key + (key << 3)) + (key << 11); */
150:   key =  key ^ (key >> 16);
151:   return key;
152: }

154: PETSC_STATIC_INLINE PetscHash_t PetscHash_UInt32(PetscHash32_t key)
155: {
156:   return PetscHash_UInt32_v1(key);
157: }

159: /* Thomas Wang's version for 64bit integer -> 32bit hash */
160: PETSC_STATIC_INLINE PetscHash32_t PetscHash_UInt64_32(PetscHash64_t key)
161: {
162:   key = ~key + (key << 18); /* key = (key << 18) - key - 1; */
163:   key =  key ^ (key >> 31);
164:   key =  key * 21;          /* key = (key + (key << 2)) + (key << 4);  */
165:   key =  key ^ (key >> 11);
166:   key =  key + (key <<  6);
167:   key =  key ^ (key >> 22);
168:   return (PetscHash32_t)key;
169: }

171: /* Thomas Wang's version for 64bit integer -> 64bit hash */
172: PETSC_STATIC_INLINE PetscHash64_t PetscHash_UInt64_64(PetscHash64_t key)
173: {
174:   key = ~key + (key << 21); /* key = (key << 21) - key - 1; */
175:   key =  key ^ (key >> 24);
176:   key =  key * 265;         /* key = (key + (key << 3)) + (key << 8);  */
177:   key =  key ^ (key >> 14);
178:   key =  key * 21;          /* key = (key + (key << 2)) + (key << 4); */
179:   key =  key ^ (key >> 28);
180:   key =  key + (key << 31);
181:   return key;
182: }

184: PETSC_STATIC_INLINE PetscHash_t PetscHash_UInt64(PetscHash64_t key)
185: {
186:   return sizeof(PetscHash_t) < sizeof(PetscHash64_t)
187:     ? (PetscHash_t)PetscHash_UInt64_32(key)
188:     : (PetscHash_t)PetscHash_UInt64_64(key);
189: }

191: PETSC_STATIC_INLINE PetscHash_t PetscHashInt(PetscInt key)
192: {
193: #if defined(PETSC_USE_64BIT_INDICES)
194:   return PetscHash_UInt64((PetscHash64_t)key);
195: #else
196:   return PetscHash_UInt32((PetscHash32_t)key);
197: #endif
198: }

200: PETSC_STATIC_INLINE PetscHash_t PetscHashCombine(PetscHash_t seed, PetscHash_t hash)
201: {
202:   /* https://doi.org/10.1002/asi.10170 */
203:   /* https://dl.acm.org/citation.cfm?id=759509 */
204:   return seed ^ (hash + (seed << 6) + (seed >> 2));
205: }

207: #define PetscHashEqual(a,b) ((a) == (b))


210: #endif /* PETSC_HASHTABLE_H */