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