Actual source code: hashmap.h

  1: #pragma once

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

  5: /* MANSEC = Sys */
  6: /* SUBMANSEC = PetscH */

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

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

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

 23:   Level: developer

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

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

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

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

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

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

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