Actual source code: hashmap.h

  1: #pragma once

  3: #include <petsc/private/hashtable.h>

  5: /* SUBMANSEC = PetscH */

  7: /*MC
  8:   PETSC_HASH_MAP - Instantiate a PETSc hash table map type

 10:   Synopsis:
 11: #include <petsc/private/hashmap.h>
 12:   PETSC_HASH_MAP(HMapT, KeyType, ValType, HashFunc, EqualFunc, DefaultValue)

 14:   Input Parameters:
 15: + HMapT - The hash table map type name suffix
 16: . KeyType - The type of keys
 17: . ValType - The type of values
 18: . HashFunc - Routine or function-like macro computing hash values from keys
 19: . EqualFunc - Routine or function-like macro computing whether two values are equal
 20: - DefaultValue - Default value to use for queries in case of missing keys

 22:   Level: developer

 24:   Note:
 25:   This code uses the standalone and portable C language khash software <https://github.com/attractivechaos/klib>

 27:   Developer Note:
 28:   Each time this macro is used to create a new hash map type, the make rule for allmanpages in $PETSC_DIR/makefile should
 29:   be updated to cause the automatic generation of appropriate manual pages for that type. The manual pages
 30:   are generated from the templated version of the documentation in include/petsc/private/hashmap.txt.

 32: .seealso: `PETSC_HASH_MAP_DECL()`, `PetscHMapI`, `PetscHMapICreate()`, `PetscHMapIJ`,
 33: `PetscHMapIJCreate()`, `PETSC_HASH_SET()`
 34: M*/

 36: #define PETSC_HASH_MAP_DECL(HashT, KeyType, ValType) \
 37:   typedef kh_##HashT##_t                   *Petsc##HashT; \
 38:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Create(Petsc##HashT *); \
 39:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##CreateWithSize(PetscInt, Petsc##HashT *); \
 40:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Destroy(Petsc##HashT *); \
 41:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Reset(Petsc##HashT); \
 42:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Duplicate(Petsc##HashT, Petsc##HashT *); \
 43:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Clear(Petsc##HashT); \
 44:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Resize(Petsc##HashT, PetscInt); \
 45:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetSize(Petsc##HashT, PetscInt *); \
 46:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetCapacity(Petsc##HashT, PetscInt *); \
 47:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Has(Petsc##HashT, KeyType, PetscBool *); \
 48:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Get(Petsc##HashT, KeyType, ValType *); \
 49:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetWithDefault(Petsc##HashT, KeyType, ValType, ValType *); \
 50:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Set(Petsc##HashT, KeyType, ValType); \
 51:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Del(Petsc##HashT, KeyType); \
 52:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##QuerySet(Petsc##HashT, KeyType, ValType, PetscBool *); \
 53:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##QueryDel(Petsc##HashT, KeyType, PetscBool *); \
 54:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Find(Petsc##HashT, KeyType, PetscHashIter *, PetscBool *); \
 55:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Put(Petsc##HashT, KeyType, PetscHashIter *, PetscBool *); \
 56:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##IterGet(Petsc##HashT, PetscHashIter, ValType *); \
 57:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##IterSet(Petsc##HashT, PetscHashIter, ValType); \
 58:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##IterDel(Petsc##HashT, PetscHashIter); \
 59:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetKeys(Petsc##HashT, PetscInt *, KeyType[]); \
 60:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetVals(Petsc##HashT, PetscInt *, ValType[]); \
 61:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetPairs(Petsc##HashT, PetscInt *, KeyType[], ValType[])

 63: #define PETSC_HASH_MAP(HashT, KeyType, ValType, HashFunc, EqualFunc, DefaultValue) \
 64: \
 65:   KHASH_INIT(HashT, KeyType, ValType, 1, HashFunc, EqualFunc) \
 66:   PETSC_HASH_MAP_DECL(HashT, KeyType, ValType); \
 67: \
 68:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Create(Petsc##HashT *ht) \
 69:   { \
 70:     PetscFunctionBegin; \
 71:     PetscAssertPointer(ht, 1); \
 72:     *ht = kh_init(HashT); \
 73:     PetscHashAssert(*ht != NULL); \
 74:     PetscFunctionReturn(PETSC_SUCCESS); \
 75:   } \
 76: \
 77:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##CreateWithSize(PetscInt n, Petsc##HashT *ht) \
 78:   { \
 79:     PetscFunctionBegin; \
 80:     PetscAssert(n >= 0, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Hash table size %" PetscInt_FMT " must be >= 0", n); \
 81:     PetscAssertPointer(ht, 2); \
 82:     PetscCall(Petsc##HashT##Create(ht)); \
 83:     if (n) PetscCall(Petsc##HashT##Resize(*ht, n)); \
 84:     PetscFunctionReturn(PETSC_SUCCESS); \
 85:   } \
 86: \
 87:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Destroy(Petsc##HashT *ht) \
 88:   { \
 89:     PetscFunctionBegin; \
 90:     PetscAssertPointer(ht, 1); \
 91:     if (!*ht) PetscFunctionReturn(PETSC_SUCCESS); \
 92:     kh_destroy(HashT, *ht); \
 93:     *ht = NULL; \
 94:     PetscFunctionReturn(PETSC_SUCCESS); \
 95:   } \
 96: \
 97:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Reset(Petsc##HashT ht) \
 98:   { \
 99:     PetscFunctionBegin; \
100:     PetscAssertPointer(ht, 1); \
101:     kh_reset(HashT, ht); \
102:     PetscFunctionReturn(PETSC_SUCCESS); \
103:   } \
104: \
105:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Duplicate(Petsc##HashT ht, Petsc##HashT *hd) \
106:   { \
107:     int     ret; \
108:     KeyType key; \
109:     ValType val; \
110:     PetscFunctionBegin; \
111:     PetscAssertPointer(ht, 1); \
112:     PetscAssertPointer(hd, 2); \
113:     *hd = kh_init(HashT); \
114:     PetscHashAssert(*hd != NULL); \
115:     ret = kh_resize(HashT, *hd, kh_size(ht)); \
116:     PetscHashAssert(ret == 0); \
117:     kh_foreach(ht, key, val, { \
118:       khiter_t i; \
119:       i = kh_put(HashT, *hd, key, &ret); \
120:       PetscHashAssert(ret >= 0); \
121:       kh_val(*hd, i) = val; \
122:     }) PetscFunctionReturn(PETSC_SUCCESS); \
123:   } \
124: \
125:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Clear(Petsc##HashT ht) \
126:   { \
127:     PetscFunctionBegin; \
128:     PetscAssertPointer(ht, 1); \
129:     kh_clear(HashT, ht); \
130:     PetscFunctionReturn(PETSC_SUCCESS); \
131:   } \
132: \
133:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Resize(Petsc##HashT ht, PetscInt nb) \
134:   { \
135:     int ret; \
136:     PetscFunctionBegin; \
137:     PetscAssertPointer(ht, 1); \
138:     ret = kh_resize(HashT, ht, (khint_t)nb); \
139:     PetscHashAssert(ret >= 0); \
140:     PetscFunctionReturn(PETSC_SUCCESS); \
141:   } \
142: \
143:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetSize(Petsc##HashT ht, PetscInt *n) \
144:   { \
145:     PetscFunctionBegin; \
146:     PetscAssertPointer(ht, 1); \
147:     PetscAssertPointer(n, 2); \
148:     *n = (PetscInt)kh_size(ht); \
149:     PetscFunctionReturn(PETSC_SUCCESS); \
150:   } \
151: \
152:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetCapacity(Petsc##HashT ht, PetscInt *n) \
153:   { \
154:     PetscFunctionBegin; \
155:     PetscAssertPointer(ht, 1); \
156:     PetscAssertPointer(n, 2); \
157:     *n = (PetscInt)kh_n_buckets(ht); \
158:     PetscFunctionReturn(PETSC_SUCCESS); \
159:   } \
160: \
161:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Has(Petsc##HashT ht, KeyType key, PetscBool *has) \
162:   { \
163:     khiter_t iter; \
164:     PetscFunctionBeginHot; \
165:     PetscAssertPointer(ht, 1); \
166:     PetscAssertPointer(has, 3); \
167:     iter = kh_get(HashT, ht, key); \
168:     *has = (iter != kh_end(ht)) ? PETSC_TRUE : PETSC_FALSE; \
169:     PetscFunctionReturn(PETSC_SUCCESS); \
170:   } \
171: \
172:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Get(Petsc##HashT ht, KeyType key, ValType *val) \
173:   { \
174:     khiter_t iter; \
175:     PetscFunctionBeginHot; \
176:     PetscAssertPointer(ht, 1); \
177:     PetscAssertPointer(val, 3); \
178:     iter = kh_get(HashT, ht, key); \
179:     *val = (iter != kh_end(ht)) ? kh_val(ht, iter) : (DefaultValue); \
180:     PetscFunctionReturn(PETSC_SUCCESS); \
181:   } \
182: \
183:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetWithDefault(Petsc##HashT ht, KeyType key, ValType default_val, ValType *val) \
184:   { \
185:     PetscHashIter it    = 0; \
186:     PetscBool     found = PETSC_FALSE; \
187: \
188:     PetscFunctionBeginHot; \
189:     PetscAssertPointer(ht, 1); \
190:     PetscAssertPointer(val, 4); \
191:     PetscCall(Petsc##HashT##Find(ht, key, &it, &found)); \
192:     if (found) { \
193:       PetscHashIterGetVal(ht, it, *val); \
194:     } else { \
195:       *val = default_val; \
196:     } \
197:     PetscFunctionReturn(PETSC_SUCCESS); \
198:   } \
199: \
200:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Set(Petsc##HashT ht, KeyType key, ValType val) \
201:   { \
202:     int      ret; \
203:     khiter_t iter; \
204:     PetscFunctionBeginHot; \
205:     PetscAssertPointer(ht, 1); \
206:     iter = kh_put(HashT, ht, key, &ret); \
207:     PetscHashAssert(ret >= 0); \
208:     kh_val(ht, iter) = val; \
209:     PetscFunctionReturn(PETSC_SUCCESS); \
210:   } \
211: \
212:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Del(Petsc##HashT ht, KeyType key) \
213:   { \
214:     khiter_t iter; \
215:     PetscFunctionBeginHot; \
216:     PetscAssertPointer(ht, 1); \
217:     iter = kh_get(HashT, ht, key); \
218:     kh_del(HashT, ht, iter); \
219:     PetscFunctionReturn(PETSC_SUCCESS); \
220:   } \
221: \
222:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##QuerySet(Petsc##HashT ht, KeyType key, ValType val, PetscBool *missing) \
223:   { \
224:     int      ret; \
225:     khiter_t iter; \
226:     PetscFunctionBeginHot; \
227:     PetscAssertPointer(ht, 1); \
228:     PetscAssertPointer(missing, 3); \
229:     iter = kh_put(HashT, ht, key, &ret); \
230:     PetscHashAssert(ret >= 0); \
231:     kh_val(ht, iter) = val; \
232:     *missing         = ret ? PETSC_TRUE : PETSC_FALSE; \
233:     PetscFunctionReturn(PETSC_SUCCESS); \
234:   } \
235: \
236:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##QueryDel(Petsc##HashT ht, KeyType key, PetscBool *present) \
237:   { \
238:     khiter_t iter; \
239:     PetscFunctionBeginHot; \
240:     PetscAssertPointer(ht, 1); \
241:     PetscAssertPointer(present, 3); \
242:     iter = kh_get(HashT, ht, key); \
243:     if (iter != kh_end(ht)) { \
244:       kh_del(HashT, ht, iter); \
245:       *present = PETSC_TRUE; \
246:     } else { \
247:       *present = PETSC_FALSE; \
248:     } \
249:     PetscFunctionReturn(PETSC_SUCCESS); \
250:   } \
251: \
252:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Find(Petsc##HashT ht, KeyType key, PetscHashIter *iter, PetscBool *found) \
253: \
254:   { \
255:     PetscFunctionBeginHot; \
256:     PetscAssertPointer(ht, 1); \
257:     PetscAssertPointer(iter, 2); \
258:     PetscAssertPointer(found, 3); \
259:     *iter  = kh_get(HashT, ht, key); \
260:     *found = (*iter != kh_end(ht)) ? PETSC_TRUE : PETSC_FALSE; \
261:     PetscFunctionReturn(PETSC_SUCCESS); \
262:   } \
263: \
264:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Put(Petsc##HashT ht, KeyType key, PetscHashIter *iter, PetscBool *missing) \
265:   { \
266:     int ret; \
267:     PetscFunctionBeginHot; \
268:     PetscAssertPointer(ht, 1); \
269:     PetscAssertPointer(iter, 2); \
270:     PetscAssertPointer(missing, 3); \
271:     *iter = kh_put(HashT, ht, key, &ret); \
272:     PetscHashAssert(ret >= 0); \
273:     *missing = ret ? PETSC_TRUE : PETSC_FALSE; \
274:     PetscFunctionReturn(PETSC_SUCCESS); \
275:   } \
276: \
277:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##IterGet(Petsc##HashT ht, PetscHashIter iter, ValType *val) \
278:   { \
279:     PetscFunctionBeginHot; \
280:     PetscAssertPointer(ht, 1); \
281:     PetscAssertPointer(val, 3); \
282:     *val = PetscLikely(iter < kh_end(ht) && kh_exist(ht, iter)) ? kh_val(ht, iter) : (DefaultValue); \
283:     PetscFunctionReturn(PETSC_SUCCESS); \
284:   } \
285: \
286:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##IterSet(Petsc##HashT ht, PetscHashIter iter, ValType val) \
287:   { \
288:     PetscFunctionBeginHot; \
289:     PetscAssertPointer(ht, 1); \
290:     if (PetscLikely(iter < kh_end(ht) && kh_exist(ht, iter))) kh_val(ht, iter) = val; \
291:     PetscFunctionReturn(PETSC_SUCCESS); \
292:   } \
293: \
294:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##IterDel(Petsc##HashT ht, PetscHashIter iter) \
295:   { \
296:     PetscFunctionBeginHot; \
297:     PetscAssertPointer(ht, 1); \
298:     if (PetscLikely(iter < kh_end(ht))) kh_del(HashT, ht, iter); \
299:     PetscFunctionReturn(PETSC_SUCCESS); \
300:   } \
301: \
302:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetKeys(Petsc##HashT ht, PetscInt *off, KeyType array[]) \
303:   { \
304:     KeyType  key; \
305:     PetscInt pos; \
306:     PetscFunctionBegin; \
307:     PetscAssertPointer(ht, 1); \
308:     PetscAssertPointer(off, 2); \
309:     pos = *off; \
310:     kh_foreach_key(ht, key, array[pos++] = key); \
311:     *off = pos; \
312:     PetscFunctionReturn(PETSC_SUCCESS); \
313:   } \
314: \
315:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetVals(Petsc##HashT ht, PetscInt *off, ValType array[]) \
316:   { \
317:     ValType  val; \
318:     PetscInt pos; \
319:     PetscFunctionBegin; \
320:     PetscAssertPointer(ht, 1); \
321:     PetscAssertPointer(off, 2); \
322:     pos = *off; \
323:     kh_foreach_value(ht, val, array[pos++] = val); \
324:     *off = pos; \
325:     PetscFunctionReturn(PETSC_SUCCESS); \
326:   } \
327: \
328:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetPairs(Petsc##HashT ht, PetscInt *off, KeyType karray[], ValType varray[]) \
329:   { \
330:     ValType  val; \
331:     KeyType  key; \
332:     PetscInt pos; \
333:     PetscFunctionBegin; \
334:     PetscAssertPointer(ht, 1); \
335:     PetscAssertPointer(off, 2); \
336:     pos     = *off; \
337:     kh_foreach(ht, key, val, { \
338:       karray[pos]   = key; \
339:       varray[pos++] = val; \
340:     }) *off = pos; \
341:     PetscFunctionReturn(PETSC_SUCCESS); \
342:   }

344: #define PETSC_HASH_MAP_EXTENDED_DECL(HashT, KeyType, ValType) static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##SetWithMode(Petsc##HashT, KeyType, ValType, InsertMode)

346: #define PETSC_HASH_MAP_EXTENDED(HashT, KeyType, ValType, HashFunc, EqualFunc, DefaultValue) \
347:   PETSC_HASH_MAP(HashT, KeyType, ValType, HashFunc, EqualFunc, DefaultValue) \
348: \
349:   PETSC_HASH_MAP_EXTENDED_DECL(HashT, KeyType, ValType); \
350: \
351:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##SetWithMode(Petsc##HashT ht, KeyType key, ValType val, InsertMode mode) \
352:   { \
353:     PetscHashIter it      = 0; \
354:     PetscBool     missing = PETSC_FALSE; \
355: \
356:     PetscFunctionBeginHot; \
357:     PetscAssertPointer(ht, 1); \
358:     PetscCall(Petsc##HashT##Put(ht, key, &it, &missing)); \
359:     if (!missing) { \
360:       ValType cur_val; \
361: \
362:       PetscHashIterGetVal(ht, it, cur_val); \
363:       switch (mode) { \
364:       case INSERT_VALUES: \
365:         break; \
366:       case ADD_VALUES: \
367:         val += cur_val; \
368:         break; \
369:       case MAX_VALUES: \
370:         val = PetscMax(cur_val, val); \
371:         break; \
372:       case MIN_VALUES: \
373:         val = PetscMin(cur_val, val); \
374:         break; \
375:       case NOT_SET_VALUES:    /* fallthrough */ \
376:       case INSERT_ALL_VALUES: /* fallthrough */ \
377:       case ADD_ALL_VALUES:    /* fallthrough */ \
378:       case INSERT_BC_VALUES:  /* fallthrough */ \
379:       case ADD_BC_VALUES:     /* fallthrough */ \
380:       default: \
381:         SETERRQ(PETSC_COMM_SELF, PETSC_ERR_SUP, "Unsupported InsertMode %d", (int)mode); \
382:       } \
383:     } \
384:     PetscCall(Petsc##HashT##IterSet(ht, it, val)); \
385:     PetscFunctionReturn(PETSC_SUCCESS); \
386:   }