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: }